编译原理531LR分析器ppt课件.ppt

第五章第五章 语法分析语法分析5.1 自下而上分析根本问题自下而上分析根本问题5.2 算符优先分析算符优先分析 5.3 LR分析分析5.4 YACC5.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 二义文法的运用二义文法的运用课前思索课前思索•自下而上分析是一种自下而上分析是一种___________过程过程•自下而上分析法的关键问题是在分析过程中自下而上分析法的关键问题是在分析过程中___________________•算符优先分析法如何确定可归约串？算符优先分析法如何确定可归约串？•什么是规范推导和规范归约？什么是规范推导和规范归约？ 它们之间有什么关系？它们之间有什么关系？•规范归约过程是当分析的栈顶符号串构成规范归约过程是当分析的栈顶符号串构成_______时就采取归约动作时就采取归约动作移进移进- -归约归约句柄句柄如何确定可归约串如何确定可归约串LR(K)•L : 自左向右扫描自左向右扫描•R : 逆向完成最右推导逆向完成最右推导 (规范归约规范归约)•K : 向右查看输入串符号的个数向右查看输入串符号的个数 (K省略时省略时, 表示表示K等于等于1)LR分析过程是规范归约过程分析过程是规范归约过程四种四种LR分析器分析器 •LR(0) •SLR(1)•LR(1)•LALR(1)LR方法的根本思想方法的根本思想•LR方法的关键方法的关键: 确定句柄确定句柄•历史历史: 已移进和归约出的整个符号串已移进和归约出的整个符号串 •展望展望: 根据所用的产生式推测未来能够根据所用的产生式推测未来能够碰到的输入符号碰到的输入符号 •现实现实: 当前的输入符号当前的输入符号 •LR分析器的每一步任务都是由栈顶形状和分析器的每一步任务都是由栈顶形状和 现行输入符号所独一决议的。

现行输入符号所独一决议的•一个一个LR分析器本质上是一个分析器本质上是一个DFA 形形状状5.3.1 LR分析器分析器 P100a1a2…ai…an#LR分析表分析表总控程序总控程序输入串：输入串：栈顶栈顶输出输出s0s1…sm形状栈形状栈#x1…xm符号栈符号栈分析栈分析栈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  i3...3.3102...2.91...8 .accr2.r4r6...r1r3r5..r2r4.r6..S11r1r3r5S4...S4.S4S4..S7r4.r6...S7r3r5.S6r2r4.r6...S6r1r3r5S5...S5.S5S501234567891011FTE#)(*+i形状形状GOTO[s,A]ACTION[s,a]表达式文法的表达式文法的LRLR分析表分析表 p101 p101将将LR分析器的任务过程看成三元式的变化过程分析器的任务过程看成三元式的变化过程形状栈形状栈符号栈符号栈输入串输入串分析开场时的初始三元式为分析开场时的初始三元式为: (s0 , ＃，＃， ala2...an＃〕＃〕分析过程每步的结果可表示为分析过程每步的结果可表示为 (s0s1...sm，，＃＃X1X2...Xm，，aiai+1…an＃〕＃〕分析器的下一步动作由分析器的下一步动作由sm和和 ai所独一决议所独一决议 栈顶栈顶栈顶栈顶现行输入符号现行输入符号Action[sm,ai]: 4Action[sm,ai]: 4种能够动作种能够动作(1) 移进移进 – sj(2) 归约归约 – rm(3) 接受接受 – acc(4) 报错报错 – 空白空白 / ‘出错出错’ / ‘error’(1) 移进移进 – sjpush s ;push ai;状状态栈符号符号栈输入串入串s0s1...sm＃＃X1X2...Xmaiai+1…an＃＃s0s1...sm＃＃X1X2...Xmai+1…an＃＃s = GOTO[ sm，，ai ] = jsaij(2) 归约归约 - rmpop 文法符号栈文法符号栈 r次次pop 形状栈形状栈 r次次 push A 查表查表 s = GOTO[sm-r , A] push s用第用第m条产生式条产生式A→β归约归约. |β| =r状状态栈符号符号栈输入串入串s0s1...sm-r…sm＃＃X1X2...Xm-r …Xmaiai+1…an＃＃s0s1...sm-r＃＃X1X2...Xm-raiai+1…an＃＃As步骤步骤 状态栈状态栈符号栈符号栈剩余输入串剩余输入串动作动作10#i*i+i#2345…例例5.7 5.7 对对i*i+i# i*i+i# 进展移进进展移进- -归约分析归约分析 P102 P102 移进移进 S50 0#*i+i# 归约归约 r6 FiG:(1) E  E+T (2) E  T(3) T  T*F (4) T  F(5) F  (E)(6) F  i0#*i+i#F3归约归约 r4 TF0#*i+i#T25 5i移进移进 S7027 7#T* *i+i# 移进移进 S5步骤步骤状态栈状态栈符号栈符号栈剩余输入串剩余输入串动作动作10#i*i+i# 移进 S5 205#i*i+i# 归约 r6 Fi 303#F*i+i# 归约 r4 TF402#T*i+i# 移进 S75027#T*i+i# 移进 S560275#T*i+i# 归约 r6 Fi7027 10#T*F+i# 归约 r3 TT*F802#T+i# 归约 r2 ET901#E+i# 移进 S610016#E+i# 移进 S5110165#E+i# 归约 r6 Fi120163#E+F# 归约 r4 TF130169#E+T# 归约 r1 EE+T1401#E# 接受 accp102补充：补充：LR分析算法分析算法 * 形状栈中放入形状形状栈中放入形状0 ; 文法符号栈中放入＃文法符号栈中放入＃ip指向输入串指向输入串w的第一个符号的第一个符号Sm为栈顶形状为栈顶形状 ; a是是ip指向的符号指向的符号 Repeat… //见下页见下页end .Repeat if ACTION[Sm,a]=Sjbegin PUSH j, a 　　　　　　 ip 前进前进 endelse if ACTION[Sm,a]=rj // A→β begin pop |β| 项项//当前栈顶形状为当前栈顶形状为Skpush GOTO[Sk, A] , A endelse if ACTION[Sm, a]=accreturn (胜利〕胜利〕else errorend .LR分析器小结分析器小结•总控程序总控程序 - 对一切的对一切的LR分析器都是一样的。

