编译原理试题及答案
一、对于文法GS：S→1A0BεA→0S1AAB→1S0BB⑴3分请写出三个关于GS的句子；⑵4分符号串11A0S是否为GS的句型？试证明你的结论。⑶3分试画出001B关于GS的语法树。二、请构造一个文法，使其产生这样的表达式E：表达式中只含有双目运算符、，且的优先级高于，采用右结合，采用左结合，运算对象只有标识符i，可以用括号改变运算符优先级。要求给出该文法的形式化描述。三、设有语言Lαα∈01，且α不以0开头，但以00结尾。⑴试写出描述L的正规表达式；⑵构造识别L的DFA（要求给出详细过程，并画出构造过程中的NDFA、DFA的状态转换图，以及DFA的形式化描述。四、给定文法GS：S→ABA→aBbScB→ASd⑴6分请给出每一个产生式右部的First集；⑵3分请给出每一个非终结符号的Follow集；⑶8分请构造该文法的LL1分析表；⑷8分什么是LL1文法？该文法是LL1文法吗？为什么？五、给定文法GS：S→SaAaA→AbSb⑴请构造该文法的以LR0项目集为状态的识别规范句型活前缀的DFA。⑵请构造该文法的LR0分析表。⑶什么是LR0文法？该文法是LR0文法吗？为什么？⑷什么是SLR1文法？该文法是SLR1文法吗？为什么？六、给定下列语句：ifabcthe
xabcbcde⑴写出其等价的逆波兰表示；⑵写出其等价的四元式序列。七、已知下列C语言程序：i
tfi
ta100retur
amai
i
tifchara“compiler”pri
tf“theresultisd
”i程序运行结果为：theresultis26157请解释为什么程序运行的结果不是期望的“theresultis100”？
1
f11三个0和1数量相等的串12S1A11AA11A0S13
第二题构造文法如下GEiEFTPE，其中P为：E→EFFF→TFTT→Ei
第三题（1）正规表达式：10100（2）第一步：将正规表达式转换为NDFA
第二步：将NDFA确定化为DFA：造表法确定化（3分）确定化后DFAM的状态转换表2分状态输入SADBDBCDBDBCZI0DBCDBCZDBCDBCZI1ADBDBDBDBDB重新命名tq0q1q2q3q40q2q4q2q41q1q3q3q3q3
2
fDFA的状态转换图（3分）
第三步：给出DFA的形式化描述DFAM（q0q1q2q3q401tq0q4）t的定义见M的状态转换表。第四题（1）FirstABabcFirstaBaFirstbSbFirstccFirstASabcFirstdd（2）FollowSabcdFollowAabcdFolr