IF-ELSE条件语句的翻译程序设计(LL(1)法、输出三地址表示) 2

武汉理工大学《编译原理》课程设计说明书

IF-ELSE条件语句的翻译程序设计

1 问题描述

要求用LL(1)自顶向下分析方法及三地址中间代码，对IF-THEN-ELSE条件语句完成编译各阶段过程，包括词法、语法、语义等分析。

2 问题分析及编译系统的概要设计

编译过程一般分为六个阶段的过程，可以由六个模块完成，它们称为词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序，此外，一个完整编译程序还必须包括“表格管理程序”和“出错处理程序”。

这次实验涉及到词法分析、语法分析、语义分析及表格管理和出错管理。其中，词法分析至少要能识别关键字“if”、“then”和“else”，标识符（即自定义变量），数字，和运算符等等；语法分析要分析程序结构的合法性，即是否为文法的句子；语义分析要能够语法制导翻译出中间代码（三地址）并将其输出；表格管理是指符号表；出错处理是指在语法分析时，所有非文法句子的错误类型处理.

3 文法及属性文法的定义 3.1 文法：

文法是用于描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的、易于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序.

IF-ELSE条件语句的文法如下所示：

0．A->EB

1.B->+EB|-EB|ε 2.E->FT 3.T->*FT|/FT|ε 4.F->i|(E) 或者能够更简洁一点:

0.S->if A THEN B ELSE C 1.A->m rop n 2.B->x=m arop n

1

武汉理工大学《编译原理》课程设计说明书

3.C->x=n arop m 4.rop->=|<|> 5.arop->+|-|*|/

3.2 属性文法：

属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）

配备若干相关的“值”（与文法符号相关的属性）。

在一个属性文法中，对应于每个产生式A→a都有一套与之相关联的语义规则，每规则的形式为：b:=f(c1,c2,?，ck)其中f是一个函数，而且或者①b是A的一个综合属性并且c1,c2,?，ck是产生式右边文法符号的属性或者②非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值。

属性文法为：

if(VT[opr]=='=') //{\判断}； { }

else if(VT[opr]=='>') //{\判断}； { }

2

arr[d][1]=arr_i[opd]; arr[d][0]='='; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++;

arr[d][1]=arr_i[opd]; arr[d][0]='>'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++;

武汉理工大学《编译原理》课程设计说明书

else if(VT[opr]=='<') //{\判断}； { arr[d][1]=arr_i[opd]; arr[d][0]='<'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++;

}

else if(VT[opr]=='+') { arr[d][1]=arr_i[opd]; arr[d][0]='+'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++;

}

else if(VT[opr]=='-') { arr[d][1]=arr_i[opd]; arr[d][0]='-'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++;

}

else if(VT[opr]=='*') {

//{\判断}； //{\判断}； //{\判断}； 3

武汉理工大学《编译原理》课程设计说明书

}

arr[d][1]=arr_i[opd]; arr[d][0]='*'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++;

else if(VT[opr]=='/') //{\判断}； { }

else if(opr==-2) //{其他字符判断}； {

arr[d][1]=id-1; arr[d][1]=arr_i[opd]; arr[d][0]='/'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++;

arr[d][0]=' '; } else

if(VT[opr]!='<'&&VT[opr]!='>'&&VT[opr]!='+'&&VT[opr]!='-'&&VT[opr]!='*'&&VT[opr]!='/')//{\结束符判断}；

{

4

arr[d][2]=arr_i[opd]; arr[d][3]=' '; arr[d][4]=' ';

arr[d][1]=id-1;

武汉理工大学《编译原理》课程设计说明书

d++; }

4 词法分析

首先应该创建一个枚举类型的变量来存放一些关键字：

char VN[11]={'K','L','P','S','E','G','T','R','F','Q','\\0'}; //产名生式头 char VT[16]={'i','=','<','>','+','-','*','/','(',')','f','t','e',';','\\0'}; //特征字符集

