编译原理第五章语法分析3解析.ppt

5.4 LR( )分析法 2. LR( )分析法分析过程示例： 3. 有限自动机用作句柄识别器： ② 利用扩展文法构造句柄识别器： ※ 句柄识别器的自动机构造示例： ※ 根据句柄识别器进行LR分析过程： 5.4.2 LR(0)分析器设计 3. LR(0)控制程序设计 ※ LR(0)分析法小结示例 ⑷ LR(0)分析法分析过程示例： 练习题: 【习题5.8】 解释下列词语： ⑴ 文法出现， ⑵ LR(0)文法， ⑶ LR(0)分析器组成。 【习题5.9】构造下述文法的LR(0)分析表： G(Z)： Z - aAb , A - cA | d ※【例5.9】LR(0)分析法示例1： ※ 构造下述文法的LR(0)分析表： G(Z)： Z - aAb , A - cA | d ⑶ 设计LR(0) 分析表： ※【例5.10】左递归文法的LR(0)分析表构造： ※【例5.11】LR(0)分析法示例1 ※ 构造下述文法的LR(0)分析表： G(Z) Z - aAb , A - Ac | d ⑴ 扩展文法：G`(Z`) Z`- Z1 (0) Z - a2 A3 b4 (1) A - A5c6 (2)| d7 (3) ⑵ 构造可归前缀图： (接上页) ∵ ?（2，A)={3,5}, ∴ 是个非确定机； (接上页) LR(0) 分析表： * * LR( )分析法是指从左到右扫描、最左归约(LR)之意；它属于自底向上分析方法。 常用的算法有LR(0)和LR(1)等，其中括号内的数是指不查看(0)或只查看一个当前符号(1)，即可确定当前句型的句柄。 ⑴ 利用一个分析表，登记选择句柄产生式的知识； ⑵ 利用一个分析栈，记录分析过程； ⑶【分析算法】依次读取单词，并进行如下操作： 当栈顶出现句柄时，规约之，否则移进。 5.4.1. LR( )分析法基本概念 ※ LR( ) 分析法的基本要点有三： 1. 什么是LR（）分析法？ 【例5.8】 G(Z): Z-aBAd, A-bc|c, B-bB|c ⑴ 符号串 abccd 最左归约过程: ⑵ 符号串 abccd 的语法树： abccd 的语法树 ① ② ③ a b c c d B B A Z ※ 归约过程的句柄： 句柄 次序 ① c ② bB ③ c ④ aBAd abccd = . abBcd = . aBcd = . aBAd = . Z ④ 句柄产生式 操 作 剩余串 w 分析栈 移进,NEXT d # c # a 归约， A - c # d # a B 移进,NEXT # d # a B 归约， Z - aBAd # # a B A OK # # B - bB B - c 移进,NEXT c d # c # a 移进,NEXT b c c d # a # 归约， d # c # a b 归约， d # c # a b 移进,NEXT c c d # b # B B Z A a b c c d 句柄 (接上页) ⑶ 利用分析栈记录行分析过程： 【注】 何时栈顶出现句柄？怎样求当前句柄产生式 ？ 设 待分析的符号串: abccd# ② 如何确认首次出现的?c 的父亲是 B,而不是 A ？ G(Z): Z - aBAd A - bc | c B - bB | c ※ 句柄一定出现于某一个产生式的右部； ⑴ 归约过程中如何确认句柄？ ※ 是否是句柄，还要看其所在符号串中的位置。 ① 怎样判断栈顶出现的句柄不是 bc,而是 c ? ∴ 显然是错误的(从文法中可判定：aA不能相邻!) ∵ 若用 bc 归约，则有 abccd aAcd( ) = . ∵ 若用 A作父亲，则有 abccd abAcd( ) = . ∴显然是错误的(从文法中可判定：Ac不能相邻! 语法树 ※ 我们讨论如下两个问题： #abc cd# 分析栈 ① 扩展文法，使文法