编译原理实验报告1

编译原理实验报告

姓名：     

班级：     

学号：     

自评：     中

实验一  词法分析程序实现

一、实验目的与要求

通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。

二、实验内容

根据教学要求并结合学生自己的兴趣和具体情况，从具有代表性的高级程序设计语言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。

输入：由符合或不符合所规定的单词类别结构的各类单词组成的源程序。

输出：把单词的字符形式的表示翻译成编译器的内部表示，即确定单词串的输出形式。例如，所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码；VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和运算符，采用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。另外，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上放置单词类别的助记符。

三、实现方法与环境

词法分析是编译程序的第一个处理阶段，本次试验用手工的方式（C语言）构造词法分析程序。根据文法和状态转换图直接编写词法分析程序。

四、基本实验题目

1）题目1：试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。

语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。

单词的分类：构造上述语言中的各类单词符号及其分类码表。

表I 语言中的各类单词符号及其分类码表

单词符号	类别编码	类别码的助记符	单词值
begin	1	BEGIN
end	2	END
if	3	IF
then	4	THEN
else	5	ELSE
标识符	6	ID	字母打头的字母数字串
整常数	7	INT	数字串
<	8	LT
<=	9	LE
=	10	EQ
<>	11	NE
>	12	GT
>=	13	GE
:=	14	IS
+	15	PL
-	16	MI
*	17	MU
/	18	DI

处理过程：在一个程序设计语言中，一般都含有若干类单词符号，为此首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后据此构造词法分析程序。在此为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、整常数之间，若未出现关系和算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表已事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。采用上述策略后，针对表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为相应单词的类别码或其助记符；当所识别的单词为标识符和整数时，实参VAL为TOKEN（即词文分别为字母数字串和数字串），对于其余种类的单词，VAL均为空串。函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。

函数REPORT_ERROR：当出现词法错误时，用于指出错误位置。

实验二  语法分析程序实现

一、实验目的与要求

通过设计、编制、调试一个典型的语法分析程序（任选有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，作为编制语法分析程序的依据），对扫描器所提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。

二、实验内容

选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象，给出其文法描述（注意应与所采用的语法分析方法比较贴近），设计并实现一个完整的语法分析程序。

输入：源程序以文件的形式输入。

输出：对于所输入的源程序，如果输入符号串是给定文法定义的合法句子，则输出“RIGHT”，并且给出每一步归约的过程；如果不是句子，即输入串有错误，则输出“ERROR”，并且显示已经归约出的各个文法符号。

三、基本实验题目

G1[<赋值语句>]：

<赋值语句> → <变量>:=<算术表达式>

<算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项>

<项> → <因式> | <项>*<因式> | <项>/<因式>

<因式> → <变量> | <常数> | (<算术表达式>)

<变量> → <标识符>

<标识符> → <标识符> <字母> | <标识符> <数字> | <字母>

<常数> → <整数> | <浮点数>

<整数> → <数字> | <数字> <整数>

<浮点数> → • <整数> | <整数> • <整数>

<字母> → A|B|C|…|X|Y|Z|a|b|c|…|x|y|z

<数字> → 0|1|2|…9

用C语言编制算符优先分析法的语法分析程序。分析对象可为赋值语句或算术表达式等。

算法：算符优先分析的算法如程序三所示。其中使用了分析栈stack，用来在分析过程中存放当前句型的某一前缀，一旦句型的最左素短语在栈顶形成，便立即进行归约。

说明：首先，对于所选定的文法（例如G1[<赋值语句>]或G2[<算术表达式>]），应确定一种合适的数据结构，以构造所给文法的机内表示。然后，构造该文法的算符优先关系矩阵。可以通过以下两种途径：一是根据各算符的优先级和结合性，直接手工构造算符优先关系；二是通过编写程序，计算出所给文法的算符优先关系矩阵。计算优先矩阵程序的主要步骤简述如下：1）分别编写计算布尔矩阵B>，B=及B<的程序，为此，还需要编写计算布尔矩阵B的闭包B+的子程序，供计算上述各布尔矩阵时调用。2）编制判定优先矩阵是否有多重定义元素的程序，用来判断所给文法是否为算符优先文法。3）输出各优先关系的布尔矩阵以及有关的判定结果信息。最后，编写程序三中所用到的各个函数，完成整个算符优先语法分析程序的开发。

图3 递归下降法分析算术表达式的框图

(a) ZC过程   (b) E过程   (c) T过程   (d) F过程   (e) SYM函数   (f) ADVANCE过程

优先矩阵：

	(	i	*	/	+	-	)	=	；
(	<	<	<	<	<	<	=	error	error
i	error	error	>	>	>	>	>	error	error
*	<	<	>	>	>	>	>	error	>
/	<	<	>	>	>	>	>	error	>
+	<	<	<	<	>	>	>	error	>
-	<	<	<	<	>	>	>	error	>
)	error	error	>	>	>	>	>	error	>
=	<	<	<	<	<	<	error	<	=
；	<	<	<	<	<	<	error	error	error

程序中所出现的语义变量及语义函数的含义和功能说明如下。

函数Parser()：在OUT()函数中调用，每调用一次，读入一个已经识别的“单词”，将类型压入分析栈，同时进行语法分析，如果能够按已知语法规约，则进行规约动作，否则继续执行词法分析。

函数Reduce()：把可以规约的项按照已知的规约表对应项进行规约，成功规约返回规约项的对应行值，否则返回0。

