编译原理自底向上的语法分析

1、编译原理自底向上的语法分析开发语法分析程序开发语法分析程序语法定义语法定义基于基于上下文无关文法上下文无关文法使用使用实现实现自顶向下自顶向下自底向上自底向上编译原理自底向上的语法分析l5.1 自底向上的语法分析方法概述自底向上的语法分析方法概述l5.2 LR(0)分析的有限自动机分析的有限自动机l5.3 LR(0) 分析分析l5.4 SLR(1) 分析分析l5.5 LR(1) 分析分析l5.6 LALR(1) 分析分析l5.7 LALR(1) 语法分析器的自动生成器语法分析器的自动生成器 (YACC)编译原理自底向上的语法分析l自顶向下语法分析回顾自顶向下语法分析回顾l自底向上语法分析的例子

2、自底向上语法分析的例子l自底向上语法分析的主要思想自底向上语法分析的主要思想l自底向上语法分析的关键问题自底向上语法分析的关键问题l一些相关概念一些相关概念编译原理自底向上的语法分析P:(1) Z aBeA(2) A Bc (3) B d(4) B bB (5) B a b e c自顶向下分析过程是从自顶向下分析过程是从文法开始符文法开始符出发，为所给出发，为所给输入串输入串构造构造最左推导最左推导的过程。的过程。句型句型输入输入动作动作Z Zabecabec推导推导(1)(1)abecabeca aB BeAeA匹配匹配(a)(a)becbecB BeAeA推导推导(4)(4)becbecb

3、 bB BeAeA匹配匹配(b)(b)ececB BeAeA推导推导(5)(5)ecece eA A匹配匹配(e)(e)c cA A推导推导(2)(2)c cB Bc c推导推导(5)(5)匹配匹配(c)(c)c c c c成功成功编译原理自底向上的语法分析P:Z ABb(2) A a (3) A b(4) B b(5) B c(6) B bBa b c b输入输入符号栈符号栈动作动作abcbabcb移入移入a abcbbcb归约归约(2)(2)A Abcbbcb移入移入AbAbcbcb移入移入AbAbc cb b归约归约(5)(5)AbAbB Bb b归约归约(6)(6)ABABb b移入移

4、入归约归约(1)(1)ABbABbZ Z成功成功自底向上分析过程是从所给自底向上分析过程是从所给输入串输入串出发，对其进行出发，对其进行最左归约最左归约的过程。的过程。编译原理自底向上的语法分析a b c bBBZ归约过程归约过程Z rm ABb rm AbBb rm Abcb rm abcbA abcb- Abcb- AbBb- ABb- Z自底向上分析中归约过自底向上分析中归约过 程的逆过程就是该句子程的逆过程就是该句子的最右推导的最右推导;编译原理自底向上的语法分析l主要思想主要思想:从输入串出发从输入串出发;尽可能地找到尽可能地找到可归约子串可归约子串并将其归约成一个非终极符并将其归约

5、成一个非终极符;直到归约成文法的开始符或发现语法错误直到归约成文法的开始符或发现语法错误;l分析动作分析动作:移入移入(shift),归约归约(reduce)l包含以下方法包含以下方法: LR 类的方法类的方法; 简单优先法简单优先法; 算符优先法算符优先法l关键问题关键问题:什么时候进行归约，按照哪条产生式进行归约什么时候进行归约，按照哪条产生式进行归约;编译原理自底向上的语法分析l短语短语一个句型形如一个句型形如, 如果存在一个句型如果存在一个句型 A ,而且而且 A+ , 则称则称 为句型为句型的的短语短语;例如句型例如句型AbBb，则，则bB,AbBb是它的短语，因为是它的短语，因为l

6、存在句型存在句型ABb，ABb AbBb， = A， = b；l存在句型存在句型Z，Z ABb AbBb ， = ， = ；l简单短语简单短语一个句型形如一个句型形如, 如果存在一个句型如果存在一个句型 A ,而且而且 A , 则称则称 为句型为句型的的简单短语简单短语;例如句型例如句型AbBb，bB是它的简单短语，是它的简单短语，AbBb不是不是它的简单短语它的简单短语(1) Z ABb(2) A a(3) A b(4) B d(5) B c(6) B bB编译原理自底向上的语法分析l句柄句柄:一个句型的简单短语可能有多个，称一个句型的简单短语可能有多个，称最最左简单短语左简单短语为为句柄句

7、柄(handler);例如：句型例如：句型abBb，简单短语有两个：，简单短语有两个：a,bBlZ ABb aBb abBb最左简单短语最左简单短语a是句柄是句柄l句柄的唯一性句柄的唯一性: 如果一个如果一个CFG无二义性无二义性,则它的任意一个句型都则它的任意一个句型都有唯一的句柄有唯一的句柄;编译原理自底向上的语法分析P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n句型句型: T+ (E+T)*i简单短语简单短语: T, E+T, i句柄句柄: T通过为所给句型建立语法分析树，可以很容易地识别出该句通过为所给句型建立

8、语法分析树，可以很容易地识别出该句型的所有短语、简单短语和句柄。型的所有短语、简单短语和句柄。句型的一个推导句型的一个推导: (该句型没有最右推导该句型没有最右推导)E E + T E + T*FE+T*i E+F*i E+(E)*i E+(E+T)*i T+(E+T)*i短语短语: T +(E+T)*i, T, E+T, i, (E+T),(E+T)*i编译原理自底向上的语法分析EE+TTT* FF（ E ）E+ Ti 语法分析树语法分析树的叶子节点构成的叶子节点构成句型句型: T+ (E+T)*i每棵每棵子树子树的叶子节点构成的叶子节点构成短语短语：T+ (E+T)*i 、T、(E+T)*