再创建一个结构体，用来存放词法分析的结果，共有两个域，一个关键字域，表明

他是什么类型，以及它自身的内容。

这个词法分析程序比较简单，因为本身的程序就局限在if-else语句，所以保留字

的类型我就只写了if、then和else三个；碰到数字开头的除了关键字就是标识符；碰到数字开头的就是数字；碰到界限符和操作符（因为引入的类型也很少），所以也很容易区别。

在词法分析结束之后，就应该把分析的结果输出来。输出的格式是【（单词，类型

编号） 类型名】

源程序文件

字符的分离

单词的判断

查找相应的表

单词的类型的判断

调用不同类型的单词处

理函数进行单词的处理

产生类型码

将中间单词和其类型码存入数组

处理完毕

5

武汉理工大学《编译原理》课程设计说明书

词法分析程序如下： void lexical()

{ //\是其一条特殊的例子 int i,j,d; char ch; j=d=0; for(i=0;var[i]!='#';i++) { ch=var[i]; if(ch=='i'&&var[i+1]=='f') { cout<<\关键字]\ queue[j++]='f';i+=1; }//{判断\关键字} else if(ch=='t') { ch=var[i+1]; if(ch=='h') { ch=var[i+2]; if(ch=='e') { ch=var[i+3]; if(ch=='n') { ch=var[i+4]; } } } cout<<\关键字]\ queue[j++]='t';i+=3; }//{判断\关键字} else if(ch=='e') { ch=var[i+5]; if(ch=='l') { ch=var[i+6]; if(ch=='s') { ch=var[i+7]; if(ch=='e')

6

武汉理工大学《编译原理》课程设计说明书

{ ch=var[i+8]; } } } cout<<\关键字]\ queue[j++]='e';i+=3; }//{判断\关键字} else if(index(ch,VT)<=0) { if(ch!='{'&&ch!='}'&&ch!='('&&ch!=')') { cout<0) { cout<

5 语法分析

主要的思想是设置一个分析栈和一个输入串队列，栈中最开始时存放的是文法开始

符和“#”。因为我这个程序本身已经确定是以if语句开头，所以，就不再把if放在 输入串中，而只是分析if以后的句子。在语法分析之前应该判定该文法是不是一个 LL(1)文法。判别的主要方法是做出文法中所有产生式的select集，对于同一个非终 结符的不同产生式，如果他们的select集合没有交集，则说明这个文法是LL(1)文法。 这个文法的预测分析表也设计的比较简单，如下表所示：

{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1},

{1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 2, -1},

7

武汉理工大学《编译原理》课程设计说明书

{4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {5, -1, -1, -1, -1, -1, -1, -1, 5, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, 6, 7, -1, -1, -1, -1, -1, 8, 8, 8}, {9, -1, -1, -1, -1, -1, -1, -1, 9, -1, -1, -1, -1, -1}, {-1, -1, -1, -1 , 12, 12, 10, 11, -1, -1, -1, 12, 12, 12}, {14, -1, -1, -1, -1, -1,- 1, -1, 13, -1, -1, -1, -1, -1}, {-1, 15, 16, 17, -1, -1, -1, -1, -1, -1, -1,- 1,- 1, -1},

//预测分析表

注：除了-1代表此处有产生式与之对应，具体的产生式在程序中给出。-1代表此处无

产生式与之对应。

void syntax() {

int n; count++; print(); X=stack[sp]; a=queue[front]; if(X=='#'&&a=='#')f=4;

if(X<'A'||X>'Z') //{判断字符集不是大写字母集合} { if(X==a) {

sp--; front++;

if(a!='i') //{\是特征字母} {

if(a!='f'&&a!='t'&&a!='e'&&a!=';'&&a!='#') {

opr=index(a,VT);

8

武汉理工大学《编译原理》课程设计说明书

}

semantic();

else if(a==';'||a=='e'||a=='t'||a=='#') {

opr=-2; }

else f=1; //字符不匹配,转去出错处理 } else {

int tx=index(X,VN);//{索引选择} int ta=index(a,VT);//{索引选择} n=M[tx][ta]; //{产生式选择} td[t++]=M[tx][ta]; //{产生式选择} if(ta==-1) {

f=2;cout<

opd=c;

//cout<

cout<<'\\t'<<'\\''<

cout<<'\\t'<<'\\''<

semantic();

} //字符没有出现在产生式终结符集VT中,转去出错处理 else if(n==-1)f=3; //没有找到合适的候选产生式来做进一步推导,转去出错处理

9

武汉理工大学《编译原理》课程设计说明书

}

