编译原理自顶向"哪"复习总结

[TOC]

自顶向下

关于集合和LL文法的那些事

三大集合

首符符集,后继集,选择集

首字符集:FIRST（α）={a | α * aβ,a∈ VT， α、β ∈V* };
后继集(follow):对于S来说非终结符的在产生式任意时;1)加上#;2)Sb,follow(S)加上b;3)A->SB,first(B)的元素加入follow(S);4)A->aaaB或A->aaBb,b可能为空,follow(A)的元素加入follow(B);5)A->SB,if(B->ε) FOLLOW(A)属于follow(S);
选择集(select):1.若a不能推出空，则SELECT(A -> a) = FIRST(a)2.若a能推出空，则SELECT(A -> a) = (FIRST(a) – ε）并 FOLLOW(A)
请点击–>参考

LL(1)文法

一个上下文无关文法是LL(1)文法的充分必要条件是每个
非终结符A的两个不同产生式，A →α ,A →β ；满足 SELECT(A →α ) ∩ SELECT(A →β )= 空; 其中， α、 β不能同时 * ε。
LL(1)的含义解释：(1)第一个L表明自顶向下分析是从左向右扫描输入串；(2)第二个L表明分析过程采用最左推导；(3)1表明只需向右看1个符号便可决定选择哪个产生式进行推导。LL(1)文法没有多余产生式。确定的自顶向下分析要求给定的文法必须满足LL(1)文法。

消除左递归: A->Aa|b,A一直到左边的A递归下去,转化为 A->bA', A'->aA'|ε

自底向上

优先分析法和LR分析法

要找出当前句型的句柄（或是他的变型），然后根据产生式判别将它归约成非终结符号。
过程:先设个栈(分析栈),其作用是用来记录分析的历史和指示分析的下一步动作。分析进行时，把输入符号一个一个地按扫描顺序移进栈中，当栈顶符号形成一个句柄（即为某产生式的右部）时，就进行一次归约，把栈顶构成句柄的那个符号串用相应的产生式左部符号来替换。

用语法树来看就行简单句型就是只用一条边的指向叶子节点,句柄是最左叶子节点
句型:
简单句型:
句柄:

用语法树求短语、简单短语和句柄的方法:

每个句型都有一棵语法树
每棵语法树的叶（从左到右）组成一句型
每个子树的叶（从左到右）组成一短语
- 地方
每个简单子树的叶（从左到右）组成一简单短语
最左简单子树的叶（从左到右）组成一句柄。

简单优先方法

先规定文法符号之间的优先关系和结合性质,然后在利用这种关系,通过这种关系,比较句型中的两个相邻的符号之间的优先顺序来确定句型的”句柄”并进行归约

相邻关系:两个连在一起或者由连在一起的被推到出来的两个符号
优先关系:
- A=B:当U->…AB…时
- A<B:当U->…Ab…时,且b=+=>B
- A>B:当U->…ab… 且 a=+=>A,b=+=>B
优先关系矩阵:使用矩阵来表示这些关系(优先关系是在相邻关系的情况下)
构造优先关系矩阵的简单方法:

对每个非终结符求下面两种集合HEAD(W)={S | W=+=>S…, S属于终结并上非终结};LSAT(W)={ S | W=+=>…S,S属于终结并上非终结};
对每个符号Si,Sj填写优先关系矩阵元素 M[Si,Sj]

简单优先文法的定义:(1)任意两个符号至多成立一种优先关系;(2)任意两个产生式具有不同右部;
# S，S # (S∈VNUVT)
简单优先文法的句柄:是Sj.>Sj+1;Si-1<.Si
给定一个句型X，寻找它的句柄是这样进行的：从左向右进行扫描，每次只查看两个相邻的文法符号，并由此得知什么时候查到句柄的尾Sj，然后再返过头来向句型左端进行加工，仍然只查看相邻的两个运算符，找出句柄的头Si。此时就可以进行归约了。

算符优先文法及优先表

算符文法定义:设有一文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符;又称OG文法
性质1：在算符文法中任何句型都不包含两个相邻的非终结符。
性质2：如果Ab或(bA)出现在算符文法的句型γ中，其中A∈VN ，b∈VT，则γ中任何含b的短语必含有A

简单优先法与算符优先法的比较

两种方法都是自下而上分析法，但简单优先法是找句柄归约成某个非终结符，而算符优先法是找最左素短语归约成统一的一个非终结符
简单优先法是任意两个文法符号之间的优先关系，而算符优先法是任意两个终结符之间的优先关系。简单优先法关系矩阵比算符优先关系矩阵要大
算符优先法是在任意两个终结符之间建立优先关系，在归约过程中，它不对单产生式进行归约，因而比简单优先法效率更高

LR分析

LR(K)分析:L表示从左向右扫描输入串,R表明逆向完成最右推导(规范归约),K表明是向右看K个符号便可唯一的确定分析器的动作是移近还是归约和用哪个产生式归约

LR分析器需要:总控程序，分析栈（状态栈和符号栈）和分析表组成。
- 分为:
- 规范LR分析式
- 简单LR(SLR):
- 向前(LALR):
  总控程序:对所有的LR分析器都是相同的
  分析表:不同的文法分析表不同,同一个文法采用的LR分析器不同时,分析表不同;分为ACTION动作表,GOTO状态转移表;
  分析栈:文法符号栈和相应的状态栈
  GOTO[S_i,X]=S_i 面临文法符号X ∈V_N ∪V_T时,应该转移到下一个状态Sj;
  ACTION[S_j,a]当栈顶状态为S_j(为行标)面临输入符号a(列标)时执行的动作,有移进,归约,接受和报错四种;
LR分析器
- ACTION[Sm,ai]=Sm+1(移进)把状态把状态 Sj=GOTO[Si,a]和输入符号 a 移入分析栈。
- ACTION[Sm, ai]= Rj (归约）当栈顶符号串  形成句柄，且文法中有A 规则，其中 || = n，则归约动作是从分析栈顶去掉 n 个文法符号和 n 个状态，并把归约符 A 和 GOTO[Si,A]=Sj 移入分析栈中，其中Si为修改指针后的栈顶状态
- ACTION[Sm, ai]=acc （接受）表示分析成功。此时，分析栈中只剩下文法开始符号S并且当前读到的输入符号是＃，即输入符号串已经结束。
- ACTION[Sm, ai]=ERROR（空白或出错）表示输入串含有错误，此时出现在栈顶的状态遇到了不该遇到的输入符号
LR(0)分析表的构造:
1. 规范句型的活前缀,前缀：一个符号串的前缀是指该串的任意首部（包含空）abcd的前缀有：,a,ab,abc,abcd
  LR分析器是一个DFA模型

LR分析表

（1）根据文法构造识别规范句型活前缀的有穷自动机DFA
（2）由DFA构造LR分析表
DFA是一个五元式,M=(S, V, GOTO, S0, Z)

构造DFA:
1）确定S集合，即LR（0）项目集规范族，同时确定S0
2）确定状态转移函数GOTO
A→β．刻划产生式A→β的右部β已出现在栈顶
A→β1．β2 刻划A→β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2推出的符号
A→．β 刻划没有句柄的任何符号在栈顶，此时期望A→β的右部所推出的符号串

由DFA转化为分析表
(1)对于每一项目集Ii中形如A→.X的项目，且有GO(Ii,X)=Ij,
若X为一终结符号 a 时，则置ACTION[i,a]=Sj;
若X为一非终结符号时，则仅置GOTO[i,X]=j
(2)若Ii中有归约项目A→. ,设A→为文法第j个产生式，则对文法的任何终结符和“#”（均记为a）置ACTION[i,a]=Rj
(3)若接受项目S’→S .属于Ii ,则置ACTION[i,#]=acc。
(4)在分析表中,凡不能按上述规则填入信息的元素,均置为“出错”
活前缀:归约以前的前缀;

使用:
1）若ACTION[i,a]=Sj, a∈VT,则把a移进符号栈，j移进状态栈。
2）若ACTION[i,a]=Rj，a∈VT或#，则用第j个产生式归约。并将两个栈的指针减去K(其中K为第j 个产生式右部的串长度），然后把产生式的左部符号A压入符号栈，同时用符号对（ Si-k,A)去查GOTO表（其中Si-k为状态栈当前栈顶元素），
若GOTO[Si-k,A]=j,则j压入状态栈，使得两个栈内的元素一样多。

LR(0)项目:A->a.:归约项目,其中栈顶已经是句柄了,下一步就是归约了;A->a1.a2:递进项目或待约项目,;A->.a:接受项目;特例:A-> ε A->.;

构造识别活前缀的NFA:

SLR(1)分析

FOLLOW(A)∩FOLLOW(B)=φ
FOLLOW(A)∩{b}=φ
FOLLOW(B)∩{b}=φ
FOLLOW(A)∩FOLLOW(B)∩{b} =φ

编译原理 自顶向"哪"复习总结