C语言编写源程序建立LR(1)分析器 - 图文

目 录

前 言 ................................................................................................................................................ 2 用C语言编写源程序建立LR(1)分析器 ........................................................................................ 3 一，设计目的，要求，算法与设计思想 ....................................................................................... 3

1.设计内容 ............................................................................................................................... 3 2.设计要求 ............................................................................................................................... 3 3.设计的基本原理 ................................................................................................................... 3

1.CLOSURE(I)的构造 ....................................................................................................... 3 2.GO(I,X)的构造 ............................................................................................................. 3 3.FIRST集合的构造 ........................................................................................................ 4 4.LR(1)分析表的构造 ..................................................................................................... 4

二，LR（1）分析器 ......................................................................................................................... 4

1.LR(1)分析器的实现图： ..................................................................................................... 4 2.LR分析器与逻辑结构及工作过程 ...................................................................................... 5 三，总体方案设计 ........................................................................................................................... 5

1. 各模块设计 .......................................................................................................................... 6 四，程序测试 ................................................................................................................................... 8

1.教科书的第142页文法的LR1分析器的构造和语法分析 ............................................... 8 2.表达式文法的LR1分析器的构造和语法分析器 ............................................................... 9 五，源程序..................................................................................................................................... 10 六，总结......................................................................................................................................... 19 七，参考文献 ................................................................................................................................. 19

编译原理学年论文

前 言

《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计细想。通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。

我选的是老师给的题，并予以扩充。即对任意给定的问法G构造LR(1)项目集规范族，其中要实现CLOSURE(1)，GO(I,X)，FIRST集合符。在此基础上，构造了LR(1)分析表。然后对输入的句子进行语法分析，给出接受或出错报告。程序采用文件输入输出方式。其中包括两个输入文件：文法grammar.txt，以及输入串input.txt；两个输出文件:项目集items.txt和文法的LR(1)分析表action_table.txt。由于语法分析的结果只给出接受或错误报告，比较简单。所以直接在屏幕上输出，也便于用户查看。

在具体编写程序中，对文法操作的各个功能模块独立成为一个子程序，而对具体输入穿得分析则放在main()函数中进行。各个变量奇函数的意义和用法我将在论述程序设计的通体方案中向西给出。

程序的通体算法细想来自《编译原理》课程。具体实现有我独立完成。程序用C/C++语言编写。在Microsoft Visual C++2005环境下调使通过。

2

编译原理学年论文

用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

编译原理学年论文

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）分析器的实现

4

编译原理学年论文

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;

5

编译原理学年论文

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) void e_closure(intT) // 计算items[T]的closure闭包

int is_containd() //判断新生成的项目集是否已经de 在项目集 族中

void go() //实现go(1)的功能 void get_action() //生成LR(1)表

int main() // 调用个个子模块，并在其中堆输入串进行语法分析

1.各模块设计

1.读入模块：Read_G()

文法要为上下无关文法。输入文件的格式为：首先输入产生式的条数：每条产生式的第一个字符为非终结符。以S结尾。输入的同时用tempofinput[temp]=true来记录符temp。为统计有哪些非终结符和终结符作准备。这些都通过ASCLL码对应位是否为true来判断。

6

编译原理学年论文

2.计算FIRST模块：get_first()

现设计FLAG1表示本轮扫描first_vn中有没有新增加的内容。要是有，还有进行下一次扫描。每一轮扫描所有的产生式，在扫描每一个产生式的时候，设置一个下标指针t用来保证不会扫过本产生式，还设置flag表示t的位置是否式一个可以推导出ξ的非终结符。是的话，还有进行下一个t位置的检查。如果t走到产生式的最后位置的下一个位置，则表明ξ属于此产生式左边非终结符的first集合。

3.判断项目数是否在项目集里：is_in(proj temp,int T) Scan项目集原有的每一个项目，和新生成的项目作比较。若有相同的就返回true，否则返回false。

4.获得计算closure(I)时需要的First(βa):gete_expc(proj temp)

设计Flag表示是否还要进行下一轮计算，若处理的位置已经查过了产生式的长度，则直接把项目中的那个搜索字符添加进去。这个模块的返回结果放在BUFFER数据中。

5.项目集的CCLUSER计算：e_closure(int T)

在GO()函数中会产生items[T]的一些基本项目。对items[T]中已经有的每一个项目检查在“。”之后的是否为非终结符；若是，则计算FIRST(a)，把每一个BUFFER中的元素和相应的产生式构成一个项目，加入到项目集中。（注意，此时的项目记得大小时随着项目的不断加入而变大的，所以可以用FOR循环保证项目集中不会有错误。