else

{ //用产生式M[tx][ta]来做进一步推导 } }

if(f==0)syntax(); else {

td[t]='-1'; err(f); }

sp--;

cout<<'\\t'<

else cout<<\空串\

for(int i=len(p[n])-1;i>=0;i--) { }

cout<

stack[++sp]=p[n][i];

cout<

因为在推导过程中，会一并完成产生式后面附加的语义动作，所以这两部分是一起做的。 另外，在LL(1)分析过程中，会出现错误信息，如字符不匹配，或字符没有出现在产生式终结符集VT中，或没有找到合适的候选产生式来做进一步推导，会调用相应的出错处理函数err(f)。另外，此函数是递归实现，结束标志是f!=0，即成功或失败。

10

武汉理工大学《编译原理》课程设计说明书

11

武汉理工大学《编译原理》课程设计说明书

6 出错处理

由于输入的表达式有错误就要产生相应的出错处理函数

void err(int n) { if(n==1) cout<<\字符不匹配\ else if(n==2) cout<<\字符没有出现在产生式终结符集VT中\ else if(n==3) cout<<\没有找到合适的候选产生式来做进一步推导\ else cout<<\该句子是文法语言的句子！\}

7 语义分析及中间代码输出

根据上面给出的属性文法所规定的翻译方案，即可对输入的程序进行相应的语义分

析。对于中间代码部分，老师给的题目是以三地址的形式输出。对于三地址形式，在学习编译原理的时候接触的不是很多。我们接触的多的一般都是逆波兰式和四元式。仔细看书才发现，三地址和四元式是很相近的。比如说计算一个表达式a+b-c，四元式的形式是（+，a,b,t1）,(-,t1,c,t2)。而三地址的形式为t1:=a+b,t2=t1-c。而对于跳转语句，无条件跳转如jump L1的四元式形式为(jump,-,-,L1)；而其对应的三地址形式为goto L1。而对于条件跳转语句，则四元式为（jrop，a，b，L1），而三地址形式为if a rop b goto L1。

产生跳转的主要有三个地方，第一，就是if条件成立，则跳转到then后面的语局；第二，执行完then后面的语句后跳转到程序的出口；第三，就是if条件不成立则跳转到else后面的语句。在判断完if后面的条件后，保存这个布尔值，并产生跳转地址，这时，应该继续向前读取，如果碰到then这个关键字，则回填地址到then前面，否则报错。

关键是回填地址的那个函数一定要写准确。在有跳转的语句后面，一定要有跳转的地址，即要跳到什么地方。产生跳转的语句有在token这个结构体中有个地址域，用来保存转向的地址。而在产生运算结果的语句中，token这个结构体中有个result域，用来保存这个结果。 //打印词法分析结果

void print()

12

武汉理工大学《编译原理》课程设计说明书

{

cout<<\

if(count<10)cout<<'0'; cout<

for(i=0;i<=sp;i++)cout<

for(;queue[i]!='#';i++)cout<

for(;i<=20;i++)cout<<\}

//语义分析程序 void semantic() {

if(VT[opr]=='=') { arr[d][1]=arr_i[opd]; arr[d][0]='='; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='>') { arr[d][1]=arr_i[opd]; arr[d][0]='>'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='<') { arr[d][1]=arr_i[opd]; arr[d][0]='<'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='+') {

//{\判断}； //{\判断}； //{\判断}； //{\判断}； 13

武汉理工大学《编译原理》课程设计说明书

arr[d][1]=arr_i[opd]; arr[d][0]='+'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='-') //{\判断}； { arr[d][1]=arr_i[opd]; arr[d][0]='-'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='*') //{\判断}； { arr[d][1]=arr_i[opd]; arr[d][0]='*'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='/') //{\判断}； { arr[d][1]=arr_i[opd]; arr[d][0]='/'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(opr==-2) //{其他字符判断}； { arr[d][1]=id-1; arr[d][0]=' '; arr[d][2]=arr_i[opd]; arr[d][3]=' '; arr[d][4]=' '; } else

if(VT[opr]!='<'&&VT[opr]!='>'&&VT[opr]!='+'&&VT[opr]!='-'&&VT[opr]!='*'&&VT[opr]!='/')//{\结束符判断}；

14

武汉理工大学《编译原理》课程设计说明书

arr[d][1]=id-1; { d++; } }