分析器都是一样的•根据当前栈顶的形状号和输入符号，去查根据当前栈顶的形状号和输入符号，去查LR分析分析表，决议采取什么动作，移进还是归约等表，决议采取什么动作，移进还是归约等•分析表分析表 - 规定了动作和形状的转换规定了动作和形状的转换•不同的文法，分析表将不同不同的文法，分析表将不同•同一个文法采用不同的同一个文法采用不同的LR分析器，分析表也将不分析器，分析表也将不同•分析栈分析栈 - 文法符号栈和形状栈文法符号栈和形状栈•它们在移进和归约的过程中是同步的，栈中元素一它们在移进和归约的过程中是同步的，栈中元素一样多样多,栈指针用同一个栈指针用同一个•在普通的移进－归约过程中也有文法符号栈，但没在普通的移进－归约过程中也有文法符号栈，但没有形状栈有形状栈几个概念几个概念•LR文法文法: 对于一个文法，假设可以构造一张分对于一个文法，假设可以构造一张分析表，使得它的每个入口均是独一确定的，那析表，使得它的每个入口均是独一确定的，那么我们将把这个文法称为么我们将把这个文法称为LR文法•LR(k)文法文法: 一个文法假设能用一个每步最多向一个文法假设能用一个每步最多向前检查前检查k个输入符号的个输入符号的LR分析器进展分析，那分析器进展分析，那么这个文法就称为么这个文法就称为LR(k)文法。

文法 非非LR构造构造知文法知文法 G : S  iCtS | iCtSeS假定一个自下而上分析器，它处于如下情形假定一个自下而上分析器，它处于如下情形:栈栈输入输入… iCtSe…#问题问题: : 无法确定无法确定iCtSiCtS能否为句柄能否为句柄? ? 或者移进或者移进e e，或者将，或者将iCtSiCtS归约为归约为S S结论结论: : 任何二义文法都不是任何二义文法都不是LR(K)LR(K)文法文法知文法知文法 G : 〔〔1〕语句〕语句  i〔参数表〕〔参数表〕〔〔2〕语句〕语句  表达式表达式 := 表达式表达式〔〔3〕参数表〕参数表  参数表，参数参数表，参数〔〔4〕参数表〕参数表  参数参数〔〔5〕参数〕参数  i〔〔6〕表达式〕表达式  i〔表达式表〕〔表达式表〕〔〔7〕表达式〕表达式  i〔〔8〕表达式表〕表达式表  表达式表，表达式表达式表，表达式〔〔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)…#。