函数IsVt()：判断词法分析出的“单词”是否是终结符号，是返回1，否则返回0。

函数IsHigherThan ()：根据优先矩阵判断分析栈中的符号的优先级，优先级高返回1，否则返回0。

函数IsLowerThan ()：根据优先矩阵判断分析栈中的符号的优先级，优先级低返回1，否则返回0。

函数IsEqualTo ()：根据优先矩阵判断分析栈中的符号的优先级，优先级相等返回1，否则返回0。

实验三  语义分析程序实现

一、实验目的与要求

在实现词法、语法分析程序的基础上，编写相应的语义子程序，进行语义检查，加深对语法制导翻译原理的理解，进一步掌握将语法分析所识别的语法范畴变换为某种中间代码（四元式）的语义分析方法，完成编译器的前端开发工作。

二、实验内容

语法制导翻译模式是在语法分析的基础上，增加语义操作来实现的。对于给定文法中的每一产生式，编写相应的语义子程序。在语法分析过程中，每当用一产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，还要调用相应的语义子程序，以便完成生成中间代码、查填有关表格、检查并报告源程序中的错误等工作。每个语义子程序需指明相应产生式中各个符号的具体含义，并规定使用该产生式进行分析时所应采取的语义动作。这样，语法制导翻译程序在对源程序从左到右进行的一遍扫描中，既完成语法分析任务，又完成语义分析和中间代码生成方面的工作。

高级语言的语法结构类型很多，例如说明语句、程序流程控制语句、子程序结构语句、格式语句等，可选择其中一类进行语义分析程序的开发。

输入：作为测试用例的源程序文件。

输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。若源程序中有错误，应指出错误信息。

三、基本实验题目

针对实验一中定义的文法G1[<赋值语句>]，首先根据需进行的语义工作，完成对文法的必要拆分和语义动作的编写，从而为每个产生式都配备相应的语义子程序。然后编写并调试相应的语法制导翻译程序。在此，中间代码以四元式表示，并且对于不同数据类型的运算对象，在进行算术运算前须转换为相同的数据类型。

要求完成词法、语法和语义分析的整体设计，重点通过对实验二中语法分析程序的扩展，将编译程序前端涉及的各个模块组合在一起，形成一个将源程序翻译为四元式序列的编译系统。

四、实验算法

对实验二中的示例一给出的文法G2[<算术表达式>]，在利用递归下降法进行语法分析的同时，生成四元式形式的中间代码序列。语法制导翻译程序的核心部分（指表达式、项和因式的处理）的算法，可用程序四描述如下：

程序四 利用递归下降法生成简单算术表达式的四元式序列

E( )  /* 识别<算术表达式>*/

{

E1_PLACE=T( );  /* 语法范畴E的一个属性 */

while (SYM=’+’ || SYM=’-’)

{

ADVANCE;  /* 将输入串指针调整至指向下一个输入符号 */

E2_PLACE=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=’标识符’)

{

ADVANCE;

return Entry(i.词文);  /* 以标识符的词文为名字查、填符号表 */

}

else

if ( SYM=’(’ )

{

ADVANCE;

PLACE=E( );

if ( SYM=’)’ )

{

ADVANCE;

return PLACE;

}

else ERROR;

}

else ERROR;

}

程序中所出现的语义变量及语义函数的含义和功能说明如下。

函数GEN ()：生成一个四原式，并显示在屏幕上。

函数Enter ()：以Name为名字在符号表中登记新的一项，返回值为该项的序号。

函数Entry ()：以Name为名字查、填符号表。

函数LookUp()：以Name查符号表，若查到则返回相应登记项的序号（>=1），否则返回0。

函数NewTemp()：生成一个临时项。

函数S ()：用于识别<赋值语句>，返回该四原式在登记表中的序号。

函数E ()：用于识别<算术表达式>，返回该四原式在登记表中的序号。

函数T()：用于识别<项>，返回该四原式在登记表中的序号。

函数F ()：用于识别<因式>，返回该四原式在登记表中的序号。

五、实验结果

1、输入源文件 a.cpp中的内容：

x:=35.E7+4*my3id;

    y:=5.4-6;  

2、输出结果：

3、运行结果分析：输出结果的顺序为（CLASS，VALUE）的二元式编码，CLASS字段为相应的类别码，VALUE字段则是该标识符、常数的具体值，规约表达式，语义程序产生的四原式。

4、改进设想：由于时间和精力所限，本次实验只是实现了实验要求的基本题目，可以进一步改进的地方如下

  （1）、错误提示信息不够完整。本程序中只给出了此法分析错误的准确定位，没有给出语法和语义错误的提示信息，可以在此次实验的基础之上给出语法和语义错误的提示信息。

  （2）、程序中存在冗余代码。由于编程能力所限，程序中存在由于某些想法而编写的代码，但是后来又被其他想法代替而遗留的一些冗余代码，或者一些在调试过程中为了验证实验结果而加入查看代码。

   （3）、一部分的数据结构设计不合理。例如宏定义的类别码中的有关运算的类别码不能和算符优先矩阵直接对应，需要转换。

六、实验总结

实验流程：由文件中读入字符流，执行语法分析程序，调用词法分析程序，分析出合法的“单词”，并同时建立语法分析栈和语义分析栈，语法按照算符优先的算法进行规约，语义分析按照递归下降法生成简单的四原式。