学 学
号
《 编译原理》 实验2:语法分析器设计
学 生 姓 名
专 业 、 班 级
指 导 教 师
赵璐
成 绩
计算机与信息工程学院 2018 年 11 月 27 日
一、实验目的
1. 理解语法分析程序的功能。
2. 熟悉语法分析程序的设计原理和构造方法。
3. 掌握递归下降语法分析程序的构造方法。
4. 设计一个递归下降的语法分析器,作为实验一构造的词法分析器的下一步编译工具,能语法分析前一步词法分析器输出的单词符号序列。
二、实验要求 1. 根据书 P206 给出的简单语言的语法规则,编写 C 或 C++语言源程序,实现针对该简单语言的递归下降的语法分析器; 2. 独立做实验,输入、调试所编程序; 3. 实验结束后,根据实验报告模板编写实验报告。
三、实验内容和步骤 用 Visual C++作为实验开发环境,创建一个 Win32 Console Application 工程,工程名为你的学号,添加三个文件:
(1)存储结构定义:以 ParserDef.h 和 LexerDef.h 为文件名;
(2)基本操作的算法:以 ParserAlgo.h 和 LexerAlgo.h 为文件名;
(3)调用基本操作的主程序:以 ParserMain.cpp 为文件名。
编写程序:
(1)文件 LexerDef.h 和 LexerAlgo.h 为实验一的内容。
(2)文件 ParserDef.h 定义语法分析所需的全局变量等。
(3)文件 ParserAlgo.h 实现对语法规则中各语法成分的分析子算法。
(4)文件 ParserMain.cpp 实现针对 P206 简单语言语法规则的递归下降语法分析器。
源程序代码:
:
=============================ParserDef.h================================ int kk; #define _KEY_WORD_END "waiting for your expanding" char * rwtab[]={"begin","if","then","while","do","end",_KEY_WORD_END}; char input[255]; char token[255]=""; int p_input; int p_token; char ch; ============================ParserAlgo.h================================ char prog[80]; int syn,p,m,n,sum=0; void scaner() {
m=0;
for(n=0; n<8; n++) token[n]=NULL;
ch=prog[p++];
while(ch==" ") ch=prog[p++];
if((ch>="a" && ch<="z") ||(ch>="A" && ch<="Z")) {
while((ch>="a" && ch<="z") ||(ch>="A" && ch<="Z")||(ch>="0" && ch<="9")) {
token[m++]=ch;
ch=prog[p++];
}
token[m++]="\0";
syn=10;
p=p-1;
//回退一个字符
for(n=0; n<6; n++) {
if(strcmp(token,rwtab[n])==0) {
syn=n+1;
break;
}
}
} else if(ch>="0" && ch<="9") {
sum=0;
while(ch>="0" && ch<="9") {
sum=sum*10+ch-"0";
ch=prog[p++];
}
p=p-1;
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;
p=p-1;
}
p=p+1;
token[m]="\0";
break;
case ">":
m=0;
token[m++]=ch;
ch=prog[p++];
if(ch=="=") {
syn=24;
token[m++]=ch;
} else {
syn=23;
p=p-1;
}
break;
case ":":
m=0;
token[m++]=ch;
ch=prog[p++];
if(ch=="=") {
syn=18;
token[m++]=ch;
} else {
syn=17;
p=p-1;
}
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=26;
token[0]=ch;
break;
case "(":
syn=27;
token[0]=ch;
break;
case ")":
syn=28;
token[0]=ch;
break;
case "=":
syn=25;
token[0]=ch;
break;
case "#":
syn=0;
token[0]=ch;
break;
default:
syn=-1;
}
} } ============================ParserMain.cpp============================== #include<stdio.h> #include<stdlib.h> #include<string.h> #include"LexerDef.h" #include"ParserDef.h" #include"LexerAlgo.h" #include"ParserAlgo.h"
void lrparser(); void yucu(); void statement(); void expression(); void term(); void factor();
void lrparser() {
if (syn==1) { //begin
scaner();
yucu();
if (syn==6) { //end
scaner();
if (syn==0 && kk==0) printf("success \n");
} else {
if(kk!=1) printf("error,lose "end" ! \n");
kk=1;
}
} else {
printf("error,lose "begin" ! \n");
kk=1;
}
return; }
void yucu() {
statement();
while(syn==26) {
scaner();
statement();
}
return; }
void statement() {
if (syn==10) { //为标识符
scaner();
if (syn==18) { //为 :=
scaner();
expression();
} else {
printf("error!");
kk=1;
}
} else {
printf("error!");
kk=1;
}
return; }
void expression() {
term();
while(syn==13 || syn==14) {
scaner();
term();
}
return; }
void term() {
factor();
while(syn==15 || syn==16) {
scaner();
factor();
}
return; }
void factor() {
if(syn==10 || syn==11)scaner(); //为标识符或整常数时,读下一个单词符号
else if(syn==27) {
scaner();
expression();
if(syn==28)scaner();
else {
printf(" ")" 错误\n");
kk=1;
}
} else {
printf("表达式错误\n");
kk=1;
}
return; }
void main() {
p=0;
printf("********************语法分析程序***************\n");
printf("请输入源程序:\n");
do {
scanf("%c",&ch);
prog[p++]=ch;
} while(ch!="#");
p=0;
scaner();
lrparser();
printf("语法分析结束!\n"); } 四、解答下列问题 (1)简述该语法分析器的算法思想。
(2)用右递归的上下文无关文法描述 P206 给出的简单语言的语法规则(书上用扩充的 BNF表示法描述),简化各语法成分成如下符号:<程序>P、<语句串>Y、<语句>A、<赋值语句>S、<表达式>E、<项>T、<因子>F 。
(3)解释程序变量 kk 的作用、可能取值及对应含义。
五、实验结果 针对输入的源程序,经语法分析后,给出实验结果截图。
(1)源程序 begin a:=9; x:=2*3; b:=a+x end # 实验结果截图:
(2)源程序 x:=a+b*c end # 实验结果截图:
实验结果截图:
(3)输入一段此简单语言的源程序, 要求每人不同 输入的简单语言字符串:
begin a:=3;b:=5;c:=a+b end # 实验结果截图:
六 、实验中遇到的问题及解决方法 通过本次实验使我对递归下降分析方法有了更深得了解。