3--文法【荐】.pptVIP

第一章 形式语言与自动机基础 文法及其形式定义 文法：所谓文法就是描述语言的语法结构的形式规则。 任何一个文法都可以表示为一个四元组G=(VT,VN,S, ?) VT是一个非空的有限集合，它的每个元素称为终结符号。 VN是一个非空的有限集合，它的每个元素称为非终结符号。 VT∩VN =φ S是一个特殊的非终结符号，称为文法的开始符号。 ?是一个非空的有限集合，它的每个元素称为产生式。 产生式的形式为：??? “?” 表示 “定义为”（或“由……组成”） ?、??(VT∪VN)* ，??? 左部相同的产生式???1、???2、……、???n可以缩写 ???1|?2|……|?n “|” 表示 “或”， 每个?i(i=1,2,…,n)称为?的一个候选式 文法的分类 根据对产生式施加的限制不同，定义了四类文法和 相应的四种形式语言类。 上下文无关文法及相应的语言 所定义的语法单位(或称语法实体)完全独立于这种语法单位可能出现的上下文环境 现有程序设计语言中，许多语法单位的结构可以用上下文无关文法来描述。 例：描述算术表达式的文法G： G=({i,+,-,*,/,(,)},{表达式,项,因子},表达式,?) 其中?： 表达式?表达式+项 | 表达式-项 | 项 项?项*因子 | 项/因子 | 因子 因子?(表达式) | i 语言L(G)是所有包括加、减、乘、除四则运算的算术表达式的集合。 BNF（Backus-Normal Form）表示法 如果用“::=”代替“?”，这组产生式可以写为： 表达式 ::= 表达式+项 | 表达式-项 | 项 项 ::= 项*因子 | 项/因子 | 因子 因子 ::= (表达式) | i 元符号： ::= 表示 “定义为” 或 “由……组成” …… 表示非终结符号 | 表示“或” 文法书写约定 终结符号 次序靠前的小写字母，如：a、b、c 运算符号，如：+、-、*、/ 各种标点符号，如：括号、逗号、冒号、等于号 数字1、2、…、9 黑体字符串，如：id、begin、if、then 非终结符号 次序靠前的大写字母，如：A、B、C 大写字母S常用作文法的开始符号 小写的斜体符号串，如：expr、term、factor、stmt 终结符号串 次序靠后的小写字母，如：u、v、…、z 文法符号串 小写的希腊字母，如：?、?、?、? 可以直接用产生式的集合代替四元组来描述文法，第一个产生式的左部符号是文法的开始符号。 Wensheng Li BUPT * LI Wensheng, BUPT 文法类型 产生式形式的限制 文法产生的语言类 ??? 0型文法 其中 ?,??(VT∪VN)* ，|?|?0， 0型语言 ? 中至少有一个非终结符号 1型文法，即 ??? 1型语言，即 上下文有关文法 ?,?满足0型文法的要求，并且 上下文有关语言 |?|?|?| 2型文法，即 A?? 2型语言，即 上下文无关文法 其中 A?VN，??(VT∪VN)* 上下文无关语言 3型文法，即 A?a或A?aB（右线性），或 3型语言，即 正规文法 A?a或A?Ba（左线性） 正规语言 （线性文法） 其中 A,B?VN， a?VT∪{?} 文法符号 次序靠后的大写字母，如：X、Y、Z Backus为了在ALGOL 60报告中描述ALGOL语言的语法首先提出使用的 * * Wensheng Li BUPT