编译原理语法分析3.ppt

《编译原理语法分析3.ppt》由会员分享，可在线阅读，更多相关《编译原理语法分析3.ppt（283页珍藏版）》请在三一文库上搜索。

1、第三章 语法分析,本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开,3.1 上下文无关文法,3.1.1 上下文无关文法的定义 正规式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复 例：a (ba)5, a (ba)* 正规式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：wcw | w是a和b的串,3.1 上下文无关文法,上下文无关文法是四元组（VT , VN , S, P） VT : 终结符集合 VN : 非终结符集合 S : 开始符号 P : 产生式集合， 产生式形式 : A 例 ( id, +, , , (, ), e

2、xpr, op, expr, P ) expr expr op expr expr (expr) expr expr expr id op + op ,3.1 上下文无关文法,简化表示 expr expr op expr | (expr) | expr | id op + | 简化表示 E E A E | (E ) | E | id A + | ,3.1 上下文无关文法,3.1.2 推导 把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替 例 E E + E | E E | (E ) | E | id E E (E) (E + E) (id + E) (id + id) 概念

3、上下文无关语言、等价的文法、句型 记号 S *、 S + w,3.1 上下文无关文法,例 E E + E | E E | (E ) | E | id 最左推导 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),3.1 上下文无关文法,3.1.3 分析树 例 E E + E | E E | (E ) | E | id,E,E,(,),E,E,E,+,id,id,3.1 上下文无关文法,3.1.4 二义性 E E E E E +

4、 E id E E E +E id E + E id E + E id id + E id id + E id id + id id id + id,3.2 语言和文法,文法的优点 文法给出了精确的，易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改 文法的问题 文法只能描述编程语言的大部分语法,3.2 语言和文法,3.2.1 正规式和上下文无关文法的比较 正规式 (a|b)*ab 文法 A0 a A0 | b A0 | a A1 A1 b A2 A2 ,3.2 语言和文法,3.2.2 分离词法分析器理由 为什么要用正规式定义词法 词法规

5、则非常简单，不必用上下文无关文法 对于词法记号，正规式描述简洁且易于理解 从正规式构造出的词法分析器效率高,3.2 语言和文法,从软件工程角度看，词法分析和语法分析的分离有如下好处 简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分,3.2 语言和文法,能否把词法分析并入到语法分析中，直接从字符流进行语法分析 若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大大复杂 注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多,3.2 语言和文法,3.2.3 验证文法产生的语言 G : S (S ) S | L(G

6、) = 配对的括号串的集合,3.2 语言和文法,3.2.3 验证文法产生的语言 G : S (S ) S | L(G) = 配对的括号串的集合 按推导步数进行归纳：推出的是配对括号串 归纳基础： S 归纳假设：少于n步的推导都产生配对的括号串 归纳步骤：n步的最左推导如下： S (S )S * (x) S * (x) y,3.2 语言和文法,3.2.3 验证文法产生的语言 G : S (S ) S | L(G) = 配对的括号串的集合 按串长进行归纳：配对括号串可由S推出 归纳基础： S 归纳假设：长度小于2n的都可以从S推导出来 归纳步骤：考虑长度为2n(n 1)的w = (x) y S (

7、S )S * (x) S * (x) y,3.2 语言和文法,3.2.4 适当的表达式文法 用一种层次观点看待表达式 id id (id+id) + id id + id id id (id+id) 文法 expr expr + term | term term term factor | factor factor id | (expr),3.2 语言和文法,expr expr + term | term term term factor | factor factor id | (expr),id + id id 分析树,id id id 分析树,3.2 语言和文法,3.2.5 消除二义性

8、 stmt if expr then stmt | if expr then stmt else stmt | other 句型：if expr then if expr then stmt else stmt 两个最左推导： stmt if expr then stmt if expr then if expr then stmt else stmt stmt if expr then stmt else stmt if expr then if expr then stmt else stmt,3.2 语言和文法,无二义的文法 stmt matched _stmt | unmatched_

