《编译原理》
实验目的和内容
编译原理实验的目的是使学生将编译理论运用到实际当中,实现一个简单语言集的词法、语法和语义分析程序,验证实际编译系统的实现方法,并加深对编译技术的认识。
实验内容共需实现编译器的词法、语法和语义分析程序三个组成部分。要求学生必须完成每个实验的基本题目要求,有余力的同学可尝试实验的扩展要求部分。
实验报告
要求每人针对所完成的实验内容上交一份实验报告,其中主要包括三方面内容:1、实验设计:实验采用的实现方法和依据(如描述语言的文法及其机内表示,词法分
析的单词分类码表、状态转换图或状态矩阵等,语法分析中用到的分析表或优先矩阵等,语法制导翻译中文法的拆分和语义动作的设计编写等);具体的设计结果(应包括整体设计思想和实现算法,程序结构的描述,各部分主要功能的说明,以及所用数据结构的介绍等)。
2、程序代码:实验实现的源程序,要求符合一般的程序书写风格,并包括必要的注释。
3、实验结果分析:自行编写若干源程序作为测试用例,对所生成的编译程序进行测试
(编译程序的输入与输出以文件的形式给出);运行结果分析(至少包括一个正确和一个错误单词或语句的运行结果);以及改进设想等。
另外,在实验报告的最后,欢迎每位同学写上对每个实验的收获、体会,特别是希望和建议,以利于今后不断改进教学,积累经验。
注意事项
1、电子版实验报告和源程序在最后一次机时后的一周内上交。(每个同学上交一个压
缩文件,其命名格式为“学号_姓名.rar”,内含实验报告和一个命名为“源程序”
的文件夹。注意提交的源程序应是经过调试、测试成功的较为通用的程序,并应有相应的注释、运行环境和使用方法简介。)
2、不接受不完整的实验报告和没有说明注释的源程序,或者说明与程序、运行结果不
符合的作业。
特别鼓励:扩展题目
1、为亲身经历一个小型编译器的开发全过程,触摸一下与实际编译器开发相关的工作,
大家可以自由组成3人左右的小组,推举组长,模拟一个团队分工协作开发大型软件的实战环境,融入软件工程的思想规范和一般理论方法,初步体验从系统分析设计、编码测试到交付维护的一个完整编译器软件的开发过程。要求组长为每个小组成员分配主要负责的任务,完成相应的分析设计员、程序员和测试员等角色的工作,并以小组为单位提交一份实验报告和源程序,在报告封面上写明每个同学主要完成和负责的部分。
2、以组为单位完成的实验内容至少必须整合词法、语法和语义三个部分的实验,对于
选定的适当规模的文法(如C语言的一个大小适宜的子集),进行系统的总体设计、功能分析、编码测试等工作。完成一个从对源程序的词法分析开始,到中间代码生成的完整的编译器前端的开发,使所涉及到的编译系统的各个组成模块有机地衔接在一起,提交一份完整的实验报告和源程序,并将以下几个方面描述清楚:
1)任务概述
2)系统的设计
3)系统实现(包括框图,各.h和.c文件说明,所有函数功能的说明,数据结构、各种表格、变量等的说明,以及函数调用关系图等)
4)系统工作过程及运行说明(使用操作指南)
5)源程序清单(要求有详细注释)和实例程序运行结果
6)体会和讨论
3、实验题目
1)参考题目:在词法、语法和语义三个基本实验题目的基础上,完成以下扩展部分的要求:实验一:
(1)扩充关键字的数目、增加单词类别(如分界符、逻辑运算符等)、将常数分成字符串常量、整型常量和实型常量等;添加词法分析中单词出错的位置、加细错误类型的检查以
及删除注释部分等;并考虑如何在词法分析阶段建立变量名表和常数表,以备后续的编
译过程查询。
(2)选作:识别一个程序设计语言(如C语言)所有单词的词法分析程序设计。建议自学LEX系统。
实验二:
(1)至少完成文法G2[<复合语句>]的两种典型的语法分析程序的设计与实现。
(2)在所给文法G2[<复合语句>]的基础上,适当扩大分析对象,增加功能。如赋值语句的左部不再只局限于简单变量和常数,可以是下标变量等;右部的算术表达式中可以包括
函数调用、数组元素等。除赋值语句外,还可进一步选择高级语言的其它语法结构类型,
如流程控制语句、子程序结构语句、说明语句等。语法分析的结果以语法树的形式输出,
并显示分析过程的信息(如分析栈、符号栈、当前应被归约的最左子串、归约后所得的
符号等)。
(3)增强错误检查和处理能力。例如,当输入的源程序存在错误时,把所发现的每一处错误的性质(错误编码)和位置填入一张表中,以备以后输出之用;同时再跳过错误所在的语法范畴(如单词、表达式、语句等),继续对输入串的后续部分进行编译。至于对错误的具体处理措施应结合所采用的语法分析方法,以LR分析为例,可对LR分析表中的空白单元进行出错原因分析,填入一个指向出错处理子程序的指示字。
(4)选作:学习编译器的自动生成工具LEX、YACC(或其它类似工具)的使用方法,运用LEX和YACC编写并生成以下文法G[<程序>]所定义语言的词法和语法分析程序。
G[<程序>]:
<程序> → PROGRAM<标识符>;<分程序>
<分程序> → <变量说明>BEGIN<语句表>END.
<变量说明> → V AR<变量说明表>;
<变量说明表> → <变量表>:<类型> | <变量表>:<类型>;<变量说明表>
<类型> → INTEGER | REAL
<变量表> → <变量> | <变量>,<变量表>
<语句表> → <语句> | <语句>;<语句表>
<语句> → <赋值语句> | <条件语句> |
<赋值语句> → <变量>:=<算术表达式>
<条件语句> → IF<关系表达式>THEN<语句>ELSE<语句>
<复合语句> → BEGIN<语句表>END
<算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项>
<项> → <因式> | <项>*<因式> | <项>/<因式>
<因式> → <变量> | <常数> | (<算术表达式>)
<关系表达式> → <算术表达式> <关系符> <算术表达式>
<变量> → <标识符>
<标识符> → <标识符> <字母> | <标识符> <数字> | <字母>
<常数> → <整数> | <浮点数>
<整数> → <数字> | <数字> <整数>
<浮点数> →? <整数> | <整数> ? <整数>
<关系符> → < | <= | = | > | >= | <>
<字母> → A|B|C|…|X|Y|Z|a|b|c|…|x|y|z
<数字> → 0|1|2|…|9
实验三:
(1)增加语义分析的范围,如进一步完成布尔表达式(参见教材P200)、常见程序流程控制语句(参见教材P205)等的翻译。
(2)语法制导翻译过程的可视化处理,选择编译各阶段用到的典型算法实现其动态演示。
(3)选作:完成实验二中文法G[<程序>]所定义的语言的语法制导翻译程序。
2)自拟题目:根据小组成员的兴趣自主选择或自定实验题目。要求先提交一份申请文档,说明所选题目、实现方案和技术路线;然后小组成员再与教师就题目的难易程度和工作量具体讨论调整,细化课程设计内容,最终确定要完成的主要工作;在得到老师的认可之后方可继续进行。
实验一词法分析程序实现
一、实验目的与要求
通过编写和调试一个词法分析程序,掌握在对程序设计语言的源程序进行扫描的过程中,将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。
二、实验内容
根据教学要求并结合学生自己的兴趣和具体情况,从具有代表性的高级程序设计语言的各类典型单词中,选取一个适当大小的子集。例如,可以完成无符号常数这一类典型单词的识别后,再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。
输入:由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。
输出:把单词的字符形式表示翻译成编译器的内部表示,确定单词串的输出形式,并将其结果放到某个文件中。要求所输出的每一单词均按形如(CLASS,V ALUE)的二元式编码。对于变量和常数,CLASS字段为相应的类别码;V ALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号(要求在变量名表登记项中存放该标识符的字符串;常数表登记项中则存放该常数的二进制形式)。对于关键字和运算符,采用一词一类的编码形式;由于采用一词一类的编码方式,所以仅需在二元式的CLASS字段上放置相应的单词的类别码,V ALUE字段则为“空”。不过,为便于查看由词法分析程序所输出的单词串,要求在CLASS字段上放置单词类别的助记符。三、实现方法与环境
词法分析是编译程序的第一个处理阶段,可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义(如BNF),用手工的方式(例如可用C语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应的状态矩阵,该状态矩阵连同控制程序一起便组成了编译器的词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成,即首先用正规式对语言中的各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程序所应进行的语义处理工作,然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。
总的来说,开发一种新语言时,由于它的单词符号在不停地修改,采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了,则采用手工编写词法分析程序效率更高。
四、基本实验题目
题目1:试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。
语言中具有的单词包括五个关键字begin、end、if、then、else;标识符;整型常数;六种关系运算符;一个赋值符和四个算术运算符。参考实现方法简述如下。
单词的分类:构造上述语言中的各类单词符号及其分类码表。
表I 语言中的各类单词符号及其分类码表
处理过程:在一个程序设计语言中,一般都含有若干类单词符号,为此可首先为每类单词建立一张状态转换图,然后将这些状态转换图合并成一张统一的状态图,即得到了一个有限自动机,再进行必要的确定化和状态数最小化处理,最后据此构造词法分析程序。在此为了使词法分析程序结构比较清晰,且尽量避免某些枝节问题的纠缠,假定要编译的语言中,全部关键字都是保留字,程序员不得将它们作为源程序中的标识符;在源程序的输入文本中,关键字、标识符、整常数之间,若未出现关系和算术运算符以及赋值符,则至少须用一个空白字符加以分隔。作了这些限制以后,就
可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时,若扫视到的第一个字符为字母,则把后续输入的字母或数字字符依次进行拼接,直至扫视到非字母、数字字符为止,以期获得一个尽可能长的字母数字字符串,然后以此字符串查所谓保留字表(此保留字表已事先造好),若查到此字符串,则取出相应的类别码;反之,则表明该字符串应为一标识符。采用上述策略后,针对表I中部分单词可以构造一个如图1所示的有限自动机(以状态转换图表示)。在图1中添加了当进行状态转移时,词法分析程序应执行的语义动作。根据图1,可用C语言编写出符合以上几项要求的一个相应的扫描器程序,如程序一所示。
图1 识别表I所列语言中的部分单词的DFA及相关的语义过程
图1及程序一中所出现的语义变量及语义函数的含义和功能说明如下:
函数GETCHAR:每调用一次,就把扫描指示器当前所指示的源程序字符送入字符变量ch,然后把扫描指示器前推一个字符位置。
字符数组TOKEN:用来依次存放一个单词词文中的各个字符。
函数CAT:每调用一次,就把当前ch中的字符拼接于TOKEN中所存字符串的右边。
函数LOOKUP:每调用一次,就以TOKEN中的字符串查保留字表,若查到,就将相应关键字的类别码赋给整型变量c;否则将c置为零。
函数RETRACT:每调用一次,就把扫描指示器回退一个字符位置(即退回多读的那个字符)。
函数OUT:一般仅在进入终态时调用此函数,调用的形式为OUT(c,VAL)。其中,实参c为相应单词的类别码或其助记符;当所识别的单词为标识符和整数时,实参V AL为TOKEN(即词文分别为字母数字串和数字串),对于其余种类的单词,V AL均为空串。函数OUT的功能是,在送出一个单词的内部表示之后,返回到调用该词法分析程序的那个程序。
程序一根据图1编写的扫描器
# include
# include
# include
# define ID 6
# define INT 7
# define LT 8
# define LE 9
# define EQ 10
# define NE 11
# define GT 12
# define GE 13
char TOKEN[20];
extern int lookup (char*);
extern void out (int, char*);
extern report_error (void);
void scanner_example (FILE *fp)
{
char ch; int i, c;
ch=fgetc (fp);
if (isalpha (ch)) /*it must be a identifer!*/
{
TOKEN[0]=ch; ch=fgetc (fp); i=1;
while (isalnum (ch))
{
TOKEN[i]=ch; i++;
ch=fgetc (fp);
}
TOKEN[i]= ′\0′
fseek(fp,-1,1); /* retract*/
c=lookup (TOKEN);
if (c==0) out (ID,TOKEN); else out (c," ");
}
else
if(isdigit(ch))
{
TOKEN[0]=ch; ch=fgetc(fp); i=1;
while(isdigit(ch))
{
TOKEN[i]=ch; i++;
ch=fgetc(fp);
}
TOKEN[i]= ′\0′;
fseek(fp,-1,1);
out(INT,TOKEN);
}
else
switch(ch)
{
case ′<′: ch=fgetc(fp);
if(ch==′=′)out(LE," ");
else if(ch==′>′) out (NE," ");
else
{
fseek (fp,-1,1);
out (LT," ");
}
break;
case ′=′: out(EQ, " "); break;
case ′>′: ch=fgetc(fp);
if(c h==′=′)out(GE," ");
else
{
fseek(fp,-1,1);
out(GT," ");
}
break;
default: report_error( ); break;
}
return;
}
提示:扫描器所用的若干函数以及主程序有待于具体编写,并需事先建立好保留字表,以备查询。例如:
/* 建立保留字表*/
#define MAX_KEY_NUMBER 20 /*关键字的数量*/
#define KEY_WORD_END “waiting for your expanding”/*关键字结束标记*/
char *KeyWordTable[MAX_KEY_NUMBER]={“begin”,“end”, “if”, “then”, “else”, KEY_WORD_END}; /* 查保留字表,判断是否为关键字*/
int lookup (char *token)
{
int n=0;
while (strcmp(KeyWordTable[n], KEY_WORD_END)) /*strcmp比较两串是否相同,若相同返回0*/ {
if (!strcmp(KeyWordTable[n], token)) /*比较token所指向的关键字和保留字表中哪个关键字相符*/ {
return n+1; /*根据单词分类码表I,设置正确的关键字类别码,并返回此类别码的值*/
break;
}
n++;
}
return 0; /*单词不是关键字,而是标识符*/
}
另外,在扫描源程序字符串时,一旦识别出关键字、标识符、整常数以及运算符
中之一,即以二元式形式(类别编码,值)输出单词到指定文件中。每次调用该词法分析程序,它均能自动继续扫描下去,形成下一个单词,直至整个源程序全部扫描完毕,并形成相应的单词串形式的源程序文件。
题目2:将表I单词集中的整常数改为无符号常数, 修改题目1中已开发的扫描器。
无符号常数的单词分类码助记符:UCON;其值为无符号常数的机内二进制表示。
描述无符号数的正规文法和状态转换图:
无符号数的右线性文法G1[<无符号数>]如下:
〈无符号数〉→d〈余留无符号数〉
〈无符号数〉→·〈小数部分〉
〈无符号数〉→ d
〈余留无符号数〉→d〈余留无符号数〉
〈余留无符号数〉→·〈十进小数〉
〈余留无符号数〉→E〈指数部分〉
〈余留无符号数〉→ d
〈余留无符号数〉→·
〈十进小数〉→E〈指数部分〉
〈十进小数〉→d〈十进小数〉
〈十进小数〉→ d
〈小数部分〉→d〈十进小数〉
〈小数部分〉→ d
〈指数部分〉→d〈余留整指数〉
〈指数部分〉→+〈整指数〉
〈指数部分〉→-〈整指数〉
〈指数部分〉→ d
〈整指数〉→d〈余留整指数〉
〈整指数〉→ d
〈余留整指数〉→d〈余留整指数〉
〈余留整指数〉→d
图2所示为上述文法的状态转换图,其中编号0、1、2、…、6分别代表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>。
图2 文法G1[<无符号数>]的状态转换图
实现无符号数识别的参考方法:在计算机内实现状态转换图的方法之一,是以状态图中的各个状态为行,以可能输入的各个输入符号为列,组成一个状态矩阵。其中,
矩阵的元素用来指明下一个状态和扫描器应完成的语义动作(如拼接字符、数制转换、查填符号表以及输出单词的内部表示等)。由于在一个状态矩阵中,通常有许多状态都是出错状态,为了节省存放状态矩阵的存储空间,在具体实现时,常常采用更为紧凑和有效的数据结构。例如,对于文法G1[<无符号数>]的状态转换图,可按表II的形式来存放其状态矩阵。表II中的第一列为各状态Si的编号,第二列分别列出了在每一状态下可能扫视到的输入符号aj(其中“other”是一个符号集合,用来表示在相应状态所属的那一栏中,除其前所列字符之外的全部其它字符),第三列指出当(Si,aj)出现时应执行的语义动作(通常用若干个语句来实现,若其为空,则表示不进行任何处理),最后一列用来指明下一状态的编号(若其为NULL或“结束”则表示无后继状态)。状态矩阵中所嵌入的语义动作,其功能是在扫描源程序字符串的过程中,把识别出的字符串形式的无符号数的值,逐步转换为相应的二进制整数(ICON)或二进制浮点数(FCON)的内部形式,方法详见教材第56页。(注:考虑能否采用C语言的库函数实现此语义处理工作。)
表II 包含语义处理过程的识别无符号数的状态矩阵
根据加入语义过程说明的识别无符号数的状态矩阵,编写词法分析程序,部分实现代码如程序二所示。
程序二单词分类码为UCON的无符号数的识别程序
1 #include
2 #include
3 #include
4
5 #define DIGIT 1
6 #define POINT 2
7 #define OTHER 3
8 #define POWER 4
9 #define PLUS 5
10 #define MINUS 6
11 #define UCON 7 //Suppose the class number of unsigned constant is 7
12 #define ClassOther 200
13 #define EndState -1
14 int w,n,p,e,d;
15 int Class; //Used to indicate class of the word
16 int ICON;
17 float FCON;
18 static int CurrentState; //Used to present current state, the initial value:0
19
20 int GetChar (void);
21 int EXCUTE (int,int);
22 int LEX (void);
23 int HandleOtherWord (void)
24 {return ClassOther;
25 }
26 int HandleError (void)
27 {printf ("Error!\n"); return 0;}
28
29 int GetChar (void)
30 {
31 int c;
32 c=getchar ( );
33 if(isdigit(c)) {d=c-′0′;return DIGIT;}
34 if (c==′.′) return POINT;
35 if (c==′E′||c==′e′) return POWER;
36 if (c==′+′) return PLUS;
37 if (c==′-′) return MINUS;
38 return OTHER;
39 }
40 int EXCUTE (int state, int symbol)
41 {
42 switch (state)
43 {
44 case 0:switch (symbol)
45 {
46 case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break;
47 case POINT: w=0;n=0;p=0;e=1;CurrentState=3;Class=UCON;break;
48 default: HandleOtherWord( );Class=ClassOther;
49 CurrentState=EndState;
50 }
51 break;
52 case 1:switch (symbol)
53 {
54 case DIGIT: w=w*10+d;break; //CurrentState=1
55 case POINT: CurrentState=2;break;
56 case POWER: CurrentState=4;break;
57 default: ICON=w;CurrentState=EndState;
58 }
59 break;
60 case 2:switch (symbol)
61 {
62 case DIGIT: n++;w=w*10+d;break;
63 case POWER: CurrentState=4;break;
64 default: FCON=w*pow(10,e*p-n);CurrentState=EndState;
65 }
66 break;
67 case 3:switch (symbol)
68 {
69 case DIGIT: n++;w=w*10+d;CurrentState=2;break;
70 default: HandleError( );CurrentState=EndState;
71 }
72 break;
73 case 4:switch (symbol)
74 {
75 case DIGIT: p=p*10+d;CurrentState=6;break;
76 case MINUS: e=-1;CurrentState=5;break;
77 case PLUS: CurrentState=5;break;
78 default: HandleError( );CurrentState=EndState;
79 }
80 break;
81 case 5:switch (symbol)
82 {
83 case DIGIT: p=p*10+d;CurrentState=6;break;
84 default: HandleError( );CurrentState=EndState;
85 }
86 break;
87 case 6:switch (symbol)
88 {
89 case: DIGIT:p=p*10+d;break;
90 default: FCON=w*pow(10,e*p-n);CurrentState=EndState;
91 }
92 break;
93 }
94 return CurrentState;
95 }
96 int LEX (void)
97 {
98 int ch;
99 CurrentState=0;
100 while (CurrentState!=EndState)
101 {
102 ch=GetChar( );
103 EXCUTE (CurrentState,ch);
104 }
105 return Class;
106 }
五、注意
1、上机前的准备:完成词法分析程序的程序流图,并选择好相应的数据结构。
2、编程:用C语言或你熟悉的其它高级程序设计语言编写一个规模适当的扫描器。
3、调试:将各个模块连接成一个完整程序,并整体调试成功。
4、测试:用于测试扫描器的实例源文件中应有词法正确的,也应有错误的字符串,并至少应包含两行以上的源代码。
5、输出结果:对于输入的测试用例的源程序文件,以对照的形式将扫描器的分析结果在输出文件中表示出来,必要时给出错误提示信息。例如,输入:“1.5E?2+100”,输出:(UCON,0.015)对应“1.5E?2”
(PL,)对应“+”
(UCON,100)对应“100”
实验二语法分析程序实现
一、实验目的与要求
通过设计、编制、调试一个典型的语法分析程序(任选有代表性的语法分析方法,如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等,作为编制语法分析程序的依据),对扫描器所提供的单词序列进行语法检查和结构分析,实现并进一步掌握常用的语法分析方法。
二、实验内容
选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象,给出其文法描述(注意应与所采用的语法分析方法比较贴近),设计并实现一个完整的语法分析程序(分析过程暂不嵌入任何的语义动作)。
输入:由实验一输出的单词串,例如:UCON,PL,UCON ······
输出:对于输入的符号串,若是给定文法定义的合法句子,则输出“RIGHT”,并且给出每一步分析过程;若不是句子,即输入串有错误,则输出“ERROR”,并且显示分析至此所得的中间结果,如分析栈、符号栈中的信息等,以及必要的出错说明信息。
三、一般实现方法说明
例如,以如下文法G2所定义的算术表达式的赋值语句作为分析对象,编写并调试一个语法分析程序。
G2[<复合语句>]:
<复合语句> → begin<语句表>end
<语句表> → <语句>|<语句>;<语句表>
<语句> → <赋值语句>
<赋值语句> → <变量>:=<算术表达式>
<算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项>
<项> → <因式> | <项>*<因式> | <项>/<因式>
<因式> → <变量> | <常数> | (<算术表达式>)
<变量> → <标识符>
<标识符> → <标识符> <字母> | <标识符> <数字> | <字母>
<常数> → <整数> | <浮点数>
<整数> → <数字> | <数字> <整数>
<浮点数> →? <整数> | <整数> ? <整数>
<字母> → A|B|C|…|X|Y|Z|a|b|c|…|x|y|z
<数字> → 0|1|2|…|9
说明:1)可将以上文法G2[<复合语句>]中的语法范畴<常数>替换为实验一中的
文法G1[<无符号数>],并将单词类型——无符号常数进一步细分成整数和浮点数两类
单词。2)注意修改实验一中的词法分析程序,将它编写为子程序的形式,以便供语法分析程序调用,从而在对源程序的一遍扫描过程中,同时完成词法和语法分析任务。3)应加强错误检查,对输入符号串中的词法、语法错误,给出必要的说明信息,尽可能多地、确切地指出错误的位置、原因和性质。例如,在词法分析阶段,对当前正在处理的字符ch,可进一步定义一些与该字符相关的信息row和col,分别表示该字符所在的行和列,这些内容在出错处理时用来提供和源程序位置相关的信息。即定义:char ch; /*The current character*/
int row; /*The line number position of the current character*/
int col; /*The column number position of the current character*/
四、基本实验题目
题目:对算术表达式的一个简化子集,根据如下其语法结构的BNF定义G3[<算术表达式>],任选学过的一种语法分析方法,针对运算对象为无符号数的四则运算,编制一个语法分析程序。
G3[<算术表达式>]:
<算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项>
<项> → <因式> | <项>*<因式> | <项>/<因式>
<因式> → <运算对象> | (<算术表达式>)
若将非终结符号<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F和
i代表,则G3可写成:
E→T|E+T|E-T T→F|T*F|T/F F→i|(E)
下面简要给出基于递归下降法、预测分析法、算符优先法、SLR(1)四种语法分析程序的开发方法示例说明。
示例一:采用具有递归功能的高级语言编制递归下降法的语法分析程序。
运算对象i可以进一步定义为变量、常数等,例如,此处将i定义为:
i→<变量> <变量>→<标识符> <标识符>→<字母> <字母>→A|B|C|…|X|Y|Z 利用扩充的BNF消除G3[E]中E和T的左递归后,采用递归下降法分析上述算术表达式的框图见图3。其中ZC过程为总控程序,被设计成可以分析无穷多个算术表达式,主要完成:1)通知外界键入算术表达式。2)控制E过程分析算术表达式。3)根据分析结果之正误,分别输出不同的信息。
图3 递归下降法分析算术表达式的框图
(a) ZC 过程 (b) E 过程 (c) T 过程 (d) F 过程 (e) SYM 函数 (f) ADV ANCE 过程
E、T和F三个过程分别对应<算术表达式>、<项>和<因式>三个产生式的处理。它们利用到两个公共函数:一个是函数SYM,它负责从输入字符串ST中取出下一个字符,并存入SYM中等待分析;另一个是ADV ANCE过程,负责剔除ST中的首字符,可通过挪动字符串指针的办法来实现。实际上是通过调用词法分析程序来实现SYM和ADANCE功能的。变量TZ之值标志分析的结果(表达式是否有错)。
示例二:基于预测分析法的语法分析程序。
参考教材P121例4.3,首先编写无二义性的简单算术表达式的文法(4.1),并通过消除左递归对其进行改写。然后求出如表4-1所示的各个FIRST集和FOLLOW集。再检查是不是LL(1)文法,并按照LL(1)文法构造如表4-2所示的预测分析表。最后根据预测分析器的工作流程,实现预测分析器的控制程序。
示例三:用C语言编制算符优先分析法的语法分析程序如程序三所示。其中使用了分析栈stack,用来在分析过程中存放当前句型的某一前缀,一旦句型的最左素短语在栈顶形成,便立即进行归约。
程序三算符优先分析算法
#define RIGHT 1
#define ERROR 0
#define MAXINPUT 300
#define MAXSTACK 100
#define STARTSYMBOL ′S′
int stack[MAXSTACK],a[MAXINPUT]; /* a[ ] is input line */
int IsHigherThan (int, int); /* priority detection */
int IsLowerThan (int, int); /* priority detection */
int IsEqualTo (int, int); /* priority detection */
int Reduce (int begin, int end, int len);
int IsVt (int); /* determine if stack symbol is in Vt */
int parser (void)
{
int i, k, r, NewVn; /* NewVn holds left side of a production */
i=0; k=0; /* i, k is index of a[ ] and stack[ ] separately */
stack[0]= ′#′;
do
{
int j;
r=a[i++];
if (IsVt(stack[k])) j=k; else j=k-1;
while (IsHigherThan(stack[j],r))
{
int q;
do {
q=stack[j];
if (IsVt(stack[j-1])) j--; else j-=2;
} while(!IsLowerThan(stack[j],q);
NewVn=Reduce(stack[j+1],stack[k],k-j);
k=j+1; /* reduce the leftmost prime phrase */
stack[k]=NewVn; /* it is stack[j+1] stack[j+2] … stack[k] */
} /*end of while*/
if (IsLowerThan(stack[j],r)) || IsEqualTo(stack[j],r))
stack[++k]=r;
else return ERROR;
} while (r!=′#′);
return RIGHT;
}
首先,对于分析对象,如无符号数的四则运算编写文法G3[<算术表达式>],确定一种合适的数据结构,以构造所给文法的机内表示。然后,构造该文法的算符优先关系矩阵。在此可以根据算术表达式中各算符的优先级和结合性,直接手工构造算符优先关系。最后,编写程序三中所用到的各个函数,完成整个算符优先语法分析器的开发。
另外,如果我们希望在分析过程中为句子建立一棵“语法树”,则可在每移进一个终结符号时,就建立一个末端结点;而在用某一产生式将句型的最左素短语归约为某个非终结符号N时,就建立以N为标记的结点,此结点的各子结点(从左到右)依次是最左素短语的各个符号。
示例四:SLR(1)分析器的开发。
可以根据文法G3[<算术表达式>]构造识别其全部活前缀的DFA,再据此构造SLR(1)分析表,然后编程实现SLR(1)分析表的驱动程序,即LR分析器的总控程序,完成对算术表达式的识别。
五、注意
1、上机前的准备:结合题目的要求,确定语法分析程序的流程图,同时考虑相应的数据结构,用C或其它高级语言初步编写一个语法分析源程序。
2、调试:将词法、语法分析合在一起构成一个完整的程序,并调试成功。
3、测试:供测试的例子应包括符合语法规则的语句,以及分析程序能够判别的若干错例。
4、结果输出:对于所输入的字符串,不论对错,都应有明确的信息告诉外界。
5、编写的源程序中应有较为详细的说明和注释。例如,对文法机内表示的解释、数据结构的说明、函数的作用、全局变量的含义等等。
实验三语义分析程序实现
一、实验目的与要求
在实现词法、语法分析程序的基础上,编写相应的语义子程序,进行语义处理,加深对语法制导翻译原理的理解,进一步掌握将语法分析所识别的语法范畴变换为某种中间代码(四元式)的语义分析方法,并完成相关语义分析器的代码开发。
二、实验内容
语法制导翻译模式是在语法分析的基础上,增加语义操作来实现的。对于给定文法中的每一产生式,编写相应的语义子程序。在语法分析过程中,每当用一个产生式进行推导或归约时,语法分析程序除执行相应的语法分析动作之外,还要调用相应的语义子程序,以便完成生成中间代码、查填有关表格、检查并报告源程序中的语义错误等工作。每个语义子程序需指明相应产生式中各个符号的具体含义,并规定使用该产生式进行分析时所应采取的语义动作。这样,语法制导翻译程序在对源程序从左到右进行的一遍扫描中,既完成语法分析任务,又完成语义分析和中间代码生成方面的工作。
输入:包含测试用例,如由无符号数和+、?、*、/、(、)构成的算术表达式的源程序文件。
输出:将源程序转换为中间代码形式表示,并将中间代码序列输出到文件中。若源程序中有错误,应指出错误信息。
三、一般实现方法
语法制导翻译模式实际上是对前后文无关文法的一种扩展。一般而言,首先需要根据进行的语义工作,完成对文法的必要拆分和语义动作的编写,从而为每个产生式都配备相应的语义子程序,以便在进行语法分析的同时进行语义解释。要求从编译器的整体设计出发,重点通过对实验二中语法分析程序的扩展,完成一个编译器前端程序的编写、调试和测试工作,形成一个将源程序翻译为中间代码序列的编译系统。
四、基本实验题目
题目:对文法G3[<算术表达式>]中的产生式添加语义处理子程序,完成无符号数的四则运算的计值处理,将输入的四则运算转换为四元式形式的中间代码。
例如,对文法G3[<算术表达式>]在利用递归下降法进行语法分析的同时,生成四
元式形式的中间代码序列。其语法制导翻译程序的核心部分(指表达式、项和因式的处理)的算法思想,可用程序四所示的框架描述。
程序四利用递归下降法生成简单算术表达式的四元式序列E( ) /* 识别<算术表达式> */
{
E1_PLACE=T( ); /*调用T( )分析产生算术表达式计算的第一项E1*/
while (SYM=’+’ || SYM=’-’)
{
ADVANCE; /*使输入串指针指向下一个输入符号,即调用扫描器读入下一个单词符号*/
E2_PLACE=T( ); /*调用T( )分析产生算术表达式计算的第二项*/
T1=NewTemp( ); /*分配一个新的临时变量,以便存储计算结果*/
GEN(±, E1_PLACE, E2_PLACE, T1); /*根据所给实参产生一个四元式,送入四元式表*/
E1_PLACE=T1; /*将计算结果作为下一次表达式计算的第一项*/
}
return E1_PLACE;
}
T( ) /* 识别<项>*/
{
T1_PLACE=F( );
while (SYM=’*’ || SYM=’/’)
{
ADVANCE;
T2_PLACE=F( );
T1=NewTemp( );
GEN(*/, T1_PLACE, T2_PLACE, T1);
T1_PLACE=T1;
}
return T1_PLACE;
}
F( ) /* 识别<因式>*/
{
if (SYM=’标识符’) /*在此设运算对象i为标识符,即简单变量*/
{
ADVANCE;
return Entry(i.词文); /*以标识符的词文为名字查、填符号表,可理解为返回标识符的值*/ }
else
if ( SYM=’(’ )
{
ADVANCE;
PLACE=E( );
if ( SYM=’)’ )
{
ADVANCE;
return PLACE;
}
else ERROR; /*例如:输出“缺少‘)’错误”*/
}
else ERROR; /*例如:输出“算术表达式应以‘标识符’或‘(’开头”*/ }
说明:1)程序四中出现的主要语义变量和辅助函数的功能为:
编译原理实验指导 实验安排: 上机实践按小组完成实验任务。每小组三人,分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行,然后每小组将程序连接在一起调试,构成一个相对完整的编译器。 实验报告: 上机结束后提交实验报告,报告内容: 1.小组成员; 2.个人完成的任务; 3.分析及设计的过程; 4.程序的连接; 5.设计中遇到的问题及解决方案; 6.总结。
实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序,加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程,从输入的源程序中,识别出各个具有独立意义的单词,即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1.词法分析器的功能和输出格式 词法分析器的功能是输入源程序,输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码,单词符号的属性值)。 2.TEST语言的词法规则
编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序: 把汇编语言程序翻译成等价的机器语言程序 3.编译程序: 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式: 解释程序,逐个语句地模拟执行 翻译执行方式: 翻译程序,把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似,一般分为五个阶段: 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务: 扫描源程序的字符串,识别出的最小的语法单位(标识符或无正负号数等) 语法分析是: 在词法分析的基础上的,语法分析不考虑语义。语法分析读入词法分析程序识别出的符号,根据给定的语法规则,识别出各个语法结构。 语义分析的任务是检查程序语义的正确性,解释程序结构的含义,语义分析包括检查变量是否有定义,变量在使用前是否具有值,数值是否溢出等。
语法分析完成之后,编译程序通常就依据语言的语义规则,利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统,可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换,以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成,其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序,独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序,完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是: 可以优化配置不同的编译程序组合,实现编译重用,保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号,字母表,符号串,符号串的长度计算P18,子符号串的含义,符号串的简单运算XY,Xn, 2.符号串集合的概念,符号串集合的乘积运算,方幂运算,闭包与正闭包的概念P19,P20A0 ={ε} 3.重写规则,简称规则。非xx(V
编译原理实验报告实验名称:实验一编写词法分析程序 实验类型:验证型实验 指导教师:何中胜 专业班级:13软件四 姓名:丁越 学号: 电子邮箱: 实验地点:秋白楼B720 实验成绩: 日期:2016年3 月18 日
一、实验目的 通过设计、调试词法分析程序,实现从源程序中分出各种单词的方法;熟悉词法分析 程序所用的工具自动机,进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解;提高词法分析方法的实践能力。通过本实验,应达到以下目标: 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 (1)主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表,每个数组元素存放一个关键字。采用定长的方式,较短的关键字 后面补空格。 P数组存放分界符。为了简单起见,分界符、算术运算符和关系运算符都放在 p表中 (编程时,还应建立算术运算符表和关系运算符表,并且各有类号),合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后,先以人工方式输入关键字,造 k表;再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词;接收键盘上 送来的一个单词;调用词法分析过程;输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图1-1。 图1-1 该过程取名为 lexical,它根据输入单词的第一个字符(有时还需读第二个字符),判断单词类,产生类号:以字符 k表示关键字;i表示标识符;c表示常数;p表示分界符;s表示运算符(编程时类号分别为 1,2,3,4,5)。 对于标识符和常数,需分别与标识符表和常数表中已登记的元素相比较,如表中已有 该元素,则记录其在表中的位置,如未出现过,将标识符按顺序填入数组id中,将常数 变为二进制形式存入数组中 ci中,并记录其在表中的位置。 lexical过程中嵌有两个小过程:一个名为getchar,其功能为从instring中按顺序取出一个字符,并将其指针pint加1;另一个名为error,当出现错误时,调用这个过程, 输出错误编号。 2.实践部分
南华大学 计算机科学与技术学院 实验报告 ( 2018~2019学年度第二学期) 课程名称编译原理 实验名称词法分析器的设计与 实现 姓名学号
专业班级 地点教师 1.实验目的及要求 实验目的 加深对词法分析器的工作过程的理解;加强对词法分析方法的掌握;能够采用一种编程语言实现简单的词法分析程序;能够使用自己编写的分析程序对简单的程序段进行词法分析。 实验要求 1.对单词的构词规则有明确的定义; 2.编写的分析程序能够正确识别源程序中的单词符号; 3.识别出的单词以 <种别码,值 >的形式保存在符号表中,正确设计和维护 符号表; 4.对于源程序中的词法错误,能够做出简单的错误处理,给出简单的错误 提示,保证顺利完成整个源程序的词法分析; 2.实验步骤 1.词法分析规则 <标识符 >::=< 字母 >|< 标识符 ><字母 >|< 标识符 ><数字 >
<常数 >::=< 数字 >|< 数字序列 ><数字 > <数字序列 >:: =<数字序列 ><数字 >|< 数字 >|<.> <字母 >::=a|b|c|??|x|y|z <数字 >::=0|1|2|3|4|5|6|7|8|9 <运算符 >::=< 关系运算符 >|< 算运算符 >|< 运算符 >|< 位运算符 >|< 运算符 > <算数运算符 >:: =+|-|*|/|...|-- <关系运算符 >:: =<|>|!=|>=|<=|== <运算符 >::=&&| || |! <位运算符 >::=&| | |! <运算符 >::==|+=|-=|/=|*= <分界符 >:: = ,|;|(|)|{|}|:| // |/**/ <保留字 >:: = main|if|else|while|do|for|...|void 2.符号的 符号种符号种 main0>26 if1>=27 else2<28 while3<=29 do4!30 for5!=31
编译原理复习题 一、选择题 1、编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 2、(A)是一种典型的解释型语言。 A.BASIC B.C C.FORTRAN D.PASCAL 3、把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 4、用高级语言编写的程序经编译后产生的程序叫(B) A.源程序 B.目标程序C.连接程序D.解释程序 5、(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 6、通常一个编译程序中,不仅包含词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成等六个部分,还应包括(C)。 A.模拟执行器B.解释器 C.表格处理和出错处理D.符号执行器 7、编译程序绝大多数时间花在(D)上。 A.出错处理B.词法分析C.目标代码生成D.表格管理 8、源程序是句子的集合,(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 9、词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 10、词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 11、文法:G:S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 12、如果文法G是无二义的,则它的任何句子α(A) A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能不同 C.最左推导和最右推导必定相同 D.可能存在两个不同的最左推导,但它们对应的语法树相同
编译原理上机实验试题 一、实验目的 通过本实验使学生进一步熟悉和掌握程序设计语言的词法分析程序的设计原理及相关的设计技术, 如何针对确定的有限状态自动机进行编程序;熟悉和 掌握程序设计语言的语法分析程序的设计原理、熟悉 和掌握算符优先分析方法。 二、实验要求 本实验要求:①要求能熟练使用程序设计语言编程;②在上机之前要有详细的设计报告(预习报告); ③要编写出完成相应任务的程序并在计算机上准确 地运行;④实验结束后要写出上机实验报告。 三、实验题目 针对下面文法G(S): S→v = E E→E+E│E-E│E*E│E/E│(E)│v │i 其中,v为标识符,i为整型或实型数。要求完成 ①使用自动机技术实现一个词法分析程序; ②使用算符优先分析方法实现其语法分析程序,在 语法分析过程中同时完成常量表达式的计算。
1、题目(见“编译原理---实验题目.doc,“实验题目”中的第一项) 2、目的与要求(见“编译原理---实验题目.doc”) 3、设计原理: (1)单词分类:标识符,保留字,常数,运算符,分隔符等等 (2)单词类型编码 (3)自动机 4、程序流程框图 5、函数原型(参数,返回值) 6、关键代码(可打印,只打印关键代码) 7、调试: (1)调试过程中遇到的错误,如何改进的; (2)需要准备测试用例(至少3个,包含输入和输出)——(可打印) 8、思考: (1)你编写的程序有哪些要求是没有完成的,你觉得该采用什么方法去完成; (2)或者是你觉得程序有哪些地方可以进一步完善,简述你的完善方案。
1、题目(见“编译原理---实验题目.doc,“实验题目”中的第二项) 2、目的与要求(见“编译原理---实验题目.doc”) 3、设计原理:构造出算法优先关系表 4、程序流程框图 5、函数原型(参数,返回值) 6、关键代码(可打印,只打印关键代码) 7、调试: (1)调试过程中遇到的错误,如何改进的; (2)需要准备测试用例(至少3个,包含输入和输出)——(可打印) 8、思考: (1)你编写的程序有哪些要求是没有完成的,你觉得该采用什么方法去完成; (2)或者是你觉得程序有哪些地方可以进一步完善,简述你的完善方案。
《编译原理》实验指导书 实验目的和内容 编译原理实验的目的是使学生将编译理论运用到实际当中,实现一个简单语言集的词法、语法和语义分析程序,验证实际编译系统的实现方法,并加深对编译技术的认识。 实验内容共需实现编译器的词法、语法和语义分析程序三个组成部分。要求学生必须完成每个实验的基本题目要求,有余力的同学可尝试实验的扩展要求部分。 实验报告 要求每人针对所完成的实验内容上交一份实验报告,其中主要包括三方面内容:1、实验设计:实验采用的实现方法和依据(如描述语言的文法及其机内表示,词分析 的单词分类码表、状态转换图或状态矩阵等,语法分析中用到的分析表或优先矩阵等,语法制导翻译中文法的拆分和语义动作的设计编写等);具体的设计结果(应包括整体设计思想和实现算法,程序结构的描述,各部分主要功能的说明,法以及所用数据结构的介绍等)。 2、程序代码:实验实现的源程序清单,要求符合一般的程序书写风格,有详细的注释。 3、实验结果分析:自行编写若干源程序作为测试用例,对所生成的编译程序进行测试 (编译程序的输入与输出以文件的形式给出);运行结果分析(至少包括一个正确和一个错误单词或语句的运行结果);以及改进设想等。 注意事项 1、电子版实验报告和源程序在最后一次机时后的一周内上交。(每个同学上交一个压 缩文件,其命名格式为“学号_姓名.rar”,内含实验报告和一个命名为“源程序” 的文件夹。注意提交的源程序应是经过调试、测试成功的较为通用的程序,并应有相应的注释、运行环境和使用方法简介。) 2、不接受不完整的实验报告和没有说明注释的源程序,或者说明与程序、运行结果不 符合的作业。 特别鼓励:扩展题目 1、为亲身经历一个小型编译器的开发全过程,触摸一下与实际编译器开发相关的工作, 大家可以自由组成3人左右的小组,推举组长,模拟一个团队分工协作开发大型软件的实战环境,融入软件工程的思想规范和一般理论方法,初步体验从系统分析设计、编码测试到交付维护的一个完整编译器软件的开发过程。要求组长为每个小组成员分配主要负责的任务,完成相应的分析设计员、程序员和测试员等角色的工作,并以小组为单位提交一份实验报告和源程序,在报告封面上写明每个同学主要完成和负责的部分。 2、以组为单位完成的实验内容至少必须整合词法、语法和语义三个部分的实验,对于 选定的适当规模的文法(如C语言的一个大小适宜的子集),进行系统的总体设计、功能分析、编码测试等工作。完成一个从对源程序的词法分析开始,到中间代码生成的完整的编译器前端的开发,使所涉及到的编译系统的各个组成模块有机地衔接在一起,提交一份完整的实验报告和源程序,并将以下几个方面描述清楚:
第3章文法和语言 第1题 文法G=({A,B,S},{a,b,c},P,S)其中P为: S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案: L(G[S])={abc} 第 11题 令文法 G[E]为: E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明 E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。答案: 此句型对应语法树如右,故为此文法一个句型。 或者:因为存在推导序列: E=>E+T=>E+T*F,所 以E+T*F句型 此句型相对于E的短语有:E+T*F;相对于 T的短语 有 T*F 直接短语为:T*F 句柄为:T*F 第 13题 一个上下文无关文法生成句子abbaa的推导树如下: (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合 P可能有哪些元素? (3)找出该句子的所有短语、直接短语、句柄。 A S a S B B B A S a
《编译原理》课后习题答案第三章 答案: (1)串abbaa最左推导: S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推导: S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有:S→ABS |Aa|ε A→a B→SBB|b abbaa aaabbaa ? 可能元素有:ε aa ab (3)该句子的短语有: a是相对 A的短语 ε是相对 S的短语 b是相对 B的短语 εbb是相对 B的短语 aa是相对 S的短语 aεbbaa是相对 S的短语 直接短语有:a ε b 句柄是:a
实验四中间代码生成 一.实验目的: 掌握中间代码的四种形式(逆波兰式、语法树、三元式、四元式)。 二.实验内容: 1、逆波兰式定义:将运算对象写在前面,而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象(语法)树:运算对象作为叶子结点,运算符作为内部结点。 3、三元式:形式序号:(op,arg1,arg2) 4、四元式:形式(op,arg1,arg2,result) 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈,此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式,为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式,从第一个字符开始判断,如果该字符是数字,则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字,该字符则是运算符,此时需比较优先关系。 做法如下:将该字符与运算符栈顶的运算符的优先关系相比较。如果,该字符优先关系高于此运算符栈顶的运算符,则将该运算符入栈。倘若不是的话,则将此运算符栈顶的运算符从栈中弹出,将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式,确定所有字符都得到正确处理,我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码: //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: ";
《编译原理》课程实验指导书 课程编号: 课程名称:编译原理/Compiler Principles 实验总学时数: 8 适用专业:计算机科学与技术、软件工程 承担实验室:计算机学院计算机科学系中心实验室、计算机技术系中心实验室 一、实验教学的目的与要求 上机实习是对学生的一种全面综合训练,是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常,实习题中的问题比平时的练习题要复杂,也更接近实际。编译原理这门课程安排的2次上机实验都属于一种设计类型的实验,每个实验的训练重点在于基本的编译技术和方法,而不强调面面俱到;实验的目的是旨在使学生进一步巩固课堂上所学的理论知识,深化理解和灵活掌握教学内容;培养学生编制算法的能力和编程解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作,熟悉机器的操作系统和语言的集成环境,独立完成算法设计和程序代码的编写;上机时应随带有关的编译原理教材或参考书;要学会程序调试与纠错。 每次实验后要交实验报告,实验报告的内容应包括: (1)实验题目、班级、学号、姓名、完成日期; (2)简要的需求分析与概要设计; (3)详细的算法描述; (4)源程序清单; (5)给出软件的测试方法和测试结果; (6)实验的评价、收获与体会。 开发工具: (1)DOS环境下使用Turbo C; (2)Windows环境下使用Visual C++ 。 考核: 实验成绩占编译原理课程结业成绩的10%。 三、单项实验的内容和要求: 要求每个实验保证每个学生一台微机。 实验一(4学时):单词的词法分析程序设计。 (一)目的与要求 1.目的 通过设计、编制、调试一个具体的词法分析程序,加深对词法分析原理的理解,并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。
集美大学计算机工程学院实验报告 课程名称:编译原理班级: 指导教师:: 实验项目编号:实验一学号: 实验项目名称:词法分析器的设计实验成绩: 一、实验目的 通过设计编制调试一个具体的词法分析程序,加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 二、实验容 编写一个词法分析器,从输入的源程序(编写的语言为C语言的一个子集)中,识别出各个具有独立意义的单词,即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的部编码及单词符号自身值。(遇到错误时可显示“Error”,然后跳过错误部分继续显示) 三、实验要求 1、词法分析器的功能和输出格式 词法分析器的功能是输入源程序,输出单词符号。词法分析器的单词符 2 别单词的类型,将标识符和常量分别插入到相应的符号表中,增加错误处理等。 3、编程语言不限。
四、实验设计方案 1、数据字典 本实验用到的数据字典如下表所示:
3、实验程序 #include
1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 答案:S→AB|B A→a|aA B→bBc|bc 2.给出下面语言的相应文法 L1={a n b n c m d m| m,n≥1,n为奇数,m为偶数}。 答案:文法G(S):S→AC A→aaAbb/ab C→ccCcc/cc 3、构造一个DFA,它接受 ={a,b}上所有包含ab的字符串。 (要求:先将正规式转化为NFA,再将NFA确定化,最小化) (一)相应的正规式为(a|b)*ab(a|b)* (二)①与此正规式对应的NFA为 答案;在自己写的纸上 4、对下面的文法G: E→TE’E’→+E|εT→FT’T’→T|ε F→PF’F’→*F’|εP→(E)|a|b|∧ (1)证明这个文法是LL(1)的。 考虑下列产生式: E’->E|ε T’->T|ε F’->*F’ |ε P->(E) |∧a|b FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法.
计算这个文法的每个非终结符的FIRST和FOLLOW。(8分) 答案:FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#} FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} (3)构造它的预测分析表。(6分) 答案;在手机上 写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。 答案:逆波兰式:(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 给出下面语言的相应文法 L1={a n b n a m b m|n,m≥0} 给出下面语言的相应文法 答案:S→AB|A|B|∑ A→aAb|ab B→aBb|ab
编译原理实验指导书 主编:徐静李娜 信息与电气工程学院 2010年3月
概述 一、本课程实验的目的和任务 编译原理是一门实践性很强的课程,只有通过实践,才能真正掌握。实际的编译程序是十分复杂的,有时由多达十几万条指令组成。为此,编译原理的实践教学,采用简化编译过程的办法,选择最关键的3个环节──词法分析、语法分析(包括语义处理、产生无优化的目标指令)、连接调试,进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试,再连接在一起总调。 二、实验方法 任何一个实用的高级语言,其语法都比较复杂,如选其作为源语言,很难实践全过程。故本实验将定义一个简化的语言── C语言的一个子集作为源语言,设计调试出它的编译程序。前后贯穿这一条主线进行实践。每次都可利用课余时间编程,利用上机时间进行输入和调试。 三、实验报告的规范和要求 每个实验完成后写出实验报告。实验报告的内容包括如下内容: 一、实验目的 二、程序设计时采用的算法和方法 三、输入的源程序 四、词法分析程序清单和输出结果。 五、心得体会
实验一词法分析 一、实验目的: (1)通过设计编制调试一个具体的词法分析程序,理解词法分析在编译程序中的作用。 (2)加深对有穷自动机模型的理解。 (3)掌握词法分析程序的实现方法和技术。 (4)用C语言对一个简单语言的子集编制一个一遍扫描的程序,以加深对编译原理的理解,掌握编译程序的实现方法和技术。 编制一个读单词过程,从输入的源程序中,识别出各个具有独立意义的单词,即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。(遇到错误时可显示“Error”,然后跳过错误部分继续显示)。 二、实验预习提示 1. 词法分析器的功能和输出格式 词法分析器的功能是输入源程序,输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码,单词符号的属性值)。本实验中,采用的是一类符号一种别码的方式。 2. 单词的BNF表示 <标识符>→ <字母><字母数字串> <字母数字串>→<字母><字母数字串>|<数字> <字母数字串>| <下划线><字母数字串>|ε <无符号整数>→<数字> <数字串> <数字串>→<数字><数字串>|ε <加法运算符>→+ <减法运算符>→- <大于关系运算符>→> <大于等于关系运算符>→>= 3. “超前搜索”方法
2011春课程情况 (1)考试题目来自教材的例题和习题、教材的辅助程序、实验内容几个方面;(2)题型:填空(20%)、简单作答(10%),文法题(10%)、词法分析(20%)、语法分析(20%)、代码优化10%、Lex/yacc程序10%。 (3)重点在计算题上,即形式语言、词法分析、语法分析和代码优化,将占60-70%。主要有 形式语言(根据语言描述写上下文无关文法)(10分), 词法分析(自动机、正则式、正则文法之间相互转化,自动机应用)(20分); 语法分析部分是给出文法和待分析的串,按照某个分析方法构建分析表列分析过程(20分), 可能出现的分析方法有LL(1)、算符优先分析、LR(0)分析 左递归的消除、公共因子提取对文法进行改造 代码优化(10分)。给定一段程序(可能是中间代码形式的),进行优化或找出循环之类的题目。 Lex或Yacc程序简单设计(10) (4)共有题目7道,时间100min; (5)具体考试时间、地点待后通知。
1、给出如图所示NFA(非确定自动机)等价的DFA 2、构造正规式1(1|0)*101相应的DFA. 3、为正规式(ab)*a(a|b)构造NFA、DFA。 4、(1)考虑正规表达式1(1|0)*101,构造可以生成语言L(r)的一个正规文法。 (2)考虑如图所示的NFA N,构造可以生成语言L(N)的一个正规文法. 5、考虑如下文法G: S-->1S|0S|1A A-->0B|1B B-->e (空串) (1) 试构造语言为L(G)的一个正规表达式。 (2) 试构造语言为L(G)的一个有限自动机。 6、构造产生如下语言的上下文无关文法: (1){a n b n|n>0} (2){wcw R|w由a,b组成的任意串} (3){ww R|w由a,b组成的任意串} (4){w|w由a,b组成的任意串且w与其逆串相等} (5) {w|w由a,b组成的任意串且w中a的个数是b个数的2倍} 7、考虑下面的文法: S-->aS|aSbS|e e是空串的意思 这个文法是二义的,试给出串a a b的两个不同的: (1)分析树。 (2)最左推导。 (3)最右推导。 8、已知文法G[S]:
编译原理 实 验 指 导 书
前言 编译原理是计算机科学与技术、软件工程等专业的主干课和必修课,由于这门课程相对抽象且内容较复杂,一直是比较难学的一门课程。在编译原理的学习过程中,实验非常重要,只有通过上机实验,才能使学生对比较抽象的课程内容产生一个具体的感性认识。 本书实验环境主要为C环境及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序,但由于实验者熟悉精通的语言工具不尽相同,因而强求采用统一的编程语言编程是不现实的。实验者在掌握了编译程序各个阶段的功能和原理之后,不难借助使用其他自己熟悉的语言实现相关功能。 实验者在实验过程中应该侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色,写出设计和实现过程中遭遇到的难点和解决办法,可以不拘泥于实验指导给出的参考性设计思路,尽可能在深度和广度上加以拓展。只有这种各具特色的实验报告,才将更有利于体现实验者在创新思维和动手能力上的差异。 通过这些实验,能使学生对这些部份的工作机理有一个详细的了解,达到“知其然,且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。 由于手工生成词法和语法分析器的工作量太大,在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。它们现已成为UNIX的标准应用程序同UNIX一起发行。与此同时GNU推出与LEX完全兼容的FLEX,与YACC完全兼容的BISON。这两个程序都在Internet上以源代码的形式免费发行,所以很容易在其它操作系统下重新编译安装。我们实验采用的就是for dos的FLEX和BISON。本书有关的编译工具及其源程序例子,可到BISON的网站上下载。关于FLEX和BISON的用法简介,参见附录,如需更详细的介绍,请参阅编译工具中帮助文件。
第一章引论 1.编译过程的阶段 由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段 2.编译程序的概念 3.编译程序的结构 例:(B)不是编译程序的组成部分。 A. 词法分析器; B. 设备管理程序 C. 语法分析程序; D. 代码生成程序 4.遍的概念 对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理,生成新的中间形式或最终目标程序,称为一遍。 5.编译程序与解释程序的区别 例:解释程序和编译程序是两类程序语言处理程序,它们的主要区别在于(D)。 A. 单用户与多用户的差别 B. 对用户程序的差错能力 C. 机器执行效率 D. 是否生成目标代码 第三章文法和语言 文法的概念 字母表、符号串和集合的概念及运算 例:(ab|b)*c 与下面的那些串匹配?(ACD) A. ababbc; B. abab; C. c; D. babc; E. aaabc 例:ab*c*(a|b)c 与后面的那些串匹配?(BC) A.acbbc B.abbcac C.abc D.acc 例:(a|b)a+(ba)*与后面的那些串匹配? (ADE)A.ba B.bba C.ababa D.aa E.baa 文法的定义(四元组表示) 文法G定义为四元组(V N,V T,P,S) V N:非终结符集 V T:终结符集 P:产生式(规则)集合 S:开始符号(或识别符号) 例:给定文法,A::= bA | cc,下面哪些符号串可由其推导出(①② ⑤)。 ①cc ②b*cc ③b*cbcc ④bccbcc ⑤bbbcc 什么是推导 例:已知文法G: E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 试给出下述表达式的推导:i*i+i 推导过程:E->E+T ->T+T ->T*F+T ->F*F+T ->i*F+T ->i*i+T ->i*i+F ->i*i+i ●句型、句子的概念 例:假设G一个文法,S是文法的开始符 号,如果S=>*x,则称x是句型。 例:对于文法G,仅含终结符号的句型称 为句子。 ●语言的形式定义 例:设r=(a|b|c)(x|y|z),则L(r)中元素为 9个。 例:文法G产生式为S→AB,A→aAb|ε, B→cBd|cd,则B∈L(G)。 A. ababcd; B. ccdd; C. ab; D. aabb ●等价文法 例:如果两个文法描述了同一个语言,则这两个文法是等价文法。 ●文法的类型 0型:左边至少有一个非终结符 1型:右边长度>=左边长度 2型:左边有且仅有一个非终结符 3型:形如:A->aB,A->a 各类型文法都是逐级包含关系, 例:文法S→abC|c,bC→d是几型文法?0 型 例:文法S→abC,bC→ad是几型文法?1 型 例:文法G[A]:A→ε,A→aB,B→Ab,B→a 是几型文法?2型 例:文法S→a|bC,C→d是几型文法? 3
《编译原理》实验报告软件131 陈万全132852
一、需求分析 通过对一个常用高级程序设计语言的简单语言子集编译系统中词法分析、语法分析、语义处理模块的设计、开发,掌握实际编译系统的核心结构、工作流程及其实现技术,获得分析、设计、实现编译程序等方面的实际操作能力,增强设计、编写和调试程序的能力。 通过开源编译器分析、编译过程可视化等扩展实验,促进学生增强复杂系统分析、设计和实现能力,鼓励学生创新意识和能力。 1、词法分析程序设计与实现 假定一种高级程序设计语言中的单词主要包括五个关键字begin、end、if、then、else;标识符;无符号常数;六种关系运算符;一个赋值符和四个算术运算符,试构造能识别这些单词的词法分析程序。 输入:由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。 输出:把所识别出的每一单词均按形如(CLASS,VALUE)的二元式形式输出,并将结果放到某个文件中。对于标识符和无符号常数,CLASS字段为相应的类别码的助记符;VALUE字段则是该标识符、常数的具体值;对于关键字和运算符,采用一词一类的编码形式,仅需在二元式的CLASS字段上放置相应单词的类别码的助记符,VALUE字段则为“空”。 2、语法分析程序设计与实现 选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的
一个简化子集——作为分析对象,根据如下描述其语法结构的BNF定义G2[<算术表达式>],任选一种学过的语法分析方法,针对运算对象为无符号常数和变量的四则运算,设计并实现一个语法分析程序。 G2[<算术表达式>]: <算术表达式>→<项> | <算术表达式>+<项> | <算术表达式>-<项> <项>→<因式>|<项>*<因式>|<项>/<因式> <因式>→<运算对象> | (<算术表达式>) 若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F和i 代表,则G2可写成: G2[E]:E → T | E+T | E-T T → F | T*F | T/F F → i | (E) 输入:由实验一输出的单词串,例如:UCON,PL,UCON,MU,ID······输出:若输入源程序中的符号串是给定文法的句子,则输出“RIGHT”,并且给出每一步分析过程;若不是句子,即输入串有错误,则输出“ERROR”,并且显示分析至此所得的中间结果,如分析栈、符号栈中的信息等,以及必要的出错说明信息。 3、语义分析程序设计与实现 对文法G2[<算术表达式>]中的产生式添加语义处理子程序,完成运算对象是简单变量(标识符)和无符号数的四则运算的计值处理,将输入的四则运算转换为四元式形式的中间代码。 输入:包含测试用例(由标识符、无符号数和+、?、*、/、(、)构成的算术表达式)的源程序文件。 输出:将源程序转换为中间代码形式表示,并将中间代码序列输出到文件中。 若源程序中有错误,应指出错误信息 二、设计思路 1、词法分析程序设计与实现 1)单词分类 为了编程的实现。我们假定要编译的语言中,全部关键字都是保留字,程序员不得将它们作为源程序中的标识符;作了这些限制以后,就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时,若扫视到的第一个字符为字母,则把后续输入的字母或数字字符依次进行拼接,直至扫视到非字母、数字字符为止,以期获得一个尽可能长的字母数字字符串,然后以此字符串查所谓保留字表(此保留字表要事先造好),若查到此字符串,则取出相应的类别码;反之,则表明该字符串应为一标识符。
《编译原理》复习题 题型:选择题简述题计算题综合(证明)题 第一章引论 1、运行编译程序的计算机称为?而运行目标程序的计算机称为? 宿主机;目标机 2、何谓编译程序?编译程序的输入是?输出是?编译程序:把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序; 输入:源程序; 输出:目标程序; 3、请说明编译程序的逻辑结构。即,画出其逻辑结构图。
4、编译程序的“前端”主要由与源语言有关但与(目标机器)无关的哪些部分组成? 编译前端:与源语言有关,如词法分析,语法分析,语义分析与中间代码产生,与机器无关的优化 5、编译程序的“后端”主要由与(源语言)无关但与(目标机器)相关的哪些部分组成? 编译后端:与目标机有关,与目标机有关的优化,目标代码产生
6、要在某种机器上为某程序语言构造编译程序,必须掌握那几方面的内容? 构造编译程序的前提: 1掌握源语言;2掌握目标语言;3掌握编译方法 7、编译程序的生成方法有哪些? 方法:1高级语言书写;2移植方法;3自编译方式 第二章 高级语言及语法描述 1、简述语言的定义,并写出文法G 定义的语言的集合表示。 语言由语法跟语义(语用)定义; },|{)(* T V S G L ∈?=+ααα 2、给定文法G ,如何写出由G 生成的语言的集合表示? (1、2题结合看,并看不懂他问什么ORZ )
3、语法规则用来描述什么?(语言的形式结构) 语法规则定义了程序的形式结构 4、程序设计语言的语法规则描述方法是什么? 语法规则描述方法:上下文无关文法 5、上下文无关文法由哪几部分组成?其中的终结符号集合、非终结符号集合如何规定? 6、怎样进行句子(句型)的最左推导?最右推导? 7、以形式语言的文法规则手段,描述指定语言方法这不是一个祈使句吗,问题在哪
编译原理实验指导 书
《编译原理》实验指导书 太原科技大学计算机学院 -3-1
序 《编译原理》是国内外各高等院校计算机科学技术类专业,特别是计算机软件专业的一门重要专业课程。该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强,内容较为抽象复杂,涉及到大量的软件设计和算法,因此,一直是一门比较难学的课程。为了使学生更好地理解和掌握编译原理和技术的基本概念、基本原理和实现方法,实践环节非常重要,只有经过上机进行程序设计,才能使学生对比较抽象的教学内容产生具体的感性认识,增强学生综合分析问题、解决问题的能力,并对提高学生软件设计水平大有益处。 为了配合《编译原理》课程的教学,考虑到本课程的内容和特点,本指导书设置了七个综合性实验,分别侧重于词法分析、NFA的确定化、非递归预测分析、算符优先分析器的构造、LR分析、语义分析和中间代码的生成、基于DAG的基本块优化,以支持编译程序的各个阶段,基本涵盖了《编译原理》课程的主要内容。 本指导书可作为《编译原理》课程的实验或课程设计内容,在课程教学的同时,安排学生进行相关的实验。实验平台可选择在MS-DOS或Windows操作系统环境,使用C/C++的任何版本作为开发工具。学生在做完试验后,应认真撰写实验报告,内容应
包括实验名称、实验目的、实验要求、实验内容、测试或运行结果等。
目录 实验一词法分析 ........................................................... 错误!未定义书签。实验二 NFA的确定化.................................................... 错误!未定义书签。实验三非递归预测分析 ............................................... 错误!未定义书签。实验四算符优先分析器的构造................................... 错误!未定义书签。实验五 LR分析 .............................................................. 错误!未定义书签。实验六语义分析和中间代码生成................................ 错误!未定义书签。实验七基于DAG的基本块优化................................... 错误!未定义书签。