Part5语法分析自底向上的语法分析1解读.docx
- 文档编号:16243063
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:27
- 大小:51.49KB
Part5语法分析自底向上的语法分析1解读.docx
《Part5语法分析自底向上的语法分析1解读.docx》由会员分享,可在线阅读,更多相关《Part5语法分析自底向上的语法分析1解读.docx(27页珍藏版)》请在冰点文库上搜索。
Part5语法分析自底向上的语法分析1解读
Part5.语法分析——自底向上的语法分析
(1)
作业
1.对于文法
S→AA→BAA→εB→aBB→b
(1)构造LR
(1)分析表;
(2)给出用LR
(1)分析表对输入符号串abab的分析过程。
2.设已给文法
(1)G1[S]:
S→Aa|bAc|dc|bda
A→d
(2)G2[S]:
S→Aa|bAc|Bc|bBa
A→d
B→d
试证明:
G1是LALR
(1)文法但不是SLR
(1)文法;G2是LR
(1)文法但不是LALR
(1)文法。
3.试为如下的文法构造LALR
(1)分析表。
E→E+T|TT→TF|FF→F*|a|b
4.给出下面二义文法的语法分析表:
E→EsubEsupE
E→EsubE
E→EsupE
E→{E}
E→c
1.1自底向上分析的基本问题
自底向上的语法分析方法,也称为移动归约分析法。
最易于实现的一种移动归约分析方法,叫做算符优先分析法,而更一般的移动归约分析方法叫做LR分析法,LR分析法可以用作许多自动的语法分析器的生成器。
移动归约分析法为输入串构造分析数时是从叶结点(底端)开始,向根结点(顶端)前进。
我们可以把该过程看成是把输入串ω“归约”成文法开始符号的过程。
在每一步归约中,如果一个子串和某个产生式的右部匹配,则用该产生式的左部符号代替该子串。
如果每一步都能恰当的选择子串,我们就可以得到最右推导的逆过程。
在实现上,就是说用一个寄存符号的先进后出栈,把输入符号一个一个的移进到栈里,当栈顶形成某个产生式的一个候选式时,即把栈顶的这一部分替换(归约)为该产生式的左部符号。
所有不同的自底向上分析法的一个共同特点就是,便输入单词符号(移进符号栈),边归约。
也就是从左到右移进输入串的过程中,一旦发现栈顶符号呈现可归约串就立即进行归约。
1.1.1句柄和归约
非形式的,一个符号串的“句柄”是和一个产生式右部匹配的子串,而且把它归约到该产生式左部的非终结符代表了最右推导逆过程的一步。
形式的说,右句型(最右推导可得到的句型)γ的句柄是一个产生式A→β以及γ的一个位置,在该位置可以找到串β,而且用A代替β可以得到γ的最右推导的前一个右句型,即如果S=>*αAω=>αβω,其中ω全部由终结符构成,那么我们就说β是句型αβω的句柄。
在αβω中,把β归约到A可以想象成“剪裁句柄”,即把A的子结点从分析树中删除。
通过“剪裁句柄”可以得到最右推导的逆过程。
每一次的归约,都是把栈顶的一串符号用某个产生式的左部符号来代替。
栈顶这样一串符号可以叫做“可归约串”,当然,在后面讲到不同的自底向上归约方法是,对它的称呼也略有不同。
1.1.2规范归约简述
假定α是文法G的一个句子,我们称序列:
αnαn-1,…,α0
是α的一个规范归约,如果次序列满足
(1)αn=α;
(2)α0为文法的开始符号,即α0=S
(3)对任何i,0
可以看出来,规范归约是关于α的一个最右推导的逆过程。
因此,规范归约也称最左规约。
注意句柄的这一“最左”特征,这一点对于移进归约来说是很重要的。
因为,句柄的“最左”性和符号栈的栈顶两者是相关的。
对于规范句型来说,句柄的后面不会出现非终结符(即,句柄的后面只能出现终结符)。
基于这一点,我们可以使用句柄来刻画移进归约过程的“可归约串”。
因此,移进归约的实质是,当发现栈顶呈现句柄时就用相应的产生式的左部符号进行替换。
1.1.3用符号栈实现移动规约分析
基于上述讨论的分析方法,有两个问题必须要解决:
第一个问题是定为右句型中将要归约的子串;第二个问题是,如果这个子串是多个产生式的右部,如何确定使用哪个产生式。
前面讲到的例子中,我们可以发现,移动归约语法分析器的基本动作就是移动和归约,但实际上有四种可能的动作:
移动、归约、接受、出错。
(1)移动:
把下一个输入符号移动到栈顶
(2)归约:
语法分析器知道句柄的右端已在栈顶,它必须在栈中确定句柄的左端,选择正确的非终结符替代句柄。
(3)接收:
语法分析宣告分析成功
(4)出错:
语法分析器发现了一个语法错误,并调用错误恢复程序进行错误处理。
有一个重要的事实说明在移动归约分析中使用栈是有道理的:
句柄最终总是会出现在栈顶,而不是栈的里面,语法分析器不需要深入到栈中去寻找句柄。
1.1.4移动归约分析过程中的冲突
有些上下文无关文法不能使用移动归约分析方法进行分析。
这种文法的每一个移动归约语法分析器会形成这样的格局:
根据栈中的内容和下一个输入符号不能决定是移动还是归约(移动-归约冲突);或不能决定按哪一个产生式进行归约(归约-归约冲突)。
二义性文法肯定不是LR文法
1.2算符优先分析法
算法优先分析法是一种简单直观、广为使用的自底向上分析法,特别有利于表达式分析,宜于手工实现。
算符优先分析过程是自底向上的归约过程,但这种归约未必是严格的最左归约。
也就是说,算符优先分析法不是一个规范归约法。
算符优先文法就是对于一个文法G,其所有产生式的右部都不是ε或两个相邻的非终结符,也就是说,如果G中没有形如A→…BC…的产生式,其中B和C为非终结符,则称G为算符文法(OperatorGrammar)也称OG文法。
算符优先文法优先关系的定义:
(1)a
文法中有形如A→…aB...的产生式而B+b…或B+Cb…
(2)a=b:
文法中有形如A→…ab…或者A→…aBb…的产生式
(3)a>b:
文法中有形如A…Bb…的产生式,而B+…a或B+…aC
如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三种关系之一:
a=b,ab
则称G是一个算符优先文法。
需要注意的是这三个关系不同于数学中的“<”“=”和“>”。
例如,如果a>b,不能推出bb,有可能b>a;如果a>b,b>c,不一定a>c。
1.2.1算符优先分析算法
再算符优先文法中,为了刻画什么是“可归约串”,将引入文法句型的“最左素短语”这个概念。
所谓素短语是指这样的一个短语,它至少含有一个终结符,并且,除它自身之外不再含有任何更小的素短语。
所谓最左素短语就是处于句型最左边的那个素短语。
现在考虑算符优先文法,我们把句型(括在两个#之间)的一般形式写成:
#N1a1N2a2…NnanNn+1#
其中,每一个ai都是终结符,Ni是可有可无的非终结符。
换言之,句型中含有n个终结符,任何两个终结符中间顶多只有一个非终结符。
必须注意的是,任何算符文法的句型都具有这种形式。
一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串Njaj…NiaiNi+1,
vaj-1 vaj=aj+1,…,ai-1=ai vai>ai+1 应用上面的定义,使用下面的过程发现句柄: 1.从左端开始扫描串,直到遇到第一个>为止。 2.向左扫描,跳过所有=,直到遇到一个<为止。 3.句柄包括从第二步遇到的<的右部到第一个>的左部之间的所有符号 为了和定理的叙述相适应,我们现在仅使用一个符号栈S,既用它寄存终结符,也用它寄存非终结符。 下面的分析算法就是根据这个定理构造出来的,其中k代表符号栈S的使用深度 k: =1;S[k]: =‘#’; REPEAT 把下一个输入符号读进a中; IFs[k]∈VTTHENj: =kELSEj: =k-1; WHILES[j]>aDO BEGIN REPEAT Q: =S[j]; IFS[j-1]∈VTTHENj: =j-1ELSEj: =j-2; UNTILS[j] 把S[j+1]…S[k]归约为某个N; k: =j+1; S[k]=N ENDOFWHILE IFS[j] BEGINk: =k+1;S[k]: =aEND ELSEERROR/*调用出错诊察程序*/ UNTILa=’#’ 上述算法中,如果发现j减1后的值小于等于0,则意味着输入串有错。 在正确的情况下,算法工作完毕时,符号栈S应该呈现: #N#。 注意,我们并没有指出应把所找到的最左素短语规约到哪个非终结符号‘N’。 N是指那样一个产生式的左部符号,此产生式的右部和S[j+1]…S[k]构成如下一一对应关系: 自左至右,终结符对终结符,非终结符对非终结符,而且对应的终结符相同。 由于非终结符对归约没有影响,因此,非终结符根本就可以不进符号栈S。 就像前面指出的,算符优先分析一般不等价于规范归约。 由于算符优先分析并未对文法的非终结符定义优先关系,所以就无法发现由单个非终结符组成的“可归约串”。 也就是说,在算符优先归约过程中,我们无法用那些右部仅含一个非终结符的产生式(称为单非产生式,如P→Q)进行归约。 这样,算符优先分析比规范归约要快很多,因为算符优先分析跳过了所有单非产生式所对应的归约步骤。 这既是算符优先分析的优点,也是它的缺点。 因为,忽略非终结符在归约过程中的作用,存在某种危险性,可能导致把本来不成句子的输入串误认为是句子。 1.2.2优先函数 在实际实现算符优先分析算法时,一般不用优先表,而是采用两个优先函数f和g。 f和g把终结符映射为整数。 对于符号a和b,选择f和g以满足: (1)f(a) (2)f(a)=g(b),如果a=b (3)f(a)>g(b),如果a>b 使用优先函数有两方面的优点: 便于做比较运算,并且节省存储空间,因为优先关系表占用的存储量比较大。 其缺点是,原先不存在优先关系的两个终结符,由于与自然数相对应,变成可比较的了。 因而,可能会掩盖输入串的某些错误。 下面介绍一个从优先关系表构造优先函数的办法。 注意,对应一个优先关系表的优先函数f和g不是唯一的。 也有许多优先函数表不存在对应的优先函数。 如果优先函数存在,那么从优先表构造优先函数的一个简单方法是: (1)为每个终结符(包括#)创建fa和ga。 并以其作为结点,画出2n个结点 (2)如果a>b或者a=b,则画一条从fa到gb的箭弧 (3)如果a (4)如果构造的图中有环路,则不存在优先函数;如果没有环路,则将f(a)设为从fa开始的最长路径的长度;g(a)为从ga开始的最长路径的长度。 (5)检查所构造出来的函数f和g,看它们同原来的关系表是否有矛盾。 1.2.3算符优先分析中的错误恢复 算符优先分析器能发现的语法错误: v如果栈顶的终结符和当前输入之间没有优先关系(如果用优先函数存储,这个错误不能发现) v如果发现句柄,但句柄不是任何产生式的右部 归约时的错误处理 v给出相应的具有描述性的出错信息 v试图通过插入、删除来获得句柄 可能的错误处理示例 vE1: 缺少整个表达式: ⏹把id插入输入字符串中; ⏹输出诊断信息Missingoperand vE2: 表达式以右括号开始: ⏹从输入中删除) ⏹输出诊断信息Unbalancedrightparenthesis vE3: id/)后面跟id/( ⏹把+插入输入字符串 ⏹输出诊断信息Missingoperator vE4: 表达式以左括号结束 ⏹从栈中弹出( ⏹输出诊断信息Missingrightparenthesis Part5.语法分析——自底向上的语法分析 (2) 教学目标: LR分析的基本概念、LR(0)分析法 教学重点: LR语法分析器、LR语法分析算法 教学难点: LR(0)项目集族和分析表构造、LR(0)分析算法 1.3LR语法分析器 本节介绍一个有效的自底向上的分析技术,可以用于一大类上下文无关文法的语法分析。 这种技术叫做LR(k)分析法,其中L表示从左到右扫描输入串,R表示构造一个最右推导的逆过程,k指的是在决定语法分析动作时需要向前看的符号个数。 (k)省略时,假设k是1。 LR分析富有吸引力的原因有以下几点: vLR语法分析器能识别几乎所有能用上下文无关文法描述的程序设计语言的结构。 vLR分析法是已知的最一般的无回溯移动归约语法分析法,而且可以和其他移动归约分析一样被有效地实现。 vLR分析法分析的文法类是预测分析法能分析的文法类的真超集。 v在自左向右扫描输入符号串时,LR语法分析器能及时发现语法错误。 这种分析方法的主要缺点是,对典型的程序设计语言文法,手工构造LR语法分析器的工作量太大,需要专门的工具。 在讨论完LR语法分析器的操作后,我们将给出三种构造LR分析表的方法。 第一种方法称为简单LR方法(简称SLR),它最容易实现,但功能也最弱。 对某些文法,另外两种方法能成功的产生语法分析表,但用它会失败。 第二种方法称为规范的LR分析法,它的功能最强,代价也最高。 第三种方法叫做向前看的LR分析法(简称LALR),其功能和代价介于前两者之间。 LALR方法可用于大多数程序设计语言的文法,并且可以高效的实现。 1.3.1LR语法分析算法 规范归约(最左归约-最右推导的逆过程)的关键问题是寻找句柄。 在一般的“移进-归约”过程中,当一串貌似句柄的符号串呈现于栈顶时,我们有什么方法可以确定他是否为相对于某一个产生式的句柄呢? LR分析的基本思想是,在规范归约过程中,一方面记住已移进和归约出的整个符号串,即记住“历史”,另一方面根据所用的产生式推测未来可能碰到的输入符号,即对未来进行“展望”。 当一串貌似句柄的符号串呈现于分析栈的顶端时,我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号等三方面的材料,来确定栈顶的符号串是否构成相对某一产生式的句柄。 从LR分析方法可以看出,其实现有一定的困难。 作为归约过程的“历史”材料的积累虽不困难(实际上,这些材料都存在分析栈中),但是“展望”材料的汇集却是一件很不容易的事情。 这种困难不是理论上的,而是实际实现上的。 后面所讨论的LR分析方法都是带有一定限制的。 一个LR分析器实质上十一个带先进后出存储器(栈)的确定有限状态自动机。 我们将把“历史”和“展望”材料综合的抽象成某些“状态”,存放在栈里。 栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。 LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一确定的。 为了有助于明确归约手续,我们把已归约出的文法符号串也同时放在栈里。 由此,可以看到栈的结构如下: 栈的每一项内容包括状态S和文法符号X两部分。 (S0,#)为分析开始前预先放到栈里的初始状态和句子括号(#句子#)。 栈顶状态为Sm,符号串X1X2…Xm是至今已移进归约出的部分。 LR分析器模型如下图所示: LR分析器的核心部分是一张分析表。 这张分析表包括两部分,一个是“动作”(action)表,一个是“状态转移”(goto)表。 它们都是二维数组。 ACTION[s,a]规定了当前状态s面临输入符号a时应采取什么动作。 GOTO[s,X]规定了状态s面对文法符号X(终结符或非终结符)时下一个状态是什么。 显然GOTO[s,X]定义了一个以文法符号为字母表DFA。 每一项ACTION[s,a]所规定的动作不外是下述四种可能之一。 (1)移进: 把(s,a)的下一个状态s’=GOTO[s,a]和输入符号a推进栈,下一个输入符号变成现行输入符号 (2)归约: 指用某一个产生式A→β进行归约。 假若β的长度为r,归约的动作是A,去除栈顶的r个项,使状态Sm-r变成栈顶状态,然后把(Sm-r,A)的下一个状态s’=GOTO[Sm-r,A]和文法符号A推进栈。 归约动作不改变现行输入行。 执行归约动作意味着β(=Xm-r+1…Xm)已经呈现于栈顶而且是一个相对于A的句柄。 (3)接受: 宣布分析成功,停止分析器的工作。 (4)报错: 发现源程序含有错误,调用出错处理程序。 LR分析器的总控程序本身的的工作是非常简单的,任何一步动作都只需按照栈顶状态s和现行输入符号a执行ACTION[s,a]所规定的动作。 对不同的分析表,总控程序都是一样的工作。 一个LR分析器的工作过程可以看成是栈里的状态序列、已归约串和输入串所构成的三元式的变化过程。 v分析开始时的初始三元式为(S0,#,a1a2…an#)。 其中S0为分析器的初态;#为句子的左括号;a1a2…an为输入串,其后的#为结束符(句子的右括号)。 分析过程的每步结果可表示为: (S0S1…Sm,#X0X1…Xm,aiai+1…an#) v分析器的下一步动作是由栈顶状态Sm和现行输入符号ai所唯一决定的。 即,执行ACTION[Sm,ai]所规定的动作。 执行之后三元式的变化情形是: (1)若ACTION[Sm,ai]为移进,且s=GOTO[Sm,ai],则三元式变成: (S0S1…SmS,#X0X1…Xmai,ai+1…an#) (2)若ACTION[Sm,ai]={A→β},则按产生式A→β进行归约。 此时三元式变为 (S0S1…Sm-rS,#X0X1…Xm-rA,aiai+1…an#) 此处s=GOTO[Sm-r,A],r为β的长度,β=Xm-r+1…Xm (3)若ACTION[Sm,ai]为“接受”,则三元式不再变化,变化过程终止,宣布分析成功。 (4)若ACTION[Sm,ai]为“报错”,则三元式的变化过程终止,报告错误。 对于一个LR分析器来说,栈顶状态提供了所需的一切“历史”和“展望”信息。 请注意一个非常重要的事实: 如果仅由栈的内容和现实的输入符号就可以识别一个句柄,那么就可以用一个有限自动机自底向上扫描栈的内容和检查现行输入符号来确定呈现于栈顶的句柄是什么(当栈顶呈现一个句柄时)。 实际上,LR分析表的goto函数就是这样一个有限自动机,只是它不需要每次移动都读栈。 显然,上面提到的这种代替我们做扫描的动作不是在栈的形成过程中完成的,也不是总控程序应该完成的动作,它应该是在分析表的构造过程中实现的。 那么如何为给定的文法构造LR语法分析表,就是我们下面要讲述的重点。 给定文法G,如果我们能为G构造出语法分析表,则称G是LR文法。 很多上下文无关文法不是LR文法,但典型的程序设计语言的结构一般都可以避免非LR文法。 直观的,为了使一个文法是LR文法,只要保证句柄出现在栈顶时,自做到右扫描的移动归约分析器能够及时的识别它。 。 LR语法分析器不需要扫描整个栈就可以知道什么时候句柄出现在栈顶。 栈顶的状态符号包含了所需要的一切信息。 如果识别句柄的有穷自动机自底向上读栈中的文法符号,栈顶所存的状态符号正好是这个自动机所进入的状态,于是LR语法分析器从栈顶的状态即可确定它需要从栈中了解的一切。 能够用来帮助LR语法分析器做出移动归约决定的另一个的信息源是下k个输入符号。 我们实际上感兴趣的是k=0或k=1的情况。 这里我们仅讨论k≤1的情况。 LL文法和LR文法之间有明显的区别,LL文法要求每个非终结符的所有候选首字符均不相同,因为预测程序认为,一旦看到首符之后就看准了该用哪一个产生式进行推导。 但LR分析程序只有在看到整个右部所推导的东西之后才认为是看准了归约方向。 因此,LR方法比LL方法更加一般化。 1.3.2LR(0)项目集族和LR(0)分析表的构造 首先讨论一种只概括“历史”资料而不包含推测性“展望”材料的“状态”。 我们希望仅由这种简单状态就能识别呈现在栈顶的某些句柄。 下面讨论的LR(0)项目集就是这样一种简单状态。 相关概念: v前缀: 字的前缀是指该字的任意首部。 例如,字abc的前缀有ε、a、ab、abc。 v活前缀: 指规范句型的一个前缀,这种前缀不含句柄之后任何符号。 之所以称为活前缀,是因为在右边添加一些符号之首,就可以使它称为一个规范句型。 在LR分析工作过程中的任何时候,栈里的文法符号(自栈底而上)X0X1…Xm应该构成活前缀,把输入串的剩余部分配上之后即应成为规范句型。 因此只要输入串的已扫描部分保持可归约成一个活前缀,那就意味着所扫描过的部分没有错误。 对于一个文法G,我们可以构造一个有限自动机,识别G的所有活前缀,在这个基础上,我们将讨论如何将这种自动机变成LR分析表。 对于一个文法G,我们首先要构造一个NFA,它能识别G的所有活前缀。 这个NFA的每一个状态是下面定义的一个“项目”。 文法G的每一个产生式的右部添加一个圆点称为G的一个LR(0)项目(简称项目)。 例如产生式A→XYZ对应有四个项目: A→•XYZ A→X•YZ A→XY•Z A→XYZ• 但是,产生式A→ε只对应一个项目A→•。 在计算机中,每一个项目可以用一对整数表示,第一个整数代表产生式编号,第二个整数指出圆点的位置。 直观上说,一个项目指明了在分析过程的某时刻我们看到产生式多大部分。 例如,上面四项的第一个项目意味着,我们希望能从后面输入串中看到可以从XYZ推出的符号串。 第二个项目意味着,我们已经从输入串中看到能从X推出的符号串,我们希望能进一步看到可以从YZ推出的符号串。 我们可以用项目状态构造一个NFA,用来识别这个文法所有的活前缀。 文法的开始符号S’仅在第一个产生式左部出现。 使用这个事实,我们对文法进行拓广,加入一个新的开始符号S’。 状态之间转换规则依照如下两条: (1)如果状态i和j来自同一个产生式,而且状态j的圆点只落后于状态i的原点一个位置,如状态i为X→X1…Xi-1•Xi…Xn,而状态j为X→X1…Xi•Xi+1…Xn,那么就从状态i画一条标志为Xi的弧到状态j。 (2)假若状态i的圆点之后的那个符号为非终结符,如i为X→α•Aβ,A为非终结符,那么就从状态i画ε弧到所有A→•γ状态。 即,所有这些圆点出现在最左边的A的项目。 (3)NFA的接受状态就是那些圆点出现在最右边的项目。 然后对这个NFA进行确定化,就得到了一个以项目集合为状态的DFA,在这个DFA中,我们对状态进行了重新编号,并且把每个状态所含的项目都列在其中。 构成识别一个文法活前缀的DFA的项目集(状态)的全体称为这个文法的LR(0)项目集规范族。 为了便于叙述,我们用一些专门术语来称呼不同的项目。 凡圆点在最右的项目,如A→α•称为一个“归约项目”。 对文法的开始符号S’的归约项目,如S’→α•称为“接受”项目。 显然“接受”项目是一种特殊的归约项目。 形如A→α•aβ的项目,其中a为终结符,称为“移进”项目。 形如A→α•Bβ的项目,其中B为非终结符,称为“待约”项目。 下面我们用ε-CLOSURE(闭包)的办法来构造一个文法G的LR(0)项目集规范族。 为了使“接受”状态易于识别,我们总把文法G进行拓广。 假定文法G是一个以S为开始符号的文法,我们构造一个文法G’,它包含整个G,但它引进了一个不出现在G中的非终结符S’,并加进一个新产生式S’→S,而这个S’是G’的开始符号。 那么我们称G’是G的拓广文法。 这样,便会有一个仅含项目S’→S•的状态,这就是唯一的“接受”状态。 假定I是文法G’的任一项目集,定义和构造I的闭包CLOSURE(I)的办法是: (1)I的任何项目都属于CLOSURE(I); (2)若A→α•Bβ属于CLOSURE(I),那么,对任何关于B的产生式B→γ,项目B→•γ也属于CLOSURE(I); (3)重复执行上述两步骤直至CLOSURE(I)不再增大为止。 函数GO是一个状态转换函数。 GO(I,X)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Part5 语法分析 向上 解读