//输出三地址

cout<<\输出三地址:\ for(i=0;i=0&&arr[i][j]<=9) cout<<\ else cout<

而三元式的输出则很简单。但也要根据它具体的语义来进行输出。如果是if语句，则要根据if后面的bool语句来实现跳转。如果为真，应该调到then后面的语句，如果为假，则跳转到else后面的语句，每个语句都有自己的标号，用label来标识。而对于每个计算结果的表达式，则首先用一个中间变量来存放结果，每次按照运算符的优先级算出一个结果，保存在中间变量中，最后将中间变量的结果赋给语句中的变量。

8 软件测试方法和结果

输入一组正确的词法和语法的if-else语句，和一组有词法错误和语法错误的if语句。

1. if {m>n} then i=i+3

else

b=b/2 测试结果如下：

15

武汉理工大学《编译原理》课程设计说明书

char queue[MAX]; int sp,front;

int M[10][14]={ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,-1,-1,-1}, {1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 3, 2,-1}, {4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, {5,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,6,7,-1,-1,-1,-1,-1, 8, 8, 8}, {9,-1,-1,-1,-1,-1,-1,-1,9,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,12,12,10,11,-1,-1,-1,12,12,12}, {14,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,-1,-1,-1}, {-1,15,16,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, }; //预测分析表 int f=0; int count=0; int c=0;

char arr_i[MAX]; //字符管理 char var[MAX]; //表格管理

int td[MAX]; //输出产生式序列 int t=0; int opd=-1; int opr=-1; int id=0;

//int ptr[MAX]; int d=0;

char arr[MAX][5]; //存放待输出的三地址 //char keyword[2][11]={\

int len(char str[]) { int i=0; while(str[i]!='\\0')i++; return i; }

int index(char ch,char str[]) { int i=0; while(str[i]!='\\0') { if(ch!=str[i])i++; else break; } if(str[i]=='\\0')return -1; return i;

21

武汉理工大学《编译原理》课程设计说明书

}

//出错管理选项 void err(int n) { if(n==1) cout<<\字符不匹配\ else if(n==2) cout<<\字符没有出现在产生式终结符集VT中\ else if(n==3) cout<<\没有找到合适的候选产生式来做进一步推导\ else cout<<\该句子是文法语言的句子！\}

//打印此法分析结果 void print() { cout<<\ if(count<10)cout<<'0'; cout<

//语义分析程序 void semantic() { if(VT[opr]=='=') //{\判断}； { arr[d][1]=arr_i[opd]; arr[d][0]='='; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; } else if(VT[opr]=='>') //{\判断}； { arr[d][1]=arr_i[opd];

22

武汉理工大学《编译原理》课程设计说明书

arr[d][0]='>'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='<') //{\判断}； { arr[d][1]=arr_i[opd]; arr[d][0]='<'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='+') { arr[d][1]=arr_i[opd]; arr[d][0]='+'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='-') { arr[d][1]=arr_i[opd]; arr[d][0]='-'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='*') { arr[d][1]=arr_i[opd]; arr[d][0]='*'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(VT[opr]=='/') { arr[d][1]=arr_i[opd];

