《编译原理》实验指导书.doc

《编译原理》实验指导书

《编译原理》课程实验指导书
（Compiler Principle）

软件工程专业2014

孙金庆 编写

华信软件学院

2017年4月

35 / 37
目录
序言 1
实验安排 2
第一次实验：编译器的词法分析器 2
第二次实验：编译器的语法分析器 10

序言
本《编译原理》实验指导，其目的是让大家动手设计和实现规模适中的语言的词法分析器、语法分析器和编译代码生成器，该编译器不仅涉及编译程序的各个阶段，而且也强调了编译的总体设计、各个阶段的接口安排等等。
通过上机实践，来设计这个相对完整的编译器，一方面可以使同学们增加对编译程序的整体认识和了解——巩固《编译原理》课程所学知识，另一方面，通过上机练习，学生也可以学到很多程序调试技巧和设计大型程序一般的原则，如模块接口的协调，数据结构的合理选择等等。
实验安排
第一次实验：编译器的词法分析器（学时：4）
词法分析器实验样本
C．1.1 实验目的
设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。
C．1.2实验要求
C．1.2.1待分析的简单语言的词法
（1）关键字：
bengin if then while do end
所有的关键字都是小写。
（2）运算符和界符：
：= + - * / < <= <> > >= = ; ( ) #
（3）其他单词是标志符（ID）和整形常数（NUM），通过以下正规式定义：
ID=letter（letter|digit）*
NUM=digit digit*
（4）空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM、运算符、界符和关键字，词法分析阶段通常被忽略。

C．1.2.2各种单词符号对应的种别码

单词符号
种别码

单词符号
种别码
begin
1
：
17
if
2
：=
18
then
3
<
20
while
4
<>
21
do
5
<=
22
end
6
>
23
Letter(letter|digit)
10
>=
24
digit digit *
11
=
25
+
13
;
26
-
14
(
27
*
15
)
28
/
16
#
0

C．1.2.3词法分析程序的功能

输入：所给文法的源程序字符串。
输出：二元组（syn，token或sum）构成的序列。
其中：syn为单词种别码；
token为存放的单词自身字符串；
sum为整形常数。
例如：对源程序
begin x:=9; if x>0 then x:= 2*x+1/3; end #
的源文件，经词法分析后输出如下序列：
（1， begin）（10，’x’）(18,:=) ( 11,9) (26,;) (2,if)…
功能测试：
（1） 输入字符串begin x:=9; if x>0 then x:= 2*x+1/3; end #
其结果如下图所示：

（2）输入字符串if x>2; y=3; end #其结果如下图所示：

（3）输入字符串where#其输出结果如下图所示：

（4）输入字符串1234#其结果显示如下：

C．1.3 词法分析程序的基本思想
算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想示根据扫描到单词符号的第一字符的种类，拼出相应的单词符号。
1. 主程序示意图
主程序示意图如图C。1所示。其中初值包括如下两个方面：
（1） 关键字表的初值。
关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：
char * rwtab[6]{“begin ”,”if”,”then”,”while”,”do”,”end”};

图C.1 词法分析主程序示意图
（2） 程序中需要用到的主要变量为syn，token和sum。
2. 扫描子程序的算法思想
首先设置3个变量：a.token用来存放构成单词符号的字符串；b.sum用来存放整形单词；c.syn用来存放单词符号的种别码。扫描子程序主要部分流程如图C.2所示。

图C.2 词法分析程序流程
C.1.4 词法分析程序源代码
#include<stdio.h>
#include<string.h>

char prog[80],token[6];
char ch;
int syn,p,m,n,sum;
char * rwtab[6]={"begin","if","then","while","do","end"};
main()
{
p=0;
printf("\nplease intput string:");
do
{
ch=getchar();
prog[p++]=ch;
}while(ch!='#');
p=0;
do
{
scaner();
switch(syn)
{
case 11:printf("(%d,%d)",syn,sum);break;
case -1:printf("input error\n"); break;
default:printf("(%d,%s)",syn,token);
}
}while(syn!=0);
getch();
}