6.检查项目集是否已经在项目族里：is_contation()

把已经有的项目集和新生成的项目集进行比较，要是有相等的话则表示已经存在相同的项目集合，此时返回相同的那个项目集的编号，否则，返回0.四，程序测试。

7.GO()函数地实现： 第一步制作一个初始项目（即扩展文法的第一条产生式），然后用e_closure构造项目集0.在程序中Ccount制作项目集的计数从0开始到（包括n)，所以在for循环中是。即扫描每一个项目集，对每一个项目在“.”之后的终结符，向后移动一位“.”的位置生成新的项目，暂存在buf数组中。然后预生成项目集，并且求其closure，再判断新的项目集是否已经存在，若存在了，就删除这个项目集，并设置相应的trans。否则就生成的项目集，也设置相应的trans。在以上过程中，每次确定生成一个项目集的时候都把它输出到items.txt中。

8.LR(1)分析表的构造get_action()

Scan 每一个项目集，若其中有规约项目，则转换表增加一个归约（用负值表示）。然后，根据trans 数组中的元素，构造转换表的移进项（用正值表示）。接受项目也是一个归约项，用0表示。生成的转换表输出到action_table.txt中。

7

编译原理学年论文

9.堆输入串的语法分析：在main()中实现

用stack模拟语法分析的过程，先在stack 中放入（0，#），然后，用当前栈项状态和当前输入字符查找action_table。根据action_table中的值的情况做相应处理（即执行移进和归约动作）。若遇到接受项目则给出接受提示，程序结束。若遇到出错的情况给出出错提示，页结束程序。

四，程序测试

本程序在Dev_C++和Microsoft Visual C++2005中调试通过。下面给出两个调试实例：

1.教科书的第142页文法的LR1分析器的构造和语法分析

输入文法：

3 EBBS BaBS BbS

? 生成的项目集族：

? 生成的转换表：

? 输入句子测试：

图3 输入句子运行结果

8

编译原理学年论文

2.表达式文法的LR1分析器的构造和语法分析器

? 生成的项目集族：

图4 生成的项目集组表

9

编译原理学年论文

? 生成的转换表：

? 输入句子测试

图5 输入句子运行结果

五，源程序

/*

Name: LR(1)分析器的构造

Author: ELNUR Date: 08-06-07

Description: 输入文法，构造出相应的LR(1)分析器 */

#include%using namespace std;

char G[20][20]; //use a matrix to store grammar G

int length[20]; //length use to store each formula's length int number = 0;

bool tempofinput[150]; //buffer of input char str_vn[20]; //put all vn into it int size_vn = 0;

char str_vt[150]; //put all vt into it int size_vt = 0;

bool first_vn[30][150];

char buffer[50]; //用来存放生成LR（1） 项目集时需要的first_set

10

编译原理学年论文

int bsize = 0; struct thri{ int beg; int nex; char ch; };

thri trans[200]; int size_trans = 0; /*

定义项目集的形式 */

struct proj{

int formula_numb; int part; char expc; };

proj items[100][100]; int Ccount = 0; int size_item[100];

void Read_G() {

cin >> number; //user should give the number of formula first for(int i = 1; i <= number; i++){ char temp; int j = 0; cin >> temp;

while(temp != '$'){

tempofinput[temp] = true; G[i][j++] = temp; cin >> temp; }

length[i] = j; }

G[0][0] = 'S';

G[0][1] = G[1][0]; length[0] = 2;

for(int i = 0; i < 64; i++) if(tempofinput[i])

str_vt[size_vt++] = i;

11

编译原理学年论文

for(int i = 91; i < 128; i++) if(tempofinput[i])

str_vt[size_vt++] = i; for(int i = 65; i < 91; i++) if(tempofinput[i])

str_vn[size_vn++] = i; /*for(int i = 0; i < size_vn; i++) cout << str_vn[i] << \ cout << endl << endl;

cout << \ for(int i = 0; i < size_vt; i++) cout << str_vt[i] << \ cout << endl; */ }

