编译原理：第二章 高级语言与其语法描述.ppt

2.3.2 语法树与二义性 用一张图表示一个句型的推导,称为语法树。 (i*i+i)的语法树 E ?(E) ?(E+E) ?(E*E+E) ?(i*E+E) ?(i*i+E) ?(i*i+i) E ?(E) ?(E+E) ?(E+i) ?(E*E+i) ?(E*i+i) ?(i*i+i) 一棵语法树是不同推导过程的共性抽象。 G(E)：E ?i|E+E|E*E|(E) (i*i+i) 如果使用最左(右)推导，则一个最左(右)推导与语法树一一对应。 一个句型是否只对应唯一一棵语法树？ 定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。 G(E)： E ? i|E+E|E*E|(E) 是二义文法。 语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。 可能存在G和G’，一个为二义的，一个为无二义的。但L(G)=L(G’) 二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。 可以找到一组无二义文法的充分条件。 二义文法： G(E)： E ? i|E+E|E*E|(E) 表达式 ?项|表达式+项 项 ? 因子 | 项*因子 因子 ? (表达式) | i 无二义文法： G(E)：E ? T | E+T T ? F | T*F F ? (E) | i ) E E E F F T T T T i + * ( E F i i E ?T ?F ?(E) ?(E+T) ?(T+T) ?(T*F+T) ?(F*F+T) ?(i*F+T) ?(i*i+T) ?(i*i+F) ?(i*i+i) 考虑句子(i*i+i) 描述程序设计语言时，对于上下文无关文法的限制 ： 1 不含P?P形式的产生式 2 每个非终结符P必须有用处 即： 2.3.3 形式语言鸟瞰 Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。 与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。 0型(短语文法，图灵机)： 产生式形如： ? ? ? 其中：?? (VT ? VN)*且至少含有一个非终结符；?? (VT ? VN)* 1型(上下文有关文法，线性界限自动机)： 产生式形如： ? ? ? 其中：|?| ? |?|，仅 S?? 例外。 2型(上下文无关文法，非确定下推自动机)： 产生式形如： A ? ? 其中：A? VN；?? (VT ? VN)*。 3型(正规文法，有限自动机)： 产生式形如： A ? ?B 或 A ? ? 其中： ?? VT*；A，B?VN 产生式形如： A ? B? 或 A ? ? 其中： ?? VT*；A，B?VN 右线性文法 左线性文法 四种类型描述能力比较 0型 1型 2型 3型 L5={anbn|n?1} 不能由正规文法产生，但可由上下文无关文法产生： G5(S)： S ? aSb| ab L6={anbncn|n?1}不能由上下文无关文法产生，但可由上下文有关文法产生： G6(S)： S ? aSBC| aBC CB ? BC aB ? ab bB ? bb bC ? bc cC ? cc 程序设计语言不是上下文无关语言，甚至不是上下文有关语言。 L7={?c?| ??(a|b)*}不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由0型文法产生。 标识符引用 过程调用过程中，形-实参数地对应性(如个数，顺序和类型一致性) 现今程序设计语言的语言结构，用上下文无关文法描述就足够了。 作业 P36-6，7，8，9，10，11 * 程序设计语言(10)Alan?J.?Perlis?(1966)?--?ALGOLEdsger?Wybe?Dijkstra?(1972)?--?ALGOLJohn?W.?Backus?(1977)?--?FORTRANKenneth?Eugene?Iverson?(1979)?--?APL程序语言Niklaus?Wirth?(1984)?--?PASCALJohn?Cocke?(1987)?--?RISC??编译优化Ole-Johan?Dahl，Kristen?Nygaard?(2001)?--?Simula语言和面向对象概念Alan?Kay(2003)?--?SmallTalk语言和面向对象程序设计Peter?Na