编译原理实验题目

1、编译原理课程设计指导书题目一 基于语法制导翻译的表达式转换编译器一、设计目的通过本课程设计获得对实际编译器的构造原理、过程和方法的感性认识，全面掌握语法制导翻译技术。二、设计内容采用语法制导翻译模式设计一个包含词法分析、语法分析、符号表管理、错误处理及输出等功能模块的、由中缀表达式到后缀表达式的完整编译器。该翻译器的规格说明如下：start à list eoflist à expr |expr à expr + term print(+) | expr term print(-) | term|term à term * factor print(*)

2、 | term / factor print(/) | term div factor print(DIV) | term mod factor print(MOD) factor à ( expr )| id print( ) | num print( num.value ) 三、设计要求1、使用模块化设计思想来设计该编译器；2、词法分析模块用于读入输入串，并将其转换成供语法分析模块使用的记号流。其中包括滤掉空格和注释、识别常数、识别标识符和关键字等功能；3、要求在语法分析模块中利用语法制导翻译技术完成具体的中缀表达式到后缀表达式的翻译，其中包括按前述翻译器的规格说

3、明构建对应表达式、项、因子的非终结符expr、term和factor的函数以及检查记号是否匹配的函数；并在不匹配时调用错误处理模块；4、要求符号表管理模块主要完成符号表对应数据结构的具体实现功能；5、错误处理模块负责报告错误信息及位置，并终止分析过程；6、输出模块完成翻译后所得到的后缀表达式的输出。四、运行结果1、从键盘输入任意中缀表达式，如： 4 - 5 * 6 DIV 4 + 8 MOD 2输出相应的后缀表达式： 456*4DIV-82MOD+1、 若键盘输入串为非中缀表达式时，如： 4 !+* 5 - 6 DIV 4 + 8 MOD 2输出相应语法错误报告信息，并停止语法分析，如： li

4、ne 1 : compiler error !五、提示1、将各功能模块设计为独立的源程序文件；2、建立一个全局头文件，将本设计所需要用到的系统头文件的打开、一些必要的宏定义和全局变量的声明信息放在该全局头文件中；3、将本设计所有文件加入一个工程文件。六、分析与讨论1、如何修改错误处理模块，使得编译器在发现错误后能跳过出错语句，继续进行语法分析；2、试使用手工构造和自动生成相结合的方法来完成本课程设计；3、仔细研读附录C有关“PL/0语言词法分析器的手工构造和自动生成”的设计内容，并通过借鉴PL/0语言词法分析器的设计方法和具体实现技术，对本课程设计的综合设计进行优化。题目二 说明语句的词法分析

5、器一、设计目的了解的基本构造原理，掌握词法分析程序的手工构造及自动构造方法。二、设计内容根据PASCAL语言的说明语句形式，用手工及自动方法构造一个对说明语句进行词法分析的程序。该程序能对从键盘输入或从文件读入的形如：“const count=10,sum=81.5,char1=f,string1=”hj”, max=169；”的常量说明串进行处理，分析常量说明串中各常量名、常量类型及常量值，并统计各种类型常量个数。三、设计要求1、输入的常量说明串，要求最后以分号作结束标志；2、根据输入串或读入的文本文件中第一个单词是否为“const”判断输入串或文本文件是否为常量说明内容；3、识别输入串或打

6、开的文本文件中的常量名。常量名必须是标识符，定义为字母开头，后跟若干个字母，数字或下划线；4、根据各常量名紧跟等号“=”后面的内容判断常量的类型。其中：字符型常量定义为放在单引号内的一个字符；字符串常量定义为放在双引号内所有内容；整型常量定义为带或不带+、- 号，不以0开头的若干数字的组合；实型常量定义为带或不带+、- 号，不以0开头的若干数字加上小数点再后跟若干数字的组合；5、统计并输出串或文件中包含的各种类型的常量个数；6、以二元组(类型,值)的形式输出各常量的类型和值；7、根据常量说明串置于高级语言源程序中时可能出现的错误情况，模仿高级语言编译器对不同错误情况做出相应处理。四、运行结果1