void get_first(){ bool flag1; do{

flag1 = false;

for(int i = 1; i <= number; i++){ int t = 1;

bool flag2 = false; do{

flag2 = false;

if (G[i][t] >= 'A' && G[i][t] <= 'Z'){ for(int k = 0; k < 64; k++) if(first_vn[G[i][t]-'A'][k] == && !first_vn[G[i][0]-'A'][k]){

first_vn[G[i][0]-'A'][k] = true; flag1 = true; }

for(int k = 91; k < 128; k++) if(first_vn[G[i][t]-'A'][k] == && !first_vn[G[i][0]-'A'][k]){

first_vn[G[i][0]-'A'][k] = true; flag1 = true; }

if(first_vn[G[i][t]-'A'][64] == true){ t++;

flag2 = true; } }

true

true

12

编译原理学年论文

else if(!first_vn[G[i][0]-'A'][ G[i][t] ]){ first_vn[G[i][0]-'A'][ G[i][t] ] = true; flag1 = true; }

}while(flag2 && t < length[i]); if(t == length[i])

first_vn[G[i][0]-'A'][26] = true; }

}while(flag1); }

/*j判断项目数否在项目集里*/ bool is_in(proj temp,int T){

for(int i = 0; i < size_item[T]; i++)

if(temp.formula_numb == items[T][i].formula_numb && temp.part == items[T][i].part && temp.expc == items[T][i].expc)

return true; return false; }

void gete_expc(proj temp){ bsize = 0; bool flag;

int tt = temp.part; do{

flag = false;

if(tt+1 >= length[temp.formula_numb]){ buffer[bsize++] = temp.expc; return; } else if(G[temp.formula_numb][tt+1] < 'A' || G[temp.formula_numb][tt+1] > 'Z'){

buffer[bsize++] = G[temp.formula_numb][tt+1]; return; } else if(G[temp.formula_numb][tt+1] >= 'A' && G[temp.formula_numb][tt+1] <= 'Z'){

for(int i = 0; i < 64; i++){

if(first_vn[ G[temp.formula_numb][tt+1]-'A' ][i]) buffer[bsize++] = i; }

for(int i = 91; i < 128; i++){

if(first_vn[ G[temp.formula_numb][tt+1]-'A' ][i]) buffer[bsize++] = i;

13

编译原理学年论文

}

if(first_vn[ G[temp.formula_numb][tt+1]-'A' ][64]){ tt++;

flag = true; } }

}while(flag); }

void e_closure(int T){

//cout << \

for(int i = 0; i < size_item[T]; i++){ proj temp;

if(G[items[T][i].formula_numb][items[T][i].part] >= 'A' && G[items[T][i].formula_numb][items[T][i].part] <= 'Z'){

for(int j = 0; j < 20; j++)

if(G[j][0] == G[items[T][i].formula_numb][items[T][i].part]){ gete_expc(items[T][i]);

for(int k = 0; k < bsize; k++){ temp.formula_numb = j; temp.part = 1;

temp.expc = buffer[k]; if(!is_in(temp,T))

items[T][size_item[T]++] = temp; }

bsize = 0; } } }

/* for(int i = 0; i < size_item[T]; i++)

printf(\

cout << \*/

return ; }

int is_contained() {

for(int i = 0; i < Ccount; i++){

int s = 0; //记录有多少是匹配的

14

编译原理学年论文

if(size_item[i] == size_item[Ccount])

for(int j = 0; j < size_item[Ccount]; j++){ for(int k = 0; k < size_item[i]; k++) if((items[Ccount][j].formula_numb == items[i][k].formula_numb) && (items[Ccount][j].part == items[i][k].part) && (items[Ccount][j].expc == items[i][k].expc)){

s++; break; } }

if(s == size_item[Ccount]) return i; } return 0; }

