课程设计说明书

1.1 课题简介。

试编写一个程序，用来计算给定文法的全部first集及follow集，并判定所给文法是否ll(1)文法，掌握消除左递归及消除回溯的方法，掌握ll(1)分析器的基本结构及first集、follow集、ll(1)分析表的构造方法，能根据文法写出给定输入串的自下而上分析过程。

1.2 方案及其论证。

ll(1)文法使用的是确定的自顶向下的分析技术。ll(1)的含义是：第一个l表明自顶向下分析是从左向右扫描输入串，第2个l表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。

ll(1)文法的判别需要依次计算first集、follow集和sellect集，然后判断是否为ll(1)文法，最后再进行句子分析。

本次课程设计要求编写一个程序，用来计算给定文法的全部first集及follow集，并判定所给文法是否ll(1)文法。首先要面临一个问题就是本次程序具体实现的是一个内部给定的正确文法，其次是依次计算first集、follow集和sellect集，然后判断是否为ll(1)文法，最后再进行句子分析。终结符，非终结符，first集，follow集，sellect集和ll(1)分析表对于课程设计ll(1)问题的解决是特别的重要，计算出first集、follow集和sellect集后，后面ll(1)分析表的构造以及判断文法是否为ll(1)文法就很容易解决了。

3.1系统结构图。

3.2主要控制流程。

由于本程序简单，所以依次扫描遇到的每一个字符即可确定哪些是终结符哪些是非终结符。

首先进行第一次扫描，把能够直接推出$的非终结符号记录到空串表，把不能直接推出$的符号依次记录下来，然后单个扫描每一个不能直接推出$的符号。扫描这个符号能够直接推出的第一个非终结符记录到一个队列，接下来依次检查队列中每一个元素，把二次能够推出$的符号记录到空串表，把二次也推不出空串的继续送入到队列，然后再从队列取元素扫描，直到队列为空没能找到能够星推导出$的终结符，那么可以确定这个非终结符推导不出$，接下去扫描下一个非终结符。

first集使用以下四个步骤判定：

1)、若x∈vt ,则first(x)=

2)、若x∈vn,且有产生式x→a…，a∈vt

则把a加入到first(x)中，即a∈first(x)

3)、若x∈vn,且有产生式x→$，则把$也加到first(x)中，即$∈first(x)

4)、若x∈vn, y1，y2，…，yi 都∈vn，且有产生式x→y1y2…yn。

当y1，..yi-1=>$1≤i≤n)，则first(y1)-，first(yi-1first(yi)都包含在first(x)中，即：

first(yi-1)- first(x)

所有y1,…yn *=则把$加到first(x)中，即：

first(yi) ∈first(x)

其中第1-3个方法都很好处理，关键是第四个方法判断时首先判断第一个字符为非终结符，设定一个布尔型扫描标志flag，赋初值true，接下去依次扫描产生式右部每一个字符yi，假如第i个字符可以推出空，那么就把这个字符的first集去除$加入到产生式左部字符的first集中，即first(yi)- first(x),假如yi是终结符或者不可以推出$，那么就把这个字符的first集直接加入到first(x)中，即first(yi) first(x)同时置flag为false不再向下扫描，假如yi恰好是最后一个字符，那么不管它能不能星推导出空都直接把它的first集加入到first(x)中。同时要设置一个队列和一组布尔型变量记录first集是否完成，队列用来记录first(x)用到了哪些其它非终结符的first集。

第一遍扫描完成后就扫描队列，把first集完成的非终结符的first集加入到那些没有完成的非终结符的first集中去，没有完成的非终结符再送回到队列，这时候可能出现死循环，比如first(s)用到了first(a),而first(a)用到了first(b)，first(b)又用到了first(s),这时候s,a,b的first标志均为false，无限循环下去。这时候可以记录一下，比如循环了100次，强行设置first(s)的标志为true，那么first(a),first(b)也就依次可以求出了。我们在实际计算时也是这样处理的，只是没有把标志写出来而是记录在心里的。

对于100次循环或许有些多了，那么到极限情况，可能就是循环总共产生式的个数次数时如果再循环就可以确定是进入死循环了。

follow集使用以下三个步骤判定：

1)、如果 x 是开始符那么把 # 加入到 follow(x)

