语法分析器的设计
（说明）
一． 要求：
建立一个针对 LL(1)文法编译器的自动生成器。要完成此编译器的生成器需
对源文件进行两遍处理：第一遍词法分析，第二遍语法分析。语法分析程序用
LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用 LL(1)
分析)，然后建立词法分析器，包括词法分析主程序、扫描器部分、关键字表等。
经词法分析后分别计算所输入的文法的每个非终结符号的 FIRST 集合，每个非
终结符号的 FOLLOW 集合，以及每个规则的 SELECT 集合，并判断任意一个
非终结符号的任意两个规则的 SELECT 集的交集是不是都为空，如果是则输入
文法符合 LL(1)文法则可以进行分析。
二． 语法分析器实现
语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，
从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，
为语义分析和代码生成作准备。这里采用自顶向下的 LL(1)分析方法。
语法分析程序的流程图如图 5-4 所示。
1.计算 FIRST 集
对于文法 G 的任意一个符号串=X
1
X
2
…X
n
可按下列步骤构造其 FIRST()集
合：
令 FIRST()=Æ，i=1；
(1) 若 X
i
V
T
，则 X
i
FIRST()；
(2) 若 X
i
V
N
：
① 若 e FIRST(X
i
)，则 FIRST(X
i
) FIRST()；
② 若 eFIRST(X
i
)，则 FIRST(X
i
)-{e} FIRST()；
i=i+1；
重复(1)(2)，直到(X
i
V
T
(i=2,3,…,n)或 X
i
V
N
且 e FIRST(X
i
)或 i>n 为止)。
(3)若对于一切 1≤i≤n，eFIRST(X
i
)，则将 e 符号加进 FIRST()。
实例中求单个符号的 FIRST 集的算法描述如下：
void findSingleFIRST(int i){
开始
读入文法
有
效？
判断句型
报错
结束
语法分析程序流程图
是 LL(1) 文法？
剩余33页未读，继续阅读
评论1