东南大学编译原理课件cp2.ppt

2 语言与文法 翟玉庆 周晓宇 字母表和符号 字母表：符号的非空有穷集合 符号: 语言中不可再分的单位 字母表：Σ，V或其它大写字母 V1 = {a, b, c} V2 = {+, -, 0, 1, …,9} Σ= {x|x?ASCII字符} 符号串（字符串） 某字母表上的符号的有穷序列 a, b, c, abc, bc,…：V1上的符号串 1250, +2, -1835,…：V2上的符号串 空串（ε）：不含任何符号的串 语句 字母表上符合某种构成规则的符号串序列 He is a good student. Peanut eats monkey. 我们约定，用a, b, c,…表示符号; 用?, ?, ?…表示符号串; 用A, B, C,…表示符号或符号串的集合 语言 某字母表上的句子的集合。 符号串集合的积 设A={?1, ?2, …}，B={?1, ?2, ...}，二者的笛卡尔积 AB={?? ? ??A, ??B} 若A={a, b}, B={c, e, d}，那么 AB = {ac, ae, ad, bc, be, bd} 字符串集合的幂 A0={ε}， An=AAn-1={ ? } 若 |A|=m，那么，|A0|=1，|A1|=m， |An|=mn Kleene闭包和正闭包 Kleene闭包： A*=A0?A1 ? A2 ? … {a, b}*={?} 正闭包: A+=A1 ? A2 ? …=A*-{ε} {a, b}+={?} 一个语言是其字母表上闭包的子集. 文法（grammar） 表达语言构成规则的形式化方法 自然语言文法示例 产生式 句子?主语谓语宾语 主语?形容词名词 谓语?动词 宾语?形容词名词 形容词?yong ? pop 名词?men ? music 动词?like 产生式文法的组成 非终结符（VN） 终结符（VT） 开始符号 产生式 推导与规约 推导：使用产生式的右部取代左部的过程 规约：推导的逆过程，用产生式的左部取代右部的过程 推导及规约的顺序 推导及规约的顺序 最左归约和最右归约称为规范归约。 句型、句子与语言 句型：从文法开始符号S开始，每步推导（包括0步推导）所得到的字符串? S ?，其中? ?(VN ? VT) * 句子：仅含终结符的句型 语言：由S推导所得的句子的集合 L(G)={?|S ?，且? ? VT*}，G为文法 文法规则的递归定义 非终结符的定义中包含了非终结符自身 设?={0,1} 整数?数字整数|数字 数字?0 | 1 使用递归定义时要谨慎，要有递归出口，否则，可能永远产生不出句子 扩充的BNF表示 () ——提因子 U ? ax | ay | az 改写为U ? a (x | y | z) {} ——重复次数的指定 标识符?字母{字母|数字} 05 [] ——任选符号 整数?[+|-]数字{数字} 元语言符号 用来说明文法符号之间关系的符号 ? | 文法与语言的形式定义 Chomsky 0型文法 G：四元组(VN, VT, P, S) 0型文法（短语文法或无限制文法） P：???，其中??V+ 并至少含有一个非终结符, ??V*. 是对产生式限制最少的文法； 识别0型语言的自动机称为图灵机(TM)； 对0型文法的产生式作某些限制，可以得到其他类型的文法。 Chomsky 1型文法 长度增加文法（上下文有关文法） P：???，除可能有S ? ? 外均有|?|=|?|；若有S ? ?，规定S不得出现在产生式右部。或 P中产生式???，除可能有S ? ?外均有?A??? ? ?，其中?, ??V* ， A ?VN，? ?V+ 。 Chomsky 1型文法（续） 1型文法对非终结符进行替换时必须考虑上下文。 除文法开始符号外不允许将其它的非终结符替换成?。 识别1型语言的自动机称为线性界限自动机(LBA)。 Chomsky 2型文法 P：A??，其中A?VN ，??V*。 产生式左部一定是非终结符，产生式右部可以是VN 、VT或?。 非终结符的替换不必考虑上下文，故也称作上下文无关文法。 识别2型语言的自动机称为下推自动机(PDA)。 Chomsky 3型文法 P中产生式具有形式A? ? B， A? ? ，或者A? B?， A? ?， 其中A，B?VN，??VT*。 也称为正规文法RG、线性文法：若所有产生式均是左线性，则称为左线性文法；若所有产生式均是右线性，则称为右线性文法。 Chomsky 3型文法（续） 产生式要么均是右线性产生式，要么是左线性产生式，不能既有左线性产生式，又有右线性产生式。 识别3型语言的自动机称为有限状态自动机。 由文法产生语言 由文法产生语言 由语言构造文法 例：设L1={a2nbn|n=