编译原理实验报告——词法分析器和LL(1)文法.doc

《编译原理》综合性
实 验 报 告

实验学期 2016 至 2017 学年 第 1 学期
专业 计算机科学与技术 班级 1403
学生姓名 黄世增 学号 1411640305
任课教师 赵曦
实验成绩

《编译原理》课程综合性实验报告

开课实验室：C210 2016年 12月 6日
实验题目
词法分析器的设计
一、实验目的
通过设计、编制、调试一个具体的词法分析程序，实现对高级程序设计语言源程序进行扫描， 并将其分解为各种单词的词法分析方法；加深对课堂教学的理解；提高词法分析方法的实践能力。
二、实验要求
任选一种高级程序设计语言编程完成词法分析器。词法分析器应以教材所述分词原理为依据，使用恰当的数据结构和方法，结构清晰、高效。
编制一个读单词过程，源程序保存在文本文件中（也可键盘输入），读取该文件，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、分界符五大类。依次输出各个单词的内部单词种别及单词符号自身值，遇到错误时可显示“Eorror”，然后跳过错误部分继续显示。
二、实验设备与环境
1．硬件：PC机Pentium100以上。
2．软件：Win10，VS2010。
三、实验内容
1．正规文法
<关键字>-> int |for| while | do | return | break | continue
<运算符和界符>-> |+ | - | * | / |==| < | <= |!= | > | >= | , | ; | ( | ) | {|}
<标识符>-> letter (letter | digit)*
<整型常数>-> digit digit*
2．算法思想
算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼接出相应的单词符号。
2.1 主程序

置初值

调用扫描子程序

将结果存入结构体

输入串结束
否

是
输出单词二元组

结束

图1 词法分析主程序示意图

其中初始包括关键字、运算符、界限符的置初值。
2.2 扫描子程序的算法思想：
在词法分析中，先以只读方式读取一个文件，自文件头开始扫描文本，滤去开头的空格、回车符、换行符等。读取的字符送入word。扫描第一个字符，看匹配的类型，并进行相应的类型分析，满足判断类型时，输出其种别码和值。

忽略空格

text是否扫描结束

返回
是 是

否
字母
拼字符串
数字 其他
运算符、 符号
界符等符号
是否关键字？
返回
拼数

否
（4/5，单词自身值）

报错

（2，单词自身值）
是

（1，单词自身值）

（3，单词自身值）

图 2 扫描子程序

四、实验步骤
编写程序时，先定义几个全局变量，key[]事先存放7个关键字，words[]用来存放识别出来的单词二元组，text用来存放从文件读取的内容，word用于存放识别出来的单词，length存放字符个数，k存放识别出来的单词个数。
首先，将文本内容读取到text中，文本内容最后一个字符是空白符，然后调用scan方法，逐个扫描每个字符，如果word的第一个字符是字母，则进行拼字符串，再判断是关键字还是标识符；如果word的第一个字符是数字，则在word清空之前判断是否有识别出非数字字符，若有，则出错，若没有，则识别出来的字符串是常数；若word第一个字符是运算符或界限符，则各自存到words[]中。最后扫描结束后输出。
五、实验结果及分析

六、实验小结和思考
通过这次实验，我对词法分析器有了进一步的了解，而且对词法分析和语法分析在实践中的应用有了深入的掌握, 让我对高级语言的学习有了更深的认识 ，了解得更透彻。
七、源程序清单

#include<stdio.h>
#include<stdlib.h>
#include<string>
using namespace std;
#define MAX 10000

struct WordString
{
string Word;//单词
int category;//类别
};

char *key[7] = {"int","for", "while", "do", "return", "break", "continue"};//关键字
WordString words[MAX]; //创建一个单词符号串
string text; //读入的文本存入text中
string word; //分割出的单词用word表示
int length; //字符个数
int k; //总单词个数

