编译原理课程设计 - - - C语言编译器的实现

扬州大学

编译原理课程设计

学 号： 091202122 姓 名： 专 业： 计算机科学与技术 课 程： 编译原理 指导教师： 陈宏建

1

目录

一．程序简介与分析---------------------------------------------------------3 二．程序适用范围-----------------------------------------------------------3 三．词法分析---------------------------------------------------------------3 四．语法分析---------------------------------------------------------------4 五．语义分析和中间代码生成------------------------------------------------10 六．代码生成--------------------------------------------------------------12 七．流程图----------------------------------------------------------------13 八．实现------------------------------------------------------------------14 九．程序运行结果----------------------------------------------------------14 十．总结------------------------------------------------------------------18

十一.附录（源程序）--------------------------------------------------------18

2

简单的编译程序设计

一． 程序简介与分析

本程序由四个部分组成：词法分析子程序，语法分析子程序，语义分析子程序，目标代码生成程序。本程序输入一个叫libo.txt的c语言源程序，然后对它进行词法，语法，语义分析，并输出汇编代码。

词法分析输入的是c语言源程序，输出的3是具有独立语法意义的单词符号。

语法分析以词法分析产生的编码流为输入，按照SLR(1)分析方法进行语法分析，产生语法树，输出移进和归约的动作，如果源程序不符合文法，则有“语法分析出错”的提示。

语义分析阶段，在语法分析的同时，在归约的时候，给出相应的语义动作，最后输出中间代码四元式和新的符号表，如果有未声明的变量出现，则会提示出出错，并显示出此变量的名称。

代码生成阶段，将语义分析得到的中间代码四元式转化为汇编语言的目标代码并输出。

二． 程序适用范围

本程序的使用范围为：整型常量，四则运算（为了简化问题，本程序只考虑加法运算和乘法运算）和布尔表达式以及相应的赋值语句，条件转移语句和循环语句。

三． 词法分析

根据词法分析的需要，我将源程序中的单词符号分为：保留字，字母（标识符）， 界符三类，统一用一张表表示如下：

界符，保留字表

单= + * > : 词 ; { } ( ) and if then while do int 标志符 25 编1 2 3 4 5 6 7 8 9 10 31 码

32 33 35 36 37 程序从源程序文件libo.txt中一次读入一个字符，并判断它是不是字母，界符， 保留字，空格，换行，结束符号或者非法字符。

流程图如下：

3

子程序开始程序读入一个字符ch判断字符ch非法字符空格 换行 结束符界符子程序继续编号并输出编号并输出字母出错处理关闭文件判断是否要写入文件显示错误信息写入到磁盘文件Y子程序结束NEOF 词法分析流程图

四． 语法分析

1．源程序中涉及的文法G[P]定义如下表： ○

说明语句 0、P’→P 1、P→id () L;R 2、L→L;D 3、L→D 4、D→id:int 表达式 布尔表达式 句法 13、M→id=E 14、S→if B then M 15、S→while B do M 16、S→M 17、N→N;S 18、N→S 19、R→{N} 4

5、E→E+T 11、B→B and B 6、E→T 12、B→id>id 7、T→T*F 8、T→F 9、F→(E) 10、F→id

2.上述文法的每个非终结符的FIRST 集和FOLLOW集如下表： ○

P L D E T F B M S N R

