編譯原理試題與解析-北京工業(yè)大學

1、北京工業(yè)大學2003-04-2學期010700-11班級編譯原理試卷學號 姓名 成績題號 一四五7分數(shù)（10分）改寫以下文法，使其滿足采用自頂向下分析方法的要 求。S ? aXcYl YdX ? XaY| cY ? bYcX| b解：（1）消除X ? XaY|c的左遞歸X?cX * X' ? aYX' | &（2）提取Y ? bYcX|b的左因子Y ?bY 1Y' ? YcX| &整理后，原文法變?yōu)镾 ? aXcY | Yd X ? cX 'X1 ? aYX' |&Y ?bZZ ? YcX| £二.（15分）考慮文法GS

2、：S ? xSNy| NxN ?zN|&1 .求出該文法的每個非終結符的FOLLOW集;2 ,構造該文法的預測分析表。解：FIRST(S) = x, z FIRST(N) = z, & FOLLOW(S) = #, y, z FOLLOW(N) = x, y2預測分析表S?NxS?xSNy S?NxN?S N ? zN(20分)符號串xxyyyx是如下文法GS的句子，S ? xB | yAA ?xS|yAA|xB ?yS|xBB | y(1)構造該句子的分析樹；(2)寫出生成該句子的最左推導；(3)寫出生成該句子的規(guī)范歸約過程；指出每步歸約中的句柄。解：(1)語法分析樹(6分)

3、XX句柄為y 句柄為x 句柄為yA 句柄為ys 句柄為xBB 句柄為xB（2） S ?xB?xxBB?xxyB?xxyyS?xxyyyA?xxyyyx （5 分）規(guī)范歸約（9分）xxyyyx ? xxByyx xxByyx ? xxByyA xxByyA ? xxByS xxByS ? xxBB xxBB ?xB xB ?S四,(20分)考慮簡單賦值語句的文法GS：S?id:=E E?E + E E?E*E E?id(1)試構造識別該文法所有規(guī)范句型活前綴的有限自動機(2) 判斷該文法是否為LR(O)文法(必須說明理由)。解：(1)Io： S 1 ?.S+S ? .id = E L： S &#

4、39; ?S. 12： S?id. = E 13： S ? id = .EE?.E + E E?.E*E E?.id14： S ? id = E.E?E. + EE?E. *E I5： E ? id.16： E ? E +.E (2)由于14、I 8、I 9均有移進一歸約沖突，E?.E + EE ?.E E故該文法不是LR(O)文法VE?.id17： E?E*EE?.E + EE?.E*EE?.id1s： E ? E + EE?E.+ EE ? E. * E19： E?E*E.E ? E .+ EE?E.*E產(chǎn)生式語義規(guī)則S ? Li. L 2Print( + *)L?LiB=2* +=+ 1L?B=1B ?0=0B ? 1=1（1 ）寫出句子的帶注釋分析樹、或屬性計算過程 （2）給出處理該句子的結果（Print輸出結果）解：（1）句子的帶注釋分析樹:（2）處理該句子的結果（Print輸出結果）為六.(20分)設語言L是“能被5整除的十進制正整數(shù)”組成的集合, (1)試寫出描述語言L的正規(guī)表達式；(2