void go(){ proj init;

init.expc = '#';

init.formula_numb = 0; init.part = 1;

items[0][0] = init; size_item[0]++;

e_closure(0);

cout << \

for(int i = 0; i < size_item[0]; i++)

printf(\

cout << \

bool beginflag = true;

for(int index = 0; (index < Ccount) || beginflag ; index++){ beginflag = false;

for(int j = 0; j < size_vt; j++){ proj buf[50]; int buf_size = 0; proj tp;

int ccc = 0;

for(int p = 0; p < size_item[index]; p++){ if((items[index][p].part <

15

编译原理学年论文

length[ items[index][p].formula_numb ]) && ( G[ items[index][p].formula_numb ][ items[index][p].part ] == str_vt[j]) ){

tp.formula_numb = items[index][p].formula_numb;

tp.expc = items[index][p].expc; tp.part = items[index][p].part+1; buf[buf_size++] = tp; //ccc++; } }

printf(\

if(buf_size != 0){ Ccount++;

for(int t = 0; t < buf_size; t++){

items[Ccount][ size_item[Ccount]++ ] = buf[t]; }

e_closure(Ccount); int next_state = is_contained(); //看生成的项目集是否已经在项目集族中了

if(next_state != 0){

size_item[Ccount] = 0; Ccount--;

trans[size_trans].beg = index; trans[size_trans].nex = next_state; trans[size_trans].ch = str_vt[j]; size_trans++; } else{

cout << \ for(int i = 0; i < size_item[Ccount]; i++)

printf(\Ccount][i].expc);

cout << \

trans[size_trans].beg = index; trans[size_trans].nex = Ccount; trans[size_trans].ch = str_vt[j]; size_trans++; }

16

编译原理学年论文

}

} //对文法的每一个终结符

for(int j = 0; j < size_vn; j++){ proj buf[50]; int buf_size = 0; proj tp;

int ccc = 0;

for(int p = 0; p < size_item[index]; p++){ if((items[index][p].part < length[ items[index][p].formula_numb ]) && ( G[ items[index][p].formula_numb ][ items[index][p].part ] == str_vn[j]) ){

tp.formula_numb = items[index][p].formula_numb;

tp.expc = items[index][p].expc; tp.part = items[index][p].part+1; buf[buf_size++] = tp; //ccc++; } }

printf(\

if(buf_size != 0){ Ccount++;

for(int t = 0; t < buf_size; t++){

items[Ccount][ size_item[Ccount]++ ] = buf[t]; }

e_closure(Ccount);

int next_state = is_contained(); //看生成的项目集是否已经在项目集族中了

if(next_state != 0){

size_item[Ccount] = 0; Ccount--;

trans[size_trans].beg = index; trans[size_trans].nex = next_state;

17

编译原理学年论文

trans[size_trans].ch = str_vn[j]; size_trans++; } else{

cout << \ for(int i = 0; i < size_item[Ccount]; i++)

printf(\Ccount][i].expc);

cout \

trans[size_trans].beg = index; trans[size_trans].nex = Ccount; trans[size_trans].ch = str_vn[j]; size_trans++; } }

} //对文法的每一个非终结符 } }

int main() {

for(int i = 0; i< 150; i++) tempofinput[i] = false; for(int i= 0; i < 100; i++) size_item[i] = 0; for(int i = 0; i < 30; i++)

for(int j = 0; j < 150; j++) first_vn[i][j] = false;

Read_G(); //read G and put the number of formula into count // cout << \

get_first(); //each vn's first_set /*for(int i = 0; i < 128; i++) if(first_vn[1][i])

printf(\ go();

for(int i = 0; i < size_trans; i++){

printf(\ }

<< 18

编译原理学年论文

/*cout << \ for(int i = 1; i <= number; i++){ cout << length[i] << \

for(int j = 0; j < length[i]; j++){ cout << G[i][j]<<\ }

cout << endl; }

cout << \ cout << Ccount << endl; system(\ return 0; }

六，总结

在这次课程设计期间，经过长时间的修改与调试，发现了自己的许多不足之处，由于对以前学习的知识还有些地方不太熟练，所以程序在调试初期有很多错误。比如说指针部分，稍有不注意就弄错了，还有输出格式部分，程序判断部分，在调试过程中都先后出现了些小小的问题，在此期间，通过查看相关资料，寻求老师和同学们的帮助，通过反复修改调试，最后终于调试成功。并起到了很好的查漏补缺作用。由于调试时过程的反复与修改，不便做记录，故在此没写调试记录。由于时间有限，所遍程序没有经过特别的优化，代码可能有些重复、烦琐、纰漏，所编程序难免存在一些问题，比如说，本程序没有对多字符构成的运算符和界符作为单独的单词进行分析。通过这次课程设计，我深深的认识到，如果仅仅只是运用理论知识，是远远不够的。我们必须将理论知识学好，然后理论联系实际，才能很好的将《编译原理》等课程学好，并用于实际案例中。同时，经过这次课程设计，我发觉自己对以前所学的《C》、《C++》、《数据结构》等课程的理解加深了，知识巩固了，动手操作能力也变强了，也为今后后的科研、工作打下了良好的基础。

七，参考文献

［1］《编译原理》 吕映芝 张素琴 蒋维杜 遍著 清华大学出版社

［2］《编译原理教程》习题解析与上机指导 西安电子科技大学出版社

19

本文来源：https://www.bwwdw.com/article/02hx.html