/*词法扫描程序：*/
scaner()
{
for(n=0;n<8;n++)
token[n]=NULL;
m=0;
ch=prog[p++];
while(ch==' ')ch=prog[p++];
if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A'))
{
while((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')||(ch<='9'&&ch>='0'))
{
token[m++]=ch;
ch=prog[p++];
}
token[m++]='\0';
ch=prog[--p];
syn=10;
for(n=0;n<6;n++)
if(strcmp(token,rwtab[n])==0)
{
syn=n+1;
break;
}
}
else
if((ch<='9'&&ch>='0'))
{
sum=0;
while((ch<='9'&&ch>='0'))
{
sum=sum*10+ch-'0';
ch=prog[p++];
}
ch=prog[--p];
syn=11;
}
else
switch(ch)
{
case '<':m=0;token[m++]=ch;
ch=prog[p++];
if(ch=='>')
{
syn=21;
token[m++]=ch;
}
else
if(ch=='=')
{
syn=22;
token[m++]=ch;
}
else
{
syn=20;
ch=prog[--p];
}
break;
case '>':token[m++]=ch;
ch=prog[p++];
if(ch=='=')
{
syn=24;
token[m++]=ch;
}
else
{
syn=23;
ch=prog[--p];
}
break;
case ':':token[m++]=ch;
ch=prog[p++];
if(ch=='=')
{
syn=18;
token[m++]=ch;
}
else
{
syn=17;
ch=prog[--p];
}
break;
case '+':syn=13;token[0]=ch;break;
case '-':syn=14;token[0]=ch;break;
case '*':syn=15;token[0]=ch;break;
case '/':syn=16;token[0]=ch;break;
case ':=':syn=18;token[0]=ch;break;
case '<>':syn=21;token[0]=ch;break;
case '<=':syn=22;token[0]=ch;break;
case '>=':syn=24;token[0]=ch;break;
case '=':syn=25;token[0]=ch;break;
case ';':syn=26;token[0]=ch;break;
case '(':syn=27;token[0]=ch;break;
case ')':syn=28;token[0]=ch;break;
case '#':syn=0;token[0]=ch;break;
default:syn=-1;
}
}

C．1.5 实验心得体会：

……
……

第二次实验：编译器的语法分析器（学时：4）
词法分析器实验样本
1.2预期目标
熟练掌握运用VC++建立工程，并用VC++语言进行程序编写，掌握编程思想和算法。熟练掌握LL(1) 文法的分析方法，利用FIRST集合、FOLLOW集合以及SELECT集合得到预测分析表，并且各集合的计算方法也是设计的目标。
1.3解决问题
(1)对于一个输入文法，消除文法的左递归；
(2)理解计算FIRST、FOLLOW集合和SELECT集合的方法；
(3)理解文法分析表的构造。
2 系统分析
2.1涉及的知识基础
2.1.1 LL(1)文法
LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。一个用来描述语言语法结构的文法G[2]可形式地定义如下：
一个文法G[S]可表示成形如(VN，VT，P，S)的四元式。其中VN，VT，P均为非空的有限集，分别称为非终结符集、终结符集和产生式集。具体来说：
VN，一系列需要定义的语法范畴。
VT，若干基本符号，不需要进一步定义。
P，用“->“连接起来的有序对(A,α)的集合，称为规则，也叫产生式。其中A是一个非终结符，α是一个由终结符或非终结符组成的符号串，即α∈(VN∪VT)*。
S， 是文法的开始符号。S∈VN
此外 ，我们还将出现在产生式左、右侧的全部符号的集合称为词汇表，记为V。显然：V=VN∪VT；VN∩VT =φ。
更确切地说，上面给出的是上下文无关文法的定义。这是因为由符号串a去替换A时，并不考虑A所处的环境，即及A的上下文无关。除非另做说明，我们以后所说的文法均指上下文无关文法。
LL(1)的含义：
l 第一个L表示从左至右扫描输入符号串
l 第二个L表示生成输入串的一个最左推导
l 1表示在决定分析程序的每步动作时，向前看一个符号
2.1.2确定的自顶向下分析思想
LL(1)文法是一类可以进行确定的自顶而下语法分析的文法。而自顶而下分析法的基本思想是从文法的开始符号出发采用最左推导，根据当前的输入符号(单词符号)惟一地确定选用哪个产生式替换相应非终结符以下推导。这种分析过程实质是一种试探过程，是反复使用不同产生式匹配输入符号串的过程。
若有文法：S->cAd
A->ab|a
输入串W=cad。为建立分析树，首先建立只有标记S单个结点树，输入指针指向W的第一个符号c。然后用S的第一个产生式来扩展该树，得到的树如图2.1所示：
S
c
A
d
S
c
A
dS
a
b
S
c
A
d
a
(a)
(b)
(c)

图2.1.1语法分析树
最左边的叶子标记为c，匹配W的第一个符号。于是，推进输入指针到W的第二个符号a，并考虑下一个标记为A的叶子。用A的第一个选择来扩展A，得到如图(b)的树。现在匹配第二个输入符号a，再推进输入指针到d，把它和下一个标记为b的叶子比较。因为b和d不匹配，报告失败，回到A，看它是否还有别的选择尚未尝试。在回到A时，必须重置指针于第二个符号，即第一次进入A的位置。现在尝试A的第二个选择，得到图(c)的分析树。叶子a匹配W的第二个符号，叶子d匹配W的第三个符号。这样，产生了W的分析树，从而宣告分析完全成功。
2.1.3 左递归的消除
直接消除产生式中的左递归是比较容易的。假定关于非终结符P的规则为P->Pa|b其中，P是开头。那么我们可以把P的规则改写为如下的非直接左递归形式：P->bR
R->aR|ε (ε为空字)
这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。
一般而言，假定P关于的全部产生式是P->Pα1|Pα2|…|Pαm|1| 2|…|n其中，每个αi(1≤i≤m)都不等于ε，1~n都不以P开头，那么消除P的直接左递归就是把这些规则改写成：  P->1R| 2R|…| nR
                R->α1R|α2R|…αmR|ε
使用这个方法，我们容易把见诸于表面的所有直接左递归都消除掉，也就是说，把直接左递归都改成直接右递归。对于间接左递归的消除需先通过产生式非终结符置换，把间接左递归变成直接左递归。
例如有文法：S->Aα| β    (1)
            A->Sγ      (2)
因为S=>Aα=>Sγα，所以S是一个间接递归的非终结符。为了消除这种间接左递归将(2)式代人(1)式，即可得到及原方法等价的方法: S->Sγα|β (3)
(3)式是直接左递归的，可以采用消除直接左递归的方法对文法进行改写，可的文法：S->βS’
       S’->γαS’|ε
由此可见，为了消除间接左递归，可首先查出那些具有左递归的非终结符号，然后对以这些非终结符为左部的产生式，通过逐步置换有关产生式的方法将它们化为直接左递归的产生式。最后在消除其中的全部直接左递归。
2.1.4消除回溯、提左因子
   为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个侯选去执行任务，并且次侯选的工作结果是确信无疑的。也就是说，若此侯选获得成功匹配，那么，这种匹配不会是虚假的；若此侯选无法完成任务，则任何其它侯选也肯定也无法完成任务。换句话说，假定现在轮到非终结符A去执行匹配任务，A共有n个侯选α1，α2，……αn,即A->α1|α2|……αn。A能够根据不同的输入符号指派相应的αi作为全权代表去执行任务，那就肯定无需回溯了。在这里A已不再是让某个侯选去试探地执行任务，而是根据所面临的输入符号α准确地指派唯一的一个侯选。其次，被指派侯选的工作成败也完全代表了A。
2.1.5 计算FIRST集合、FOLLOW集合和SELECT集合
FIRST集合：
令G[S]=(VT,VN,S,P),则
FIRST(a)={ a | a Þ * ab,a∈VT ,a、b∈V*}、
－若a Þ* ε，则ε∈FIRST(a)
－对每以文法符号X，计算FIRST(X)过程如下：
(a)若X∈VT ,则FIRST(X)={X}；
(b)若X∈VN,且有产生式X®a…,a∈VT,则把a加入到FIRST(X)中；
(c)若X∈VN ,若X®e也是一条产生式,则把e也加到FIRST(X)中；
(d)若X∈VN,有产生式X®Y1Y2…Yn,Y1,…Yi都是非终结符，对于任何j，1≤j≤i-1，FIRST(Yj)都含有ε，则把FIRST(Yj)中的所有非ε元素都加到FIRST(X)中； FIRST(Yi)的元素加入到FIRST(X)
－特别地，若所有的FIRST(Yj , j=1,2,…,n)均含有e,则把e ,FIRST(Yj)中的所有非ε元素都加到FRIST(X)中。
FOLLOW集合：
设G[S]=(VT,VN,S,P)是上下文无关文法,
(a)设S为开始符号,则#∈FOLLOW(S)
(b)若有产生式A® aBb，b *Þ ε
则FIRST(b)ÌFOLLOW(B)
(C)若b Þ ε(可理解为A® aB)则FIRST(b)-{ε}∪FOLLOW(A)Ì FOLLOW(B)
SELECT集合：
A® a的可选集SELECT
aÞε，则SELECT(A®a)=FIRST(a)
aÞε，则SELECT(A®a)=(FIRST(a)-{ε})∪ FOLLOW(A)
2.2 解决问题的基本思路
首先根据一定的规则输入一个合法的文法，化简成LL(1)文法，利用一定的算法消除文法中的左递归，然后再利用首先预定的规则计算出FIRST和FOLLOW集合，以及算出SELECT集合，然后就是显示出LL(1)文法的分析表。最后一步是输入一串字符串，然后对字符串进行分析，输出分析过程表，这样系统就成形了。
2.3 功能模块框图
初始数据
产生式处理
计算机FOLLOW集合
显示预测分析表
图2.3 功能模块框图
输入文法

3 系统设计
语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的一个问题。
其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。
3.1 LL(1)文法输入设计
标准的文法有一定的规则，若在设计过程中，输入的文法不正确，则不能正确的实现程序功能，所以首先在编写程序时，要对输入文法进行限制，规则如下：
(1) 大写英文字母表示非终结符，所以产生式左部一定要输入大写字母；
(2) e表示空产生式；
(3) 除大写字母、#、'、| 外的单字符表示终结符，所以产生右部不能包括以上几个字符；
(4) 不能出现递归文法。(如 S->S或S->A, A->S;)；
(5) 不能出现多余文法规则。(如 S->A，A不是非终结符)；
(6) 文法产生式长度不超过10个字符。
3.2 LL(1)语法分析详细流程图
我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，其结构图如图3.2。

开始操作
读源程序字符
常数分析程序
关键字标识符分析程序
其它单词分析程序
输出单词内部表示
开始
结束
是字母?
有字符?
是数字?
Y
Y
Y
N
N
N
图3.2 LL(1)语法分析详细流图

3.3算法描述
3.3.1 消除左递归的算法
(1) 把文法G的所有非终结符按任一种顺序排列成P1，P2,……Pn;按此顺序执行；
(2)  FOR  i:=1  TO   n    DO
BEGIN
          FOR  j:=1   TO   i-1   DO
                把形如Pi->Pjγ产生式变为Pj->δ1|δ2|…|δk关于Pj的所有规则
消除关于Pi规则的直接左递归性
       END
(3) 化简由(2)所得的文法。即去除那些从开始符号出发永远也无法到达的非终结符的产生规则。
3.4系统流程图
整个程序可分为如下几步：
(1) 读入文法；
(2) 判断正误；
(3) 若无误，判断是否为LL(1)文法；
(4) 若是，构造分析表；
(5) 由总控算法判断输入符号串是否为该文法的句型。

图3.4.1 程序主流程图

图3.4.2消除左递归流程图

4 代码编写
4.1相关代码
/*******************************************
分解含有左递归的产生式
********************************************/
void recur(char *point)
{/*完整的产生式在point[]中*/
int j,m=0,n=3,k;
char temp[20],ch;
ch=c();/*得到一个非终结符*/
k=strlen(non_ter); /*非终结符号长度*/
non_ter[k]=ch;//得到最后一个非终结符号
non_ter[k+1]='\0';
for(j=0;j<=strlen(point)-1;j++)
{
if(point[n]==point[0])
{ /*如果‘|’后的首符号和左部相同，含直接左递归*/
for(j=n+1;j<=strlen(point)-1;j++)
{
while(point[j]!='|'&&point[j]!='\0')
temp[m++]=point[j++];
left[count]=ch;
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
m=0;
count++;
if(point[j]=='|')
{
n=j+1;
break;
}
}
}
else
{ /*如果‘|’后的首符号和左部不同*/
left[count]=ch;
right[count][0]='^';
right[count][1]='\0';
count++;
for(j=n;j<=strlen(point)-1;j++)
{
if(point[j]!='|')
temp[m++]=point[j];
else
{
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
printf(" count=%d ",count);
m=0;
count++;
}
}
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
count++;
m=0;
}
}
}

/*******************************************
分解不含有左递归的产生式
********************************************/
void non_re(char *point)
{
int m=0,j;
char temp[20];
for(j=3;j<=strlen(point)-1;j++)
{
if(point[j]!='|')
temp[m++]=point[j];
else
{
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]='\0';
m=0;
count++;
}
}
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]='\0';
count++;
m=0;
}
/*******************************************
总控算法
********************************************/
void syntax()
{
int i,j,k,m,n,p,q;
char ch;
char S[50],str[50];
printf("请输入该文法的句型：");
scanf("%s",str);
getchar();
i=strlen(str);
str[i]='#';
str[i+1]='\0';
S[0]='#';
S[1]=start;
S[2]='\0';
j=0;
ch=str[j];
while(1)
{
if(in(S[strlen(S)-1],termin)==1)
{
if(S[strlen(S)-1]!=ch)
{
printf("该符号串不是文法的句型！");
return;
}
else if(S[strlen(S)-1]=='#')
{
printf("该符号串是文法的句型.");
return;
}
else
{
S[strlen(S)-1]='\0';
j++;
ch=str[j];
}
}
else
{
for(i=0;;i++)
if(non_ter[i]==S[strlen(S)-1])
break;
for(k=0;;k++)
{
if(termin[k]==ch)
break;
if(k==strlen(termin))
{
printf("词法错误！");
return;
}
}
if(M[i][k]==-1)
{
printf("语法错误！");
return;
}
else
{
m=M[i][k];
if(right[m][0]=='^')
S[strlen(S)-1]='\0';
else
{
p=strlen(S)-1;
q=p;
for(n=strlen(right[m])-1;n>=0;n--)
S[p++]=right[m][n];
S[q+strlen(right[m])]='\0';
}
}
}
printf("符号栈:%s 剩余字符串:",S);
for(p=j;p<=strlen(str)-1;p++)
printf("%c",str[p]);
printf(" \n");
}
}
4.2运行结果
编译调试，运行程序。输入文法，如图4.2.1，按回车键得到分析结果，如图4.2.2，判断其是否为LL(1)文法，并得到该文法的分析表；输入该文法的句型，回车得到句型的预测分析过程，如图4.2.3，再次输入不是该文法的句型，如图4.2.4

图4.2.1

图4.2.2

图4.2.3

图4.2.4

C．1.5 实验心得体会：

……
……
……