目 录
引言...............................................................1 第一章 概述.....................................................4 1.1设计内容....................................................4 1.2设计要求...................................................4 第二章 设计的基本原理...........................................4 2.1预测分析表的构成原理.......................................4 2.2预测分析程序的生成.........................................5 第三章 程序设计.................................................5 3.1总体方案设计...............................................6 3.2各模块设计.................................................6 第四章 程序测试.................................................7 附录 程序清单.................................................8
1
课 程 设 计
设计题目
LL(1)文法分析器
学生姓名
学 号 专业班级 指导教师
2010 年 12 月
2
合肥工业大学课程设计任务书
设 计 题 目 LL(1)文法分析器 成绩 预测分析表自动构造程序的实现 设计内容及要求：对于任意输入的一个LL(1)文法，构造其预测分析表。要求：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再实现教材主 要 内 容 P.79给出的预测分析表构造算法。程序显示输出预测分析表或输出到指定文件中。 预测分析程序的实现 设计内容及要求： 对文法 G: E→E+T|T 按教材P.76表4.1构造出G的预测分析程序， T→T*F|F 程序显示输出如P.78那样的匹配过程。 F→（E）|i 指 导 教 师 意 见 该生能按时完成课程设计任务书所规定的程序设计，综合运用所学知识独立分析和解决问题的能力 。程序设计方案 。论文论述 ，文理 ，格式 。程序运行结果 。程序验收时回答问题 。 签名：
第一章 概述
1.1 设计内容:
1:预测分析表自动构造程序的实现
2:预测分析程序的实现
1.2 设计要求
1:设计内容及要求：对于任意输入的一个LL(1)文法，构造其预测分析表。要求：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再实现教材P.79给出的预测分析表构造算法。程序显示输出预测分析表或输出到指定文件中。 2:设计内容及要求：
对文法 G: E→E+T|T 按教材P.76表4.1构造出G的预测分析程序， T→T*F|F 程序显示输出如P.78那样的匹配过程。 F→（E）|i
第二章 设计的基本原理
2.1预测分析表的构成原理
对于任意给定的LL(1) 文法G,为了构造它的预测分析表M,我们就必须构造与文法G有关的集合First和fellow.首先我们对每一个X∈VT U Vn ,构造FIRST(X),办法是,连续使用下面的规则,直至每个集合FIRST不再增大为止. (1)若X∈VT,,则FIRST(X)={X}.
(2)若X∈Vn ,且有产生式X->a……,则把a加入到FIRST(X)中,若X->ε,也是一条产
生式,则把ε也加到FIRST(X)中.
(3)若X->Y……是一个产生式且Y∈Vn,则把FIRST(Y)中所有非ε-元素都加到
FIRST(X)中,若X->Y1Y2……YK ,是一个连续的产生式, Y1Y2……Yi-1 都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj) 都含有ε(即Y1Y2……Yi-1=>ε),则把FIRST(Yi) 中的所有非ε-元素都加到FIRST(X)中,特别是,若所有的FIRST(Yj)均含有ε,j=1,2,……,k,则把ε加到FIRST(X)中.
对于文法G中每个非终结符A构造FOLLOW(A)的办法是,连续使用下面的规则,直到每个FOLLOW不在增大为止.
(1)对于文法的开始符号S,置#于FOLLOW(S)中;
(2)若A->aBb是一个产生式,则把FIRST(b)\\{ ε}加至FOLLOW(B)中;
(3)若A->aB是一个产生式,或A->aBb是一个产生式而b=>ε(即ε∈FIRST( b))则把
FOLLOW(A)加至FOLLOW(B)中
4
构造分析表M的算法是:
(1)对文法G的每个产生式A->a执行第二步和第三步; (2)对每个终结符a∈FIRST(a), 把A->a加至M[A,a]中;
(3)若ε∈FIRST(a),则把任何b∈FOLLOW(A)把A->a加至M[A,b]中; (4)把所有无定义的M[A,a]标上出错标志.
2.2 预测分析程序的生成
预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号行事的,对于任何(X,a),总控程序每次都执行下述三种可能的动作之一; (1) 若X=a=”#”,则宣布分析成功,停止分析过程.
(2) 若X=a≠”#”,则把X从STACK栈顶逐出,让a指向下一个输入符号. (3) 若X是一个非终结符,则查看分析表M,若M[A,a]中存放着关于X的一个产
生式,那么,首先把X逐出STACK栈顶,然后,把产生式的右部符号串按反序一一推进STACK栈(若右部符号为ε,则意味着不推什么东西进栈).在把产生式的右部符号推进栈的同时应做这个产生式相应得语义动作,若M[A,a]中存放着”出错标志”,则调用出错诊察程序ERROR.
第三章 程序设计
3.1 总体方案设计
在看到这个题目后,首先想到的就是要分模块进行设计.
(1) 第一模块:把文本文件中的LL(1)文法读入到程序中grammer类中的数组成员g
中.
(2) 第二模块:通过对已输入到数组g中的文法,进行扫描,把相应的非终结符和终
结符输入到非终结符数组VN中和终结符数组VT中.
(3) 第三模块:生成所有的非终结符的FIRST集合 (4) 第四模块:生成所有的非终结符的FOLLOW集合 (5) 第五模块:生成文法的预测分析表 (6) 第六模块:生成文法的预测分析程序
通过这六模块的设计,最后可连接成一个预测分析程序.
3.2 各模块程序设计
首先要建立两个类,分别是grammer类和SeqStack类
Grammer类中有保存从文本文件读入的LL(1)文法,用一个二维字符数组g保存, 保存非终结符的字符数组VN,保存终结符的字符数组VT,文法开始符号字符变量begin , 元素对应first集合中的有空字符的非终结符数组emptychar,预测分析表为二维整形数组form.
5