part5自底向上的语法分析.pptx

Part5语法分析授课：胡静自底向上的语法分析概述自底向上的语法分析较常用的自底向上语法分析法移动－归约分析法用栈实现移动归约分析最易于实现的移动归约分析法 算符优先分析法算符优先分析法定义、优先分析表的确定、优先函数的定义使用算符优先关系进行分析算符优先分析中的错误恢复最一般的移动归约分析方法LR分析法自底向上语法分析概述自底向上的语法分析方法，也称为移动归约分析法。最易于实现的一种移动归约分析方法，叫做算符优先分析法，而更一般的移动归约分析方法叫做LR分析法，LR分析法可以用作许多自动的语法分析器的生成器。移动归约分析法为输入串构造分析数时是从叶结点（底端）开始，向根结点（顶端）前进。我们可以把该过程看成是把输入串ω“归约”成文法开始符号的过程。在每一步归约中，如果一个子串和某个产生式的右部匹配，则用该产生式的左部符号代替该子串。如果每一步都能恰当的选择子串，我们就可以得到最右推导的逆过程。 移动归约分析法相关概念规范归约文法的最右推导为规范推导，自底向上分析是自顶向下最右推导的逆过程，叫规范归约句柄直观来看：一个符号串的“句柄”是和一个产生式右部匹配的子串，而且把它归约到该产生式左部的非终结符代表了最右推导逆过程的一步。形式定义：右句型（最右推导可得到的句型）γ的句柄是一个产生式A→β以及γ的一个位置，在该位置可以找到串β，而且用A代替β可以得到γ的最右推导的前一个右句型对于有二义性的文法而言，由于最右推导不一定，则句柄不一定唯一。只有当文法没有二义性时，每个右句型才只有一个句柄。句柄剪裁通过“剪裁句柄”可以得到最右推导的逆过程在归约过程中用到的产生式序列的逆序就是输入串的最右推导 (1)S ? aABe (2)A? b (3)A? Abc (4)B? dS＝aABe＝aAde＝aAbcde＝abbcde步骤 符号栈 输入符号串 动作1 $ abbcde$移动2 $a bbcde$移动3 $ab bcde$归约(2)4 $aA bcde$移动5 $aAb cde$移动6 $aAbc de$归约（3）7 $aA de$移动8 $aAd e$归约(4)9 $aAB e$移进10 $aABe $归约(1)11 $S $接受移动归约分析中需要解决的问题定位右句型中将要归约的子串（可归约串）在用堆栈实现时，这个子串总是在栈顶。语法分析器不需要深入到栈中去寻找句柄选择产生式对选定的串进行归约如果选定的子串是多个产生式的右部，要确定选择哪个产生式进行归约移动归约分析过程中的冲突根据栈中的内容和下一个输入符号不能决定是移动还是归约（移动-归约冲突）不能决定按哪一个产生式进行归约（归约-归约冲突）算符优先分析法 算符优先分析法算符文法的定义：所有产生式的右部都不是ε或两个相邻的非终结符设有一个文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法(Operator Grammar)也称OG文法.算符优先文法的特点：一旦我们构造了算符优先语法分析器，就可以忽略原来的文法，栈中的非终结符仅仅作为与这些非终结符相关的属性的占位符难以处理像减号这样有不同优先级的符号由于分析的语言的文法和算符优先语法分析器本身的关系不是很紧密，所以不能肯定语法分析器接受的就是所期望的语言算符优先关系的定义a的优先级低于ba b：文法中有形如A→…aB...的产生式而B?+b…或B?+Cb… a的优先级等于ba = b：文法中有形如A→…ab…或者A→…aBb…的产生式a的优先级高于ba b：文法中有形如A?…Bb…的产生式,而B?+…a或B?+…aC算符的优先关系是有序的如果a b，不能推出b a如果a b，有可能b a如果a b， b c，不一定a c算符优先关系定义（续1）a b，则存在语法子树如下A…aB…Pb…δ其中，δ为ε或者C，a和b不在同一个句柄中，b先被归约算符优先关系定义（续2）a = b，则存在语法子树如下A…aδb…其中，δ为ε或者B，a和b在同一个句柄中，同时被归约，算符优先关系定义（续3）a b，则存在语法子树如下A…Bb…P…aδ其中，δ为ε或者C，a和b不在同一个句柄中，a先被归约最左素短语一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 Njaj…NiaiNi+1，aj-1ajaj=aj+1,…, ai-1=aiaiai+1使用算符优先关系算符优先关系主要用于界定右句型的句柄标记句柄的左端；=出现在句柄的内部；标记句柄的右端。发现句柄的过程：从左端开始扫描串，直到遇到第一个为