当前位置 博文首页 > kbtx的博客:编译原理-第四章-语法分析之知识点梳理
设有文法G,
G: S → cAd
?????A → ab
那么,识别S的递归下降函数的伪代码为:
//识别 S
void S()
{ match(c);
A();
match(d);
}
//识别 A
void A()
{
match(a);
match(b);
}
为了避免重复扫描词法分析输出的单词序列(提高效率),需要先将文法G采用EBNF表示法,然后写出递归下降分析程序
void A() {
match(a);
if(token==b){
match(b);
}
}
void exp() {
term();
while (token=="+" || token=="-") {
match(token);
term();
}
}
左递归
如果一个文法中有一个非终结符号A使得对某个串α存在一个推导A → Aα,那么这个文法就是左递归的。递归分为立即左递归和非立即左递归:
立即左递归:
1)A → β
2)A → Aα
非立即左递归:
1)A→aB
2)A→Bb
3)B→Ac
4)B→d
消除
将A → Aα | β 转换为
A → β A’
A’ → α A’ | ε
对于非立即左递归:
1)A→aB
2)A→Bb
3)B→Ac
4)B→d
先将其变为立即左递归
1)B→aBc
2)B→Bbc
3)B→d
可化简为:B→aBc | Bbc | d
然后按照上面的规则进行转换即可
1)B→aBcB’ |dB’
2)B’→bcB’ |ε
最后进行整合
1)A→aB
2)A→Bb
3)B→(aBc|d)B’
4)B’→bcB’|ε
提取左公因子
假定有如下规则:
S → aB1|aB2|aB3|aB4|…|aBn|y
显然前n项拥有一个共同的左公因子:a,所以可以把它提取出来。
提取规则:将规则S中公因子之后的变化的部分用一条新规则S’代表,其他保持不变,变化的部分在S’中用或连接。即:
S → aS’|y
S’ → B1|B2|B3|B4|…|Bn
第1个“L”指的是由左向右地处理输入;
第2个“L”指的是它为输入串找出一个最左推导;
括号中的数字1意味着它使用输入单词序列中的一个单词预测分析的动作。
First | 内容 | 来源 |
---|---|---|
E | (,i | First(T) |
E’ | +,ε | 直接读取 |
T | (,i | First(F) |
T’ | *,ε | 直接读取 |
F | (,i | 直接读取 |
Follow 集仅针对非终结符,并且不包含ε
求解Follow(A) ,应重复以下步骤,直到所有的Follow集合不再变化为止:
例:求文法G(E)的Follow集(需要用到先前的First集)
① E → TE’
② E’ → +TE’ | ε
③ T → FT’
④ T’ → *FT’ | ε
⑤ F → (E) | i
First | 内容 | 来源 |
---|---|---|
E | $,) | 开始符号、⑤ |
E’ | $,) | 开始符号、①Follow(E) |
T | $,+,) | 开始符号、①②First(E’)-{ε}、①②Follow(E’) |
T’ | $,+,) | 开始符号、③Follow(T) |
F | $, * ,+,) | 开始符号、③④First(T’)-{ε}、③Follow(T)、④Follow(T‘) |
显然,应该重点关注导致First(X)-{ε}出现以及可以直接获取终结符的产生式;此外,即使某些产生式左侧不属于开始符号,可能因为包含其它式的Follow集而获得$符。
分析表以非终结符作为行索引,以终结符作为列索引,分析表的元素位置存储产生式。
过程描述: 把每一个非终结符的每一个候选产生式放到分析表的正确位置上,使得当栈顶出现该非终结符、面临某些终结符的时候,能够选择正确的候选产生式进行扩展”。
如何正确放置产生式?
构造G的分析表M[A, a], 确定每个产生式A→α在表中的位置
视频演示
如果G是左递归或二义的,那么,M至少含有一个多重定义入口。因此,消除左递归和提取左因子将有助于获得无多重定义的分析表M。
可以证明,一个文法G的预测分析表M不含多重定义入口,当且仅当该文法为LL(1)的。
LL(1)文法不是二义的。
前缀:从符号串的尾部删去若干(包括0个)个符号之后所余下的部分
活前缀:分析栈中存储的符号串,不含有句柄之后的任何符号
后缀:从符号串的首部删去若干(包括0个)个符号之后所余下的部分
例如,对于 W=androidstudio,W的前缀有androidstudio、androidstudi、androidstud、androidstu、…、ε;W的后缀有ndroidstudio、droidstudio、roidstudio、…、ε 。
可归前缀:若文法G存在推导 αAω => αβω,则可由 αβω规约到αAω,此时称αβ的前缀为文法G的活前缀,αβ称为G的可归前缀。
句柄:如果符号栈的内容是当前句型的可归前缀,那么栈顶已经形成当前句型的句柄,进行归约,否则继续移进。在语法树结构下,最左端的两层子树末端是句柄。
自下而上分析法从输入单词序列开始,自左至右逐步进行归约,试图将其归约为文法的开始符号。自左至右规约是规范推导的逆过程,所以称之为规范规约,规范规约的每一步是从当前的规范句型中将句柄归约为相应的非终结符
规范规约定义:假定α是文法G的一个句子,当序列αn,αn-1,αn-2,…,α1,α0满足
① αn = α
② α0为文法开始符号S
③ 对于任意 0<i≤n,αi-1是将αi的句柄替换为产生式左部的符号得到的
则称该序列为α的一个规范规约
对于G[S]:S→aAcBe,A→b,A→Ab,B→d
当输入串为abbcde时,我们进行了如下规约:
句型 | 规约规则 | 句柄 | 语法树 |
---|---|---|---|
abbcde | A→b | b | |
aAbcde | A→Ab | Ab | |
aAcde | B→d | d | |
aAcBe | S→aAcBe | aAcBe | |
S | 规约完毕 | - | S |
一个显而易见的问题是,按照上述方法,我们必须要构建出语法树才能找到句柄,但语法树应该是语法分析的输出结果,因此在实际分析时,不可能通过语法树找句柄。
L是指自左(Left)向右分析输入单词序列
R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)
括号中的 k 是指在决定当前分析动作时向右看的单词个数为 k
LR分析表由两张子表构成
LR分析过程
设初始分析栈内容如下:
输入串:a1a2…an$ ;Stop=S0
状态栈 | 符号栈 |
---|---|
S0 | $ |
设当前分析栈状态为
输入串:aiai+1…an$ ; Stop = Sm
状态栈 | 符号栈 |
---|---|
Sm | Xm |
… | … |
S2 | X2 |
S1 | X1 |
S0 | $ |
我们总是根据 栈顶的状态和当前的输入符号,从ACTION(Sm,ai)中确定下一步动作:
若ACTION(Sm,ai)表示移进,且下一状态为 Snew,我们把Snew和ai入栈,分析栈状态变为:
输入串:ai+1ai+2…an$; Stop = Snew
状态栈 | 符号栈 |
---|---|
Snew | ai |
Sm | Xm |
… | … |
S2 | X2 |
S1 | X1 |
S0 | $ |
若ACTION(Sm,ai)表示按 A → Xm-r+1Xm-r+2…Xm进行规约(产生式右部长度为r),则分析栈状态变为:
输入串:aiai+1…an$ (输入串没有发生变化) ; Stop = Sm-r+1= GOTO(Sm-r , A)
状态栈 | 符号栈 |
---|---|
Sm-r+1 = GOTO(Sm-r , A) | A |
Sm-r | Xm-r |
… | … |
S2 | X2 |
S1 | X1 |
S0 | $ |
若ACTION(Sm,ai)表示接受,宣布分析成功
若ACTION(Sm,ai)表示出错,停止分析,按出错处理。
LR分析过程满足两条性质:
其余内容请直接观看视频。
活前缀:活前缀中不含句柄之后的字符,因此只要保证分析栈中的符号始终是活前缀,我们的分析就不会出错。
构造识别活前缀的DFA:
用得到的的DFA构造LR(0)分析表:
LR(0)文法的要求过于严苛,稍微具有实际意义的文法就很可能不符合LR(0)的要求。
释义:S-simple;(1)最多向前看一个单词
请直接观看视频
在有些情况下,当状态i显现于栈顶时,当前单词是a,栈里的活前缀βα未必允许把α归约为A,因为可能根本就不存在一个形如“βAa"的规范句型,在这种情况下,用“A→α”归约不一定合适。
产生这个问题的根本原因是Follow集合提供的信息太泛。
定义:扩展LR(0)项目,附带有k个终结符 [A→α?β, a1a2…ak]
a1a2…ak 称为向前搜索符串(或展望串)。
归约项目 [A→α?,a1a2…ak]的意义:当它所属的状态呈现在栈顶且后续的k个输入符号为 a1a2…ak 时,才可以把栈顶上的α归约为 A
对于任何移进或待约项目[A→α?β, a1a2…ak], β≠ε,搜索符串 a1a2…ak没有直接作用。
一般情况下,我们只对k≤1的情况感兴趣
假定I是文法G’的任一项目集,定义和构造I的闭包CLOSURE(I)如下:
令I是一个项目集,X是一个文法符号,函数GO(I,X)定义为:
GO(I,X)=CLOSURE(J),其中 J={ 任何形如[ A→αX?β, a ]的项目 | [ A→α?Xβ, a ]∈I }
LR(1)的状态数远多于SLR(1)
请直接观看视频