编译原理复习题中国矿业大学

《编译原理复习题中国矿业大学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、复习要点第1章引论编译程序、解释程序编译程序的5个阶段遍编译前端与后端复习要点高级语言极其语法描述（P2.3节）上下文无关文法、最左推导、最右推导、句子、句型、语言、语法分析树、二义性文、形式语言分类复习要点词法分析正规式、正规集、有限自动机（确定的有限自动机、非确定的有限自动机）三者之间的相互转化自动机的确定化、化简复习要点语法分析-自上而下分析递归下降分析法LL（1）分析法消除左递归、提左因子、FIRST集、FOLLOW集P73:LL(1)文法的判定条件LL(1)分析器的构造：P76-79复习要点语法分析-自下而上分析移进-归约、规范规约、短语、直接短

2、语、句柄算符优先分析算符文法、素短语、最左素短语LR分析法LR(0)、SLRLR分析法考核要点构造文法G[S]的LR(0)项目集规范族及相应的DFA。构造文法的LR(0)或SLR分析表对于输入串xxxxxxx，给出LR(0)或SLR分析器所作出的动作。复习要点属性文法和语法制导翻译属性文法、继承属性、综合属性、S-属性文法、L-属性文法、翻译模式S-属性文法的自下而上计算复习要点语义分析和中间代码产生中间语言形式：后缀式、三地址代码（主要是四元式）控制语句的翻译字母表{0,1,2,3}对给定正则表达式0*（1

3、23）（0

4、12）0（1

5、13）*构造与之等价

6、的NFAM。习题举例设文法G(S):S→S+aF

7、aF

8、+aFF→*aF

9、*a⑴消除左递归和回溯；⑵构造非终结符的FIRST和FOLLOW集合；⑶构造预测分析表(4)给出句子a*a+a*a的LL(1)分析过程（格式：栈，输入缓冲区，动作）习题举例解：⑴S→aFS'

10、+aFS'S'→+aFS'

11、εF→*aF'F'→F

12、ε⑵FIRST(S)={a,+}FOLLOW(S)={#}FIRST(S')={+,ε}FOLLOW(S')={#}FIRST(F)={*}FOLLOW(F)={+,#}FIRST(F')={*,ε)FOLLOW(F')={+,

13、#}习题举例-a+*#SS→aFS'S→+aFS'--S'-S'→+aFS'-S'→εF--F→*aF'-F'-F'→εF'→FF'→ε习题举例文法G[S]的产生式为：SS+A

14、AAA*S

15、BBa

16、（S）给出（a+a）*a的最左推导、最右推导及相应的分析树；列出句型B+A*B的所有短语、直接短语和句柄。习题举例已知文法G=({b,e,f},{S’,S,R,T},S’,P)其中P:(0)S’→S(1)S→bRST(2)S→bR(3)R→e(4)T→f构造文法的LR（0）项目集规范族构造识别活前缀的DFA这个文法哪类LR文法并说明理由习题举例S’→·SS

17、→·bRSTS→·bRI0S’→S·I1SS→b·RSTR→·eS→b·RI2bR→e·I4eS→bR·STS→bR·S→·bRSTS→·bRI3RbSS→bRS·TT→·fI5T→f·I7fS→bRST·I6T状态actiongotobef#SRT0S211acc2S433S2r2r254r3r3r35S766r1r17r4r4状态栈符号栈输入缓冲区动作0#bebef#S202#bebef#S4024#bebef#r3023#bRbef#S20232#bRbef#S402324#bRbef#r302323#bRbRf#r20235#bRSf#S70235

18、7#bRSf#r402356#bRST#r101#S#acc