9、stmt matched_stmt if expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt,3.2 语言和文法,3.2.6 消除左递归 文法左递归 A+Aa 直接左递归 AAa |b 串的特点 ba . . . a 消除直接左递归 A b A A a A | ,3.2 语言和文法,例 算术表达文法 E E + T | T （ T + T . . . + T ） T T F | F （ F

10、 F . . . F ） F ( E ) | id 消除左递归后文法 E TE E + TE | T FT T F T | F ( E ) | id,3.2 语言和文法,非直接左递归 S Aa | b A Sd | 先变换成直接左递归 S Aa | b A Aad | bd | 再消除左递归 S Aa | b A bd A | A A adA | ,3.2 语言和文法,3.2.7 提左因子 有左因子的文法 A 1 | 2 提左因子 A A A 1 | 2,3.2 语言和文法,例 悬空else的文法 stmt if expr then stmt else stmt | if expr then

11、stmt | other 提左因子 stmt if expr then stmt optional_else_part | other optional_else_part else stmt | ,3.2 语言和文法,3.2.8 非上下文无关的语言构造 L1 = wcw | w属于(a | b)* 标识符的声明应先于其引用的抽象 L2 = anbmcndm | n 0, m 0 形参个数和实参个数应该相同的抽象 L3 = anbncn | n 0 早先排版描述的一个现象的抽象,3.2 语言和文法,L1= wcwR | w(a|b)* S aSa | bSb | c L2 = anbmcmdn

12、 | n 1, m 1 S aSd | aAd A bAc | bc L 2 = anbncmdm | n 1，m 1 S AB A aAb | ab B cBd | cd,3.2 语言和文法,L3 =anbn | n 1 S aSb | ab L3是不能用正规式描述的语言的一个范例 若存在接受L3 的DFA D，状态数为k个 设D读完, a, aa, , ak 分别到达状态s0, s1, , sk 至少有两个状态相同，例如是si和sj，则ajbi属于L3,3.2 语言和文法,3.2.9 形式语言鸟瞰 文法 G = (VT , VN, S, P) 0型文法： ， , (VN VT)*, | |

13、 1,3.2 语言和文法,3.2.9 形式语言鸟瞰 文法 G = (VT , VN, S, P) 0型文法： ， , (VN VT)*, | | 1 短语文法,3.2 语言和文法,3.2.9 形式语言鸟瞰 文法 G = (VT , VN, S, P) 0型文法： ， , (VN VT)*, | | 1 1型文法：| | | |，但S 可以例外 短语文法,3.2 语言和文法,3.2.9 形式语言鸟瞰 文法 G = (VT , VN, S, P) 0型文法： ， , (VN VT)*, | | 1 1型文法：| | | |，但S 可以例外 短语文法、上下文有关文法,3.2 语言和文法,3.2.9

14、形式语言鸟瞰 文法 G = (VT , VN, S, P) 0型文法： ， , (VN VT)*, | | 1 1型文法：| | | |，但S 可以例外 2型文法：A ，AVN , (VN VT)* 短语文法、上下文有关文法,3.2 语言和文法,3.2.9 形式语言鸟瞰 文法 G = (VT , VN, S, P) 0型文法： ， , (VN VT)*, | | 1 1型文法：| | | |，但S 可以例外 2型文法：A ，AVN , (VN VT)* 短语文法、上下文有关文法、上下文无关文法,3.2 语言和文法,3.2.9 形式语言鸟瞰 文法 G = (VT , VN, S, P) 0型文法

15、： ， , (VN VT)*, | | 1 1型文法：| | | |，但S 可以例外 2型文法：A ，AVN , (VN VT)* 3型文法：A aB或A a，A, BVN , a VT 短语文法、上下文有关文法、上下文无关文法,3.2 语言和文法,3.2.9 形式语言鸟瞰 文法 G = (VT , VN, S, P) 0型文法： ， , (VN VT)*, | | 1 1型文法：| | | |，但S 可以例外 2型文法：A ，AVN , (VN VT)* 3型文法：A aB或A a，A, BVN , a VT 短语文法、上下文有关文法、上下文无关文法、正规文法,3.2 语言和文法,例 L3a

