编译原理 之 自下而上的语法分析.ppt

《编译原理 之 自下而上的语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、自下而上语法分析概述简单优先分析算符优先分析第六章自下而上的语法分析6.1自下而上语法分析概述自下而上语法分析试图将一个字符串反向归约至开始符号。自下而上语法分析比自上而下语法分析更有效率，对语法的限制更少。自下而上语法分析的策略：移进-归约分析；6.1自下而上语法分析概述移进就是将一个终结符推进栈归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈自下而上语法分析分类优先分析法简单优先分析法算符优先分析法LR分析自底向上的语法分析.VAR；ABEGINENDREAD（）A<标识符><标识符>

2、<语句><复合语句><语句><分程序><程序><读语句>VARA;BEGINREAD(A)END.<变量说明部分>移进归约接受错误例6.1文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabbcde步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcde#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8）#aAcde#归约(B→d)9）#aAcBe#移进11）#S#

3、接受S10）#aAcBe#归约(S→aAcBe)分析符号串abbcde是否G[S]的句子对输入串abbcde#的移进-归约分析过程SaAcBeaAcdeaAbcdeabbcde6.1自下而上语法分析概述在每一步中如何选择子串进行归约？即如何精确定义“可归约串”。上例第五步：A→Ab，A→b.移进－归约是规范推导（最右推导）的逆过程，即规范归约（最左归约）对于无二义性文法，句子的规范推导是惟一的，规范归约也必然是惟一的。简单优先分析法：按照文法符号（包括终结符和非终结符）的优先关系确定句柄，这种归约实

4、际上是一种规范归约。简单优先分析方法，准确、规范，但分析效率低，实际实用价值不大。6.2自底向上优先分析方法概述6.2自底向上优先分析方法概述算符优先分析法：求出算符之间，即只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到“可归约串”就进行归约，并不考虑归约到那个非终结符（不进行单非终结符的归约，如E→T）。因此这种归约实际上不是规范归约。6.3算符优先分析方法6.3.1直观算符优先分析法人为规定其算符的优先顺序。6.3.2算符优先文法6.3.2算符优先文法【定义6.1】算符文

5、法（OperatorGrammar），也称OG文法。设有一个文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法（OperatorGrammar），也称OG文法。例1：E→E＋E

6、E-E

7、E*E

8、E/E

9、EE

10、(E)

11、-E

12、i性质1：在算符文法中，任何句型都不包含两个相邻的非终结符。证明：设是文法G的一个句型，则有假设Sω0ω1…ωn-1ωn=，当n=1时，即S=ω0ω1=，S,S→是G的一条产生式，所以结论成立。假设n>1，ωn-1满足性质1.由于

13、ωn-1ωn,假设ωn-1=αAδ,A→β.则α的尾符号和δ的首符号都不可能是非终结符。ωn-1ωn=αβδ=,而A→β是算法文法G的一条产生式，所以β不含两个相邻的非终结符，这样也不含两个相邻的非终结符。证毕。性质2：如果Ab或（bA）出现在算符文法的句型中，其中A∈VN，b∈VT，则中任何含b的短语必含A.证明：反证法。由已知条件=αbAβ,假如存在,b和A不同时归约，则必有，存在相邻的非终结符的句型，与性质1矛盾。证毕。优先关系定义定义6.2设是G不含产生式的算符文法，a,bVT,A

14、,B,C∈VN,ab当且仅当G中含有形如：A…ab…或A…aBb…的产生式。a<·b当且仅当G中含有形如：A…aB…的产生式，且Bb…或者BCb….a·>b当且仅当G中含有形如：A…Bb...的产生式，且B…a或者B…aC.【定义6.3】算符优先文法（OperatorPrecedenceGrammar），OPG文法。设G是不含产生式的算符文法，a,bVT,a,b至多有，<·，·>三种关系中的一种成立，则称G是一个算符优先文法。注意：允许b·>c,c·>b;不允许b·>c,b<·c,bc中任两个

15、同时存在。bc不一定cb。例1中：“（”“）”，“）”≠“（”.6.3.3算符优先关系表的构造首先定义如下两个集合：FIRSTVT(B)=｛b｜Bb…或BCb…｝LASTVT(B)=｛a｜B…a或B…aC｝按如下算法计算出给定文法中任何两个终结符对(a,b)之间的优先关系：1)‘‘关系直接看产生式的右部，若出现了A→…ab…或A→…aBb,则ab2)’<·‘关系求出每个非终结符B的FIRSTVT(B)若A→…aB