编译原理51-自下而上分析基本问题

第五章语法分析－自下而上分析Bottom-upParsing自下而上语法分析优先分析法简单优先分析法*算符优先分析法LR分析法－YACC第五章语法分析5.1自下而上分析根本问题5.2算符优先分析5.3LR分析5.4YACC5.1自下而上分析根本问题5.1.1归约5.1.2标准归约简述5.1.3符号栈的使用和语法树的表示1.自下而上分析过程2.自下而上分析面临的问题1.自下而上分析过程-补充例

G[S]:S→cAd A→ab A→a识别输入串

cabd是否该文法的句子

ScAdab自下而上分析过程中的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号,该子串称为“可归约串〞G[S]:S→cAd A→ab A→acdabASScAdab2.自下而上分析面临的问题当串中的某局部和某个产生式右部匹配时,该不该归约?如何确定"可归约串"?a不是"可归约串",ab是"可归约串"可归约串最左素短语句柄算符优先分析标准规约如何精确定义“可归约串〞?本章核心1.采用哪一种自下而上分析方法?2.如何定义可归约串?3.如果在当前符号串中确定可归约串?5.1.1归约G: (1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d识别输入串abbcde#是否该文法的句子

abbcdeAABS例:p83abbcdeAABSG: (1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d输入串abbcde#可行的实现方案:边扫描,边归约最左归约(标准归约)复习最左推导、最右推导、最左归约、最右归约、标准推导、标准归约的概念aG:(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d

输入串abbcde#baAbc何时移进,何时归约?归约谁?如何确定可归约串?aaAaAaAcaAdcaABcaABeS动作移进移进归约移进归约移进归约归约移进移进ab(2)b(3)cd(4)e(1)图5.1符号栈的变迁移进-归约分析用栈实现标准归约栈顶出现可归约串即可归约

5.1.2标准归约简述1.短语、直接短语、句柄的定义2.从句型的语法树上找出句型的短语、直接短语、句柄3.标准归约与句柄的关系精确定义标准归约过程中的可归约串短语〔Phrase〕SαAδ,且Aβ,那么称β是句型αβδ 相对于非终结符A的短语直接短语(简单短语,Simplephrase)SαAδ,且Aβ,那么称β是句型αβδ 相对于规那么A→β的直接短语*+*句柄(Handle)一个句型的最左直接短语称为该句型的句柄.1.定义找出句型

i1*i2+i3

的所有

短语,直接短语,句柄.G: E→T|E+T T→F|T*F F→(E)|iTFEE+T*FTFi1i2i3短语:i1,i2,i3,i1*i2,i1*i2+i3

直接短语:i1,i2,i3,句柄:i1一棵子树的所有末端结点自左至右排列起来就形成一个相对子树根的短语.2.从语法树中p85例5.1p85例5.2

找出句型

E+T*F+i的所有短语,

直接短语,句柄G: E→T|E+T T→F|T*F F→(E)|i短语:E+T*F+i

E+T*F,i,T*F直接短语:T*F,i句柄:T*FEE+TFiE

+TT

*

FG: (1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→dabbcdeAABS例:p83abaAbcaaAaAaAcaAdcaABcaABeS移进移进归约移进归约移进归约归约移进移进ab(2)b(3)cd(4)e(1)图5.1符号栈的变迁标准归约过程中的可归约串是句柄3.标准归约与句柄的关系标准归约精确定义P86假定α是文法G的一个句子, 如果序列:αn,αn-1,……,α0满足如下条件, 那么αn,αn-1,……,α0是一个标准归约:(1)αn=α是给定的句子(2)α0=S是文法的开始符号(3)对任何i,0<in，αi-1是从αi经过把句柄替换为相应文法产生式的左部符号而得到的。结论标准归约过程中的可归约串是句柄标准归约的实质:在移进的过程中,当发现栈顶呈现句柄就用相应的产生式的左部符号进行替换.标准归约的中心问题:如何寻找或确定一个句型的句柄?5.1.3符号栈的使用和语法树的表示abaAbcaaAaAaAcaAdcaABcaABeS移进移进归约移进归约移进归约归约移进移进ab(2)b(3)cd(4)e(1)abaAbcaaAaAaAcaAdcaABcaABeS移进移进归约移进归约移进归约归约移进移进ab(2)b(3)cd(4)e(1)移进-归约分析用栈实现标准归约G[S]: S→cAd A→ab A→aScAdab