《编译原理531LR分析器ppt课件》由会员分享，可在线阅读，更多相关《编译原理531LR分析器ppt课件（22页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 语法分析语法分析5.1 自下而上分析根本问题自下而上分析根本问题5.2 算符优先分析算符优先分析 5.3 LR分析分析5.4 YACC5.3 LR分析分析5.3.1 LR分析器分析器5.3.2 LR(0)工程集族工程集族LR(0)分析表的构造分析表的构造5.3.3 SLR分析表的构造分析表的构造5.3.4 规范规范LR分析表的构造分析表的构造5.3.5 LALR分析表的构造分析表的构造5.3.6 二义文法的运用二义文法的运用课前思索课前思索自下而上分析是一种自下而上分析是一种_过程过程自下而上分析法的关键问题是在分析过程中自下而上分析法的关键问题是在分析过程中_。算符优先分析法如
2、何确定可归约串？算符优先分析法如何确定可归约串？什么是规范推导和规范归约？什么是规范推导和规范归约？ 它们之间有什么关系？它们之间有什么关系？规范归约过程是当分析的栈顶符号串构成规范归约过程是当分析的栈顶符号串构成_时就采取归约动作时就采取归约动作移进移进- -归约归约句柄句柄如何确定可归约串如何确定可归约串LR(K)L : 自左向右扫描自左向右扫描R : 逆向完成最右推导逆向完成最右推导 (规范归约规范归约)K : 向右查看输入串符号的个数向右查看输入串符号的个数 (K省略时省略时, 表示表示K等于等于1)LR分析过程是规范归约过程分析过程是规范归约过程四种四种LR分析器分析器 LR(0)
3、SLR(1)LR(1)LALR(1)LR方法的根本思想方法的根本思想LR方法的关键方法的关键: 确定句柄确定句柄历史历史: 已移进和归约出的整个符号串已移进和归约出的整个符号串 展望展望: 根据所用的产生式推测未来能够根据所用的产生式推测未来能够碰到的输入符号碰到的输入符号 现实现实: 当前的输入符号当前的输入符号 LR分析器的每一步任务都是由栈顶形状和分析器的每一步任务都是由栈顶形状和 现行输入符号所独一决议的。现行输入符号所独一决议的。一个一个LR分析器本质上是一个分析器本质上是一个DFA 形形状状5.3.1 LR分析器分析器 P100a1a2aian#LR分析表分析表总控程序总控程序输入
4、串：输入串：栈顶栈顶输出输出s0s1sm形状栈形状栈#x1xm符号栈符号栈分析栈分析栈GotoAction 图图5.4 LR5.4 LR分析器模型分析器模型 分析表分析表例：例： p101G:(1) E E+T (2) E T(3) T T*F (4) T F(5) F (E)(6) F i3.3.3102.2.91.8 .accr2.r4r6.r1r3r5.r2r4.r6.S11r1r3r5S4.S4.S4S4.S7r4.r6.S7r3r5.S6r2r4.r6.S6r1r3r5S5.S5.S5S501234567891011FTE#)(*+i形状形状GOTOs,AACTIONs,a表达式文法
5、的表达式文法的LRLR分析表分析表 p101 p101将将LR分析器的任务过程看成三元式的变化过程分析器的任务过程看成三元式的变化过程形状栈形状栈符号栈符号栈输入串输入串分析开场时的初始三元式为分析开场时的初始三元式为: (s0 , ， ala2.an分析过程每步的结果可表示为分析过程每步的结果可表示为 (s0s1.sm，X1X2.Xm，aiai+1an分析器的下一步动作由分析器的下一步动作由sm和和 ai所独一决议所独一决议 栈顶栈顶栈顶栈顶现行输入符号现行输入符号Actionsm,ai: 4Actionsm,ai: 4种能够动作种能够动作(1) 移进移进 sj(2) 归约归约 rm(3)
6、接受接受 acc(4) 报错报错 空白空白 / 出错出错 / error(1) 移进移进 sjpush s ;push ai;状状态栈符号符号栈输入串入串s0s1.smX1X2.Xmaiai+1ans0s1.smX1X2.Xmai+1ans = GOTO sm，ai = jsaij(2) 归约归约 - rmpop 文法符号栈文法符号栈 r次次pop 形状栈形状栈 r次次 push A 查表查表 s = GOTOsm-r , A push s用第用第m条产生式条产生式A归约归约. | =r状状态栈符号符号栈输入串入串s0s1.sm-rsmX1X2.Xm-r Xmaiai+1ans0s1.sm-r
7、X1X2.Xm-raiai+1anAs步骤步骤 状态栈状态栈符号栈符号栈剩余输入串剩余输入串动作动作10#i*i+i#2345例例5.7 5.7 对对i*i+i# i*i+i# 进展移进进展移进- -归约分析归约分析 P102 P102 移进移进 S50 0#*i+i# 归约归约 r6 FiG:(1) E E+T (2) E T(3) T T*F (4) T F(5) F (E)(6) F i0#*i+i#F3归约归约 r4 TF0#*i+i#T25 5i移进移进 S7027 7#T* *i+i# 移进移进 S5步骤步骤状态栈状态栈符号栈符号栈剩余输入串剩余输入串动作动作10#i*i+i# 移
8、进 S5 205#i*i+i# 归约 r6 Fi 303#F*i+i# 归约 r4 TF402#T*i+i# 移进 S75027#T*i+i# 移进 S560275#T*i+i# 归约 r6 Fi7027 10#T*F+i# 归约 r3 TT*F802#T+i# 归约 r2 ET901#E+i# 移进 S610016#E+i# 移进 S5110165#E+i# 归约 r6 Fi120163#E+F# 归约 r4 TF130169#E+T# 归约 r1 EE+T1401#E# 接受 accp102补充：补充：LR分析算法分析算法 * 形状栈中放入形状形状栈中放入形状0 ; 文法符号栈中放入文法符
9、号栈中放入ip指向输入串指向输入串w的第一个符号的第一个符号Sm为栈顶形状为栈顶形状 ; a是是ip指向的符号指向的符号 Repeat /见下页见下页end .Repeat if ACTIONSm,a=Sjbegin PUSH j, a ip 前进前进 endelse if ACTIONSm,a=rj / A begin pop | 项项/当前栈顶形状为当前栈顶形状为Skpush GOTOSk, A , A endelse if ACTIONSm, a=accreturn (胜利胜利else errorend .LR分析器小结分析器小结总控程序总控程序 - 对一切的对一切的LR分析器都是一样的
10、。分析器都是一样的。根据当前栈顶的形状号和输入符号，去查根据当前栈顶的形状号和输入符号，去查LR分析分析表，决议采取什么动作，移进还是归约等。表，决议采取什么动作，移进还是归约等。分析表分析表 - 规定了动作和形状的转换。规定了动作和形状的转换。不同的文法，分析表将不同不同的文法，分析表将不同同一个文法采用不同的同一个文法采用不同的LR分析器，分析表也将不分析器，分析表也将不同。同。分析栈分析栈 - 文法符号栈和形状栈文法符号栈和形状栈它们在移进和归约的过程中是同步的，栈中元素一它们在移进和归约的过程中是同步的，栈中元素一样多样多,栈指针用同一个。栈指针用同一个。在普通的移进归约过程中也有文法
11、符号栈，但没在普通的移进归约过程中也有文法符号栈，但没有形状栈。有形状栈。几个概念几个概念LR文法文法: 对于一个文法，假设可以构造一张分对于一个文法，假设可以构造一张分析表，使得它的每个入口均是独一确定的，那析表，使得它的每个入口均是独一确定的，那么我们将把这个文法称为么我们将把这个文法称为LR文法。文法。LR(k)文法文法: 一个文法假设能用一个每步最多向一个文法假设能用一个每步最多向前检查前检查k个输入符号的个输入符号的LR分析器进展分析，那分析器进展分析，那么这个文法就称为么这个文法就称为LR(k)文法。文法。 非非LR构造构造知文法知文法 G : S iCtS | iCtSeS假定一
12、个自下而上分析器，它处于如下情形假定一个自下而上分析器，它处于如下情形:栈栈输入输入 iCtSe#问题问题: : 无法确定无法确定iCtSiCtS能否为句柄能否为句柄? ? 或者移进或者移进e e，或者将，或者将iCtSiCtS归约为归约为S S结论结论: : 任何二义文法都不是任何二义文法都不是LR(K)LR(K)文法文法知文法知文法 G : 1语句语句 i参数表参数表2语句语句 表达式表达式 := 表达式表达式3参数表参数表 参数表，参数参数表，参数4参数表参数表 参数参数5参数参数 i6表达式表达式 i表达式表表达式表7表达式表达式 i8表达式表表达式表 表达式表，表达式表达式表，表达式
13、9表达式表表达式表 表达式表达式 数组元素援用和过程调用的表示方式一样数组元素援用和过程调用的表示方式一样, ,如如A(I,J)A(I,J)经词法分析后得到经词法分析后得到i(i,i)i(i,i)栈栈输入输入 i(i, i)#对于串对于串 i ( i , i )，当它处于如下情形，当它处于如下情形:那么栈顶的那么栈顶的 i i 应该按照应该按照 产生式产生式(5)(5)归约归约, ,还是还是按照产生式按照产生式(7)(7)归约归约一种处理方法一种处理方法: : 将产生式将产生式(1)(1)中的中的 i i 改为改为prociproci，让词法分析查询符号表，让词法分析查询符号表, ,识别识别i i是过程是过程名还是数组名。当为过程名时，变成名还是数组名。当为过程名时，变成 proci(i, i)#