16、nbncn| n 1的上下文有关文法 S aSBC S aBC CB BC aB ab bB bb bC bc cC cc anbncn的推导过程如下： S * an-1S(BC)n1 用S aSBC n-1次 S + an(BC)n 用S aBC 1次 S + anBnCn 用CB BC交换相邻的CB S + anbBn1Cn 用aB ab 1次 S + anbnCn 用bB bb n-1次 S + anbncCn-1 用bC bc 1次 S + anbncn 用cC cc n-1次,3.3 自上而下分析,3.3.1 自上而下分析的一般方法 例 文法 S aCb C cd | c 为输入串w

17、 = acb建立分析树,不能处理左递归,3.3 自上而下分析,不能处理左递归的例子 算术表达文法 E E + T | T T T F | F F ( E ) | id,E,3.3 自上而下分析,3.3.1 自上而下分析的一般方法 例 文法 S aCb C cd | c 为输入串w = acb建立分析树,不能处理左递归、复杂的回溯技术,3.3 自上而下分析,3.3.1 自上而下分析的一般方法 例 文法 S aCb C cd | c 为输入串w = acb建立分析树,不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来,3.3 自上而下分析,3.3.1 自上而下分析的一般方法 例 文法 S a

18、Cb C cd | c 为输入串w = acb建立分析树,不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置,3.3 自上而下分析,3.3.1 自上而下分析的一般方法 例 文法 S aCb C cd | c 为输入串w = acb建立分析树,不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效率低,3.3 自上而下分析,3.3.2 LL(1)文法 对文法加什么样的限制可以保证没有回溯？ 先定义两个和文法有关的函数 FIRST( ) = a | * a, a VT 特别是， * 时，规定 FIRST( ) 对A的任何两个不同选择i 和

19、j，希望有 FIRST(i ) FIRST(j ) = 若FIRST(i ) 或 FIRST(j )含，还需增加条件,3.3 自上而下分析,3.3.2 LL(1)文法 对文法加什么样的限制可以保证没有回溯？ 先定义两个和文法有关的函数 FIRST( ) = a | * a, a VT 特别是， * 时，规定 FIRST( ) FOLLOW(A) = a | S * Aa，aVT 如果A是某个句型的最右符号，那么$属于FOLLOW(A),3.3 自上而下分析,LL(1)文法 任何两个产生式A | 都满足下列条件： FIRST( ) FIRST( ) = 若 * ，那么FIRST() FOLLOW

20、(A) = 例如, 对于下面文法，面临a时不知用什么规则 S A B A a b | a FIRST(ab) FOLLOW(A) B a C C ,3.3 自上而下分析,LL(1)文法 任何两个产生式A | 都满足下列条件： FIRST( ) FIRST( ) = 若 * ，那么FIRST() FOLLOW(A) = LL(1)文法有一些明显的性质 没有公共左因子 不是二义的 不含左递归,3.3 自上而下分析,例 E TE E + TE | T FT T FT | F (E) | id FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +,

21、 FRIST(T ) = , FOLLOW(E) = FOLLOW(E ) = ), $ FOLLOW(T) = FOLLOW (T ) = +, ), $ FOLLOW(F) = +, , ), $,3.3 自上而下分析,3.3.3 递归下降的预测分析 为每一个非终结符写一个分析过程 这些过程可能是递归的 例 type simple | id | array simple of type simple integer | char | num dotdot num,3.3 自上而下分析,一个辅助过程 void match (terminal t) if (lookahead = t) loo

22、kahead = nextToken( ); else error( ); ,3.3 自上而下分析,void type( ) if ( (lookahead = integer) | (lookahead = char) | (lookahead = num) ) simple( ); else if ( lookahead = ) match(); match(id); else if (lookahead = array) match(array); match( ); simple( ); match( ); match(of ); type( ); else error( ); ,ty