void scan()
{
int i,j;
k=0;
word="";
for(i=0;i<=length-1;i++)
{
if(word!=""){
if(((word[0]>='A')&&(word[0]<='Z'))||((word[0]>='a')&&(word[0]<='z')))//首字符是字母
{
if(((text[i]>='A')&&(text[i]<='Z'))||((text[i]>='a')&&(text[i]<='z'))||((text[i]>=48)&&(text[i]<=57)))
{
word+=text[i];
}
else
{
words[k].Word=word;
for(j=0;j<7;j++)
{
if(words[k].Word==key[j])
{
words[k].category=1;//表示关键字
break;
}
else if(j==6)
words[k].category=2;//表示标识符
}
k++;
word="";
i--;
}
}
else if(word[0]==','||word[0]==';'||word[0]=='{'||word[0]=='}'||word[0]=='('||word[0]==')')//首字符是界限符
{
words[k].Word=word;
words[k].category=5;//表示界限符
k++;
word="";
i--;
}
else if(word[0]=='+'||word[0]=='-'||word[0]=='*'||word[0]=='/'||word[0]=='='||word[0]=='>'||word[0]=='<'||word[0]=='!')//首字符是运算符
{
if(text[i]=='=')
{
word+=text[i];
words[k].Word=word;
words[k].category=4;//表示运算符
k++;
word="";
}
else
{
words[k].Word=word;
words[k].category=4;//表示运算符
k++;
word="";
i--;
}
}
else if(word[0]>=48&&word[0]<=57)//首字符是数字
{
if(text[i]>=48&&text[i]<=57)
{
word+=text[i];
}
else if((text[i]>='A'&&text[i]<='Z')||(text[i]>='a'&&text[i]<='z'))
{
word+=text[i];
words[k].category=6;//表示出错，标识符以数字开头
}
else
{
words[k].Word=word;
if(words[k].category!=6)
words[k].category=3;//表示常数
k++;
word="";
i--;
}
}
}
else
{
if(text[i]!=10&&text[i]!=32&&text[i]!=9)
{
word+=text[i];
}
}
}
}

int main()
{
FILE *fp; //文件指针
fp=fopen("text.txt","r"); //打开文件
if(fp==NULL)
{
printf("Can't open this file!\n");
exit(0);
}
int i=0;
while(!feof(fp)) //判断是否到文件结尾
{
text+=fgetc(fp);
i++;
}
length=i;//text最后一个字符是空字符
fclose(fp); //关闭文件
scan();
for(i=0;i<k;i++) //输出
{
if(words[i].category==6)
printf("%s Eorror\n",words[i].Word.c_str());
else
printf("(%d, %s)\n",words[i].category,words[i].Word.c_str());
}
getchar();
return 0;
}

开课实验室：C210 2016年 12月 8日
实验题目
语法分析——LL(1)语法分析方法的实现
一、实验目的
通过设计、开发一个高级语言的LL（1）语法分析程序，实现对源程序的语法检查和结构分析，加深对相关课堂教学内容（包括自顶向下语法分析、First集、Follow集、Select集、判断LL（1）文法的方法、文法等价变换、LL(1)分析表的构造、对某一输入串的分析过程的理解，提高语法分析方法的实践能力。
二、实验要求
消除直接左递归前的文法       消除直接左递归后的等价文法
 G [E]：E→E+T                        G’[E]： E→TE’
     E→T                                  E’→+TE’|ε
     T→T*F                                T→FT’
     T→F                                  T’→*FT’|ε
     F→(E)|i                             F→(E)|i

根据文法建立LL(1)分析表，并对输入串i+i*i进行语法分析，判断其是否是合法的句子，给出句子的分析过程。
具体要求如下：
1、理解语法分析在编译程序中的作用；
2、理解LL(1)语法分析方法对文法的要求(必须是LL(1)文法)；
3、理解LL(1)分析器模型；
4、熟练掌握文法变换方法(消除直接左递归和提取左公共因子)。
5、熟练掌握Select集合的求解方法和LL(1)分析表的构造方法；
二、实验设备与环境
1．硬件：PC机Pentium100以上。
2．软件：Win10，VS2010。
三、实验内容
给定一个上下文无关文法G，在LL(1)语法分析方法中，必须先求出Select集，通过Select集判断是否是LL(1)文法，若是，则构造预测分析表。求出预测分析表之后，键盘输入一个字符串，依据LL(1)分析表单步输出字符串的分析过程。
四、实验步骤

输入字符串
和初始符号栈

符号栈大小大于等于0？

N

待分析字符是否为合法字符？
Y
Y N

栈顶字符是否为合法字符？

Y N
待分析字符是否和符号栈栈顶字符相等？

N Y
待分析字符和栈顶字符同时为“#”
对照分析表判断采用产生式

