? P+i*(i+i) ? i+i*(i+i [3] 考虑文法S->aSbS | bSaS |ε （a） 为句abab构造两个不同的最左推导，以此说明该文法是二义的。 （b） 为abab构造对应的最右推导。 答案： （3）分析树[简答题5分]； [1] 考虑文法S->aSbS | bSaS |ε （1） 为abab构造对应的分析树。 （2） 这个文法产生的语言是什么？ 答案：
E T （1）（2）该文法产生 a、b 个数相等的 ab 串（含空串） [2] 对于文法G(E): E?T|E+T T?F|T*F F?(E)|i 写出句型(T*F+i)的最右推导并画出语法树。 答案： （1）E?T?F?(E) ?(E+T) ?(E+F) ?(E+i) ?(T+i) ?(T*F+i) （2）语法树如右图。 [3] 令文法G[S]为： S→AB A→aAb | ab B→b, （1）G[S]定义的语言L(G)是什么？ （2）给出句子aabbb的最左推导，并给出其语法分析树。 答案： （1）S?abB?abb S?aAbB?aabbB?aabbb S?aAbB?aaAbbB?aaabbbB?aaabbbb ( E T T * F E + ) T F i F
…… S?anbm(n>=0,m>=1) （2）s ?AB?aAbB?aabbB?aabbbb /. （4）二义性概念[选择题2分] [1] 如果文法G是无二义的，则它的任何句子α（ ）。 A. 最左推导和最右推导对应的语法树必定相同 B. 最左推导和最右推导对应的语法树可能不同 C. 最左推导和最右推导必定相同 D. 可能存在两个不同的最左推导，但它们对应的语法树相同 答案：A [2] 如果一个文法G是无二义性文法，对于任何一个句子，该句子（ ）。 A. 可能存在两个不同的最左推导 B. 可能存在两个不同的最右推导 C. 最左推导和最右推导不同
D. 仅存在一个最左推导和一个最右推导 答案：D [3] 若文法 G 定义的语言是无限集，则文法必然是（ ）。 A. 递归的 B. 前后文无关的 C. 二义性的 D. 无二义性的 答案：A F （1）消除左递归[填空题2分]； [1] 一个文法是左递归的，如果它有非终结符A，对某个串a，存在推导 。 答案：A=>+Aa [2] 的分析方法不能用于左递归文法，因此需要消除左递归。 答案：自上而下 [3] 由形式为A->Aa的产生式引起的左递归称为 。 答案：直接左递归 （2）提取左因子[填空题2分]； [1] 提取左因子用于产生适合于 的文法。 答案：自上而下 [2] A->aB|aC，经过提取左因子，原来的产生式成为 和 。 答案：A->aA’ A’->B|C [3] 对于悬空else的文法 stmt->if expr then stmt else stmt | if expr then stmt | other 提取左因子后的文法成为 和 。 第三章 3.2 语言和文法
相关推荐：
loading