编译原理课程设计：二---十进制的语法分析及语义分析程序设计(LR法)
课 程 设 计
课程名称
编译原理
论文题目 二---十进制的语法分析及语义分析程序
设计（LR 法）
学 院 计算机科学与技术学院
专 业 软件工程
班 级 姓
名 指导教师
2015 年 1 月 14 日
课程设计任务书
学生姓名：专业班级：
指导教师：工作单位：计算机科学与技术学院题目:二---十进制的语法分析及语义分析程序设计（LR法）
1．目的：通过设计、编制、调试语法及语义分析程序，加深对语法及语义分析原理的理解。
2．设计内容及要求：
（1）学号19-22的同学按顺序分别选择递归下降法、LL（1）、算符优先分析法（或简单优先法）、LR法完成以下任务。
（2）写出二---十进制的符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。
（3）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。
课程设计进度安排：
目录
1 系统描述 (1)
1.1 目的 (1)
1.2 设计内容及步骤 (1)
2 翻译方法概述 (2)
2.1 语法分析 (2)
2.2 属性文法 (2)
3 LR分析法 (2)
3.1 LR分析器的逻辑结构 (3)
3.2 LR分析算法 (3)
4 系统的详细设计 (4)
4.1 LR分析过程 (4)
4.2 LR分析表 (6)
5 详细的算法描述 (6)
5.1 判别二进制数 (6)
5.2 LR语法分析部分 (6)
5.3 进制转换函数 (8)
6 源程序清单 (9)
7 测试结果 (14)
8 设计的评价及心得体会 (15)
8.1 设计评价 (15)
8.2 心得体会 (15)
9 参考文献 (15)
二-十进制的语法分析及语义分析程序设计
—— LR法
1系统描述
1.1目的
通过设计、编制、调试一个二---十进制的语法及语义分析程序，加深对语法及语义分析原理的理解。
1.2设计内容及步骤
本次实验使用windows 7的Visual C++软件，设计一个二---十进制的翻译程序设计，语法分析采用LR分析法。
主要流程图如下：
(1)写出LR分析方法要求的文法和属性文法描述。
(2)描述LR语法分析方法的思想。
(3)给出结构设计。
(4)完成相应的语法分析和语义分析程序设计。
(5)测试用例和测试结果。
2翻译方法概述
2.1语法分析
语法分析是编译过程的一个逻辑阶段。语法分析的任务是在的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等。语法分析程序判断源程序在结构上是否正确，源程序的结构由上下文无关文法描述。语法分析程序可以用YACC等工具自动生成。
语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。语法分析的主要工作：是识别由词法分析给出的单词序列是否是给定的正确句子（程序）。语法分析常用的方法：自顶向下的语法分析和自底向上的语法分析两大类。此次设计中语法分析中主要通过递归下降分析法对语法分析处理过程进行控制，使输出的三地址表示的翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。
2.2属性文法
对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。
3LR分析法
LR分析法是一种有效的自底向上的语法分析技术，它给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K≥0）符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。
LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归
约过程，每一步归约的都是真正的句柄。
3.1 LR分析器的逻辑结构
（1）在总控程序的控制下，从左到右扫描输入串根据分析栈和输入符号的情况，查分析表确定分析动作；
（2）分析表是LR分析器的核心，它跟文法有关，它包括动作表(Action)和状态转换表(Goto)两部分，总控程序据分析表确定分析动作；
（3）分析栈包括文法符号栈X[i]和相应的状态栈S[i]两部分(状态是指能识别活前缀的自动机状态)，LR分析器通过判断栈顶元素和输入符号查分析表确定下步分析动作。
3.2 LR分析算法
（1）将初始状态S0和输入串的左边界(#) 分别进分析栈；
（2）根据状态栈栈顶和当前输入符号查动作表进行移进、规约、接受或者出错操作；
（3）重复以上(2)的工作直到接受或出错为止。
4系统的详细设计4.1 LR分析过程
（1）二进制文法
S -> L
S -> L.L
L -> B
L -> LB
B -> 0
B -> 1
（2）拓展文法
S’ -> S
S -> L r1
S -> L.L r2
L -> B r3
L -> LB r4
B -> 0 r5
B -> 1 r6
I0
S’ -> *S S -> *L S -> *L.L L -> *B L -> *LB B -> *0 B -> *1
I1
S’ -> S* I2
S -> L*
S -> L*.L
L -> L*B
B -> *0
B -> *1
I3
L -> B*
I4
B -> 0*
I5
B -> 1*
I6
S -> L.*L
L -> *B
L -> *LB
B -> *0
B -> *1
I7
L -> LB*
I8
S -> L.L*
L -> L*B
B -> *0
B -> *1
4.2 LR分析表
5详细的算法描述
5.1判别二进制数
void Syntax()
{ printf("判别二进制数的文法\n");
printf(" (0) S -> L\n (1) S -> L.L\n (2) L -> B\n (3) L -> LB\n (4) B -> 0\n (5) B -> 1\n");
printf("--------------------------------------------------------------------\n");} 5.2 LR语法分析部分
do{ y=z;m=0;n=0; //y,z指向状态栈栈顶
g=top;j=0;k=0;
x=c[top]; //将输入符号赋给x
count++; p++;
printf("%d\t",count);//输出步骤序号
while(m<=top1)
{ //输出状态栈
printf("%d",a[m]); m=m+1; }
printf("\t\t");
while(n<=top2)
{ //输出符号栈
printf("%c",b[n]); n=n+1; }
printf("\t\t");
while(g<=top3)
{ //输出输入串
printf("%c",d[g]); g=g+1; }
printf("\t\t");
while(x!=vt[j]&&j<=3) //获取当前x对应j的值j++;
if(j==3&&x!=vt[j])//如果x不是终结符则报错
{ printf("error\n"); return; }
if(action[y][j]==NULL){
printf("error\n"); return; }
else
strcpy(copy,action[y][j]);
if(copy[0]=='S')
{ //处理移进
if(copy[2]=='#') z=copy[1]-'0';//因为状态从0开始else z=(copy[1]-'0')*10+(copy[2]-'0');
top1=top1+1;
top2=top2+1;
a[top1]=z;//数组a实现状态栈
b[top2]=x;//数组b实现符号栈
top=top+1;//
i=0; //输入符号串数组c的顶
while(copy[i]!='#')//例"S3#" 输出ACTION
{ printf("%c",copy[i]); i++; }
printf("\n"); p--;}
if(copy[0]=='r')
{ i=0; //处理归约
while(copy[i]!='#')//例"S3#" 输出ACTION
{ printf("%c",copy[i]); i++; }
h=copy[1]-'0';//因为状态从0开始
strcpy(copy1,LR[h]);
while(copy1[0]!=vn[k]) //获取当前k值
k++;
l=strlen(LR[h])-4;
top1=top1-l+1;
top2=top2-l+1;
y=a[top1-1];
p=goto1[y][k];
a[top1]=p;
b[top2]=copy1[0];
z=p;
printf("\t");
printf("%d\n",p); }
}while(action[y][j]!="acc");
printf("acc\n");
5.3进制转换函数
double change(char a[]){ //进制转换函数
int n; n = strlen(a) - 1; //strlen()为系统给出的函数，用作返回数组元素个数，返回元素不回空的个数
double result=0; char *str;
str = new char[n];
str[n]='\0';
for(int i=0;i < n;i++)
str[i]=a[i];
printf("二进制数");
for(int j=0;(size_t)j < strlen(str);j++)
{printf("%d",str[j]-48);
result=result+(str[j]-48)*pow(2,n-j-1);}
return result;}
6源程序清单
#include
#include
#include
void Syntax();
double change(char a[]);
//ACTION表
char *action[9][4]={NULL, "S3#", "S4#", NULL, //0
NULL, NULL, NULL, "acc", //1
"S5#", NULL, NULL, "r1#", //2
"r5#", "S3#", "S4#", "r5#", //3
"r5#", "S3#", "S4#", "r5#", //4
"r5#", "S3#", "S4#", "r5#", //5
"r3#", "r3#", "r3#", "r3#", //6
"r4#", "r4#", "r4#", "r4#", //7
"r2#", "r2#", "r2#", "r2#" //8
};
//GOTO表
int goto1[9][2]={ 1,2,0,0,0,0,0,6, 0,7, 0,8, 0,0,0,0,0,0};
char vt[4]={'.','0','1','#'}; //存放终结符
char vn[2]={'E','A'}; //存放非终结符
char*LR[9]={"S->E#","E->A#","E->A.A#","A->0A#","A->1A#","A->#"};
//存放产生式
int a[20];//数组a实现状态栈
char b[20],c[20],d[20],c1,d1;//数组b实现符号栈，数组c存放输入的字符串int top1,top2,top3,top,m,n;
void main()
{ Syntax();
int g,h,i,j,k,l,p,y,z,count;
char x,copy[20],copy1[20];
top1=0;
top2=0;
top3=0;top=0;
a[0]=0;y=a[0];
b[0]='#';
count=0;
z=0;
//输入要识别的字符串
printf("输入二进制表达式，注意以# 结束\n");
do{
scanf("%c",&c1);
d1=c1;
if(c1!='0'&&c1!='1'&&c1!='#'&&c1!='.'){
printf("输入的二进制数格式错误\n");
return;}
c[top3]=c1; //字符数组c[20]存放输入的字符串
d[top3]=d1;
top3=top3+1;//字符串的总个数
}while(c1!='#');
//输出分析结果
printf("------------对给定的字符串的分析结果-------------------------------\n"); printf("步骤\t状态栈\t\t符号栈\t\t输入串\t\tACTION\tGOTO\n");
do{
y=z;m=0;n=0; //y,z指向状态栈栈顶
g=top;j=0;k=0;
x=c[top]; //将输入符号赋给x
count++; p++;
printf("%d\t",count);//输出步骤序号
while(m<=top1)
{ //输出状态栈
printf("%d",a[m]); m=m+1;
}
printf("\t\t");
while(n<=top2)
{ //输出符号栈
printf("%c",b[n]); n=n+1; }
printf("\t\t");
while(g<=top3)
{ //输出输入串
printf("%c",d[g]); g=g+1; }
printf("\t\t");
while(x!=vt[j]&&j<=3) j++; //获取当前x对应j的值
if(j==3&&x!=vt[j])//如果x不是终结符则报错
{ printf("error\n"); return; }
if(action[y][j]==NULL){
printf("error\n"); return; }
else
strcpy(copy,action[y][j]);
if(copy[0]=='S')
{ //处理移进
if(copy[2]=='#') z=copy[1]-'0';//因为状态从0开始else z=(copy[1]-'0')*10+(copy[2]-'0');
top1=top1+1;
top2=top2+1;
a[top1]=z;//数组a实现状态栈
b[top2]=x;//数组b实现符号栈
top=top+1;//
i=0; //输入符号串数组c的顶
while(copy[i]!='#')//例"S3#" 输出ACTION
{ printf("%c",copy[i]); i++; }
printf("\n"); p--;}
if(copy[0]=='r')
{ i=0; //处理归约
while(copy[i]!='#')//例"S3#" 输出ACTION
{ printf("%c",copy[i]); i++; }
h=copy[1]-'0';//因为状态从0开始
strcpy(copy1,LR[h]);
while(copy1[0]!=vn[k]) //获取当前k值
k++;
l=strlen(LR[h])-4;
top1=top1-l+1;
top2=top2-l+1;
y=a[top1-1];
p=goto1[y][k];
a[top1]=p;
b[top2]=copy1[0];
z=p;
printf("\t");
printf("%d\n",p); }
}while(action[y][j]!="acc");
printf("acc\n");
printf("\n");
printf("转换成十进制数为%f\n",change(c)); //进制转换} void Syntax()
{ printf("判别二进制数的文法\n");
printf(" (0) S -> L\n (1) S -> L.L\n (2) L -> B\n (3) L -> LB\n (4) B -> 0\n (5) B -> 1\n");
printf("--------------------------------------------------------------------\n");} double change(char a[]){ //进制转换函数
int n;
n = strlen(a) - 1; //strlen()为系统给出的函数，用作返回数组元素个数，返回元素不回空的个数
double result=0;
char *str;
str = new char[n];
str[n]='\0';
for(int i=0;i < n;i++) str[i]=a[i];
printf("二进制数");
for(int j=0;(size_t)j < strlen(str);j++)
{ printf("%d",str[j]-48);result=result+(str[j]-48)*pow(2,n-j-1);} return result;}
7测试结果（1）输入一个二进制数，程序运行结果如下：
（2）输入不合要求的字符串时，运行如下：
8设计的评价及心得体会
8.1设计评价
本程序的优点是能对输入的二进制字符串进行正确的语法分析，并完成二进制到十进制的转换。不过程序仍存在一些明显的不足，譬如无法对有小数部分的二进制数进行语法分析等。
8.2心得体会
LR分析法与其它语法分析方法相比，应用更广泛，具有更强的吸引力。它能够通过LR分析程序识别所有采用上下文无关文法描述的程序设计语言的结构，它也是最一般的无回溯的移进—归约方法，能够像其它的移进—归约方法一样有效的实现，此外，LR分析器还能够及时发现语法错误和准确指出错误位置。
通过这次课设——二-十进制的语法分析及语义分析程序设计（LR文法实现），我加深了对语法及语义分析原理的理解。在编程实现的过程中，我参考了同学的程序，查阅了很多资料与文献，收获颇丰。当然，这次课设也让我深刻意识到自己编程能力仍有待提高，我会更加努力的。
谢谢饶老师和专业同学的指导！
9参考文献
[1]吕映芝，张素琴，蒋维杜.编译原理.北京:清华大学出版社.2004.11
[2]张辛儿，戴新宇.编译原理——编译程序构造与实践教程.北京：人民邮电出版社.2010.10
[3]毛红梅.编译原理学·练·考.北京:清华大学出版社.2005.8
本科生课程设计成绩评定表班级：姓名：学号：
注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格
指导教师签名：
年月日
语法分析程序报告
xx理工大学 《编译原理》 题目语法分析程序 姓名： 学号： 班级：
一、实验目的 编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。 二、实验要求 利用C语言编制递归下降分析程序，并对简单语言进行语法分析。 2.1 待分析的简单语言的语法 用扩充的BNF表示如下： ⑴<程序>：：=begin<语句串>end ⑵<语句串>：：=<语句>{；<语句>} ⑶<语句>：：=<赋值语句> ⑷<赋值语句>：：=ID：=<表达式> ⑸<表达式>：：=<项>{+<项> | -<项>} ⑹<项>：：=<因子>{*<因子> | /<因子> ⑺<因子>：：=ID | NUM | （<表达式>） 2.2 实验要求说明 输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。 例如： 输入begin a:=9; x:=2*3; b:=a+x end # 输出success 输入x:=a+b*c end # 输出error 2.3 语法分析程序的酸法思想 ⑴主程序示意图如图2-1所示。 图2-1 语法分析主程序示意图 ⑵递归下降分析程序示意图如图2-2所示。 ⑶语句串分析过程示意图如图2-3所示。
图2-2 递归下降分析程序示意图 图2-3 语句串分析示意图 ⑷statement 语句分析程序流程如图2-4、2-5、2-6、2-7所示。 图2-4 statement 语句分析函数示意图 图2-5 expression 表达式分析函数示意图
图2-7 factor分析过程示意图三、语法分析程序的C语言程序源代码 #include "stdio.h" #include "string.h" char prog[100],token[8],ch; char *rwtab[6]={"begin","if","then","while","do","end"}; int syn,p,m,n,sum; int kk; factor(); expression(); yucu(); term(); statement(); lrparser(); scaner(); main() { p=kk=0; printf("\nGrade:05 Class:03 Name:Qiyubing Number:200507096 \n"); printf("\n----Please input the string end with '#':-------- \n"); do
编译原理实验报告《LL(1)语法分析器构造》
《LL（1）分析器的构造》实验报告 一、实验名称 LL(1)分析器的构造 二、实验目的 设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。 三、实验内容和要求 设计并实现一个LL(1)语法分析器，实现对算术文法: G[E]:E->E+T|T T->T*F|F F->(E)|i 所定义的符号串进行识别，例如符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。 实验要求: 1、检测左递归，如果有则进行消除； 2、求解FIRST集和FOLLOW集； 3、构建LL(1)分析表； 4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。 四、主要仪器设备 硬件：微型计算机。 软件： Code blocks（也可以是其它集成开发环境）。 五、实验过程描述 1、程序主要框架 程序中编写了以下函数，各个函数实现的作用如下： void input_grammer(string *G);//输入文法G
//将文法G预处理得到产生式集合P，非终结符、终结符集合U、u， int eliminate_1(string *G,string *P,string U,string *GG);//消除文法G中所有直接左递归得到文法GG int* ifempty(string* P,string U,int k,int n);//判断各非终结符是否能推导为空 string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)；求所有非终结符的FIRST集 string FIRST(string U,string u,string* first,string s)；//求符号串s=X1X2...Xn的FIRST集 string** create_table(string *P,string U,string u,int n,int t,int k,string* first)；//构造分析表 void analyse(string **table,string U,string u,int t,string s)；//分析符号串s 2、编写的源程序 #include 编译原理 实 验 报 告 目的要求 1.构造文法的语法分析程序，要求采用预测分析法对输入的字符串进行语法 分析。 2.加深对预测分析LL（1）分析法的理解和掌握。 实验内容 对文法G进行语法分析，文法G如下所示： *0. S→a */ *1. S→^ *2. S→(T) *3. T→SW * *4. W→,SW *5. W→ε; 并对任给的一个输入串进行语法分析检查。程序要求能对输入串进行预测分析，能判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。 程序输入/输出示例： 输入:一个以 # 结束的符号串：例如：(a,a)# 输出: 步数分析栈输入串所用规则 (1) #S (a,a))# 2 源程序： //LL(1)预测分析控制程序 #include 实验三自下而上语法分析及语义分析 一、实验目的： 通过本实验掌握LR分析器的构造过程，并根据语法制导翻译，掌握属性文法的自下而上计算的过程。 二、实验学时： 4学时。 三、实验内容 根据给出的简单表达式的语法构成规则（见五），编制LR分析程序，要求能对用给定的语法规则书写的源程序进行语法分析和语义分析。 对于正确的表达式，给出表达式的值。 对于错误的表达式，给出出错位置。 四、实验方法 采用LR分析法。 首先给出S-属性文法的定义（为简便起见，每个文法符号只设置一个综合属性，即该文法符号所代表的表达式的值。属性文法的定义可参照书137页表6.1），并将其改造成用LR分析实现时的语义分析动作（可参照书145页表6.5）。 接下来给出LR分析表。 然后程序的具体实现： ●LR分析表可用二维数组（或其他）实现。 ●添加一个val栈作为语义分析实现的工具。 ●编写总控程序，实现语法分析和语义分析的过程。 注：对于整数的识别可以借助实验1。 五、文法定义 简单的表达式文法如下： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 上式中，i 为整数。 六、处理程序例 例1: 正确源程序例： 23+(45+4)* 40分析结果应为：正确的表达式。其值为：1983 例2: 错误源程序例： 5+(56+)-24 分析结果应为：错误的表达式：出错位置为） 附录：源程序 #include LL(1)语法分析实验报告 一、实验题目 LL（1）语法分析 二、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，检查语法错误，进一步掌握常用的语法分析方法。 三、实验内容 构造LL(1)语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合则输出错误信息。 消除递归前的文法消除递归和提取公因子后的等价文法 S →S ∨ a T | a T | ∨ a T S→aTS’ |vaTS’ T →∧ a T | ∧a S’→vaTS’ |ε T→∧ a T’ T’→∧ aT’ |ε 根据已建立的分析表，对下列输入串：a∧ a∧ a进行语法分析，判断其是否符合文法。 四、实验要求 1.根据已由的文法规则建立LL（1）分析表； 2.输出分析过程。 请输入待分析的字符串: a∧ a∧ a 符号栈输入串所用产生式 #S a∧ a∧ a# #S’Ta a∧ a∧ a# S→aTS’ #S’T ∧ a∧ a# # S’T’a∧∧ a∧ a# T→∧ a T’ # S’T’a a∧ a# # S’T’∧ a# # S’T’a∧∧ a# T’→∧ aT’ # S’ T’a a# # S’ T’# # S’ # T’→ε # # S’→ε 五、程序思路 模块结构： 1、定义部分：定义常量、变量、数据结构。 2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）； 3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则； 4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。 六、程序源代码 /* 程序名称： LL(1)文法分析程序 */ /* S->S>aT|aT|>aT */ /* T-> 1.实验目的：掌握LL(1)分析法的基本原理，掌握LL(1)分析表的构造方法，掌握LL(1) 驱动程序的构造方法。 2.实验要求：实现LR分析法（P147,例）或预测分析法（P121,例）。 3.实验环境：一台配置为1G的XP操作系统的PC机;Visual C++. 4.实验原理：编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语 法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该 语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单 位。编译程序的语法规则可用上下文无关文法来刻画。 语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法 的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想 是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生 式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。 自顶向下带递归语法分析：1、首先对所以的生成式消除左递归、提取公共左因子 2、在源程序里建立一个字符串数组，将所有的生成式都存在这个数组中。 3、给每个非终结符写一个带递归的匹配函数，其中起始符的函数写在main函数里。 这些函数对生成式右边从左向右扫描，若是终结符直接进行匹配，匹配失败，则调用出错函 数。如果是非终结符则调用相应的非终结符函数。 4、对输入的符号串进行扫描，从起始符的生成式开始。如果匹配成功某个非终结符 生成式右边的首个终结符，则将这个生成式输出。匹配过程中，应该出现的非终结符没有出 现，则出错处理。 5.软件设计与编程：对应源程序代码： #include <> #include <> #include 编译原理实验报告 实验一 一、实验名称：词法分析器的设计 二、实验目的：1，词法分析器能够识别简单语言的单词符号 2，识别出并输出简单语言的基本字.标示符.无符号整数.运算符.和界符。 三、实验要求：给出一个简单语言单词符号的种别编码词法分析器 四、实验原理： 1、词法分析程序的算法思想 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 2、程序流程图 （1 （2）扫描子程序 3 五、实验内容： 1、实验分析 编写程序时，先定义几个全局变量a[]、token[]（均为字符串数组),c,s( char型)，i,j,k（int型），a[]用来存放输入的字符串，token[]另一个则用来帮助识别单词符号，s用来表示正在分析的字符。字符串输入之后，逐个分析输入字符，判断其是否‘#’，若是表示字符串输入分析完毕，结束分析程序，若否则通过int digit(char c)、int letter(char c)判断其是数字，字符还是算术符,分别为用以判断数字或字符的情况，算术符的判断可以在switch语句中进行，还要通过函数int lookup(char token[])来判断标识符和保留字。 2 实验词法分析器源程序： #include 题目：词法分析器的设计与实现 一、引言................................ 错误!未定义书签。 二、词法分析器的设计 (3) 2.1词的内部定义 (3) 2.2词法分析器的任务及功能 (3) 3 2.2.2 功能： (4) 2.3单词符号对应的种别码： (4) 三、词法分析器的实现 (5) 3.1主程序示意图： (5) 3.2函数定义说明 (6) 3.3程序设计实现及功能说明 (6) 错误!未定义书签。 7 7 四、词法分析程序的C语言源代码： (7) 五、结果分析： (12) 摘要：词法分析是中文信息处理中的一项基础性工作。词法分析结果的好坏将直接影响中文信息处理上层应用的效果。通过权威的评测和实际应用表明,IRLAS是一个高精度、高质量的、高可靠性的词法分析系统。众所周知,切分歧义和未登录词识别是中文分词中的两大难点。理解词法分析在编译程序中的作用，加深对有穷自动机模型的理解，掌握词法分析程序的实 现方法和技术，用c语言对一个简单语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解,掌握编译程序的实现方法和技术。Abstract:lexical analysis is a basic task in Chinese information processing. The results of lexical analysis will directly affect the effectiveness of the application of Chinese information processing. The evaluation and practical application show that IRLAS is a high precision, high quality and high reliability lexical analysis system. It is well known that segmentation ambiguity and unknown word recognition are the two major difficulties in Chinese word segmentation. The understanding of lexical analyse the program at compile, deepen of finite automata model for understanding, master lexical analysis program implementation method and technology, using C language subset of a simple language compilation of a scanned again compiler, to deepen to compile the principle solution, master compiler implementation method and technology. 关键词：词法分析器?扫描器?单词符号?预处理 Keywords: lexical analyzer word symbol pretreatment scanner 一、引言 运用C语言设计词法分析器，由指定文件读入预分析的源程序，经过词法分析器的分析，将结果写入指定文件。本程序是在Visual?Studio环境下，使用C语言作为开发工具。基于实验任务 实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试LL （1 ）分析程序，以便对任意输入的符号串 进行分析。 ◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。 ◆分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号 以及LL（1）分析表，对输入符号串自上而下的分析过程。 三、LL（1）分析法实验设计思想及算法 ◆模块结构： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 四、实验要求 1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。 3、对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： 五、实验源程序 LL1.java import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l; JButton b0; JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3; 实验三语法分析器 一、实验目的： 理解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析表的构造及分析过程的实现，掌握语法分析方法和程序设计方法。 二、实验要求： 对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与。产生式结构几乎是一致的，通过设计、编程、调试出一个具体语法分析程序。 三、实验原理： 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器的工作本质上是按文法的产生式，识别输入串是否是一个句子。自上而下分析法的主旨是，对任何输入串，试图用一切可能的方法，从文法开始符号出发，自上而下地为输入串建立一棵语法树。这种方法本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 对于一个文法满足以下三个条件，则称该文法为LL(1)文法。 文法不含有左递归。 对于文法中的每一个非终结符A的各个产生式的侯选首符集两两不相交。即，若A->Q1|Q2|…|Qn 则FIRST(Qi) ^FIRST(Qj)=null (i!=j) 对文法中的每个非终结符号A，若他存在某个侯选首符集包含空串，则FIRST(A)^FOLLOW(A)=null 对于一个文法满足LL(1)条件时，我们就可以对其输入串进行有效的无回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符号。 四、实验步骤： 1、功能描述： 根据给定的文法，由程序生成项集族和语法分析表，对输入的源程序进行词法分析，得到语法分析的输入串，经过语法分析后得到三个栈，它们分别是状态栈，字符栈，输入栈，从而分析出输入的源程序是否有语法错误。 2、构造自己设计的小语言的语法分析器： (1) 语言的语法描述(语法规则)的设计即文法的设计； (2) 把文法形式符号中所隐含的信息内容挖掘出来并用LL或LR的资料形式(分析表)表示出来； (3) 语法分析的数据输入形式和输出形式的确定； 《编译原理》实验报告题目: 语法分析器的制作 学生姓名:江荣吉 班级: 学号: 指导教师: 成绩: 西安邮电大学计算机学院 2015 年 6 月 7 日 一：实验目的 熟悉语法分析的过程； 理解相关文法的步骤； 熟悉First集和Follow集生成 二：实验要求 对于给定的文法，试编写调试一个语法分析程序： 要求和提示： （1）可选择一种你感兴趣的语法分析方法（LL(1)、算符优先、递归下降、SLR(1)等）作为编制语法分析程序的依据。 （2）对于所选定的分析方法，如有需要，应选择一种合适的数据结构，以构造所给文法的机内表示。 （3）能进行分析过程模拟。如输入一个句子，能输出与句子对应的语法树，能对语法树生成过程进行模拟；能够输出分析过程每一步符号栈的变化情 况。 设计一个由给定文法生成First集和Follow集并进行简化的算法动态模拟。 三：实验过程 1：文法： E->TE’ E’->+TE’|ε T->FT’ T’->*FT’|ε F->(E)|i: 2程序描述（LL(1)文法） 本程序是基于已构建好的某一个语法的预测分析表来对用户的输入字符串进行分析，判断输入的字符串是否属于该文法的句子。 基本实现思想：接收用户输入的字符串（字符串以“#”表示结束）后，对用做分析栈的一维数组和存放分析表的二维数组进行初始化。然后取出分析栈的栈顶字符，判断是否为终结符，若为终结符则判断是否为“#”且与当前输入符号一样，若是则语法分析结束，输入的字符串为文法的一个句子，否则出错若不为“#”且与当前输入符号一样则将栈顶符号出栈，当前输入符号从输入字符串中除去，进入下一个字符的分析。若不为“#”且不与当前输入符号一样，则出错。 学号20102７９8 专业软件工程姓名薛建东 实验日期２013.04.０8 教师签字成绩实验报告 【实验名称】ＬL（1）语法分析 【实验目的】 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法,训练掌握开发应用程序的基本方法。 【实验内容】 ◆根据某一文法编制调试LL ( 1)分析程序，以便对任意输入的符号串进行分析。 ◆构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 ◆分析法的功能是利用LＬ（１)控制程序根据显示栈栈顶内容、向前看符号以及LL(1) 分析表,对输入符号串自上而下的分析过程。 【设计思想】 （1）、LL(１)文法的定义 ＬL(1)分析法属于确定的自顶向下分析方法。LＬ（１)的含义是：第一个Ｌ表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式（规则)进行推导。 LL(1)文法的判别需要依次计算FIRＳT集、FOLＬＯW集和SELLＥＣT集,然后判断是否为LL（1)文法，最后再进行句子分析。 需要预测分析器对所给句型进行识别。即在LＬ(１)分析法中,每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符;当出现终结符时，判断其与剩余输入串的第一个字符是否匹配,如果匹配，则继续分析,否则报错。ＬＬ（1）分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式Ａ→α，A→β,都要满足下面条件:ＳELEＣＴ(Ａ→α)∩SELＥCT（Ａ→β)＝? (2）、预测分析表构造 LL（1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推 LR分析程序设计 1实验目的 （1）构造LR 分析程序，利用它进行语法分析，判断给出的符号串是否为 该文法识别的句子； （2）了解LR分析方法是严格的从左向右扫描，和自底向上的语法分析方法。 2实验内容和实验要求 (1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。 (2)LR分析方法是已知的最一般的无回溯，移进-归约方法，它能够和其他移进-归约方法一样有效地实现。 (3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。 3 待分析的语法描述 E->vI:T I->I,i|i T->r 4算法描述 LR分析法基本思想 LR分析法是一种能够根据分析栈中的文法符号串（状态）和向右顺序查看第k个输入字符就能够唯一确定LR（k）分析器的动作是移进还是用哪一条产生式归约的分析方法。 采用LR（0）分析法进行本次实验，即无需向前查看输入符号就能够确定分析器的动作。 实现方法 LR（0）分析器由三个部分组成： (1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。 (2)分析表，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。由于它是总控程序的依据，所以在程序的第一部分就已经定义好。 (3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。 (4)LR分析器及时察觉语法错误,快到自左向右扫描输入的最大可能。 为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道这一点，栈顶的状态符号包含了所需要的一切信息。如果仅知道栈内的文法符号就能确定栈顶是什么句柄。由于LR分析表的转移函数本 实验三语法分析器的设计 一、实验内容 设计、编写和调试构造LR（0）项目集规范簇或实现基于LR分析表对给定的符号串进行LR 分析的程序。以下两个内容任选其中一项： （1）对于给定的文法，实现构造识别该文法全部活前缀DFA的程序。 （2）对于给定的LR分析表和符号串，设计程序以实现所输入符号串是否为合法符号串。 要求用JAVA语言编程。（可参考实验指导书P149至P156） 二、程序代码 AnalysisOfGrammer.java package analysis; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.awt.*; import java.awt.event.*; import java.io.*; import java.util.LinkedList; publicclass AnalysisOfGrammer extends JApplet{ private JFileChooser jfc = new JFileChooser(new File(".")); private JButton jbt1 = new JButton("打开文法文件"); private JButton jbt2 = new JButton("构造LR规范簇"); private JButton jbt3 = new JButton("构造LR分析表"); private JButton jbt4 = new JButton("清空"); private JButton jbt5 = new JButton("退出"); private JLabel jl1 = new JLabel("LR(0)项目集规范簇"); private JLabel jl2 = new JLabel("LR(0)分析表"); private JPanel p3 = new JPanel(); private JTextArea jta1 = new JTextArea(); private String[] grammer = new String[50]; privateint count = 0; private LinkedList 河南工业大学实验报告 课程编译原理实验名称实验二 LL(1)分析法 实验目的 1．掌握LL(1)分析法的基本原理； 2．掌握LL(1)分析表的构造方法； 3．掌握LL(1)驱动程序的构造方法。 一.实验内容及要求 根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。 对下列文法，用LL（1）分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG （3）G->ε （4）T->FS （5）S->*FS （6）S->ε （7）F->(E) （8）F->i 程序输入一以#结束的符号串(包括+*（）i#)，如：i+i*i#。输出过程如下： 步骤分析栈剩余输入串所用产生式 1E i+i*i#E->TG ............ 二.实验过程及结果 代码如下： #include string edge::getlf() { return left; } string edge::getrg() { return right; } string edge::getfirst() { return first; } string edge::getfollow() { return follow; } string edge::getselect() { return select; } string edge::getro() { string str; str+=right[0]; return str; } int edge::getrlen() { return right.length(); } void edge::newfirst(string w) { int i; for(i=0;i 基于LR(1)的语法分析程序 1.设计目的： 设计、编制和调试一个典型的LR(1)分析器，进一步掌握LR(1)语法分析方法,掌握用预测分析方法分析LR(1)文法的具体过程，加深对LR(1)文法和预测分析方法的理解。 2.设计要求： （1）根据LR(1)分析法编写一个语法分析程序，.输入已给定文法，直接输入根据己知文法构造的LR(1)分析表。 （2）对于输入的符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。 3.设计过程： 3.1 LR(1)文法的含义： LR分析法的规约过程是规范推倒的逆过程，所以LR分析过程是一种规范规约的逆过程，L表示从左到右扫描输入串，R表示最左规约（即最右推导的逆过程），括号中的1表示向右查看输入符号数为1。LR（1）项目可以看成两个部分组成，一部分和LR （0）项目相同，这部分成为心，另一部分为向前搜索符集合。所以只有当面临的输入符属于向前搜索符的集合，才做规约动作，其他情况均出错。LR（1）方法恰好解决SLR（1）方法在某些情况下存在的无效规约问题。 3.2 设计思想： 根据自身实际情况，给定了编译原理书中的一个LR(1)文法，求出其项目集合转换函数，从而得出此LR(1)文法的分析表，在程序中直接输出此分析表，并根据分析表中的内容可对输入的符 号串进行分析，判断是接受还是出错，从而得出该输入的符号串是否为文法的一个句子。 3.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.FIRST集合的构造 在这个程序中使用的是FIRST(βa)，这基于每一个非终结符的FRIST集合（终结符的FIRST就是它本身）。所以需要对每一个非终结符构造其FIRST集合。 方法如下： 连续使用下面的规则，直到每个集合FIRST不再增大为止。 （1）若X属于V T，则FIRST(X)={X}。 （2）若X属于V N，且有产生式X→a…，则把A加入到FIRST(X)中；若X→ξ也是一条产生式，则把ξ也加入到FIRST 中。 4.LR(1)分析表的构造 在实现GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后再扫描所有的项目集，找到其中包含归约项目的哪些项目集，根据其中项目，得到分析表中那些鬼月的部分。 4 设计内容 4.1 主要变量说明： #define SIZE 20 //宏定义，定义sSIZE为12 #define sSIZE 12 //宏定义，定义sSIZE为12 《编译原理》 课程设计 院系信息科学与技术学院 专业软件工程 年级 2011级 学号 20112723 姓名林苾湲 西南交通大学信息科学与技术学院 2013年 12月 目录 课程设计1 词法分析器 (2) 1.1 设计题目 (2) 1.2 设计容 (2) 1.3 设计目的 (2) 1.4 设计环境 (2) 1.5 需求分析 (2) 1.6 概要设计 (2) 1.7 详细设计 (4) 1.8 编程调试 (5) 1.9 测试 (11) 1.10 结束语 (13) 课程设计2 赋值语句的解释程序设计 (14) 2.1 设计题目 (14) 2.2 设计容 (14) 2.3 设计目的 (14) 2.4 设计环境 (14) 2.5 需求分析 (15) 2.6 概要设计 (16) 2.7 详细设计 (16) 2.8 编程调试 (24) 2.9 测试 (24) 2.10 结束语 (25) 课程设计一词法分析器设计 一、设计题目 手工设计c语言的词法分析器（可以是c语言的子集）。 二、设计容 处理c语言源程序，过滤掉无用符号，判断源程序中单词的合法性，并分解出正确的单词，以二元组形式存放在文件中。 三、设计目的 了解高级语言单词的分类，了解状态图以及如何表示并识别单词规则，掌握状态图到识别程序的编程。 四、设计环境 该课程设计包括的硬件和软件条件如下： 4.1.硬件 （1）Intel Core Duo CPU P8700 （2）存4G 4.2.软件 （1）Window 7 32位操作系统 （2）Microsoft Visual Studio c#开发平台 4.3.编程语言 C#语言 五、需求分析 5.1.源程序的预处理：源程序中，存在许多编辑用的符号，他们对程序逻辑功能无任何影响。例如：回车，换行，多余空白符，注释行等。在词法分析之前，首先要先剔除掉这些符号，使得词法分析更为简单。 5.2.单词符号的识别并判断单词的合法性：将每个单词符号进行不同类别的划分。单词符号可以划分成5中。 (1)标识符：用户自己定义的名字，常量名，变量名和过程名。 (2)常数：各种类型的常数。 (3) 保留字（关键字）：如if、else、while、int、float等。 (4) 运算符：如+、-、*、<、>、=等。 (5)界符：如逗号、分号、括号等。 5.3.将所有合法的单词符号转化为便于计算机处理的二元组形式：（单词分类号，单词自身值）；以图形化界面显示出来。 5.4.可选择性地将结果保存到文件中。 六、概要设计 6.1．数据类型 6.1.1.单词的分类：本词法分析器演示的是C语言的一个子集，故字符集如下：c语言编译原理预测分析法实验报告
实验三 自下而上语法分析及语义分析
语法分析程序实验报告及代码
编译原理语法分析程序设计分析法
编译原理实验报告(词法分析器-语法分析器).doc
词法分析器的实现与设计
编译原理 语法分析器 (java完美运行版)
语法分析器实验报告
西安邮电大学编译原理语法分析器的制作
编译原理LL(1)语法分析实验报告
lR语法分析器设计
编译语言-语法分析器的设计
编译原理实验报告LL(1)分析法
基于LR(1)的语法分析程序报告
编译原理词法分析器语法分析课程设计报告书