自上而下的语法分析

1、语法分析的地位

是编译程序的核心部分

2、语法分析的任务

识别由词法分析得出的单词序列是否是给定文法的句子。

3、语法分析的理论基础

上下文无关文法和下推自动机

4、语法分析的方式

自上而下语法分析：从开始符号->符号串。反复使用不同产生式进行推导以谋求与输入符号串相匹配
自下而上语法分析：从符号串->开始符号。对输入符号串，寻找不同产生式进行归约直到文法开始符号。

下推自动机

相对于一个自动机，多出了个下推栈

定义如下

H下推栈内字母表
z0是一个标志，表示栈到底了（栈空状态）
z是栈顶元素
q0是初始状态
q是状态

举例

输入：在q状态下，如果栈顶元素为z，输入符号（读头的符号）为a

使用这个函数

输出：将q变成不同状态q’，并且让栈顶元素z变成r1,r2,r3……

因为这个PDA是不确定的PDA

基本构成

将栈顶元素和读头进行比较，如果相同，就top–，读头++；
如果不相同，就从语法表中找到这个非终结符的产生式，用产生式替换非终结符（栈顶元素）位置，再取栈顶符号
当栈中的开始符号“#”和读头里面的“#”相遇时，整个过程就完成了

算法的三种情况

识别成功或失败

但这种回溯方法，计算机每次需要保留状态，浪费一定空间和时间。

并且，如果有P->Pa这种文法，如果使用上面的分析法，会无限循环下去

面临上面的两个问题，需要改进成“不带回溯的自上而下算法”

不带回溯的自上而下算法

在讲不带回溯的自上而下算法前，先学习“消除左递归”

消除左递归

左递归定义

直接左递归与间接左递归

消除左递归

消除直接左递归
消除间接左递归

消除直接左递归

举例

举例算法

通用性算法

举例1

复杂点的例子

结果

举例2

如果非终结符在右式子有多个，也要分清楚

非终结符在右侧有多个

消除左递归（通用法）

通用算法，对直接或间接左递归都适用

算法

这个算法不适合于包含P->Px的产生式，或包含空串的产生式；如果对P->P的产生式，用上面的方式

举例

对每个非终结符，如果右边的非终结符的号大于自己的号，则不处理

如果小于自己的号，则把右边的非终结符替换成右边的非终结符的候选式。比如：Q->Rb|b，R小于Q的号，用R->Sa|a的Sa|a替换掉R

====>Q->(Sa|a)b|b

顺序为Q-R-S的结果

当然，刚开始的非终结符顺序可以不同

举例2

题目：

E->ET+|T
T->TF*|F
F->E|i

解：

使用消除直接左递归，代替法。不是排序法
E->TE’
E’->T+E’|ε

T->FT’
T’->F*T’|ε

F->把处理后的E、T代入
F->FT’E’|i
再对F消除左递归
F->iF’
F’->T’E’F’|ε

消除回溯

产生回溯的原因

进行推导时，若产生式存在多个候选式，选择哪个候选式进行推导存在不确定性。

消除回溯的基本原则

对文法的任何非终结符，若能根据当前读头下的符号，准确的选择一个候选式进行推导，那么回溯就可以消除。

两种消除回溯的方法

预测
提左因子

预测法

根据读头下符号选择候选式，使其第一个符号与读头下符号相同，或该候选式可推导出的第一个符号与读头下符号相同。这相当于向前看了一个符号，所以称为预测。

求首符集

Frist()集

First算法

得到首符集

求候选式的终结首符集

输入符号为a，选择候选式的4种情况

举例

求首符集举例

提取公共左因子

注:

1)通过反复提取左因子，就能把所有非终结符的所有候选首符集变为两两不相交。
2)反复提取左因子也有一定代价，因为在提取过程中会大量引入非终结符和s产生式，增加语法分析的复杂性。

例子

题目：

A -> id | B_B
B -> S I |id

解：A->id | id_B | S I _B【将A中第一个B替换成对应的产生式，可以发现有公共左因子】

所以

A -> id A’|S I _B
A’-> ε | _B

预测分析程序

求随符集

