前 言
我们最美好的十年
《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计细想。通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。
我选的是老师给的题，并予以扩充。即对任意给定的问法G构造LR(1)项目集规范族，其中要实现CLOSURE(1)，GO(I,X)，FIRST集合符。在此基础上，构造了LR(1)分析表。然后对输入的句子进行语法分析，给出接受或出错报告。程序采用文件输入输出方式。其中包括两个输入文件：文法，以及输入串；两个输出文件:项目集和文法的LR(1)分析表。由于语法分析的结果只给出接受或错误报告，比较简单。所以直接在屏幕上输出，也便于用户查看。
在具体编写程序中，对文法操作的各个功能模块独立成为一个子程序，而对具体输入穿得分析则放在main()函数中进行。各个变量奇函数的意义和用法我将在论述程序设计的通体方案中向西给出。
程序的通体算法细想来自《编译原理》课程。具体实现有我独立完成。程序用C/C++语言编写。在Microsoft Visual C++2005环境下调使通过。
用C语言编写源程序建立LR(1)分析器
一，设计目的，要求，算法与设计思想
1.设计内容
对任意给定的上下文无关文法G，构造其LR(1)项目集族，并且在此基础上进一步构造其LR(1)分析表。然后分析输入的句子。
2.设计要求
对输入的文法G（要求是上下文无关文法），在程序终实现CLOSURE(1),GO(I,X)，FRIST等的构造，并利用这些功能函数构造出LR(1)项目集族。并且输出结果。在此基础上构造G的LR(1)分析表（这个表也输出给用户），并对输入的句子进行语法分析表，给出分析结果。
3.设计的基本原理
青海师大1.CLOSURE(I)的构造
CLOSURE(I)表示和I中项目可以识别同样活前缀的所有项目的集合。它可以有以下方法得到：
(1)I中的所有项目都属于CLOSURE(I)；
(2)若项目[A→a.Bβ,a]属于CLOSURE(I)，B→ξ是一个产生式，那么，对于FIRST<βa>中的每一个中介符b,如果[β→.ξ,b]原来不在CLOSURE(I)中，则把它加进去；
(3)重复执行步骤（2），直到CLOSURE(I)不再增大为止。
2.GO(I,X)的构造大学班主任
GO(I,X)=CLOSURE(J)
其中J={任何形如[A→aX.Β,a]的项目[A→a.X.Β,a]属于I}
3.FIRST集合的构造
在这个程序中使用的是FIRST(βa)，这基于每一个非终结符的FRIST集合（终结符的FIRST就是它本身）。所以需要对每一个非终结符构造其FIRST集合。
方法如下：
不定式用法
连续使用下面的规则，直到每个集合FIRST不再增大为止。
（1）若X属于VT，则FIRST(X)={X}。
（2）若X属于VN，且有产生式X→a…，则把A加入到FIRST(X)中；若X→ξ也是一条产生式，则把ξ也加入到FIRST中。
送徐无党南归序4.LR(1)分析表的构造
在实现GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后再扫描所有的项目集，找到其中包含归约项目的哪些项目集，根据其中项目，得到分析表中那些鬼月的部分。
二，LR（1）分析器
1.LR(1)分析器的实现图：
图1 LR（1）分析器的实现
2.LR分析器与逻辑结构及工作过程
图2 LR分析器的逻辑结构
三，总体方案设计
在main()函数中读入文件，并堆文法进行扩展，同时记录下文法的所有终结符和非终结符，对每个非终结符计算它的FIRST集合。以备在计算CLOSURE(1)时使用。然后调用GO()函数。完成LR(1)项目集组的计算。计算的结果记录到ITEMS.TXT中。并且记录下状态之间转换关系。接下来，调用GET_ACTION()根据上面的项目集族和记录的状态转换数组获得LR(1)分析表。然后就可以对输入的句子进行语法检查。程序中主要变量以及函数的说明如下：
char str_vn[20][20]; // 存放输入的文法：为简单起见，设问发的产生式条
数不多于20条，每个产生式不多与20个字符，用@
表示，且产生式输入的时候要以S结束。
int length [20]; // 每条产生式的长度
银耳雪梨红枣汤
int number=0; // 产生式的条数
bool tempofinput //记录哪些ASCII字符在文法中，以求得所有的VT和VN
char str_vn[20]; //记录所有的非终结符
中国营造学社int size_vn=0; //记录非终结符的个数
char str_vt[150]; //记录所有的终结符
int size_vt=0; //记录终结符的个数
bool first_vn[30][150]; //记录每个非终结符的FIRST集
char buffer[50]; //用来存放CLOSURE(I)时需要的FIRST_SET
也用来读入用户的输入电
int bsize=0 // buffer的有效长度
struct thri{
int beg;
int nex;
char ch;
};
thri trans[200]; //定义状态转换组中的元素格式
int size-trans=0; //用来在go()函数中记录状态间的转换trans数组
的大小
struct proj{
int part;
char expc;
}; //定义项目集的格式
proj irems[100][100]; //项目集数组，假设项目集的个数不超过100个，
且每个项目集中的项目个数不超过100个
int CCOUNT=0; //项目集的个数
int size_item[100]; //每个项目集中的项目个数
struct action{
char ch; //定义状态转换表的格式
int nxt_sta;
}; //定义状态转换表的格式
action action_table[100][100]; //状态转换表
int size_act_table[100]; // 输入文法的文件指针
ifstream G_ifile; // 输入句子的文件指针
ofstream input_ifile; // 输出项目集族的文件指针
ofstream items_ofile; // 输出转换表的文件指针
void read_G() // 计算每个非终结符的FIRST集合
void get_first() // 判断项目temp是否已经在项目集族
items[T]中
bool is_in(proj temp,int,T) // 计算item[T]closure(1)时用到的frst(βa)