//{\判断}； //{\判断}； //{\判断}； //{\判断}；23

武汉理工大学《编译原理》课程设计说明书

arr[d][0]='/'; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; } else if(opr==-2) //{其他字符判断}； { arr[d][1]=id-1; arr[d][0]=' '; arr[d][2]=arr_i[opd]; arr[d][3]=' '; arr[d][4]=' '; } else

if(VT[opr]!='<'&&VT[opr]!='>'&&VT[opr]!='+'&&VT[opr]!='-'&&VT[opr]!='*'&&VT[opr]!='/')//{\结束符判断}； arr[d][1]=id-1; { d++; } }

//语法分析程序 void syntax() { int n; count++; print(); X=stack[sp]; a=queue[front]; if(X=='#'&&a=='#')f=4; if(X<'A'||X>'Z') //{判断字符集不是大写字母集合} { if(X==a) { sp--; front++; if(a!='i') //{\是特征字母} { if(a!='f'&&a!='t'&&a!='e'&&a!=';'&&a!='#') { opr=index(a,VT); semantic(); }

24

武汉理工大学《编译原理》课程设计说明书

else if(a==';'||a=='e'||a=='t'||a=='#') {

opr=-2; semantic(); } cout<<'\\t'<<'\\''<=0;i--) { stack[++sp]=p[n][i]; cout<

if(f==0)syntax(); else

25

武汉理工大学《编译原理》课程设计说明书

{ td[t]='-1'; err(f); } }

//测法分析程序 void lexical()

{ //\是其一条特殊的例子 int i,j,d; char ch; j=d=0; for(i=0;var[i]!='#';i++) { ch=var[i]; if(ch=='i'&&var[i+1]=='f') { cout<<\关键字]\ queue[j++]='f';i+=1; }//{判断\关键字} else if(ch=='t') { ch=var[i+1]; if(ch=='h') { ch=var[i+2]; if(ch=='e') { ch=var[i+3]; if(ch=='n') { ch=var[i+4]; } } } cout<<\关键字]\ queue[j++]='t';i+=3; }//{判断\关键字} else if(ch=='e') { ch=var[i+5]; if(ch=='l') { ch=var[i+6];

26

武汉理工大学《编译原理》课程设计说明书

if(ch=='s') { ch=var[i+7]; if(ch=='e') { ch=var[i+8]; } } } cout<<\关键字]\ queue[j++]='e';i+=3; }//{判断\关键字} else if(index(ch,VT)<=0) { if(ch!='{'&&ch!='}'&&ch!='('&&ch!=')') { cout<0) { cout<

//主函数

int main() //主程序 { int i=0; char S='K'; sp=front=0; stack[0]='#'; sp++; stack[1]='K'; cout<<\

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\

27

武汉理工大学《编译原理》课程设计说明书

cout<<\ | IF-ELSE条件语句的翻译程序设计(LL(1)法、输出三地址表示) |\ cout<<\ | made by Jebb Xu|\ cout<<\

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ cout<\\n(4)S->iQE\\n(5)E->TG\\n(6)G->+TG\\n\\\n(9)T->FR\\n(10)R->*FR\\n(11)R->/FR\\n(12)R->ε\\n(13)F->(E)\\n\ <<\ cout<<\请输语句(如:'if{m>n}theni=i+3elseb=b/2#'):\ do { cin>>var[i]; i++; if(var[i]==' ')i--; }while(var[i-1]!='#'); var[i]='\\0'; cout<<\词法分析:\ lexical();//词法分析程序 cout<<\语法分析:\ syntax();//语法分析程序 cout<<\所用产生式序列:\ for(i=0;td[i]!='-1';i++)cout<=0&&arr[i][j]<=9) cout<<\ else cout<

εε

28

本文来源：https://www.bwwdw.com/article/1vx6.html