23、pe simple | id | array simple of type,3.3 自上而下分析,void simple( ) if ( lookahead = integer) match(integer); else if (lookahead = char) match(char); else if (lookahead = num) match(num); match(dotdot); match(num); else error( ); ,simple integer | char | num dotdot num,3.3 自上而下分析,3.3.4 非递归的预测分析,3.3 自上而下

24、分析,分析表的一部分,3.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,3.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,3.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,3.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,3.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,3.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,3.3 自上而下分析,预测分析器接受输入id * id + id的前一部分动作,3.3 自上而下分

25、析,预测分析器接受输入id * id + id的前一部分动作,3.3 自上而下分析,3.3.5 构造预测分析表 （1）对文法的每个产生式A ，执行(2)和(3) （2）对FIRST()的每个终结符a， 把A 加入MA, a （3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$）, 把A 加入MA, b （4）M中其它没有定义的条目都是error,3.3 自上而下分析,多重定义的条目,3.3 自上而下分析,消去多重定义,3.3 自上而下分析,3.3.6 预测分析的错误恢复 1、先对编译器的错误处理做一个概述 词法错误，如标识符、关键字或算符的拼写错 语法错误，如算术表达式的括

26、号不配对 语义错误，如算符作用于不相容的运算对象 逻辑错误，如无穷的递归调用,3.3 自上而下分析,2、分析器对错误处理的基本目标 清楚而准确地报告错误的出现，并尽量少出现伪错误 迅速地从每个错误中恢复过来，以便诊断后面的错误 它不应该使正确程序的处理速度降低太多,3.3 自上而下分析,3、非递归预测分析在什么场合下发现错误 栈顶的终结符和下一个输入符号不匹配,3.3 自上而下分析,3、非递归预测分析在什么场合下发现错误 栈顶是非终结符A，输入符号是a，而MA , a是空白,3.3 自上而下分析,4、非递归预测分析：采用紧急方式的错误恢复 发现错误时，分析器每次抛弃一个输入记号，直到输入记号属

27、于某个指定的同步记号集合为止 5、同步 词法分析器当前提供的记号流能构成的语法构造，正是语法分析器所期望的,3.3 自上而下分析,6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合,3.3 自上而下分析,6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 if expr then stmt （then是expr的一个同步记号）,3.3 自上而下分析,6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中,3.3 自上而下分析,6、同步记号集合的选择

28、 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 a = expr; if (语句的开始符号作为表达式的同步记号，以免表达式出错又遗漏分号时忽略if语句等一大段程序),3.3 自上而下分析,6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 把FIRST(A)的终结符加入A的同步记号集合 a = expr; , if （语句的开始符号作为语句的同步符号，以免多出一个逗号时会把if语句忽略了）,3.3 自上而下分析,6、同步记号集合的选择 把FOLL

29、OW(A)的所有终结符放入非终结符A的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 把FIRST(A)的终结符加入A的同步记号集合 如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式,3.3 自上而下分析,例 栈顶为T ，面临id时出错,3.3 自上而下分析,T 可以产生空串，报错并用T ,3.3 自上而下分析,同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 把高层结构的开始符号加到低层结构的同步记号集合中 把FIRST(A)的终结符加入A的同步记号集合 如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，

30、则可以使用推出空串的产生式 如果终结符在栈顶而不能匹配，弹出此终结符,3.4 自下而上分析,3.4.1 归约 例 S aABe A Abc | b B d,3.4 自下而上分析,3.4.1 归约 例 S aABe A Abc | b B d abbcde（读入ab）,3.4 自下而上分析,3.4.1 归约 例 S aABe A Abc | b B d abbcde aAbcde（归约）,3.4 自下而上分析,3.4.1 归约 例 S aABe A Abc | b B d abbcde aAbcde（再读入bc）,3.4 自下而上分析,3.4.1 归约 例 S aABe A Abc | b B

31、d abbcde aAbcde aAde（归约）,3.4 自下而上分析,3.4.1 归约 例 S aABe A Abc | b B d abbcde aAbcde aAde（再读入d）,3.4 自下而上分析,3.4.1 归约 例 S aABe A Abc | b B d abbcde aAbcde aAde aABe（归约）,3.4 自下而上分析,3.4.1 归约 例 S aABe A Abc | b B d abbcde aAbcde aAde aABe(再读入e),3.4 自下而上分析,3.4.1 归约 例 S aABe A Abc | b B d abbcde aAbcde aAde a