7、、输入如下正确的常量说明串：const count=10,sum=81.5,char1=f,max=169,str1=“h*54 2.4S!AAsj”, char2=,str2=“aa!+h”；输出：count(integer,10)sum(float,81.5)char1(char, f)max(integer,169)str1(string,“h*54 2.4S!AAsj”)char2(char, )str2(string,“aa!+h”)int_num=2; char_num=2; string_num=2; float_num=1.2、输入类似如下的保留字const错误的常量说明串：A

8、constt count=10,sum=81.5,char1=f;输出类似下面的错误提示信息：It is not a constant declaration statement! Please input a string again!3、输入类似如下含常量名或常量值错误的常量说明串：const count=10,12sum=81.5,char1=ff,max=0016；输出类似下面的错误提示信息：count(integer,10)12sum(Wrong! It is not a identifier!)char1(Wrong! There are more than one char in

9、 .)max(Wrong! The integer cant be started with 0.)int_num=1; char_num=0; string_num=0; float_num=0.4、其他类型的错误处理情况（略）。五、提示本课程设计重点有三个：一是作为常量名的标识符的识别；二是如何根据“=”后出现的内容来判断常量类型；三是对各种错误的处理。难点是对整型和实型常量的判断必须综合考虑多种可能情况。提示：1、 用指针或数组与指针相结合来处理输入的常量说明串；2、 对整型和实型常量处理时，重点考虑常数中0的位置。六、分析与讨论1、若考虑用E或e的科学计数法来表示整数和实数，应该如何实

10、现？2、若考虑布尔型常量，且规定其值只能为true或false，应该如何实现？3、如何对手工构造的词法分析程序做进一步的优化，以提高代码质量和运行效率？题目三 基于预测分析方法的表达式语法分析器一、设计目的了解预测分析器的基本构成及用自顶向下的预测法对表达式进行语法分析的方法，掌握预测语法分析程序的手工构造方法。二、设计内容已知文法GS：S->ATA->BUT->+AT|$U->*BU|$B->(S)|m其中，$表示空串。对该文法构造预测分析表，并手工构造预测分析程序，对输入串m+m*m#进行语法分析，并根据栈的变化状态输出分析过程。三、设计要求：1、判断上述文法

11、GS是否LL(1)文法，若不是，将其转变为LL(1)文法；2、对转变后的LL(1)文法建立预测分析表；3、根据清华大学出版、吕映之等编著的编译原理教材教材第五章Page 88的图5.11手工构造预测分析程序；4、用预测分析程序对键盘输入串m+m*m#进行语法分析，并根据栈的变化状态输出给定串的具体分析过程。四、运行结果从键盘输入串：m+m*m#；输出：用预测分析法分析符号串m+m*m#的过程StepStackStringRuleStepStackStringRule1#Sm+m*m#S->AT10#TUmm*m#M匹配2#TAm+m*m#A->BU11#TU*m#U->*BU

12、3#TUBm+m*m#B->m12#TUB*m#*匹配4#TUmm+m*m#M匹配13#TUBm#B->m5#TU+m*m#U->$14#TUmm#M匹配6#T+m*m#T->+AT15#TU#U->$7#TA+m*m#+匹配16#T#T->$8#TAm*m#A->BU17#接受9#TUBm*m#B->m五、提示本课程设计重点有两个：一是如何用适当的数据结构实现预测分析表存储和使用；二是如何实现各规则右部串的逆序入栈处理。建议：使用结构体数组。六、分析与讨论1、若输入串不是指定文法的句子，会出现什么情况？2、总结预测语法分析程序的设计和实现的一般

13、方法。题目四 基于算符优先分析方法的表达式语法分析器一、设计目的了解用算符优先法对表达进行语法分析的方法，编程实现算符优先表达式语法分析器。二、设计内容对简单表达式文法构造算符优先分析器。三、设计要求1、对下列简单表达式文法G E构造算符优先关系表。E # E #E E + T | TT T * F | FF P / F PP ( E )i2、根据算符优先关系表，使用栈结构来实现算符优先分析：设置两个栈：存放运算符的OPTR栈和存放操作数或运算结果的OPND栈。具体算法描述如下：（1）首先置操作数OPND栈为空栈，将#入运算符OPTR栈。（2）依次读入表达式中每个单词，若是操作数则进OPND栈

