《语法分析-自底向上分析-编译原理-05-(二)课件》由会员分享，可在线阅读，更多相关《语法分析-自底向上分析-编译原理-05-(二)课件（71页珍藏版）》请在金锄头文库上搜索。
1、第五章 语法分析自底向上分析,5.1基本问题 方法 从句子出发，反复利用产生式做归约 （用产生式的左部替代右部），逐步构造语法分析树，最后得到文法的开始符号 核心 寻找句型与句柄的匹配,分析方法,例 5-1： S a A c B e A A bb B d 分析过程: abbcde aAbcde aAcde aAcBe S,语法分析树的生成,a b b c d e,A,A,B,S,A b,A A b,B d,S a A c B e,句柄：最左直接短语,短语： 设文法T，N， 若 =* 且 =+ ， 则称是句型相对于非终结符的短语 若=* 且=，则称是直接短语。,规范归约的定义,设 为文法 G 的
2、句子，称序列 n，.，1，0 为 的规范归约，其中 1) n = 2) 0 = （开始符号） 3) 对每个 i (1 = i = n)，i-1 是将i 中的句柄归约后得到的,规范归约,规范归约是规范推导(最右推导)的逆过程 中心问题是如何寻找和确定一个句型中的句柄 各种自底向上分析采用不同的方法确定句柄,移进归约分析器,id id #, #,移进归约 控制程序,产生式序列,栈内容 + 输入缓冲区内容 # 句型 #,栈,输入缓冲区,分析器的四种动作,1) 移进：将下一输入符号移入栈 2) 归约：用产生式左侧的非终结符替换栈顶的句柄 3) 接受：分析成功 4) 出错：出错处理 各种自底向上分析方法
3、的控制方法不同,例5-2：id+id*id 的分析,动作 栈 输入缓冲区 1) # id1+id2*id3# 2) 移进 #id1 +id2*id3# 3) 归约 Eid #E +id2*id3# 4) 移进 #E+ id2*id3# 5) 移进 #E+id2 *id3# 6) 归约 Eid #E+E *id3# 7) 移进 #E+E* id3# 8) 移进 #E+E*id3 # 9) 归约 Eid #E+E*E # 10) 归约 EE*E #E+E # 11) 归约 EE+E #E # 12) 接受,产生式序列表示语法分析树,E id E id E id E E * E E E + E,id
4、 + id * id,E,E,E,E,E,移进归约分析中的冲突,文法复杂时出现: 1) 移进归约冲突 例中的 6) 可以移进 id 或 归约 EE+E 2) 归约归约冲突 存在两个可用的产生式 各种分析方法处理冲突的方法不同,5.2 算符优先分析,方法： 利用终结符之间的优先关系确定句柄。 算符优先关系的定义 (终结符之间) a b a 的优先级低于 b a b a 的优先级等于 b a b a 的优先级高于 b,算符优先文法,如果文法 中不存在具有相邻非终结符的产生式，则称为算符文法。 如果无产生式的算符文法 中，且任意两个终结符之间至多有一种优先关系，则称为算符优先文法。 算符优先分析仅适
5、用于算符优先文法。,例5-3：表达式文法的算符优先关系,E E + E E - E E * E E / E E E ( E ) id,存在优先级 + * + id +id * + id* id id # id,算符优先关系的使用,分析例：id + id * id 在输入符号串中插入优先符，形成一组以 为左端，以为中缀，以为右端的短语。 # id + id * id # 对短语进行归约后再次插入优先符 # E + E * E # # E + E # # E #,算符优先分析的实现,组成结构 移进归约分析器 + 优先关系表 工作框架 输入、输出、初态、终态不变 分析算法 P93 参照输入串、优先关
6、系表，完成一组产生式归约，产生语法分析树。,id+id*id 的分析过程,id + id * id #,算符优先分析 控制器,E id,E id,E id,E E * E,E E + E,算符优先关系表,#,id #,E #,+ E #,id + E #,E + E #,* E + E #,id * E + E #,E * E + E #,E + E #,E #,算符优先关系表的构造,对于任何符号 X 和 Y： 若 X 的运算优先级高于 Y， 则设 X Y 和 Y X 若 X 和 Y 运算优先级相同， 且具有左结合性，则设 X Y 和 Y X; 否则设 X Y 和 Y X 设 X id， id
7、 X， X (， ( X， ) X， X )，( )， X # 和 # X,算符优先分析小结,优点 简单、效率高 能够处理部分二义性文法 缺点 文法书写限制大 占用内存空间大 不规范、存在查不到的语法错误,习题：,P133 2. (2) 补充题 给出布尔表达式的文法 bexpr bexpr OR bexpr bexpr bexpr AND bexpr bexpr NOT bexpr bexpr ( bexpr ) bexpr TRUE bexpr FALSE 构造该文法的算符优先关系表,5.3 分析法,适用于分析 LR（k）文法 相当大的一类上下文无关文法 分析方法 最广义的无回朔的移进归约分
8、析 主要特征 文法限制少、错误定位准确 效率较高、易于实现自动生成,LR(k) 文法,移进归约分析法可分析的文法 L ：从左到右扫描输入符号 R ：逆向地完成最右推导 k ：超前读入的符号个数 存在无法分析的 2 型文法,5.3.1 分析器的概述,LR 分析器 移进归约分析器 + LR 分析表 特殊性 栈 = 状态栈 + 文法符号栈 分析表 = 动作表 + 状态转移表,分析器的逻辑结构,a1 ai an #,驱动程序 (P101算法),动作表 action,转移表 goto,产生式 序列,状态符号栈,输入缓冲区,分析表,Sm Sm-1 S1 S0,Xm Xm-1 X1 #,LR 分析表,act
9、ion s, a 状态 s 下输入 a 时的动作 （移进、归约、接受、出错） goto s, X 状态 s 下遇符号 X 时的转移目标 各种 LR 分析法 采用不同的构造方法,分析算法：,设置 ip 指向 w# 的第一个符号 repeat forever begin 令 s是栈顶状态，a是 ip 所指向的符号 if action s, a = shift s then begin 把 a 和 s 先后压入栈 使 ip 指向下一符号 end else if action s, a = reduce A then begin,从栈顶弹出 2 * 个符号 令 s 表示当前栈顶状态 把 A 和 got
10、o s, A 先后压入栈中 输出产生式 A end else if action s, a = accept then return else error() end.,例5-4：分析例,文法 1) S B B 2) B a B 3) B b,状态 动作表 状态转移表 a b # S B 0 s3 s4 1 2 1 acc 2 s3 s4 5 3 s3 s4 6 4 r3 r3 r3 5 r1 6 r2 r2 r2,分析表,bab 的分析过程,栈 输入 动作说明 #0 bab# action(0,b) #0b4 ab# action(4,a) B b goto(0,B) #0B2 ab# ac
11、tion(2,a) #0B2a3 b# action(3,b) #0B2a3b4 # action(4,#) B b goto(3,B) #0B2a3B6 # action(6,#) B aB goto(2,B) #0B2B5 # action(5,#) S BB goto(0,S) #0S1 # action(1,#) accept,各种 LR 分析表,LR(0)，SLR(1)，LALR(1)， LR(1)， 构造分析表的方法不同 分析能力不同 实现效率不同 共同点 逻辑结构 工作原理（状态转移）,5.3.2 SLR(1)分析,状态 表示分析的进程 方法 用产生式中符号的分割位置来近似表示分
12、析的进展状况,b a b,B,B,B,S,S B . B B . a B,分析的进展,分析位置 句型中，分析进展的当前位置（无限） 例： .bab = B .ab = BaB . = BB . = S .,LR(0) 项目,目的 用产生式中的符号分割位置(有限） 来表示分析位置(无限) 定义 右部某个位置上标有园点的产生式 坐标表示 ( x, y ) 表示 x 号产生式的 y 号位置的 LR(0) 项目,文法的改写,文法 G 的拓广文法 G： 扩充识别符号 S S （G 的识别符号 ) 例 5-5 0) S S 1) S B B 2) B a B 3) B b,LR(0) 项目例 (0,0)
13、S . S (2,1) B a . B (3,1) B b .,用状态近似表示分析位置,分析位置对应多个 LR(0) 项目，状态应是 LR(0) 项目集合。 状态计算：从一个分割位置出发，考虑向前分析中可能处于同一分析位置的分割位置。, . B ,A,. ,状态的计算,求核心位置的闭包 closure( I ) J := I; repeat J = J B .A .B J until J 不再扩大 例： closure（(0,0)）= (0,0),(1,0),(2,0),(3,0),状态转移的计算：,确定在某状态遇到一个文法符号后的状态转移目标,A,状态 I,核心 J, . X ,状态转移函数
14、,当前状态 I 文法符号 X 下一状态 go( I, X ) = closure( J ) 其中 J = A X. A .X I ,计算状态集合（P105)即：LR(0)项目集规范族,begin I := closure( S .S ); C := I ; repeat for C 中的每一状态 I 和每一文法符号 X if go(I, X)非空并且 go(I,X) 不在 C 中 将状态 go(I, X) 加入到 C 中 until 不出现新的状态 end.,例 5-6：表达式文法的状态集合,拓广文法 0) 1) + 2) 3) * 4) 5) ( ) 6) id,0 1 0,4 1,8 6
15、9 0,4 2 0,4,6 2,9 7 10 0,4,6 3 0,4,6,7 4 8 11 0,4,6,7 5,状态计算,状态 核心 闭包增加 0 (0,0) (1,0) (2,0) (3,0) (4,0) (5,0) (6,0) go(0,E) 1 (0,1) (1,1) go(0,T) 2 (2,1) (3,1) go(0,F) 3 (4,1) go(0,() 4 (5,1) (1,0) (2,0) (3,0) (4,0) (5,0) (6,0) go(0,id) 5 (6,1) go(1,+) 6 (1,2) (3,0) (4,0) (5,0) (6,0) go(2,*) 7 (3,2) (5,0) (6,0) go(4,E) 8 (5,2) (1,1) go(4,T) 2 (2,1) (3,1),go(4,F) 3 (4,1) go(4,() 4 (5,1) go(4,id) 5 (6,1) go(6,T) 9 (1,3) (3,1) go(6,F) 3 (4,1) go(6,() 4 (5,1) go(6,id) 5 (6,1) go(7,F) 10 (3,3) go(7,() 4 (5,1) go(7,id) 5 (6,1) go(8,) 11 (5,3) go(