FIRST 集 { id } { id } { id } {(,id } {(,id } {(,id } { id } { id } {id,while,if} {id,while,if} { { } FOLLOW 集 { # } { ; } { ; }

{ },;,+,),#} { },;,+,),*,#} { },;,+,),*,#} {then,do,and} { },;} { },;} { },;} { # }

3.文法G[P]的项目集部分如下： ○

0. P’→.P 1. P’→P.

2. P→.id()L;R 3. P→id.()L;R 4. P→id(.)L;R 5. P→id().L;R 6. P→id()L.;R 7. P→id()L;.R 8. P→id()L;R. 9. L→.L;D

10.L→L.;D 11. L→L;.D 12. L→L;D. 13.D→.id:int 14. D→id .:int 15. D→id: .int 16. D→id:int. 17.E→.E+T 18. E→E.+T 19. E→E+.T 20. E→E+T. 21. E→.T 22. E→T. 23. T→.T*F 24. T→T.*F 25. T→T*.F 26. T→T*F. 27. T→.F 28. T→F. 29. F→ (E) 30. F→ (.E) 31. F→ (E.) 32. F→ (E). 33. F→.id 34. F→id.

4.再由项目集构造文法的DFA活前缀。为了方便，省去了项目族集的每个状态的项目，○

直接在状态转换的箭头上标明终结符或非终结符。对于有规约动作和接受的状态，将其特别标明。文法G[P]的DFA图如下：

5

有归约动作 11 8 : int 说明语句 12 5 6 7 接受状态 D id D id 9 0 1 R 10 ; L 4 ) 3 ( 2 id P { 24 26 if 23 B then 25 M 18 id and id 句法 13 S id 14 = } if id M N 17 ; 19 S 20 id M while 30 while 27 B 28 do 29 M id and id B 31 34 布尔表达式 > and 33 32 id 21 22 35 15 T id 36 id ( F E 38 37 * ( 16 40 F 39 ( 41 id F id + E ( 表达式 42 43 + ) T 45 44 6

* G[P]：SLR（1）分析表 id ( ) ; : * Action + > = { } int and if then while 15 16 1 17 do $ goto P D R E T F B M S L N 0 1 2 3 4 5 6 7 8 9 111110 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 0 s2 1 2 s3 3 s4 4 s5 5 s6 6 s7 7 r4 8 r3 9 s10 1s s13 11 12 1s r2 s23 s15 acc 8 9 11 0 5 2 1 r1 s27 22 17 3 14 14 2 1 7

1ss4 133 5 36 8 7 6 1 16 r13 17 s19 18 1s s23 s27 22 s43 r13 s18 r19 9 14 2 0 G[P]：SLR（1）分析表 id ( ) ; : * Action + > = { } int and if then while 15 16 17 do $ goto P D R E T F B M S L N 0 1 2 3 4 5 6 7 8 9 111110 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 20 r17 21 r18 22 r16 2s r17 r18 r16 24 3 31 24 s34 2s s25 26 5 14 26 r14 2s r14 2 8

7 31 28 s34 2s s29 r15 31 s32 3s r15 8 30 9 14 30 2 33 33 r12 3s r12 r12 35 4 31 35 r11 36 r1r1 r1r1 r10 r8 r6 r11 r11 0 0 37 38 rr 0 0 rr 8 8 rr 8 8 s39 r6 6 6 3ss4 40 9 36 1 G[P]：SLR（1）分析表 id ( ) ; : * action + > = { } int and if then while do $ goto P D R E T F B M S L N 9

0 1 2 3 4 5 6 7 8 9 1111115 16 17 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 40 4ss4 rr rr r7 7 7 7 7 433 1 32 8 7 6 1 42 s45 4ss4 s43 43 3 34 7 6 1 44 rr s39 45 rr rr r9 r5 r5 5 5 9 9 9 9

五． 语义分析和中间代码生成

载语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。

语法制导翻译 归约动作 E→E+T 翻译方案 E→E1+T {E.place=newtemp; Emit(E.place’:=’E1.place’+’T.place);} E→T { E.place:=T.place;} T→T1*F {T.place=newtemp; Emit(T.place’:=’ T1.place’+’F.place);} T→F {T.place:=F.place;} F→(E) {F.place:=E.place;} F→id {p:=lookup(id.name); 10

E→T T→T*F T→F F→(E) F→id

if p<>nil then F.place:=p else error;} B→B and B B→B1 and A B2 {backpatch(B1.truelist,A.quad); B.truelist:=B2.truelist; B.falselist:=merge(B1.falselist,B2.falselist);} A→∈{A.quad:=nextquad} B→id>id B→id1>id2 {B.truelist:=makelist(nextquad); B.falselist:=makelist(nextquad+1); emit(if id1.place’>’id2.place’goto_ _’); emit(’goto_ _’);} M→id=E { p:=lookup(id.name); if p<>nil then emit(p’:=’E.place) else error;} S→if B then A M {backpatch(B.truelist,A.quad) backpatch(B.falselist,nextquad)} A→∈{A.quad:=nextquad} S→while A1 B do A2 M { backpatch(B.truelist,A2.quad) backpatch(B.falselist,nextquad+1) emit(’goto’A1.quad)} A1→∈{A1.quad:=nextquad} A2→∈{A2.quad:=nextquad} M→id=E S→if B then M S→while B do M

语法翻译生成的四元式如下：

11

六． 代码生成

目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统结构和指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。本程序生成的目标代码与0x8086微处理器兼容。

下面列举几个简单的四元式与汇编代码的转化列子：

○

1．（+，A，B，T）→ MOV R ，A ； ADD R ，B ; ST R , T ○

2. ( *, A , B , T ) → MOV R ，A ； MUL R ，B ; ST R , T ○3. ( J, _ , _ , L) → JMP L

○

4. ( J> , A , B , L ) → MOV R , A CMP R , B JB L

○5. ( =,A , _ ,T ) → LD R , A ST R , T

本程序生成的目标代码如下：

12

程序流程图 编译程序开始词法分析子程序语法分析子程序理处错出语义分析子程序目标代码生成程序错误处理 编译程序结束

编译程序流程图

七．

13

八． 实现

本程序运行的硬件环境为CPU1.66HZ ,内存为768M .软件环境为windows xp 系统，Visual C++环境。

九． 程序运行结果

1． 输入源文件路径：

2． 输出保留字

3．输出符号表的内容

14

5．输出语法分析的结果（本程序采用自下而上的LR语法分析）

15

16

6．输出中间代码

7．输出目标代码

17

十． 总结

通过本次实验，我对编译程序各阶段有了更深刻更深入的了解，也纠正了自己在某些方面的的错误，丰富了自己关于编译原理方面的知识。同时也培养了自己热爱思考，勤查资料的习惯。由于水平本次实验涉及面并不是很全面，我只考虑了c语言的一个子集。当然本程序的算法在某些地方也还存在一些缺陷。

十一． 附录（源程序）

本程序输入的c源代码如下： libo() a:int; b:int; ccc:int; d:int; {

if ccc>b and ccc>a then a=b+a; while ccc>d do a=d; a=(b+ccc)*a+d }

本程序的完整源代码如下： #include #include #include #include #include #include

using namespace std;

struct token//词法 token结构体 {

int code;//编码 int num;//递增编号 token *next; };

token *token_head,*token_tail;//token队列 struct str//词法 string结构体 {

int num;//编号

string word;//字符串内容 str *next; };

18

str *string_head,*string_tail;//string队列 struct ivan//语法 产生式结构体 {

char left;//产生式的左部 string right;//产生式的右部 int len;//产生式右部的长度 };

ivan css[20];//语法 20个产生式 struct pank//语法 action表结构体 {

char sr;//移进或归约

int state;//转到的状态编号 };

pank action[46][18];//action表 int go_to[46][11];//语法 go_to表 struct ike//语法 分析栈结构体，双链 {

ike *pre;

int num;//状态

int word;//符号编码 ike *next; };

ike *stack_head,*stack_tail;//分析栈首尾指针 struct L//语义四元式的数据结构 {

int k;

string op;//操作符 string op1;//操作数 string op2;//操作数 string result;//结果

L *next;//语义四元式向后指针 L *Ltrue;//回填true链向前指针 L *Lfalse;//回填false链向前指针 }; L *L_four_head,*L_four_tail,*L_true_head,*L_false_head;/*四元式链，true链，false

链*/

struct symb//语义输入时符号表 {

string word;//变量名称 int addr;//变量地址 symb *next; };

symb *symb_head,*symb_tail;//语义符号链表

19

////////////////////////////////词法分析有关函数声明 void outdaima();

void scan();//按字符读取源文件 void cifa_main();//词法分析主程序

int judge(char ch);//判断输入字符的类型 void out1(char ch);//写入token.txt

void out3(char ch,string word);//写入string.txt void input1(token *temp);//插入结点到队列token void input3(str *temp);//插入结点到队列string void output();//输出三个队列的内容

void outfile();//输出三个队列的内容到相应文件中

////////////////////////////////语法分析有关函数声明 void yufa_main();//语法分析主程序

void yufa_initialize();//初始化语法分析数据结构 int yufa_SLR1(int a);//语法分析主体部分

int ID1(int a);//给输入字符编号，转化成action表列编号 string ID10(int i);//给输入字符反编号

int ID2(char ch);//给非终结状态编号，转化成go_to表列编号 int ID20(char ch);//给非终结状态编号 char ID21(int j);//给非终结状态反编号

void add(ike *temp);//给ike分析栈链表增加一个结点 void del();//给ike分析栈链表删除一个结点

/////////////////////////////////语义分析相关函数的声明

void yuyi_main(int m);//语义分析主程序

void add_L_four(L *temp);//向四元式链中加一个结点 void add_L_true(L *temp);//向true链中加一个结点 void add_L_false(L *temp);//向false链中加一个结点 void add_symb(symb *temp);//向语义符号表链中加一个结点 void output_yuyi();//输出中间代码四元式和最后符号表 string newop(int m);//把数字变成字符串

string id_numtoname(int num);//把编号转换成相应的变量名 int lookup(string m);//变量声明检查

/////////////////////////////////全局变量的声明 FILE *fp;//文件指针

int wordcount;//标志符计数

int err; //标志词法分析结果正确或错误 int nl; //读取行数

int yuyi_linshi;//语义临时变量

string E_name,T_name,F_name,M_name,id_name,id1_name,id2_name,errword;//用于归约时名称传递和未声明变量的输出

20

int id_num,id1_num,id2_num,id_left,id_while,id_then,id_do;//用于记录一些特殊的字符位置信息

////////////////////////////////主程序开始 int main() {

cout<<\ cout<<\说明： *\ cout<<\第一部分：词法分析 *\ cout<<\第二部分：语法分析 *\ cout<<\第三部分：语义分析 *\ cout<<\第四部分：目标代码生成 *\ cout<<\ cifa_main();//词法 yufa_main();//语法 output_yuyi();//语义 outdaima(); //代码生成 cout<

system(\ return(0); }

//////////////////////////////////词法分析子程序 void cifa_main() {

token_head=new token; token_head->next=NULL; token_tail=new token; token_tail->next=NULL; string_head=new str; string_head->next=NULL; string_tail=new str;

string_tail->next=NULL;//初始化三个队列的首尾指针 L_four_head=new L;

L_four_head->next=NULL; L_four_tail=new L; L_four_tail->k=0;

L_four_tail->next=NULL; L_true_head=new L;

L_true_head->Ltrue=NULL; L_false_head=new L;

L_false_head->Lfalse=NULL; symb_head=new symb; symb_head->next=NULL; symb_tail=new symb; symb_tail->next=NULL;

21

yuyi_linshi=-1; id_num=0;

wordcount=0;//初始化字符计数器 err=0;//初始化词法分析错误标志 nl=1;//初始化读取行数 scan(); if(err==0) {

char m; output();

cout<<\词法分析正确完成!\如果将结果保存到文件中请输入 y ，否则请输入其它字母：\ cin>>m; cout<

outfile();

cout<<\结果成功保存在token.txt和sting.txt两个文件中，请打开查看\

cout<

void scan() {

cout<

system(\ cout<

char document[50]; int flag=0;

cout<<\请输入源文件路径及名称:\ cin>>document; cout<

cout<<\ cout<<\第一部分：词法分析 *\ cout<<\ if((fp=fopen(document,\ {

err=1;

cout<<\无法找到该文件!\ return; }

22

while(!feof(fp)) {

word=\

ch=fgetc(fp); flag=judge(ch); if(flag==1) out1(ch); else if(flag==3) out3(ch,word);

else if(flag==4 || flag==5 ||flag==6) continue; else {

cout<

fclose(fp); }

int judge(char ch) {

int flag=0;

if(ch=='=' || ch=='+' || ch=='*' || ch=='>' || ch==':' || ch==';' || ch=='{' || ch=='}' || ch=='(' || ch==')') flag=1;//界符

else if(('a'<=ch && ch<='z') || ('A'<=ch && ch<='Z')) flag=3;//字母 else if(ch==' ') flag=4;//空格 else if(feof(fp)) flag=5;//结束 else if(ch=='\\n') {

flag=6;//换行 nl++; } else

flag=0;//非法字符 return(flag); }

void out1(char ch) {

int id; switch(ch)

23

{

case '=' : id=1;break; case '+' : id=2;break; case '*' : id=3;break; case '>' : id=4;break; case ':' : id=5;break; case ';' : id=6;break; case '{' : id=7;break; case '}' : id=8;break; case '(' : id=9;break;

case ')' : id=10;break;//界符编码 default : id=0; }

token *temp; temp=new token; temp->code=id; temp->num=-1; temp->next=NULL; input1(temp); return; }

void out3(char ch,string word) {

token *temp; temp=new token; temp->code=-1; temp->num=-1; temp->next=NULL; str *temp1; temp1=new str; temp1->num=-1; temp1->word=\ temp1->next=NULL; int flag=0; word=word+ch; ch=fgetc(fp); flag=judge(ch);

if(flag==1 || flag==4 || flag==5 || flag==6) {

if(word==\|| word==\|| word==\|| word==\|| word==\|| word==\ {

if(word==\ temp->code=31;

24

else if(word==\ temp->code=32; else if(word==\ temp->code=33; else if(word==\ temp->code=35; else if(word==\ temp->code=36; else if(word==\

temp->code=37;//关键字编码 input1(temp); if(flag==1) out1(ch);

else if(flag==4 || flag==5 || flag==6) return; }

else if(flag==1) {

wordcount++; temp->code=25;

temp->num=wordcount; input1(temp);

temp1->num=wordcount; temp1->word=word; input3(temp1); out1(ch); }

else if(flag==4 || flag==5 || flag==6) {

wordcount++; temp->code=25;

temp->num=wordcount; input1(temp);

temp1->num=wordcount; temp1->word=word; input3(temp1); }

return; }

else if(flag==2 || flag==3) out3(ch,word);//形成字符串 else {

err=1;

25

cout<

void input1(token *temp) {

if(token_head->next == NULL) {

token_head->next=temp; token_tail->next=temp; } else {

token_tail->next->next=temp; token_tail->next=temp; } }

void input3(str *temp) {

if(string_head->next == NULL) {

string_head->next=temp; string_tail->next=temp; } else {

string_tail->next->next=temp; string_tail->next=temp; } }

void output() {

cout<<\表内容如下：\ token *temp1; temp1=new token;

temp1=token_head->next; while(temp1!=NULL) {

cout<code; if(temp1->num == -1) {

cout<

26

{

cout<<\ }

temp1=temp1->next; }

cout<<\符号表内容如下：\ str *temp3; temp3=new str;

temp3=string_head->next; while(temp3!=NULL) {

cout<num<<\ temp3=temp3->next; } }

void outfile() {

ofstream fout1(\写文件 ofstream fout3(\ token *temp1; temp1=new token;

temp1=token_head->next; while(temp1!=NULL) {

fout1<code; if(temp1->num == -1) fout1<

fout1<<\ temp1=temp1->next; }

str *temp3; temp3=new str;

temp3=string_head->next; while(temp3!=NULL) {

fout3<num<<\ temp3=temp3->next; } }

/////////////////////////////////////////语法分析子程序

void yufa_main()

27

{

if(err==0) {

system(\ cout<

cout<<\ cout<<\第二部分：语法分析 *\ cout<<\ yufa_initialize();//初始化语法分析数据结构 token *temp; temp=new token;

temp=token_head->next; int p,q; p=0; q=0;

cout<<\语法分析过程如下：\ while(temp!=NULL) {

int w;

w=ID1(temp->code); p=yufa_SLR1(w); if(p==1) break; if(p==0)

temp=temp->next; if(temp==NULL) q=1; }//语法分析 if(q==1) while(1) {

p=yufa_SLR1(17); if(p==3) break;

}//最后输入$来完成语法分析 } }

void yufa_initialize() {

stack_head=new ike; stack_tail=new ike; stack_head->pre=NULL;

stack_head->next=stack_tail; stack_head->num=0; stack_head->word='!';

stack_tail->pre=stack_head;

stack_tail->next=NULL;//初始化栈分析链表

28

css[0].left='Q'; css[0].right=\css[1].left='P';

css[1].right=\css[2].left='L'; css[2].right=\css[3].left='L'; css[3].right=\css[4].left='D';

css[4].right=\css[5].left='E'; css[5].right=\css[6].left='E'; css[6].right=\css[7].left='T'; css[7].right=\css[8].left='T'; css[8].right=\css[9].left='F'; css[9].right=\css[10].left='F'; css[10].right=\css[11].left='B';

css[11].right=\css[12].left='B';

css[12].right=\css[13].left='M'; css[13].right=\css[14].left='S';

css[14].right=\css[15].left='S';

css[15].right=\css[16].left='S'; css[16].right=\css[17].left='N'; css[17].right=\css[18].left='N'; css[18].right=\css[19].left='R'; css[19].right=\int i,j;

for(i=0;i<20;i++) {

char *css_len;

29

css_len=&css[i].right[0]; css[i].len=strlen(css_len); }

css[1].len=6; css[4].len=3; css[10].len=1; css[11].len=3; css[12].len=3; css[13].len=3; css[14].len=4;

css[15].len=4;//初始化产生式 for(i=0;i<46;i++) {

for(j=0;j<18;j++)

action[i][j].sr='#'; }//初始化action表 for(i=0;i<46;i++) {

for(j=0;j<11;j++) go_to[i][j]=-1; }//初始化go_to表

/****************************以下是给action************************/

action[0][0].sr='s';action[0][0].state=2; action[1][17].sr='@';//结束

action[2][1].sr='s';action[2][1].state=3; action[3][2].sr='s';action[3][2].state=4; action[4][0].sr='s';action[4][0].state=5; action[5][4].sr='s';action[5][4].state=6; action[6][11].sr='s';action[6][11].state=7; action[7][3].sr='r';action[7][3].state=4; action[8][3].sr='r';action[8][3].state=3; action[9][3].sr='s';action[9][3].state=10; action[10][0].sr='s';action[10][0].state=5; action[10][9].sr='s';action[10][9].state=13; action[11][17].sr='r';action[11][17].state=1; action[12][3].sr='r';action[12][3].state=2; action[13][0].sr='s';action[13][0].state=14; action[13][13].sr='s';action[13][13].state=23; action[13][15].sr='s';action[13][15].state=27; action[14][8].sr='s';action[14][8].state=15; action[15][0].sr='s';action[15][0].state=36; action[15][1].sr='s';action[15][1].state=41; action[16][6].sr='s';action[16][6].state=43;

表和go_to表赋初值30

action[16][3].sr='r';action[16][3].state=13; action[16][10].sr='r';action[16][10].state=13; action[17][3].sr='s';action[17][3].state=19; action[17][10].sr='s';action[17][10].state=18; action[18][17].sr='r';action[18][17].state=19; action[19][0].sr='s';action[19][0].state=14; action[19][13].sr='s';action[19][13].state=23; action[19][15].sr='s';action[19][15].state=27; action[20][3].sr='r';action[20][3].state=17; action[20][10].sr='r';action[20][10].state=17; action[21][3].sr='r';action[21][3].state=18; action[21][10].sr='r';action[21][10].state=18; action[22][3].sr='r';action[22][3].state=16; action[22][10].sr='r';action[22][10].state=16; action[23][0].sr='s';action[23][0].state=31; action[24][12].sr='s';action[24][12].state=34; action[24][14].sr='s';action[24][14].state=25; action[25][0].sr='s';action[25][0].state=14; action[26][3].sr='r';action[26][3].state=14; action[26][10].sr='r';action[26][10].state=14; action[27][0].sr='s';action[27][0].state=31; action[28][12].sr='s';action[28][12].state=34; action[28][16].sr='s';action[28][16].state=29; action[29][0].sr='s';action[29][0].state=14; action[30][3].sr='r';action[30][3].state=15; action[30][10].sr='r';action[30][10].state=15; action[31][7].sr='s';action[31][7].state=32; action[32][0].sr='s';action[32][0].state=33; action[33][12].sr='r';action[33][12].state=12; action[33][14].sr='r';action[33][14].state=12; action[33][16].sr='r';action[33][16].state=12; action[34][0].sr='s';action[34][0].state=31; action[35][12].sr='r';action[35][12].state=11; action[35][14].sr='r';action[35][14].state=11; action[35][16].sr='r';action[35][16].state=11; action[36][2].sr='r';action[36][2].state=10; action[36][3].sr='r';action[36][3].state=10; action[36][5].sr='r';action[36][5].state=10; action[36][6].sr='r';action[36][6].state=10; action[36][10].sr='r';action[36][10].state=10; action[37][2].sr='r';action[37][2].state=8; action[37][3].sr='r';action[37][3].state=8; action[37][5].sr='r';action[37][5].state=8; action[37][6].sr='r';action[37][6].state=8;

31

action[37][10].sr='r';action[37][10].state=8; action[38][2].sr='r';action[38][2].state=6; action[38][3].sr='r';action[38][3].state=6; action[38][5].sr='s';action[38][5].state=39; action[38][6].sr='r';action[38][6].state=6; action[38][10].sr='r';action[38][10].state=6; action[39][0].sr='s';action[39][0].state=36; action[39][1].sr='s';action[39][1].state=41; action[40][2].sr='r';action[40][2].state=7; action[40][3].sr='r';action[40][3].state=7; action[40][5].sr='r';action[40][5].state=7; action[40][6].sr='r';action[40][6].state=7; action[40][10].sr='r';action[40][10].state=7; action[41][0].sr='s';action[41][0].state=36; action[41][1].sr='s';action[41][1].state=41; action[42][2].sr='s';action[42][2].state=45; action[42][6].sr='s';action[42][6].state=43; action[43][0].sr='s';action[43][0].state=36; action[43][1].sr='s';action[43][1].state=41; action[44][2].sr='r';action[44][2].state=5; action[44][3].sr='r';action[44][3].state=5; action[44][5].sr='s';action[44][5].state=39; action[44][6].sr='r';action[44][6].state=5; action[44][10].sr='r';action[44][10].state=5; action[45][2].sr='r';action[45][2].state=9; action[45][3].sr='r';action[45][3].state=9; action[45][5].sr='r';action[45][5].state=9; action[45][6].sr='r';action[45][6].state=9; action[45][10].sr='r';action[45][10].state=9;

go_to[0][0]=1;go_to[4][1]=8;go_to[4][9]=9;go_to[10][1]=12;go_to[10][2]=11;go_to[13][7]=22;go_to[13][8]=21;go_to[13][10]=17;

go_to[15][3]=16;go_to[15][4]=38;go_to[15][5]=37;go_to[19][7]=20;go_to[19][8]=20;go_to[23][6]=24;go_to[25][7]=26;go_to[27][6]=28;

go_to[29][7]=30;go_to[34][6]=35;go_to[39][5]=40;go_to[41][3]=42;go_to[41][4]=38;go_to[41][5]=37;go_to[43][4]=44;go_to[43][5]=37;

/****************************action表和go_to表赋初值完毕************************/ }

int ID1(int i)//按action表，给输入字符编号 {

int j; j=-1;

if(i==25) {j=0;id_num++;}//设置变量名称标志

32

if(i==1) {j=8,id_left=id_num;}//设置产生试左边变量名称标志 if(i==2) j=6; if(i==3) j=5; if(i==4) j=7; if(i==5) j=4; if(i==6) j=3; if(i==7) j=9; if(i==8) j=10; if(i==9) j=1; if(i==10) j=2; if(i==31) j=12; if(i==32) j=13;

if(i==33) {j=14;id_then=L_four_tail->k+1;}//设置if语句中then位置标志

if(i==35) {j=15;id_while=L_four_tail->k+1;}//设置while语句中while位置标志 if(i==36) {j=16;id_do=L_four_tail->k+1;}//设置while语句中do位置标志 if(i==37) j=11; return(j); }

string ID10(int i)//反编号输入字符 {

string ch;

if(i==0) ch=\ if(i==1) ch=\ if(i==2) ch=\ if(i==3) ch=\ if(i==4) ch=\ if(i==5) ch=\ if(i==6) ch=\ if(i==7) ch=\ if(i==8) ch=\ if(i==9) ch=\ if(i==10) ch=\ if(i==11) ch=\ if(i==12) ch=\ if(i==13) ch=\ if(i==14) ch=\ if(i==15) ch=\ if(i==16) ch=\ if(i==17) ch=\ return(ch); }

int ID2(char ch)//按go_to表给非终结符编号 {

int j;

33

j=-1;

if(ch=='P') j=0; if(ch=='D') j=1; if(ch=='R') j=2; if(ch=='E') j=3; if(ch=='T') j=4; if(ch=='F') j=5; if(ch=='B') j=6; if(ch=='M') j=7; if(ch=='S') j=8; if(ch=='L') j=9; if(ch=='N') j=10; return(j); }

int ID20(char ch)//给非终结符编号{

int j; j=-1;

if(ch=='P') j=100; if(ch=='D') j=101; if(ch=='R') j=102; if(ch=='E') j=103; if(ch=='T') j=104; if(ch=='F') j=105; if(ch=='B') j=106; if(ch=='M') j=107; if(ch=='S') j=108; if(ch=='L') j=109; if(ch=='N') j=1010; return(j); }

char ID21(int j)//反编号非终结符 {

char ch;

if(j==100 || j==0) ch='P'; if(j==101 || j==1) ch='D'; if(j==102 || j==2) ch='R'; if(j==103 || j==3) ch='E'; if(j==104 || j==4) ch='T'; if(j==105 || j==5) ch='F'; if(j==106 || j==6) ch='B'; if(j==107 || j==7) ch='M'; if(j==108 || j==8) ch='S'; if(j==109 || j==9) ch='L';

34

if(j==1010 || j==10) ch='N'; return(ch); }

void add(ike *temp)//加一个结点 {

if(stack_head->next==stack_tail) {

temp->pre=stack_head; temp->next=stack_tail; stack_head->next=temp; stack_tail->pre=temp; } else {

temp->pre=stack_tail->pre; temp->next=stack_tail;

stack_tail->pre->next=temp; stack_tail->pre=temp; } }

void del()//删除一个结点 {

stack_tail->pre->pre->next=stack_tail; stack_tail->pre=stack_tail->pre->pre; }

int yufa_SLR1(int w) {

/*cout<<\当前输入符号：\

int i,flag=0,state_temp;//flag错误标志，0正常移进，1错误,2归约，3结束 char sr_temp;

sr_temp=action[stack_tail->pre->num][w].sr;//动作

state_temp=action[stack_tail->pre->num][w].state;//状态变化 if(sr_temp=='#')//错误动作 {

flag=1; err=3;

cout<<\语法分析出错!\ }

else if(sr_temp=='s')//移进动作 {

ike *temp; temp=new ike; temp->next=NULL; temp->pre=NULL;

35

temp->word=w;

temp->num=state_temp; add(temp);

cout/*<<\动作（移进）：\状态转为：\ \栈顶符号：\ flag=0; }

else if(sr_temp=='r')//归约动作 {

int p=ID2(css[state_temp].left); int q=css[state_temp].len; for(i=0;inext=NULL; temp->pre=NULL;

temp->word=ID20(css[state_temp].left);

temp->num=go_to[stack_tail->pre->num][p];//查go_to表 add(temp);

cout/*<<\动作（归约）：\\→\ \状态转为：\ \栈顶符号：\ flag=2;

yuyi_main(state_temp);//在产生树的同时进行语义分析 }

else if(sr_temp=='@')//结束动作 {

cout<<\动作（归约）：\\→\ \状态转为：\ \栈顶符号：\ flag=3;

cout<<\语法分析正确完成!\ }

else//其他意外情况 {

flag=1; err=3;

cout<<\语法分析出错!\ }

return(flag);

36

}

/////////////////////////////////////////语义分析子程序

void yuyi_main(int m) {

L *temp; int k; k=1;

temp=new L; temp->op=\ temp->op1=\ temp->op2=\ temp->result=\ temp->next=NULL; temp->Ltrue=NULL; temp->Lfalse=NULL;

if(m==4)//变量声明时加入符号表链 {

symb *Stemp; Stemp=new symb;

id_name=id_numtoname(id_num); Stemp->word=id_name; Stemp->next=NULL; add_symb(Stemp); }

if(m==5)//归约E→E+T {

temp->op=\ temp->op1=E_name; temp->op2=T_name;

yuyi_linshi++;//申请临时变量 E_name=\ temp->result=E_name;

add_L_four(temp);//加一个四元式结点 }

if(m==6)//归约E→T {

E_name=T_name; }

if(m==7)//归约T→T*F {

temp->op=\ temp->op1=T_name;

37

temp->op2=F_name;

yuyi_linshi++;//申请临时变量 T_name=\ temp->result=T_name;

add_L_four(temp);//加一个四元式结点 }

if(m==8)//归约T→F {

T_name=F_name; }

if(m==9)//归约F→(E) {

F_name=E_name; }

if(m==10)//归约F→id {

id_name=id_numtoname(id_num); F_name=id_name;

k=lookup(id_name);//检查变量是否声明 if(k==0) {

err=2;

errword=id_name; return; } }

if(m==12)//归约B→id>id {

temp->op=\ id1_num=id_num-1;

id1_name=id_numtoname(id1_num);

k=lookup(id1_name);//检查变量是否声明 if(k==0) {

err=2;

errword=id1_name; return; }

id2_num=id_num;

id2_name=id_numtoname(id2_num);

k=lookup(id2_name);//检查变量是否声明 if(k==0) {

err=2;

38

errword=id2_name; return; }

temp->result=\ temp->op1=id1_name; temp->op2=id2_name;

add_L_four(temp);//加一个四元式结点 add_L_true(temp);//加一个true链结点 L *temp2; temp2=new L; temp2->op=\ temp2->op1=\ temp2->op2=\ temp2->result=\

add_L_four(temp2);//加一个四元式结点 add_L_false(temp2);//加一个false链结点}

if(m==13)//归约M→id=E {

temp->op=\ temp->op1=E_name; temp->op2=\

id_name=id_numtoname(id_left); temp->result=id_name;

add_L_four(temp);//加一个四元式结点 yuyi_linshi=-1;//临时变量开始重新计数 }

if(m==14)//归约S→if B then M {

int a; a=id_then;

temp=L_true_head->Ltrue; while(temp!=NULL) {

temp->result=\ a=temp->k;

temp=temp->Ltrue; }

a=L_four_tail->k+1;

temp=L_false_head->Lfalse; while(temp!=NULL) {

temp->result=\ temp=temp->Lfalse;

39

}

L_true_head->Ltrue=NULL;

L_false_head->Lfalse=NULL;//回填并清空true链和false链 }

if(m==15)//归约S→while B do M {

int a; a=id_do;

temp=L_true_head->Ltrue; while(temp!=NULL) {

temp->result=\ a=temp->k;

temp=temp->Ltrue; }

a=L_four_tail->k+2;

temp=L_false_head->Lfalse; while(temp!=NULL) {

temp->result=\ temp=temp->Lfalse; }

L *temp1; temp1=new L; temp1->op=\ temp1->op1=\ temp1->op2=\ temp1->next=NULL;

temp1->result=\ add_L_four(temp1);//加一个四元式结点 L_true_head->Ltrue=NULL;

L_false_head->Lfalse=NULL;//回填并清空true链和false链 } }

string newop(int m)//数字变成字符串 {

int shang,yushu; string chuan,chuan1; shang=m; chuan=\ while(1) {

yushu=shang;

chuan=chuan+char(48+yushu);

40

shang=shang/10; if(shang==0) break; }

int i; char *ch; ch=&chuan[0]; chuan1=\

for(i=strlen(ch)-1;i>=0;i--) chuan1=chuan1+chuan[i]; return(chuan1); }

void add_L_four(L *temp)//加一个四元式结点 {

temp->k=L_four_tail->k+1; if(L_four_head->next == NULL) {

L_four_head->next=temp; L_four_tail->next=temp; } else {

L_four_tail->next->next=temp; L_four_tail->next=temp; }

L_four_tail->k=L_four_tail->next->k; }

void add_L_true(L *temp)//加一个true链结点 {

temp->Ltrue=L_true_head->Ltrue; L_true_head->Ltrue=temp; }

void add_L_false(L *temp)//加一个false链结点 {

temp->Lfalse=L_false_head->Lfalse; L_false_head->Lfalse=temp; }

void add_symb(symb *temp)//加一个语义符号表链结点{

if(symb_head->next == NULL) {

temp->addr=0;

symb_head->next=temp;

41

symb_tail->next=temp; } else {

temp->addr=symb_tail->next->addr+4; symb_tail->next->next=temp; symb_tail->next=temp; } }

void output_yuyi() {

//int QQ=0;

if(err==0)//语义分析正确时的输出 {

cout<

system(\ cout<

cout<<\ cout<<\第三部分：语义分析 *\ cout<<\ cout<<\中间代码如下：\ L *temp;

temp=L_four_head->next; while(temp!=NULL) {

cout<<\ （\\）\

temp=temp->next; }

cout<<\其他有用信息如下：\ symb *Stemp;

Stemp=symb_head->next;

cout<<\ type \ id \ identifer \

while(Stemp!=NULL) {

cout<word<<\ int \ 25 \ sv \

Stemp=Stemp->next; } }

if(err==2)//语义分析错误时的输出 {

42

cout<

system(\ cout<

cout<<\ cout<<\第三部分：语义分析 *\ cout<<\

cout<<\语义分析出错：变量\未声明!\ } }

string id_numtoname(int num)//根据编号找变量的名称 {

str *temp; string name;

temp=string_head->next; while(temp!=NULL) {

if(num==temp->num) {

name=temp->word; break; }

temp=temp->next; }

return(name); }

int lookup(string m)//检查变量是否已经声明 {

symb *temp; int i; i=0;

temp=new symb;

temp=symb_head->next; while(temp!=NULL) {

if(m==temp->word) {

i=1; break; }

temp=temp->next; }

return(i); }

///////////////////////////////////////////输出目标代码

43

void outdaima() {

int QQ=0;

if(err==0)//语义分析正确时的输出 {

cout<

system(\ cout<

cout<<\ cout<<\第四 部分：代码生成 *\ cout<<\ cout<<\目标代码如下：\ L *temp;

temp=L_four_head->next; while(temp!=NULL) {

if(temp->op==\ {

cout<<\\

cout<<\\

cout<<\\ }

if(temp->op==\ {

cout<<\\

cout<<\\

cout<<\\ }

if(temp->op==\ {

cout<<\\

cout<<\

\

cout<<\\ }

\\44

if(temp->op==\ {

cout<<\ \\ }

if(temp->op==\ {

cout<<\\

cout<<\\ }

temp=temp->next; }

} }

45

本文来源：https://www.bwwdw.com/article/6uhx.html