《编译原理实践及应用》第4章自上而下语法分析.pptVIP

自上而下语法分析方法;本章要求;高级语言的语法结构适合用上下文无关文法来描述，上下文无关文法是语法分析的基础。

语法分析是编译过程的核心，其任务是在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。;4.1语法分析的任务;;语法分析器的输入

Token序列：词法分析的输出，是各个单词都正确的源程序的变换形式，是一个有限序列

语法分析器的输出

分析树：表示方法？见教材P89

错误处理信息：定位、继续编译;语法分析器的功能

按照语言的语法构成规则,识别输入的符号串能否构成一个句子。这些规则是用文法的产生式来定义的。

问题

对给定的一个输入串，如何判定它是不是一个句子？

方法

根据文法的产生式规则，从开始符号出发，看能否推导出与这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。;G=({E},{i,+,*,(,)},P,E)

P：E?E+E

E?E*E

E?(E)

E?i;大家有疑问的，可以询问和交流;常用的语法分析方法：;4.3自顶向下语法分析及面临的问题;例1：设有文法

(1)S?xAy

(2)A?**|*

现有输入串：x*y

其分析过程如右：;左递归：文法中存在某个A?Vn，有AA?。

直接左递归：有产生式A?A?

间接左递归：;结论;4.3问题的解决方法;消除左递归;一般而言，若产生式形式为： A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

将其替换为：;练习;例：给定间接左递归文法，请消除左递归;方法是:反复“提取公共左因子”，使得文法的每个非终结符号的各个候选式的首终结符集两两不相交，来避免回溯。;例3：有如下两个产生式：

IF语句?ifEthenS1elseS2;

IF语句?ifEthenS1;

;练习;问题:如果希望没有回溯，对文法有什么要求？;

对不含左递归的文法G，对某非终结符的侯选式：

First(α)={a|αa…,a∈VT}

若αε，则ε∈First(α);;S?Ap

S?Bq

A?a

A?cA

B?b

B?dB;(1)S?xAy

(2)A?**|*;因此，不产生回溯的条件就是：

对非终结符A的任意两个不同的侯选式ai和aj，??有：

First(ai)∩First(aj)=φ

当要求用A进行匹配时，就能根据所面临的输入字符，准确地选取一个A的侯选式。;非终结符A的首终结符集的定义;S?Ap

S?Bq

A?a

A?cA

B?b

B?dB;求非终结符A的First集的算法;S?Ap

S?Bq

A?a

A?cA

B?b

B?dB;E?TE

E?+TE

E?ε

T?FT

T?*FT

T?ε

F?(E)

F?i;;确定的自上而下的分析

举例1：对于文法G1[S]：S→pA

S→qB

A→cAd

A→a

对输入串pccadd，自上而下的推导过程是：

S=pA=pcAd=pccAdd=pccadd

对应的分析树：;例2：对于文法G2[S]：

;例3：使用下述文法对i+i进行分析：;后随符号集的定义;;求非终结符A的Follow集的算法;例:求下题的Follow集;练习;(对文法进行不带回溯的确定的自顶向下分析的条件)，据此判别是否为LL(1)文法。

(1)文法不含左递归

(2)对文法中的任一个非终结符A的各个候选式的首终结符集两两不相交，即：若

A?α1|α2|…|αn，则

First(ai)∩First(aj)=φ(i≠j)

(3)对文法中的每个非终结符A,若它的某个首终结符集含有ε，则

First(A)∩Follow(A)=φ;LL(1)文法的判别;;练习;例3：使用下述文法对i+i进行分析：;LL(1)文法的分析过程;4.4递归下降分析方法;基本架构(1);基本架构(2);基本架构(3);;在给定的语法定义中选择与IF语句有关的产生式。

if语句::=if布尔表达式then执行句else执行句

布尔表达式::=变量关系符变量

关系符::=|||=|=|=

执