程序设计语言——编译原理 第五章总结
程序设计语言——编译原理 第五章总结
CHP5.1自下而上语法分析基本问题
1.归约：是指根据文法的产生式规则，把产生式的右部替换成左部符号
在算符优先分析中，用最左素短语刻画可归约串，在规范规约中用句柄刻画可归约串
2.短语（条件：①句型由开始符号推出②短语是由非终结符号推出），直接短语（由非终结符号经一步推出），句柄（最左直接短语）
3.规范归约：
规范归约是关于是一个最右推导的逆过程
由规范推导推出的句型称为规范句型
4.修建语法树（使用修剪语法树的方法来加深对自下而上语法分析的理解）
①每个句型都有一棵语法树与之对应②每棵语法树的叶结点自左至右排列就组成一个句型③每棵子树（同一个子
树）的叶结点自左至右排列就组成一个短语④每棵简单子树的叶结点自左至右排列就组成一个直接短语⑤每棵最
左简单子树的叶结点自左至右排列就组成一个句柄
5.用符号栈进行自下而上的语法分析
①在分析开始时，将“#”预先进栈，作为栈底符号②将“#”作为输入串的结束符③自左向右对输入串ω不断向
栈中进行移进——归约④一旦发现栈顶形成一个可归约串时，就替换这个串为相应的归约符号（在规范归约的情
况下用相应产生规则的左部符号）代替。
CHP5.2算符优先分析法
1.算符优先分析是定义算符的某种优先关系，借助这种关系来寻找“可归约串”和进行归约
2.算符文法：
一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：
…QR…
则我们称该文法为算符文法，也称OG文法
3.算符优先文法
① a =. b 当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；
② a <. b 当且仅当G中含有形如P→…aR…的产生式， 而R→b…或R→Qb…；
③ a>.b 当且仅当G中含有形如P→…Rb…的产生式，而 R→…a或R→…aQ。
如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：
a=.b
a>.b
a<.b
则称G是一个算符优先文法(OPG文法)
4.构造算符优先关系表
A.
①通过检查产生式的每一个候选式可以找出满足a=.b（即P→…ab…或P→…aQb…的产生式）
②为了满足<.和>.，需对G中每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：
B.
FIRSTVT(P)
① 若有产生式P→a…或P→Qa…，则a∈FIRSTVT(P)；
② 若a∈FIRSTVT(Q)，且有产生式P→Q…，则a∈FIRSTVT(P)。
C.
LASTVT(P)
① 若有产生式P→… a或P→… aQ ，则a∈ LASTVT(P)；
② 若a∈ LASTVT(Q)，且有产生式P→… Q ，则a∈ LASTVT(P)。
D.
有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系<.和>.的所有终结符对。
①假定有个产生式的一个候选形为…aP…，那么，对任何b∈FIRSTVT(P)，有a <·b。
②假定有个产生式的一个候选形为…Pb…，那么，对任何a∈LASTVT(P)，有a ·> b。
5.算符优先分析算法的设计
素短语：指一个句型的短语，它至少包括有一个终结符号且除去它本身之外不再含任何更小的素短语
最左素短语：处在句型最左端那个素短语成为最左素短语
句型的一般表示形式：#N1a1N2a2…NnanNn+1#，其中，每个ai都是终结符，Ni是可有可无的非终结符
6.
CHP5.3LR分析法
①求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA
②把拓广文法的第一个项目｛S′→·S｝作为初态集的核，通过求核的闭包和转换函数， 求出LR(0)项目集规范族，
再由转换函数建立状态之间的连接关系得到识别活前缀的DFA
LR(0)项目：把右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目
有限自动机的每一个状态由一个项目构成。
状态之间的转换关系确定方法如下：
把识别文法所有活前缀的NFA确定化：用子集法把项目集变为状态（第三章的内容）
5.LR(0)项目集规范族构造
①构造G的拓广文法G’
设S为文法G的开始符号，构造一个文法G’，它包含整个文法G，并且引进了一个不出现在G中的非终结符S'，并加进一个新产生式S'→S，这个S'是G'的开始符号。把G’成为G的拓广文法。(有一个仅含项目S'→S. 的状态，这就是唯一的“接受”状态)
②Ｉ的闭包CLOSURE(I)
③转换函数
6.LR(0)分析表的ACTION和GOTO表的构造
7.A)移进和归约项目同时存在。移进-归约冲突
B)归约和归约项目同时存在。归约-归约冲突
若其LR(0)项目集规范族不存在移进-归约，或归约-归约冲突，称为LR(0)文法。
8.SLR文法（处理冲突）
决策
FOLLOW(A)与FOLLOW(B)不存在归约的冲突，状态I面临某输入符号a。
1)若a=b，则移进。
2)若a∈FOLLOW(A)，则用产生式A→α进行归约。
3)若aFOLLOW(B)，则用产生式B→α进行归约。
4)此外，报错。
动作
1)若a∈｛a1，a2…am｝，则移进。
2)若a∈FOLLOW(Bi)，i=1，2…n，则用Bi→γi进行归约。
3)此外，报错。
课后题
体会
这一章要学习的东西很多，感觉很庞杂，要仔细梳理看书的时候感觉自己会，但是做题时，就很乱。做题就体现出自己会还是不会知识点。在做题的时候，又复习了一遍，加深了印象。不理解的通过做题也明白了大部分。