14、，若是运算符则转（3）。（3）当前设读入的运算符为2，查找算符优先关系表，比较2与OPTR栈顶元素1 ：若1<2,则2进OPTR栈，转（2）； 若12, 如2为#，则分析成功，否则OPTR栈顶元素1出栈，并转（2）；若12，则出栈OPND栈顶元素存放到b，又出栈其新栈顶元素存放到a，再出栈OPTR栈顶元素至t，进行运算r=a t b (t为运算符)，并将结果r存入栈OPND后转（2）；（4）若1和2之间无优先关系，则报错。1、 从键盘输入表达式，利用算符优先法求出其值，如输入表达式有错，则给出报错提示。表达式以“#”结尾。 四、运行结果1、从键盘输入表达式串： 10+15*4#输出： 7

15、02、从键盘输入表达式串：10+*15+输出： The expression is error!五、提示1、 构造算符优先关系表如下：+-*/()i#+>><<<><>->><<<><>*>>>><><>/>>>><><>(<<<<<=<)>>>>>>i>>>>>>#<<<<

16、<<=2、 参考严蔚敏等编著、清华大学出版社出版的C语言版数据结构P52-P54的表达式求值算法。题目五递归下降分析法一、设计目的掌握递归下降分析法的基本原理，掌握预测符集的求法， 掌握递归下降分析程序的构造方法。二、设计内容假设文法中有如下的产生式Aàb1 | b2 | | bn，则应按如下方法编写语法分析子程序procedure A() beginif tokenÎPredict(Aàb1) then (b1) else if tokenÎPredict(Aàb2) then (b2) else if tokenÎPr

17、edict(Aàbn) then (bn) else error() end其中对bi =X1X2Xn，(bi) =(X1); (X2); (Xn);l 如果XiÎVN，(Xi)= Xil 如果XiÎVT，(Xi)= Match(Xi) l 如果Xi= e, () = skip(空语句)三、设计要求：理解递归下降语法分析方法的主要原理，理解递归下降分析法对文法的要求， 熟练掌握Predict集合的求法， 熟练掌握文法变换算法（消除左递归和消除公共前缀）。四、提示：1. 基本原理递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终极符按其产生式结构构造

18、相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。2. 文法要求递归下降法要满足的条件：假设A的全部产生式为Aà1|2|n ，则必须满足如下条件才能保证可以唯一的选择合适的产生式predict(Aài)predict(Aàj)=,当ij.五、实验步骤1求SNL文法中每个产生式Predict集合Predict(Aà)= First() ，      

19、0;    当eÏFirst()= (First()- e) Follow(A)，当eÎFirst()根据Predict集合的定义求SNL的文法中每个产生式的Predict集合，判断是否满足递归下降法分析条件，若不满足用消除左递归和消除公共前缀等文法等价变化算法对文法进行变换，使其满足递归下降法的要求。2. 构造递归下降语法分析程序采用了递归子程序方法进行语法分析,对文法中的每个非终极符号按其产生式结构产生相应的语法分析子程序,完成相应的识别任务。其中终结符产生匹配命令，非终结符则产生调用命令。每次进入子程序之前都预先读入一个单词。因为使用了递

20、归下降方法,所以程序结构和层次清晰明了,易于手工实现,且时空效率较高。实际的语法分析工作,从调用总程序的分析子程序开始，根据产生式进行递归调用各个分析子程序。附录A 部分课程设计题目参考源程序A.1 基于语法制导翻译的表达式转换编译器参考源程序/*全局头文件myglobal.h,用于存放需加载的头文件、宏定义、全局变量*/#include <stdio.h>#include <string.h>#include <ctype.h> /* 加载字符测试函数*/#define BUFSIZE 128 /* 定义缓冲区大小*/#define NONE -1#def