9、i、(E+T)、E+T、i每棵每棵简单子树简单子树(只有一层的子树只有一层的子树)的叶子节的叶子节点构成点构成简单短语简单短语：T、E+T、i最左简单子树最左简单子树的叶子节点构成的叶子节点构成句柄句柄： T编译原理自底向上的语法分析l自顶向下的语法分析方法中曾介绍过：自顶向下的语法分析方法中曾介绍过：l推导：对句型中的非终极符用产生式右部替换推导：对句型中的非终极符用产生式右部替换l规范推导：一个句型的最右推导称为该句型的规范推导：一个句型的最右推导称为该句型的规范推导规范推导;l规范句型规范句型(右句型右句型)：从开始符通过规范推导得：从开始符通过规范推导得到的句型到的句型;推导的逆过程称

10、为归约规范推导的逆过程称为规范归约(最左归约)规范归约过程中产生的句型仍是规范句型规范归约的过程也是对规范句型的最左简单短语(句柄)进行归约的过程编译原理自底向上的语法分析 Z ABb 规范前缀为规范前缀为 AB, ABd Z + Acb 规范前缀为规范前缀为 A, Ac, Acbl规范前缀规范前缀:一个规范句型的一个前缀称为一个规范句型的一个前缀称为规范前缀规范前缀, 如如果该前缀后面的符号串不包含非终极符果该前缀后面的符号串不包含非终极符;规范句型规范句型规范前缀规范前缀 或者终极符串或者终极符串编译原理自底向上的语法分析 Z ABb 规范前缀为规范前缀为 AB, ABb 规范活前缀规范活

11、前缀: AB(不包含简单短语不包含简单短语) , ABb(包含一个简单短语且在最后包含一个简单短语且在最后) l规范活前缀规范活前缀:满足如下条件之一的规范前缀称为规范满足如下条件之一的规范前缀称为规范活前缀活前缀:该规范前缀不包含简单短语该规范前缀不包含简单短语;该规范前缀只包含一个简单短语该规范前缀只包含一个简单短语,而且是在该规范前缀的最而且是在该规范前缀的最后后(这个简单短语就是句柄这个简单短语就是句柄); Z + abcb 规范前缀为规范前缀为 a, ab, abc, abcb规范活前缀规范活前缀: a (包含一个简单短语且在最后包含一个简单短语且在最后) abc是不是规范活前缀？是

12、不是规范活前缀？ (不是，包含两个简单短语不是，包含两个简单短语a和和c)编译原理自底向上的语法分析P:Z ABb(2) A a(3) A b(4) B b(5) B c(6) B bBa b c b输入输入符号栈符号栈动作动作abcbabcb移入移入a abcbbcb归约归约(2)(2)A Abcbbcb移入移入AbAbcbcb移入移入AbcAbcb b归约归约(5)(5)AbBAbBb b归约归约(6)(6)ABABb b移入移入归约归约(1)(1)ABbABbZ Z成功成功自底向上分析过程是从所给自底向上分析过程是从所给输入串输入串出发，对其进行出发，对其进行最左归约最左归约的过程。的过

13、程。规范活前缀规范活前缀 或者或者终极符串终极符串规范句型编译原理自底向上的语法分析l规范活前缀规范活前缀决定决定分析动作分析动作移入移入:规范活前缀不包含简单短语规范活前缀不包含简单短语; ; 移入型规范活前缀移入型规范活前缀归约归约:规范活前缀只包含一个简单短语规范活前缀只包含一个简单短语, ,而且是在该规范而且是在该规范活前缀的最后活前缀的最后; ; 可归约规范活前缀可归约规范活前缀 ：归约规范活前缀：归约规范活前缀 Z ABb 规范前缀为规范前缀为 AB, ABb 规范活前缀规范活前缀: AB(不包含简单短语不包含简单短语) - 移入型规范活前缀移入型规范活前缀 ABb(包含一个简单短

14、语包含一个简单短语) - 归约规范活前缀归约规范活前缀编译原理自底向上的语法分析规范归约规范归约推导推导(*)最右推导最右推导句型句型(S *) 短语短语(A + )简单短语简单短语(A )句柄句柄(最左最左)规范推导规范推导规范句型规范句型(S rm*)特例特例特例特例规范前缀规范前缀规范活前缀规范活前缀包含包含0或或1个个归约规范活前缀归约规范活前缀应用应用互逆互逆最右包最右包含含1个个自底向上自底向上分析分析编译原理自底向上的语法分析lLR 方法方法主要思想主要思想lL表示从左至右读入输入串表示从左至右读入输入串;lR表示构造一个最右推导的逆过程，即每次找到句柄表示构造一个最右推导的逆过程，即每次找到句柄 (归约规范活前缀归约规范活前缀)来进行归约来进行归约;l归约直到得到归约直到得到开始符开始符或报告语法错误或报告语法错误;关键问题关键问题: 对于一个对于一个CFG, 如何判定归约规范活如何判定归约规范活前缀前缀?l构造一个判定归约规范活前缀的自动机构造一个判定归约规范活前缀的自动机 - LR自动机自动机l由由LR自动机构造自动机构造LR分析表指导分析表指导LR分析分析编译原理自底向上的语法分析分析栈分析栈输入输入#aLR驱动程序驱