编译原理第二章概要.ppt

* 4.2 文法的二义性问题 描述一个句子的文法不是唯一的； 对于一个句子的分析应是唯一的。 考虑文法：E→E+ E|E*E|（E）|i， 句子 （i*i+i） 推导一：E? (E) ? (E+E) ? (E*E+E) ? (i*E+E) ? (i*i+E) ? (i*i+i) 推导二：E? (E) ? (E*E) ? (i*E) ? (i*E+E) ? (i*i+E) ? (i*i+i) * 推导一对应的语法树 推导二对应的语法树 E（树根） （ E ） E * E E + E i i i 1 2 3 4 5 E（树根） （ E ） E + E E * E i i i 1 2 3 4 5 * 如果一个文法的句子存在两棵不同的分析树，那么该句子是二义性的。如果一个文法包含二义性的句子，则称这个文法是二义性的；否则，该文法是无二义性的。 * 几点说明： 1）一般来说，程序语言要求无二义性文法，对于条件语句，经常使用二义性文法描述它：S? if 条件 then 语句 ?if 条件 then 语句 else 语句 ?其它语句 二义性的句子：if e1 then if e2 then s1 else s2 2）在能驾驭的情况下，使用二义性文法。 3）对于任意一个上下文无关文法，不存在一个算法，能够在有限的步骤内判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。 * 4.3 压缩过的文法（化简了的文法） 1）文法中不含有任何形如?P→P的产生式； 2）每个非终结符号P必须都有用处。即： ?S αPβ 且P γ，γ∈VT*? （两层含义：一方面意味着，必须存在含P的句型，另一方面方面意味着对于P不存在永不终结的回路） * T + T * 本章教学线索 1?高级语言的一般特性 2 字符串 3 文法和语言 4 语法分析树与二义性问题 5 文法的分类（逐渐对产生式施加限制） 5.1 乔姆斯基文法（Chomsky） 5.2 上下文有关的语法结构 5.3 自嵌套的文法 5.4 文法的递归性 5.5 文法与语言的典型题目 * 5.1 乔姆斯基文法（Chomsky） 乔姆斯基文法（Chomsky）： 四种类型：0型，1型，2型，3型 0型：G =（VT，VN，S，P） 规则形式：?? ? ?，?? (VT∪VN)*，? ? ? 推导：??? ? ??? 例如：G[S] = （?S，A，B，C，D，E}，{a}，P，S），其中P由如下产生式组成： S?ACaB Ca?aaC CB?DB CB?E aD?Da AD?AC aE?Ea AE?? * 1型（上下文有关）：对于产生式???均满足???????，仅仅S??除外，但S不得出现在任何产生式的右部。 例如：G[S] = （{S，A，B，C，A }，{a，b，c}，P，S） 其中P： S?aSBA S?abB BA?BA BA ? AA AA ?AB bA?bb bB?bc cB?cc L（G）={aibici|i≥1} * 2型（上下文无关）：G的任何产生式为A?? A ?VN，? ? (VN∪ VT)* 例如：G[S] = （{S}，{a，b}，{S?aSb，S?ab}，S） L（G）= { aibi|i≥1} 3型（右线性）：G的任何产生式为A? ?B或A ?? ， ? ?VT*，A、B∈VN （左线性）：G的任何产生式为A? B?或A ??， ? ?VT*，A、B∈VN 3型文法等价于正规式，因此又称为正规文法。 * 四种文法之间的关系 由于四种文法是按照将产生式做进一步限制而定义的，所以它们之间是逐级“包含”的关系，由四种文法产生的语言也是逐级“包含”的关系。 即： 3型语言类 2型语言类 1型语言类 0型语言类 注：0型语言除外，从其中删去或往其中添加一个空串并不改变其语言类。 语言层 正规语言3 上下文无关语言2 上下文有关语言1 递归可枚举语言0 图灵机TM 线性界限自动机LBA 下推自动机PDA 有穷自动机FA * 5.2 上下文有关的语法结构 现在使用的