编译原理复习题中国矿业大学.ppt
复习要点n第1章 引论n编译程序、解释程序n编译程序的5个阶段n遍n编译前端与后端复习要点n高级语言极其语法描述（P2.3节）n上下文无关文法、最左推导、最右推导、句子、句型、语言、语法分析树、二义性文、形式语言分类复习要点n词法分析n正规式、正规集、有限自动机（确定的有限自动机、非确定的有限自动机）n三者之间的相互转化n自动机的确定化、化简复习要点n语法分析-自上而下分析n递归下降分析法nLL（1）分析法n消除左递归、提左因子、FIRST集、FOLLOW集nP73:LL(1)文法的判定条件nLL(1)分析器的构造：P76-79复习要点n语法分析-自下而上分析n移进-归约、规范规约、短语、直接短语、句柄n算符优先分析n算符文法、素短语、最左素短语nLR分析法nLR(0)、SLRLR分析法考核要点n构造文法GS的LR(0)项目集规范族及相应的DFA。n构造文法的LR(0)或SLR分析表n对于输入串xxxxxxx，给出LR(0)或SLR分析器所作出的动作。复习要点n属性文法和语法制导翻译n属性文法、继承属性、综合属性、S-属性文法、L-属性文法、翻译模式nS-属性文法的自下而上计算复习要点n语义分析和中间代码产生n中间语言形式：后缀式、三地址代码（主要是四元式）n控制语句的翻译字母表字母表0,1,2,30,1,2,3对给定正则表达式对给定正则表达式0*（1|23）（）（0|12）0（1|13）*构造与之等价的构造与之等价的NFA M。习题举例设文法设文法G(S):G(S):SS+aF|aF|+aFSS+aF|aF|+aFF*aF|*aF*aF|*a 消除左递归和回溯；消除左递归和回溯；构造非终结符的构造非终结符的FIRSTFIRST和和FOLLOWFOLLOW集合；集合；构造预测分析表构造预测分析表(4)(4)给出句子给出句子a*a+a*aa*a+a*a的的LL(1)LL(1)分析过程分析过程 （格式：栈，输入缓冲区，动作）（格式：栈，输入缓冲区，动作）习题举例解：SaFS|+aFSS+aFS|F*aFFF|FIRST(S)=a,+FOLLOW(S)=#FIRST(S)=+,FOLLOW(S)=#FIRST(F)=*FOLLOW(F)=+,#FIRST(F)=*,)FOLLOW(F)=+,#习题举例-a+*#SSaFSS+aFS-S-S+aFS-SF-F*aF-F-FFFF习题举例文法文法GSGS的产生式为：的产生式为：S SS+A|AS+A|A A AA*S|BA*S|B B Ba|a|（S S）给给出出（a+aa+a）*a a的的最最左左推推导导、最最右右推推导导及及相相应应的的分分析析树；树；列出句型列出句型B+A*BB+A*B的所有短语、直接短语和句柄。的所有短语、直接短语和句柄。习题举例已知文法已知文法G=(b,e,f,S,S,R,T,S,P)其中其中P:(0)SS (1)SbRST (2)SbR (3)Re (4)Tf 构造构造 文法的文法的LR（0）项目集规范族）项目集规范族 构造构造 识别活前缀的识别活前缀的DFA 这个文法哪类这个文法哪类LR文法并说明理由文法并说明理由 习题举例SSSbRSTSbRI0S SI1SSbRSTReSbRI2bReI4eSbRSTSbRSbRSTSbRI3RbSSbRSTTfI5TfI7fSbRSTI6T状状态态actiongotobef#SRT0S211acc2S433S2r2r254r3r3r35S766r1r17r4r4状状态栈态栈符号符号栈栈输输入入缓缓冲区冲区动动作作0#bebef#S202#bebef#S4024#bebef#r3023#bRbef#S20232#bRbef#S402324#bRbef#r302323#bRbRf#r20235#bRSf#S702357#bRSf#r402356#bRST#r101#S#acc
