大二下期末编译原理讲.pptx

第三章语法分析源程序本章内容上下文无关文法自上而下分析和自下而上分析围绕分析器的自动生成展开词法分析器记号取下一个记号分析树前端的其余部分分析器中间表示符号表1

表达式表达式表达式标识符表达式表达式(initial)标识符(rate)数(60)*+语法分析：词法记号（token）流-〉语法短语（分析树）宾语定语宾语形容词(优秀的)名词（大工学子）initial+rate*60优秀的大工学子id+id*num形容词名词2

字符字符串记号词法分析器（正规式）表达式语句程序块程序语法分析器（上下文无关文法）语法分析树3

3.1上下文无关文法3.1.1上下文无关文法的定义正规式用来定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复。 例：a(ba)5,a(ba)*正规式不能用于描述配对或嵌套的结构 例：配对括号串的集合， {wcw|w是a和b的串}4

3.1上下文无关文法上下文无关文法是四元组（VT,VN,S,P）VT:终结符集合(非空有限集合，记号名是其同意词)VN:非终结符集合（非空有限集合,）S:开始符号(非终结符)P:产生式集合，产生式形式:A??,例({id,+,*,?,(,)},{expr,op},expr,P)expr?expropexpr expr?(expr)expr??expr expr?idop?+ op?*5

3.1上下文无关文法例({id,+,*,?,(,)},{expr,op},expr,P)expr?expropexpr expr?(expr)expr??expr expr?idop?+ op?*同一个符号可以在多个产生式中出现每个产生式之间没有强制的顺序关系，这与正规式不同终结符6

3.1上下文无关文法简化表示方法以下符号通常表示终结符1）字母表中前面的小写字母，如a,b,c2)黑体串,如id或while3)数字0,1,…,94)标点符号，如括号，逗号等5)运算符号，如+,-等以下符号通常表示非终结符1）字母表中前面的大写字母，如A,B,C2)字母S,通常它表示开始符号3)小写字母的名字，如expr和stmt另外，1)字母表中后面的大写字母，如X,Y等，表示非终结符或终结符2)字母表中后面的小写字母，如u,v,..z,代表终结符串3)小写希腊字母，代表文法的符号串4)如果A—a1，A—a2，记为A—a1|a27

3.1上下文无关文法例({id,+,*,?,(,)},{expr,op},expr,P)expr?expropexpr expr?(expr)expr??expr expr?idop?+ op?*简化表示E?EAE|(E)|?E|idA?+|*8

3.1上下文无关文法上下文无关文法E?EAE|(E)|?E|idA?+|*正规式定义letter?[A-Za-z]digit?[0-9]id?letter(letter|digit)*上下文无关文法与正规式比较9

3.1上下文无关文法3.1.2推导把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替。例 E?E+E|E*E|(E)|?E|idE??E??(E)??(E+E)??(id+E)??(id+id)记号S?*?、S?+w概念 句型、句子、上下文无关语言、等价的文法是从文法推出文法所描述的语言中所包含的合法串集合的动作10

3.1上下文无关文法E?E+E|E*E|(E)|?E|id E??E??(E)??(E+E)最左推导 E ?lm?E?lm?(E)?lm?(E+E) ?lm?(id+E)?lm?(id+id)最右推导（规范推导） E ?rm?E?rm?(E)?rm?(E+E) ?rm?(E+id)?rm?(id+id)最左推导与最右推导？？11

3.1上下文无关文法3.1.3分析树E?lm?E?lm?(E)?lm?(E+E)?lm?(id+E)?lm?(id+id)E?