天津大学编译原理讲义-Part5自底向上的语法分析

Part5语法分析授课：胡静自底向上的语法分析概述目录自底向上语法分析是一个更加强大的分析技术。LR文法——比LL描述能力更强构造程序的最右推导几乎所有的程序设计语言都是左递归的更加容易描述程序设计语言的语法。移进-归约分析LR文法的语法分析器语法生成器的自动生成器(e.g.,yacc)自顶向下vs自底向上自底向上：只需要对当前的输入给出足够的语法树的部分就行自底向上的语法分析较常用的自底向上语法分析法移动－归约分析法用栈实现移动归约分析最易于实现的移动归约分析法算符优先分析法算符优先分析法定义、优先分析表的确定、优先函数的定义使用算符优先关系进行分析算符优先分析中的错误恢复最一般的移动归约分析方法LR分析法自底向上语法分析概述自底向上的语法分析方法，也称为移动归约分析法。最易于实现的一种移动归约分析方法，叫做算符优先分析法，而更一般的移动归约分析方法叫做LR分析法，LR分析法可以用作许多自动的语法分析器的生成器。移动归约分析法为输入串构造分析数时是从叶结点（底端）开始，向根结点（顶端）前进。我们可以把该过程看成是把输入串ω“归约”成文法开始符号的过程。在每一步归约中，如果一个子串和某个产生式的右部匹配，则用该产生式的左部符号代替该子串。如果每一步都能恰当的选择子串，我们就可以得到最右推导的逆过程。移进-归约分析分析就是移进和归约动作的序列移进：将当前扫描的token移动到堆栈中。归约：将栈顶的符号串β移除，用非终结符X代替，这对应着产生式A→β(popβ,pushA)短语、直接短语、句柄的定义：文法G[S]，αβδ是文法G的一个句型，S=*αAδ且A=+β则称β是句型αβδ相对于非终结符A的短语。若有Aβ则称β是句型αβδ相对于该规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。用子树解释短语，直接短语，句柄:短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。EE+TE+T*FE+T*a3E+F*a3E+a2*a3T+a2*a3F+a2*a3E+TT*F,E+T*Fa3,T*a3,E+T*a3a3,F,F*a3,E+F*a3a3,a2,a2*a3,E+a2*a3a3,a2,T,a2*a3,T+a2*a3a3,a2,F,a2*a3,F+a2*a3a1,a2,a3,a2*a3a1+a2*a3EE+TTFa1T*FFa2a3a1+a2*a3短语移动归约分析法相关概念规范归约文法的最右推导为规范推导，自底向上分析是自顶向下最右推导的逆过程，叫规范归约句柄直观来看：一个符号串的“句柄”是和一个产生式右部匹配的子串，而且把它归约到该产生式左部的非终结符代表了最右推导逆过程的一步。形式定义：右句型（最右推导可得到的句型）γ的句柄是一个产生式A→β以及γ的一个位置，在该位置可以找到串β，而且用A代替β可以得到γ的最右推导的前一个右句型对于有二义性的文法而言，由于最右推导不一定，则句柄不一定唯一。只有当文法没有二义性时，每个右句型才只有一个句柄。句柄剪裁通过“剪裁句柄”可以得到最右推导的逆过程在归约过程中用到的产生式序列的逆序就是输入串的最右推导(1)SaABe(2)Ab(3)AAbc(4)BdS＝aABe＝aAde＝aAbcde＝abbcde步骤符号栈输入符号串动作1$abbcde$移动2$abbcde$移动3$abbcde$归约(2)4$aAbcde$移动5$aAbcde$移动6$aAbcde$归约（3）7$aAde$移动8$aAde$归约(4)9$aABe$移进10$aABe$归约(1)11$S$接受移动归约分析中需要解决的问题定位右句型中将要归约的子串（可归约串）在用堆栈实现时，这个子串总是在栈顶。语法分析器不需要深入到栈中去寻找句柄选择产生式对选定的串进行归约如果选定的子串是多个产生式的右部，要确定选择哪个产生式进行归约移动归约分析过程中的冲突根据栈中的内容和下一个输入符号不能决定是移动还是归约（移动-归约冲突）不能决定按哪一个产生式进行归约（归约-归约冲突）算符优先分析法算符优先分析法算符文法的定义：所有产生式的右部都不是ε或两个相邻的非终结符设有一个文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法(OperatorGrammar)也称OG文法.算符优先文法的特点：一旦我们构造了算符优先语法分析器，就可以忽略原来的文法，栈中的非终结符仅仅作为与这些非终结符相关的属性的占位符难以处理像减号这样有不同优先级的符号由于分析的语言的文法和算符优先语法分析器本身的关系不是很紧密，所以不能肯定语法分析器接受的就是所期望的语言算符优先关系的定义a的优先级低于bab：文法中有形如A→…aB...的产生式而B+b…或B+Cb…a的优先级等于ba=b：文法中有形如A→…ab…或者A→…aBb…的产生式a的优先级高于bab：文法中有形如A…Bb…的产生式,而B+…a或B+…aC算符的优先关系是有序的如果ab，不能推出ba如果ab，有可能ba如果ab，bc，不一定ac算符优先关系定义（续1）ab，则存在语法子树如下A…aPB…其中，δ为ε或者C，a和b不在同一个句柄中，b先被归约δb…算符优先关系定义（续2）a=b，则存在语法子树如下A…aδb…其中，δ为ε或者B，a和b在同一个句柄中，同时被归约，算符优先关系定义（续3）ab，则存在语法子树如下其中，δ为ε或者C，a和b不在同一个句柄中，a先被归约A…Bb…Pδa…最左素短语一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串Njaj…NiaiNi+1，aj-1ajaj=aj+1,…,ai-1=aiaiai+1使用算符优先关系算符优先关系主要用于界定右句型的句柄标记句柄的左端；=出现在句柄的内部；标记句柄的右端。发现句柄的过程：从左端开始扫描串，直到遇到第一个为止。向左扫描，跳过所有的=，直到遇到一个为止。句柄包括从上一步遇到的右部到第一个左部之间的所有符号，包括介于期间或者两边的非终结符非终结符的处理因为非终结符不能影响语法分析，所以不需要区分它们，于是只用一个占位符来代替它们算符优先分析算法算法的主体思想用栈存储已经看到的输入符号，用优先关系指导移动归约语法分析器的动作如果栈顶的终结符和下一个输入符之间的优先关系是或=，则语法分析器移动，表示还没有发现句柄的右端如果是关系，就调用归约算法描述输入：输入字符串ω和优先关系表输出：如果ω是语法产生的一个句子，则输出其用来归约的产生式；如果有错误，则转入错误处理规范归约和算符优先归约句型#i+i#的规范归约过程步骤符号栈剩余输入串句柄归约用产生式1#i+i#2#i+i#iPi4#F+i#FTF5#T+i#TET6#E+i#7#E+i#8#E+i#iPi10#E+F#FTF11#E+T#E+TEE+T12#E#接受E’=#E#=#E+T#=#E+F#=#E+i#=#T+i#=#F+i#=#i+i#规范归约和算符优先归约句型#i+i#的算符优先归约过程步骤栈优先关系当前符号剩余符号串动作1#i+i#移进2#i+i#归约3#P+i#移进3#P+i#移进4#P+i#归约4#P+P#归约4#E=#接受+i#+i#=算符优先分析法优缺点由于算符优先分析并未对文法的非终结符定义优先关系，所以就无法发现由单个非终结符组成的“可归约串”。也就是说，在算符优先归约过程中，我们无法用那些右部仅含一个非终结符的产生式（称为单非产生式，如P→Q）进行归约。这样，算符优先分析比规范归约要快很多。这既是算符优先分析的优点，也是它的缺点。忽略非终结符在归约过程中的作用，存在某种危险性，可能导致把本来不成句子的输入串误认为是句子。优先函数优先函数的计算方法1.f(a)g(b)，如果ab2.f(a)=g(b)，如果a=b3.f(a)g(b)，如果ab优先函数的问题使得优先关系表中的空白项是模糊的使得错误的发现被推迟优先关系表的存储方式矩阵表示：准确直观；需要大量内存空间(n+1)2优先函数：需要内存空间小2(n+1)；不利于出错处理优先函数的构造算法输入：算符优先表输出：表示输入矩阵的优先函数或指出它不存在方法：为每个终结符（包括#）创建fa和ga。并以其作为结点，画出2n个结点如果ab或者a=b，则画一条从fa到gb的箭弧如果ab或者a=b，则画一条从gb到fa的箭弧如果构造的图中有环路，则不存在优先函数；如果没有环路，则将f(a)设为从fa开始的最长路径的长度；g(a)为从ga开始的最长路径的长度。检查是否一致！实例说明i*+$i*+$=figig*f*f+g+g#f#i*+$fg45432100检查是否一致！算符优先分析中的错误恢复算符优先分析器能发现的语法错误如果栈顶的终结符和当前输入之间没有优先关系（如果用优先函数存储，这个错误不能发现）如果发现句柄，但句柄不是任何产生式的右部归约时的错误处理给出相应的具有描述性的出错信息试图通过插入、删除来获得句柄一个加入了出错处理的优先矩阵E1：缺少整个表达式把id插入输入字符串中输出诊断信息MissingoperandE2：表达式以右括号开始从输入中删除)输出诊断信息UnbalancedrightparenthesisE3：id/)后面跟id/(把+插入输入字符串输出诊断信息MissingoperatorE4：表达式以左括号结束从栈中弹出(输出诊断信息Missingrightparenthesisid()$idE3E3(=E4)E3E3$E2E1LR分析法LR语法分析器概述LR(k)语法分析器适用于一大类上下文无关文法的语法分析。K省略时，假设k是1。L指的是从左向右扫描输入字符串R指的是构造最右推导的逆过程k指的是在决定语法分析动作时需要向前看的符号个数构造LR分析表的三种方法简单LR方法（SLR），最容易实现，功能最弱规范LR方法，功能最强，代价最高向前看的LR方法（LALR），其功能和代价介于前两者之间LR语法分析器的优缺点LR分析富有吸引力的原因有以下几点：LR语法分析器能识别几乎所有能用上下文无关文法描述的程序设计语言的结构。LR分析法是已知的最一般的无回溯移动归约语法分析法，而且可以和其他移动归约分析一样被有效地实现。LR分析法分析的文法类是预测分析法能分析的文法类的真超集。在自左向右扫描输入符号串时，LR语法分析器能及时发现语法错误。这种分析方法的主要缺点是，对典型的程序设计语言文法，手工构造LR语法分析器的工作量太大，需要专门的工具。(1)SaABe(2)Ab(3)AAbc(4)BdS＝aABe＝aAde＝aAbcde＝abbcde步骤符号栈输入符号串动作1$abbcde$移动2$abbcde$移动3$abbcde$归约(2)4$aAbcde$移动5$aAbcde$移动6$aAbcde$归约（3）7$aAde$移动8$aAde$归约(4)9$aABe$移进10$aABe$归约(1)11$S$接受LR语法分析算法LR分析的基本思想是，在规范归约过程中，一方面记住已移进和归约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。LR语法分析器的结构一个LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。栈LR分析程序actiongoto输出输