编译原理习题(含历年专业考试题)解析.pptVIP

编译原理 第一章---第六章补充 例1 文法 G[P] 及相应翻译方案为： P → bQb {print: ” 1 ” ｝ Q → cR {print: ” 2 ” ｝ Q → a {print: ” 3 ” ｝ R → Qad (print: ” 4 ” ｝ （ 1) 该文法是不是算符优先文法，请构造算符优先关系表证实之。 (2) 输入串为 bcccaadadadb 时，该翻译方案的输出是什么。 (1）文法G[P]的每个非终结符的FIRSTVT集和LASTVT集如下： FIRSTVT(P)={b}；FIRSTVT(Q)={a,c}； FIRSTVT(R)={a,c}； LASTVT(P)={b}；LASTVT(Q)={a,c}； LASTVT(R)={d)。 构造优先关系表： 由表3.19可看出：终结符对（c,a )存在着两种优先关系＜和＞， 故文法G不是一个算符优先文法。 P → bQb {print: ” 1 ” ｝ Q → cR {print: ” 2 ” ｝ Q → a {print: ” 3 ” ｝ R → Qad (print: ” 4 ” ｝ P → bQb {print: ” 1 ” ｝ Q → cR {print: ” 2 ” ｝ Q → a {print: ” 3 ” ｝ R → Qad (print: ” 4 ” ｝ (2)对输入串bcccaadadadb,画出其语法树，。 采用修剪语法树的办法，按句柄方式自下而上归约语法树，每当一个产生式得到匹配（归约）时执行相应的语义动作。因此，第一个句柄匹配的产生式为Q→a,执行相应的语义动作：打印3;第二个句柄匹配的产生式为R→Qad,执行相应的语义动作：打 印4；……。由此得到最终的翻译结果为 1. 语法分析之所以采用上下文无关文法是因为它的描述能力最强。　　　　　　　　（　） 2.  欲构造行之有效的自上而下分析器，则必须消除左递归。　　　　（　　） 3. 文法 ( SaS|bcS| ε ) 描述的语言是（ a|bc ） * ( ) 4. 在自下而上的语法分析中，语法树与分析树一定相同。（ ） 5. 二义文法不是上下文无关文法.（ ） 6. 每一个算符优先文法，必定能找到一组优先函数与之对应。 7. 语法分析时必须先消除文法中的左递归。　（　） 8. 规范归约和规范推导是互逆的两个过程。　　　　　（　） 9. 一个文法所有句型的集合形成该文法所能接受的语言。（　） 10. LL(1) 文法一定不含左递归和二义性。　（　） 已知文法 G[S] ： S → dAB A → aA|a B → Bb| ε （1） 试问 G[S] 是否为正规文法，为什么？ （2） G[S] 所产生的语言是什么？ （3） G[S] 能否改写为等价的正规文法 ? 答：(1)因为S → dAB不符合正规文法产生式A→aB或A→a, a∈VT* ,A,B∈VN的格式，故G[S]不是正规文法。 (2) G[S]产生的语言为： L={danbm|n≥1,m≥0} (3)可以得到G[S]对应的正规文法G’[S]: S→dA A→aA|aB|a B→bB|ε 给出文法 G1 ： S → aSb|P P → bPc|bQc Q → Qa|a （ 1) 它是 Chomsky 哪一型文法？ （ 2 ）它生成的语言是什么？ 根据Chomsky的定义，对任何形如A→β的产生式，有A∈VN，β∈(VT∪VN)*时为2型文法。而文法G1恰好满足这一要求，故为Chomsky 2型文法。 (2)由文法Gl可以看出：S推出串的形式是aiPbi(i≥0), P推出串的形式是bjQcj(j≥1), Q推出串的形式是ak(k≥1).因此，文法G1生成的语言是L=｛aibjakcjbi|i≥0,j≥l,k≥1 }。 已知文法 G[S]: S → S*aP|aP|*aP P → +aP|+a （1）将文法 G[S] 改写为 LL(1 ）文法 G ‘［ S ］。 （2） 写出文法 G [S] 的预测分析表。 文法 G[M] 是否 LL(1) 的，说明理由。 G[M] ： M → TB T → Ba| ε B