32、ABe S（归约）,3.4 自下而上分析,3.4.1 归约 例 S aABe A Abc | b B d abbcde aAbcde aAde aABe S S rm aABe rm aAde rm aAbcde rm abbcde,3.4 自下而上分析,3.4.2 句柄 句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步 S aABe A Abc | b B d S rm aABe rm aAde rm aAbcde rm abbcde 句柄的右边仅含终结符 如果文法二义，那么句柄可能不唯一,3.4 自下而上分析,例 句柄不唯一 E

33、E + E | E E | (E ) | id,3.4 自下而上分析,例 句柄不唯一 E E + E | E E | (E ) | id E rm E E rm E E + E rm E E + id3 rm E id2 + id3 rm id1 id2 + id3,3.4 自下而上分析,例 句柄不唯一 E E + E | E E | (E ) | id E rm E E E rm E + E rm E E + E rm E + id3 rm E E + id3 rm E E + id3 rm E id2 + id3 rm E id2 + id3 rm id1 id2 + id3 rm id1

34、 id2 + id3 在句型E E + id3中，句柄不唯一,3.4 自下而上分析,3.4.3 用栈实现移进归约分析 先通过 移进归约分析器在分析输入串id1 id2 + id3时的动作序列 来了解移进归约分析的工作方式,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.

35、4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,3.4 自下而上分析,要想很好地使用移进归约方式，尚需解决一些问题 如何决策选择移进还是归约 进行归约时，确定右句型中将要归约的子串 进行归约时，如何确定选择哪一个产生式,3.4 自下而上分析,3.4.4 移进归约分析的冲突 1、移进归约冲突 例 stmt if expr then stmt | if expr then stmt else stmt | other 如果移进归约分析器处于格局 栈 输入 if expr then stmt else $,3.4 自下而上分析,2、归约归约冲

36、突 stmt id (parameter_list) | expr = expr parameter_list parameter_list, parameter | parameter parameter id expr id (expr_list) | id expr_list expr_list, expr | expr 由A(I, J)开始的语句 栈 输入 id ( id , id ),归约成expr还 是parameter ?,3.4 自下而上分析,2、归约归约冲突 stmt id (parameter_list) | expr = expr parameter_list param

37、eter_list, parameter | parameter parameter id expr id (expr_list) | id expr_list expr_list, expr | expr 由A(I, J)开始的语句(词法分析查符号表,区分第一个id) 栈 输入 procid ( id , id ) 需要修改上面的文法,3.5 LR分析器,本节介绍LR(k)分析技术 特点 适用于一大类上下文无关文法 效率高 主要介绍构造LR分析表的三种技术 简单的LR方法（简称SLR） 规范的LR方法 向前看的LR方法（简称LALR）,3.5 LR分析器,3.5.1 LR分析算法,3.5 L

38、R分析器,例 E E + T | E T T T F | T E F (E ) | F id,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5 LR分析器,3.5.2 LR文法和LR分析方法的特点 1、概念 活前缀：右句型的前缀，该前缀不超过最右句柄的右端 S *rm A w rm w 的任何前缀（包

39、括和 本身）都是活前缀,3.5 LR分析器,3.5.2 LR文法和LR分析方法的特点 1、概念 活前缀：右句型的前缀，该前缀不超过最右句柄的右端 2、定义 LR文法：我们能为之构造出所有条目都唯一的LR分析表,3.5 LR分析器,3、LR分析方法的特点 栈中的文法符号总是形成一个活前缀,3.5 LR分析器,3.5 LR分析器,3、LR分析方法的特点 栈中的文法符号总是形成一个活前缀 分析表的转移函数本质上是识别活前缀的DFA,3.5 LR分析器,例 E E + T | E T 下表绿色部分构成 T T F | T E 识别活前缀DFA的 F (E ) | F id 状态转换表,3.5 LR分析