2)、若ａ=>bβ是一个产生式，则把first(β)加至follow(b)中。

3)、若ａ=>b是一个产生式，或ａ=>bβ是一个产生式而β*=即$∈first(β)则把 follow(a)加至follow(b)中。

follow集的求法与first集类似，但有不同的地方。follow集需要扫描每一个产生式。而first集扫描的是产生式左部不同的产生式，然后扫描左部相同的产生式的每一个右部。

follow集第一次扫描可以确定哪些first集或follow集属于所求的follow集，由于first集已经求出，所以第一次扫描就可以把相应的first集加入到follow集中，设置follow集完成标记位，设置队列，把未完成的非终结符送入队列，依次取出队列元素，把求出follow集的非终结符的follow集加入到相应的follow集中，把未求出的送回队列。

如果碰到死循环使用first集一样的方法处理就可以。

first集＆follow集都已经求出来后sellect集就很好求了，扫描每一个产生式，使用以下三个步骤确定：

a→α a∈vn，α∈v*，1)、若α是终结符，那么sellect(a→α)

2)、若α是$，则select(a→α)follow(a)；

3)、若α是非终结符，那么。

若α*=则select(a→α)first(α)follow(a)；

若α┐*则select(a→α)first(α)

当sellect集求出来后就可以判断是不是一个文法是不是ll(1)文法了，扫描产生式左部相同的sellcet集是否含有相同元素，一旦发现相同元素立刻返回false，扫描结束没有发现相同元素则返回true。

当一个文法确定是ll(1)文法时就可以对输入的语句进行判定了。首先要安装sellect集生成ll(1)**分析表，最简单的方法是使用哈希表来表示，把每一个产生式左部依次和这个产生式sellect集中的每一个终结符组成关键字，其值即为这个产生式，送入哈希表。这样在进行句子的分析时就可以很容易判断是否使用某一个产生式来进行规约。

在实际分析时设置两个栈，把"#"压入分析栈和剩余栈，把开始符压入分析栈，把输入串从右向左送入剩余栈，然后只要两个栈元素个数同时大于1，那么依次从两个栈中取出两个元素进行比较，假如一样就匹配，假如可以规约就规约，否则就不是该文法的句子。

附录一。1、按照提示要求依次输入文法的非中介符号串，文法的中介符号串，文法的开始符号，文法产生式的条数以及产生式的内容。(1)文法。

2、根据要求输入一文法的所有内容。

3、输入完成后运行得出first集合follow集并得出该文发不是ll(1)文法。

4、根据要求输入另一文法的所有内容。

5、输入完成后运行得出first集合follow集并得出该文发是ll(1)文法。

附录二。#include<>

#include<>

int count=0分解的产生式的个数*/

int number所有终结符和非终结符的总数*/

char start开始符号*/

char termin[50终结符号*/

char non_ter[50非终结符号*/

char v[50所有符号*/

char left[50左部*/

char right[50][50右部*/

char first[50][50],follow[50][50各产生式右部的first和左部的follow集合*/

char first1[50][50所有单个符号的first集合*/

char select[50][50各单个产生式的select集合*/

char f[50],f[50记录各符号的first和follow是否已求过*/

char empty[20记录可直接推出@的符号*/

char temp[50求follow时存放某一符号串的first集合*/

int validity=1表示输入文法是否有效*/

int ll=1表示输入文法是否为ll(1)文法*/

int m[20][20分析表*/

char choose用户输入时使用*/

char empt[20求_emp()时使用*/

char fo[20求follow集合时使用*/

判断一个字符是否在指定字符串中。

课程设计说明书

课程设计说明书

课程设计说明书

课程设计说明书

其他用户还读了