求随符集的原因

随符集的原因

当栈顶为F，读头为a时，但F->bc|ε，正确应该用F后面的E来替换
所以应该存在一个方法，能求出Follow(F)是不是a

Follow()集

随符集定义

算法

对于非终结符A，求A的Follow(A)

1)对文法开始符号S，将开始符号入栈之前，肯定有个#号已经在栈中，所以将‘#’加入到Follow(S)中;
2)若B→αAβ是文法G的一个产生式，则将First(β)-ε（减去空串ε）加入到Follow(A)中;
3)若B→αA是文法G的一个产生式,或B→αAβ是文法G的一个产生式,且β->ε(β经过多步推出空串ε)，则将Follow(B)加入到Follow(A)中;

注意

这里的方法必须是消除了左递归并且提取了左因子后的文法

举例

求随符集举例

求Follow(E)

先求Follow(E)，因为E是开始符号，所以#一定在，则得到#
再看E出现在了F->(E) 的产生式，所以还要并上First( ) )(这里的 ) )已经是终结符了，所以没必要再求First，如果是非终结符（假如是X），需要再求First(X)。
所以Follow(E)={#,)}

求Follow(E’)

E’出现在E->TE'的产生式中，符合上面算法第三条B→αA，所以Follow(E’)=Follow(E)={#,)}
E’出现在E’->+TE’，也符合上面算法第三条B→αA，Follow(E’)=Follow(E’)就是自身……这步没必要

求Follow(T)重要！！

T出现在E’->+TE'，符合上面算法第二条B→αAβ（应该求出First(β)-ε再加入到A中），所以Follow(T)=First(E’)
因为First(E’)={+,ε}，但要把ε减去，所以Follow(T)={+}

算法中式子	对应实际式子
B	E’
α	+
A	T
β	E’

T出现在E->TE'，由上面知，First(E’)会产生空串，用ε把E->TE'的E’代替，变成E->T，那跟在E后面的其实也跟在T后面，所以Follow(T)={+} U Follow(E)={+,#,)}，这步很重要，因为E’可能会被空串代替，就需要变化到算法第三条B→αA

在算法第二条中，如果发现β会产生空串，就像上面的First(E’)={+,ε}，就要变化成算法第三条

结果

求随符集结果

上面求的首符集、随符集都是为了构造预测分析表，下面来看

构造预测分析表

基本思想

1)若A->α是一个产生式，a属于First(α)，说明α可能以a开头。那么当A是栈顶元素且将读入字符a时，选择α取代A，这样匹配成功的希望最大。
故：M[A,a]元素为A→α ，M为矩阵

若α会产生空串，或着A->ε，就是上面"求随符集"的原因举例。这时，需要判断a是否属于Follow(A)，如果a属于Follow(A)，说明A就应该被ε替代，让Follow(A)来和a匹配。

算法

构造预测分析表

根据First和Follow构造

预测分析表

上面的分析表中，因为First(E’)={+,ε}和First(T’)={*,ε}出现了ε，所以需要考虑他们为ε的情况，也就是在当某个字符在E’或T’的Follow()集中，就需要将E’或T’填写成ε

比如：First(E’)={+,ε}，所以在+号下面填写E'->+TE'。又Frist(E’) = 包含ε，所以在Follow(E')={ ) , # }，在")"和"#"处填写E'->ε

对T’也是同理

小结：

在Follow(X)集出现的位置下，填写 X->ε

在First(X)集出现的位置下，填写 X->……

预测分析表的使用

如，有得到以下的预测分析表

求式子i+i#

过程：

初始	栈内(向右是栈顶)	读头	操作
1	#E	i+i#	(E,i)=TE’	TE’倒序入栈
2	#`E'T`	i+i#	(T,i)=FT’	FT’倒序入栈
3	#E’`T'F`	i+i#	(F,i)=i	匹配
4	#E’T’	+i#	(T’,+)=ε	ε入栈
5	#E’	+i#	(E’,+)=+E	+E倒序入栈
6	#E+	+i#	(+,+)	匹配
7	#E	i#	(E,i)=TE’	TE’倒序入栈
……	…………