21、ine EOSTR 0#define NUM 256#define DIV 257#define MOD 258#define ID 259#define DONE 260int tokenval; /* 定义单词属性值*/int lineno;struct table /* 定义符号表结构*/ char *lexptr; int token;struct table symtable;/* 定义符号表*/*词法分析程序lex.c*/#include “global.h”char lexbufBUFSIZE;int lineno=1;int tokenval=NONE;int lex() /*

22、词法分析函数*/ int t;while(1)t=getchar();if (t=| t=t) ; /*滤掉空格*/else if (t=n) lineno+;else if (isdigit(t) ungetc(t,stdin); scanf(“%d”,&tokenval); return NUM;else if (isalpha(t) int p,b=0; while(isalnum(t) lexbufb=t;t=getchar();b=b+1;if (b>BUFSIZE) error(“compiler error!”); lexbufb=EOSTR;if (t!=EOF)

23、 ungetc(t,stdin);p=lookup(lexbuf);if (p=0) p=insert(lexbuf,ID); tokenval=p;return sysmtablep.token; else if (t=EOF)return DONE; else tokenval=NONE;return t; /*语法分析程序paserx.c*/#include “global.h”int lookahead;void parse() lookahead=lex(); while (lookahead!=DONE) express();match(;);void express() int

24、t; void term(); while (1) switch(lookahead) case +: case -:t= lookahead;match(lookahead); term(); emit(t,NONE); continue;default: return; void term()int t; void factor(); while (1) switch(lookahead) case *: case /: case DIV: case MOD:t= lookahead;match(lookahead); factor(); emit(t,NONE); continue;de

25、fault: return; void factor() switch(lookahead) case (:match();express();match();break; case NUM:emit(NUM,tokenval);match(NUM);break;case ID:emit(ID,tokenval);match(ID);break;default: error(“syntax error”); void match(int t) if (lookahead=t) lookahead=lex();else error(“syntax error”);/*输出程序emitter.c*

26、/#include “global.h”voidemit(int t,int tval) switch(t) case +: case -: case *: case /:printf(“%cn”,t);break;case DIV:printf(“DIVn”);break;case MOD:printf(“MODn”);break; case NUM:printf(“%dn”,tval);break; case ID:printf(“%sn”,symtabletval.lexptr);break;default:printf(“token %d, tokenval %dn”,t,tval);

27、/*符号表处理程序symbol.c*/#include “global.h”#define STRMAX 999#define SYMMAX 100char lexemesSTRMAX;int lasrchar=-1;struct entry symtableSYMMAX;int lastentry=0;int lookup(char *s) int p; for (p=lastentry;p>0;p-) if (strcmp(symtablep.lexptr,s)=0) return p; return 0;int insert(char *s,int tok) int len; le

28、n=strlen(s); if (lastentry+1>=SYMMAX) error(“symbol table full”); if (lastchar+len+1>=STRMAX) error(“lexemes array full”);lastentry=lastentry+1;symtablelastentry.token=tok;symtablelastentry.lexptr=&lexemeslastchar+1;lastchar=lastchar+len+1;strcpy(symtablelastentry.lexptr,s);return lastentr

29、y;/*在符号表中填入关键字程序init.c*/#include “global.h”struct entry keywords=“div”,DIV,“mod”,MOD,0,0void init() struct entry *p; for (p=keywords;p->token;p+) insert(p->lexptr,p->token);/*错误处理程序error.c*/#include “global.h”void error( char *m) fprintd(stderr,“line %d: %sn”,lineno,m); exit(1); /*主程序mian.c

30、*/#include “global.h”main() init();parse();exit(0);A.2 说明语句的词法分析器参考源程序一、说明1、本例中字符和字符串都用“”来识别，引号中只包含一个字符时为字符型常量，否则，为字符串常量；2、本例只起示范性作用，并没有全面考虑高级语言编译器对常量说明串中可能出现错误的处理方法。2、 实际构造本课程设计的常量说明串的词法分析程序时，建议进行模块化处理。二、源代码#include"stdio.h"#include"ctype.h"#define N 80#define M 16main()char *p0

31、,*t0,*p1,*t1, *p2,*t2,*p3,*t3="const"/*char *t="true",*f="false"*/int ci=0,cf=0,cc=0,cs=0,cb=0;printf("nInput string: ");p0=(char *)malloc(N*sizeof(char);p1=(char *)malloc(M*sizeof(char);p2=(char *)malloc(M*sizeof(char);p3=(char *)malloc(M*sizeof(char);t0=p3;t

32、1=p1;t2=p2;gets(p0);while(*p0!=' ') /* 检查输入串是否以“'const”开头 */if (*p0=*t3) p0+; t3+; else printf("nThis string isn't a const declaration!"); exit(0); while (*p0!='!') /* 开始处理输入串 p0 */ while (p1<t1+M) *p1='0' p1+; p1=t1; while (p2<t2+M) *p2='0' p2

33、+; p2=t2;if (*(p0-1)=' '|*(p0-1)='') /*从串p0中取标识符，并将其作为常量名存放到串p1中 */ if (*p0!='_'&&(!isalpha(*p0) printf("n Const name is wrong . Exit !"); break; else if (*p0='_'|isalpha(*p0) do *p1=*p0; p0+; p1+; if (*p0!='='&&*p0!='_'&&

34、amp;!isalnum(*p0) printf("n Const name is wrong . Exit !"); break; while(*p0!='='); p1=t1; printf("n Name:%s;t",p1); else if (*(p0-1)='=') /* 从串p0中取常量值存放到串p2中 */ if (!isdigit(*p0)&&*p0!='"'&&*p0!='.') printf("n Const data

35、is wrong . Exit !"); break; else if (*p0='"') /* 处理字符和字符串常量 */ do *p2=*p0; p0+; p2+; while(*p0!=''); if (*(p0-1)!='"') printf("n String data is wrong. Exit !"); break; p2=t2; if (strlen(p2)=3) cc+; printf(" Data:%s ;t Type:char !n",p2); else

36、 cs+; printf(" Data:%s ;t Type:string !n",p2); if (*p0='.') /* 处理由点号开头的实数 */ if (*(p0+1)='') printf("n Float data is wrong. Exit !"); break; else if (isdigit(*(p0+1) do *p2=*p0; p0+; p2+; if (!isdigit(*p0)&&*p0!='') printf("n Float data is wro

37、ng. Exit !"); break; while(*p0!=''); p2=t2; cf+; printf(" Data:%s ;t Type: float !n",p2); if (*p0='0') /* 处理整数0或由0作整数部分的实型常量 */ *p2=*p0; p0+; p2+; if (*p0='') ci+;printf(" Data:%c ;t Type:int !n",*(p2-1); else if (*p0='.') do *p2=*p0; p0+; p2+

38、; if (!isdigit(*p0)&&*p0!='') printf("n Float data is wrong. Exit !"); break; while(*p0!=''); p2=t2; cf+; printf(" Data:%s ;t Type:float !n",p2); if (isdigit(*p0)&&(*p0!='0') /* 处理其它整型常量和实型常量*/ p3=t0;p3="int"ci+;do *p2=*p0; p0+; p

39、2+; if (!isdigit(*p0)&&*p0!=''&&*p0!='.') printf("n Int data is wrong. Exit !"); break; else if (*p0='.')p3=t0;p3="float"ci-;cf+; while(*p0!=''); p2=t2; printf(" Data:%s ;t Type:%s !n",p2,p3); /* 存放常量值的p2处理完 */ else p0+; /

40、* 输入串p0处理完 */ printf(" n Total:n tint numbers: %dn tfloat numbers: %d",ci,cf); printf(" n tstring numbers: %dn tchar numbers: %d",cs,cc); printf(" n tbool numbers: %d",cb); /* 输出各类型常量个数的统计结果 */A.3 基于预测分析方法的表达式语法分析器参考源程序#include <stdio.h>#include <string.h>#i

41、nclude <ctype.h>#define max 100#define ERROR 1char stackmax;int top=0;struct production char a; char X;char M5; prod13=/* 将预测分析表的数据结构定义为结构体数组*/'m','S',"AT",'(','S',"AT"), '+','T',"+AT", ')','T',"$",'#','T',"$", 'm','A',"BU", '(','A',"BU"), '+','U',"$",'*','U',"*BU",')'