语法分析自底向上分析

《语法分析自底向上分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章语法分析——自底向上分析5.1基本问题方法从句子出发，反复利用产生式做归约（用产生式的左部替代右部），逐步构造语法分析树，最后得到文法的开始符号核心寻找句型与句柄的匹配分析方法例5-1：S→aAcBeA→Ab｜bB→d分析过程:abbcde→aAbcde→aAcde→aAcBe→S语法分析树的生成abbcdeAABSA→bA→AbB→dS→aAcBe句柄：最左直接短语短语：设文法Ｇ＝｛ＶT，ＶN，Ｐ，Ｓ｝若Ｓ=*>αＡδ且Ａ=+>β，则称β是句型αβδ相对于非终结符Ａ的短语若Ｓ=*>αＡδ且

2、Ａ=>β，则称β是直接短语。规范归约的定义设α为文法G的句子，称序列αn，...，α1，α0为α的规范归约，其中1)αn=α2)α0=Ｓ（开始符号）3)对每个i(1<=i<=n)，αi-1是将αi中的句柄归约后得到的规范归约规范归约是规范推导(最右推导)的逆过程中心问题是如何寻找和确定一个句型中的句柄各种自底向上分析采用不同的方法确定句柄移进归约分析器id＊id#＋Ｅ#移进归约控制程序产生式序列栈内容+输入缓冲区内容＝#句型#栈输入缓冲区分析器的四种动作1)移进：将下一输入符号移入栈2)归约：用产

3、生式左侧的非终结符替换栈顶的句柄3)接受：分析成功4)出错：出错处理各种自底向上分析方法的控制方法不同例5-2：id+id*id的分析动作栈输入缓冲区1)#id1+id2*id3#2)移进#id1+id2*id3#3)归约E→id#E+id2*id3#4)移进#E+id2*id3#5)移进#E+id2*id3#6)归约E→id#E+E*id3#7)移进#E+E*id3#8)移进#E+E*id3#9)归约E→id#E+E*E#10)归约E→E*E#E+E#11)归约E→E+E#E#12)接受产生式序

4、列表示语法分析树E→idE→idE→idE→E*EE→E+Eid+id*idEEEEE移进归约分析中的冲突文法复杂时出现:1)移进归约冲突例中的6)可以移进id或归约E→E+E2)归约归约冲突存在两个可用的产生式各种分析方法处理冲突的方法不同5.2算符优先分析方法：利用终结符之间的优先关系确定句柄。算符优先关系的定义(终结符之间)a≮ba的优先级低于ba≡ba的优先级等于ba≯ba的优先级高于b算符优先文法如果文法Ｇ中不存在具有相邻非终结符的产生式，则称为算符文法。如果无ε产生式的算符文法Ｇ中，且

5、任意两个终结符之间至多有一种优先关系，则称为算符优先文法。算符优先分析仅适用于算符优先文法。例5-3：表达式文法的算符优先关系E→E+E｜E-E｜E*E｜E/E｜E^E｜(E)｜id存在优先级+≮**≯+id≯+id≯*+≮id*≮idid≯##≮id算符优先关系的使用分析例：id+id*id在输入符号串中插入优先符，形成一组以≮为左端，以≡为中缀，以≯为右端的短语。#≮id≯+≮id≯*≮id≯#对短语进行归约后再次插入优先符#≮E+≮E*E≯##≮E+E≯##E#算符优先分析的实现组成

6、结构移进归约分析器+优先关系表工作框架输入、输出、初态、终态不变分析算法P93参照输入串、优先关系表，完成一组产生式归约，产生语法分析树。id+id*id的分析过程id+id*id#算符优先分析控制器E→idE→idE→idE→E*EE→E+E算符优先关系表#id#E#+E#id+E#E+E#*E+E#id*E+E#E*E+E#E+E#E#算符优先关系表的构造对于任何符号X和Y：若X的运算优先级高于Y，则设X≯Y和Y≮X若X和Y运算优先级相同，且具有左结合性，则设X≯Y和Y≯X;否则设X≮Y和Y≮

7、X设X≮id，id≯X，X≮(，(≮X，)≯X，X≯)，(≡)，X≯#和#≮X算符优先分析小结优点简单、效率高能够处理部分二义性文法缺点文法书写限制大占用内存空间大不规范、存在查不到的语法错误习题：P1332.(2)补充题给出布尔表达式的文法bexprbexprORbexprbexprbexprANDbexprbexprNOTbexprbexpr(bexpr)bexprTRUEbexprFALSE构造该文法的算符优先关系表5.3ＬＲ分析法适用于分析LR（k）文法相当大的一类上下文无关文

8、法分析方法最广义的无回朔的移进归约分析主要特征文法限制少、错误定位准确效率较高、易于实现自动生成LR(k)文法移进归约分析法可分析的文法L：从左到右扫描输入符号R：逆向地完成最右推导k：超前读入的符号个数存在无法分析的2型文法5.3.1分析器的概述LR分析器移进归约分析器+LR分析表特殊性栈=状态栈+文法符号栈分析表=动作表+状态转移表分析器的逻辑结构a1…ai…an#ＬＲ驱动程序(P101算法)动作表action转移表goto产生式序列状态符号栈输入缓冲区分析表SmSm-1………