40、器,3、LR分析方法的特点 栈中的文法符号总是形成一个活前缀 分析表的转移函数本质上是识别活前缀的DFA 栈顶的状态符号包含了确定句柄所需要的一切信息,3.5 LR分析器,3.5 LR分析器,3、LR分析方法的特点 栈中的文法符号总是形成一个活前缀 分析表的转移函数本质上是识别活前缀的DFA 栈顶的状态符号包含了确定句柄所需要的一切信息 是已知的最一般的无回溯的移进归约方法 能分析的文法类是预测分析法能分析的文法类的真超集 能及时发现语法错误 手工构造分析表的工作量太大,3.5 LR分析器,4、LR分析方法和LL分析方法的比较,3.5 LR分析器,4、LR分析方法和LL分析方法的比较,3.5

41、LR分析器,4、LR分析方法和LL分析方法的比较 在下面的推导中，最后一步用的是A l S rm rm A b w rm l b w,LL(1)决定用该 产生式的位置,LR(1)决定用该 产生式的位置,3.5 LR分析器,4、LR分析方法和LL分析方法的比较,3.5 LR分析器,4、LR分析方法和LL分析方法的比较,3.5 LR分析器,4、LR分析方法和LL分析方法的比较,3.5 LR分析器,4、LR分析方法和LL分析方法的比较,3.5 LR分析器,4、LR分析方法和LL分析方法的比较,3.5 LR分析器,4、LR分析方法和LL分析方法的比较,3.5 LR分析器,3.5.3 构造SLR分析表

42、术语：LR(0)项目（简称项目） 在右部的某个地方加点的产生式,3.5 LR分析器,3.5.3 构造SLR分析表 术语：LR(0)项目（简称项目） 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态,3.5 LR分析器,3.5.3 构造SLR分析表 术语：LR(0)项目（简称项目） 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态,3.5 LR分析器,3.5.3 构造SLR分析表 术语：LR(0)项目（简称项目） 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态,3.5 LR分析器,3.5.3 构造SLR分析表 术语：LR(0)项目（简称项目

43、） 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态,3.5 LR分析器,3.5.3 构造SLR分析表 术语：LR(0)项目（简称项目） 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 例 AXYZ对应有四个项目 A XYZ A XYZ A XYZ A XYZ 例 A只有一个项目和它对应 A ,3.5 LR分析器,构造SLR分析表的两大步骤 1、从文法构造识别活前缀的DFA 2、从上述DFA构造分析表,3.5 LR分析器,1、从文法构造识别活前缀的DFA 1）拓广文法 E E + T | T T T F | F F ( E ) | id,3.5 LR分析器

44、,1、从文法构造识别活前缀的DFA 1）拓广文法 E E E E + T | T T T F | F F ( E ) | id,3.5 LR分析器,1、从文法构造识别活前缀的DFA 2）构造LR(0)项目集规范族 I0: E E,3.5 LR分析器,1、从文法构造识别活前缀的DFA 2）构造LR(0)项目集规范族 I0: E E E E + T E T,3.5 LR分析器,1、从文法构造识别活前缀的DFA 2）构造LR(0)项目集规范族 I0: E E E E + T E T T T F T F,3.5 LR分析器,1、从文法构造识别活前缀的DFA 2）构造LR(0)项目集规范族 I0: E

45、E E E + T E T T T F T F F (E) F id,3.5 LR分析器,1、从文法构造识别活前缀的DFA 2）构造LR(0)项目集规范族 I0: E E (核心项目) E E + T E T (非核心项目， T T F 通过对核心项目求闭包 T F 而获得) F (E) F id,3.5 LR分析器,1、从文法构造识别活前缀的DFA 2）构造LR(0)项目集规范族 I0: I1: E E E E E E + T E E + T E T T T F T F F (E) F id,3.5 LR分析器,1、从文法构造识别活前缀的DFA 2）构造LR(0)项目集规范族 I0: I1: E E E E E E + T E E + T E T T T F I1 := goto ( I0, E ) T F F (E) F id,3.5 LR分析器,