Y
分析成功
产生式右部为空？

Y N
匹配分析字符分析下一个字符
弹出栈顶符号，不压入栈

弹出栈顶符号，产生式右部逆序入栈
N
修改栈大小

修改栈大小

五、实验结果及分析

六、实验小结和思考
本实验加深了我对 LL(1)分析法的算法和思想的理解。
七、源程序清单
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

/*1:E->TE' 2:E'->+TE' 3:E'->ε? 4:T->FT' 5:T'->*FT' 6:T'->ε? 7:F->(E) 8:F->i*/
int ll1[5][6]={{1,0,0,1,0,0},
{0,2,0,0,3,3},
{4,0,0,4,0,0},
{0,6,5,0,6,6},
{8,0,0,7,0,0}};//表示LL(1)分析表内容

int main()
{
char ch[10]={'#','E'}; //用于存放符号栈内容
char str[10]; //存放输入串
char str1[10]; //用于存放最初输入的字符串
char cha; //分析字符
int i,j,m,n; //j：终结符所代表数字;m：非终结符所代表数字;n：产生式右部大小
int l=1; //符号栈大小
int k=1; //分析输入串的第几个字符
int how; //利用哪个产生式
int step=1; //步骤
int length=0;

printf("请输入一串字符串，以#结尾:");
do
{
scanf("%c",&cha);
str[length]=cha;
str1[length]=cha;
length++;
}while(cha!='#');
printf("步骤\t符号栈\t\t输入串\t\t所用产生式\n");
do
{
cha=str1[k-1];
printf("%d\t",step);
for(i=0;i<=l;i++)
printf("%c",ch[i]); //输出符号栈
printf("\t\t");
for(i=k-1;i<length;i++)
printf("%c",str[i]);
printf("\t\t");
switch(cha)
{
case 'i':
j=0;break;
case '+':
j=1;break;
case '*':
j=2;break;
case '(':
j=3;break;
case ')':
j=4;break;
case '#':
j=5;break;
defult:
j=-1;break;
}
if(j!=-1) //正确的字符
{
if(ch[l]!=cha)
{
if(ch[l]!=39)
{
switch(ch[l])
{
case 'E':
m=0;break;
case 'T':
m=2;break;
case 'F':
m=4;break;
default:
m=-1;break;
}
}
else
{
switch(ch[l-1])
{
case 'E':
m=1;break;
case 'T':
m=3;break;
default:
m=-1;break;
}
}
}
if(m!=-1)
{
if(ch[l]!=cha)
{
how=ll1[m][j];
if(how==1)
{
printf("E->TE'\n");
n=3;
l=l+n-1;
ch[l]='T';
ch[l-1]=39;
ch[l-2]='E';
step=step+1;
}
else if(how==2)
{
printf("E'->+TE'\n");
n=4;
l=l+n-2;
ch[l]='+';
ch[l-1]='T';
ch[l-2]=39;
ch[l-3]='E';
step=step+1;
}
else if(how==3)
{
printf("E'->ε?\n");
l=l-2;
step=step+1;
}
else if(how==4)
{
printf("T->FT'\n");
n=3;
l=l+n-1;
ch[l]='F';
ch[l-1]=39;
ch[l-2]='T';
step=step+1;
}
else if(how==5)
{
printf("T'->*FT'\n");
n=4;
l=l+n-2;
ch[l]='*';
ch[l-1]='F';
ch[l-2]=39;
ch[l-3]='T';
step=step+1;
}
else if(how==6)
{
printf("T'->ε?\n");
l=l-2;
step=step+1;
}
else if(how==7)
{
printf("F->(E)\n");
n=3;
l=l+n-1;
ch[l]='(';
ch[l-1]='E';
ch[l-2]=')';
step=step+1;
}
else if(how==8)
{
printf("F->i\n");
n=1;
l=l+n-1;
ch[l]='i';
step=step+1;
}
else
{
printf("错误!\n");
break;
}
}
else
{
if(cha=='#' && ch[l]=='#')
{
printf("成功!\n");
break;
}
else
{
printf("\n");
l=l-1;
k=k+1;
step=step+1;
}
}
}
else
{
printf("错洙?误ó!");
break;
}
}
else //错误的字符
{
printf("错误的字符!");
break;
}
}while(l>=0);
getch();
return 0;
}

17