编译原理实验指导书.docx

编译原理实验指导书.docx

《编译原理实验指导书.docx》由会员分享，可在线阅读，更多相关《编译原理实验指导书.docx（45页珍藏版）》请在冰点文库上搜索。

编译原理实验指导书

编译原理实验指导

信息科学与工程学院

计算机系

2009.12.25

实验一词法分析程序

一、目的和内容

1．实验目的：

通过完成词法分析程序，了解词法分析的过程。

2．实验内容：

用C／C++实现对Pascal的子集程序设计语言的词法识别程序。

3．实验要求：

将该语言的源程序，也就是相应字符流转换成内码，并根据需要是否对于标识符填写相应的符号表供编译程序的以后各阶段使用。

二、程序设计语言的描述

程序设计语言的描述采用扩充的BNF表示：

<程序>→<程序首部><分程序>．

<程序首部>→PROGRAM标识符；

<分程序>→[<常量说明部分>][<变量说明部分>][<过程说明部分>]<复合语句>

<常量说明部分>→CONST<常量定义>{，<常量定义>}；

<常量定义>→标识符=无符号整数

<变量说明部分>→VAR<变量定义>（；<变量定义>）；

<变量定义>→标识符{，标识符}：

<类型>

<类型>→INTEGER|LONG

<过程说明部分>→<过程首部><分程序>；{<过程首部><分程序>；}

<过程首部>→PROCEDURE标识符；|PROCEDURE标识符（标识符：

<类型>）；

<语句>→<赋值语句>|<条件语句>|<当型循环语句>|<过程调用语句>

|<读语句>|<写语句>|<复合语句>|ε

<赋值语句>→标识符：

=<表达式>

<条件语句>→IF<条件>THEN<语句>

<当型循环语句>→WHILE<条件>DO<语句>

<过程调用语句>→标识符|标识符（<表达式>）

<读语句>→READ（标识符，{标识符}）

<写语句>→WRITE（<表达式>{，<表达式>}）

<复合语句>→BEGIN<语句>{；<语句>}END

<条件>→<表达式><关系运算符><表达式>|ODD<表达式>

<表达式>→[+|-]<项>{<加型运算符><项>}

<项>→<因子>{<乘型运算符><因子>}

<因子>→标识符|无符号整数|（<表达式>）

<加型运算符>→+|-

<乘型运算符>→*|/

<关系运算符>→=|<>|<|<=|>|>=

其中：

 <>：

用左右尖括号括起的字符串表示非终结符号

：

：

=：

定义为

{}：

表示该语法成分可以0—n次重复。

[]：

表示方括号内为可选项，即0或1次。

三、程序设计语言单词的内部编码

如表1-1为词法分析中的内码单词对照表。

表1-1内部码对照表

内码

单词

内码

单词

内码

单词

内码

单词

1

PROGRAM

2

CONST

3

VAR

4

INTEGER

5

LONG

6

PROCEDURE

7

IF

8

THEN

9

WHILE

10

DO

11

READ

12

WRITE

13

BEGIN

14

END

15

ODD

16

+

17

-

18

*

19

/

20

=

21

<>

22

<

23

<=

24

>

25

>=

26

.

27

.

28

;

29

:

30

:

=

31

（

32

）

33

无符号整数

34

标识符

35

#

四、词法分析程序的设计思想

为了实现的编译程序实用，这里规定源程序可采用自由书写格式，即一行内可以书写多个语句，一个语句也可以占领多行书写；标识符的前20个字符有效；整数用2个字节表示；长整数用4个字节表示。

这样词法分析程序的主要工作为：

（1）从源程序文件中读入字符。

（2）统计行数和列数用于错误单词的定位。

（3）删除空格类字符，包括回车、制表符空格。

（4）按拼写单词，并用（内码，属性）二元式表示。

（5）根据需要是否填写标识符表供以后各阶段使用。

这里采用的编译程序的实现方法是一遍扫描，即从左到右只扫描一次源程序，也就是词法分析作为语法分析的一个子程序。

故在编写词法分析程序时，用重复调用词法分析子程序取一单词的方法得到整个源程序的内码流。

扫描程序流程图，如图1-1。

取单词子程序流程图；如图1-2。

取字符和统计字符行列位置子程序；如图1-3。

实验二语法分析1——递归子程序法

一、目的和内容

1、实验目的：

通过完成语法分析程序，了解语法分析的过程和作用

2、实验内容：

用递归子程序法实现对pascal的子集程序设计语言的分析程序

3、实验要求：

对源程序的内码流进行分析，如为文法定义的句子输出”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用

二、文法的改变

为适合递归子程序法，对实验一中的文法改写成无左递归和无左共因子的ＢＮＦ如下：

<程序>→<程序首部><分程序>。

<程序首部>→PROGRAM标识符；

<分程序>→<常量说明部分><变量说明部分><过程说明部分> <复合语句>

<常量说明部>→CONST<常量定义><常量定义后缀>|ε

<常量定义>→标识符=无符号整数

<常量定义后缀>→，<常量定义><常量定义后缀> |ε

<变量说明部分>→VAR<变量定义><变量定义后缀>|ε

<变量定义>→标识符<标识符后缀>：

<类型>；

<标识符后缀>→，标识符<标识符后缀> |ε

<变量定义后缀>→<变量定义><变量定义后缀> |ε

<类型>→INTEGER|LONG

<过程说明部分>→<过程首部><分程序>；<过程说明部分后缀>|ε

<过程首部>→PROCEDURE标识符<参数部分>；

<参数部分>→（标识符：

 <类型>）|ε

<过程说明部分后缀>→<过程首部><分程序>；<过程说明部分后缀>|ε

<语句>→<赋值或调用语句>|<条件语句>|<当型循环语句>|<读语句>

|<写语句>|<复合语句>|ε

<赋值或调用语句>→标识符<后缀>

<后缀>→：

=<表达式>|（<表达式>）|ε

<条件语句>→IF<条件>THEN<语句>

<当型循环语句>→WHILE<条件>DO<语句>

<读语句>→READ（标识符<标识符后缀>）

<写语句>→WRITE（<表达式><表达式后缀>）

<表达式后缀>→，<表过式><表达式后缀>|ε

<复合语句>→BEGIN<语句><语句后缀>END

<语句后缀>→；<语句><语句后缀>|ε

<条件>→<表达式><关系运算符><表达式>|ODD<表达式>

<表达式>→+<项><项后缀>|-<项><项后缀>|<项><项后缀>

<项后缀>→<加型运算符><项><项后缀>|ε

<项>→<因子><因子后缀>

<因子后缀>→<乘型运算符><因子><因子后缀>|e

<因子>→标识符|无符号整数|（<表达式>）

<加型运算符>→+|-

<乘型运算型>→*|/

<关系运算符>→=|<>|<|<=|>|>=

三、非终结符和函数名对照表

为适用递归子程序，表2-1为非终结符和函数名对照表

表2-1非终符和函数名对照表

非终结符

函数名

非终结符

函数名

<程序>

program

<程序首部>

proghead

<分程序>

block

<常量说明部分>

consexpl

<常量定义>

consdefi

<变量说明部分>

varexl

<常量定义后缀>

conssuff

<变量定义>

vandefi

<变量定义后缀>

varsuff

<>过程说明部分>

procdefi

<类型>

typeil

<过程首部>

procedh

<过程说明部分后缀>

procsuff

<赋值或调用语句>

assipro

<语句>

sentence

<后缀>

suffix

<条件语句>

ifsent

<读语句>

read

<当型循环语句>

whilsent

<标识符后缀>

idsuff

<写语句>

Write

<复合语句>

compsent

<表达式后缀>

Exprsuff

<语句后缀>

sentsuff

<条件>

Conditio

<项后缀>

termsuff

<表达式>

Express

<项>

term

<因子后缀>

Factsuff

<参数部分>

argument

<因子>

Factor

<加型运算符>

addoper

<乘型运算符>

Muloper

<关系运算符>

respoper

四、递归子程序的设计思想

为每个非终结符设计一个识别的子程序，寻找该非终结符也就是调用相应的子程序。

由于单词在语法分析中作为一个整体，故在语法识别中仅使用其内码。

在这里将词法分析作为语法分析的一个子程序，当语法分析需要单词时，就调用相应的词法分析程序获得一个单词。

语法分析的作用是识别输入符号串是否是文法上定义的句子，即判断输入符号串是否是满足“程序”定义的要求。

也就是当语法识别程序从正常退出表示输入符号串是正确的“程序”；若从出错退出，则输入符号串不是正确的“程序”。

出错时，可以根据读字符的位置判断出错的位置。

五、部分子程序流程图

图2-1a表示程序是由首部、分程序和“．”组成的；图2-1b表示程序首部的组成；图2-1c为分程序的语法成分，图2-1d表示语句的组成；图2-1e为因子的构成。

图2-1a

图2-1b

图2-1c

图2-1d

图2-1e

实验三语法分析2——预测分析法

一、目的和内容

1、实验目的：

通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。

2、实验内容：

构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。

3、实验要求：

源程序的内码流用预测分析法进行分析。

如为文法定义的句子输出“是”，否则输出“否”，并根据需要处理说明语句填写相应的符号表供以后代码生成时使用。

二、文法的改变

由于预测分析和递归子程序都是自顶向下的分析方法，且在实验二中已将它变换成无回溯的和无左公因子的文法。

则可直接用实验二中的文法。

三、非终结符的内码表

为了将非终结符和终结符一起存入栈参，将非终结符的内码从128开始标记。

其对照表见表3-1。

表3-1非终结符和内码对照表

内码

非终结符

内码

非终结符

内码

非终结符

128

〈程序〉

129

〈程序首部〉

130

〈分程序〉

131

〈常量说明部分〉

132

〈常量定义〉

133

〈常量定义后缀〉

134

〈变量说明部分〉

135

〈变量定义〉

136

〈变量定义后缀〉

137

〈类型〉

138

〈过程说明部分〉

139

〈过程首部〉

140

〈过程说明部分后缀〉

141

〈语句〉

142

〈赋值或调用语句〉

143

〈后缀〉

144

〈条件语句〉

145

〈当型循环语句〉

146

〈读语句〉

147

〈标识符后缀〉

148

〈写语句〉

149

〈表达式后缀〉

150

〈复合语句〉

151

〈语句后缀〉

152

〈条件〉

153

〈表达式〉

154

〈项后缀〉

155

〈项〉

156

〈因子后缀〉

157

〈因子〉

158

〈参数部分〉

159

〈加型运算符〉

160

〈乘型运算符〉

161

〈关系运算符〉

四、程序设计思想

为了压缩存储，采用一个二维数组存放规则的右部，每个规则对应一个子数组，用0表示每条规则的结束。

在预测分析表中用规则的序号代表相应的规则，分析表中的出错用-1表示。

由于规则的右部存在相同的符号串，故相同的符号串只要保存一个即可，如ε规则。

（这种方法对语法识别没有影响，但不像语义分析和代码生成时，需区分是何种规则的右部）。

规则右部符号串编号及内码表示：

（1）〈程序首部〉〈分程序〉.　　　　　　　　　　　　　　129130260

（2）PROGRAM标识符；134280

（3）<学量说明部分><变量说明部分><过程说明部分><复合语句>1311341381500

（4）CONST<常量定义><常量定义后缀>；2132133280

（5）ε0

（6）标识符=无符号整数3420330

（7），<常量定义><常量定义后缀>271321330

（8）VAR<变量定义<变量定义后缀>；31351360

（9）标识符<标识符后缀>：

<类型>；3414729137280

（10），标识符<标识符后缀>27341470

（11）<变量定义><变量定义后缀>1351360

（12）INTEGER40

（13）LONG50

（14）<过程首部><分程序>；<过程说明部分后缀>139130281400

（15）PROCGDURE标识符<参数部分>；634158280

（16）<赋值或调用语句>1420

（17）<条件语句>1440

（18）<当型循环语句>1450

（19）<读语句>1460

（20）<写语句>1480

（21）<复合语句>1500

（22）标识符<后缀>341430

（23）：

=<表达式>3015310

（24）IF<条件>THEN<语句>715281410

（25）WHILE<条件>DO<>语句 9152101410

（26）READ<标识符<标识符后缀>113134147320

（27）WRITE（<表达式><表达式后缀>）1231153149320

（28），<表达式><表达式后缀>271531490

（29）BEGIN<语句><语句后缀>END13141151140

（30）；<语句><语句后缀>281411510

（31）<表达式><关系运算符><表达式>1531611530

（32）ODD<表达式>151530

（33）+<项><项后缀>161551540

（34）-<项><项后缀>171551540

（35）<项><项后缀>1551540

（36）<加型运算符><项><项后缀>1591551540

（37）<因子><因子后缀>1571560

（38）<乘型运算符><因子><因子后缀>1601571560

（39））标识符号340

（40）无符号整数330

（41）（<表达式>）31153320

（42）无符号整数26330

（43）+160

（44）-170

（45）*180

（46）/190

（47）=200

（48）＜＞210

（49）＜220

（50）＜=230

（51）＞240

（52）＞＝250

（53）（标识符：

〈类型〉）313429137320

图3-1为预测分析程序流程图。

图3-1预测分析程序流程图

五、分析表和程序

在预测分析法中所有预测分析法的总控分析程序都是一样的，主要是分析表不同。

在预测分析表中的元素如用规则来表示，则分析表需三维数组，若用该方法表示分析表所需的存储空间较大，为此用规则号表示预测分析表中的元素。

另外，一个算法语言的预测分析表中

的元素大多是出错元素，则可用0表示。

要在程序中直接用内码表示预测分析表，则该分析表还是很大的，可用（非终结符,终结符,规则号）三元式表示；非终结符和终结符匹配时，用规则号的规则推导。

为减少查询分析表的时间，在分析程序初始化时，将三元式（非终结符，终结符，规则号）转换成分析表。

最后，由总控程序根据分析表来分析源程序是否是文法上定义的“程序”。

实验四语义分析和代码生成

一、目的和内容

1、实验目的：

通过完成语义分析和代码生成程序，了解语义分析和代码生成与词法分析、语法分析的关系，从而体会编译程序的全过程。

2、实验内容：

在语法分析的基础上，配有相应的代码生成语句使源程序生成相应的目标代码（汇编代码）。

3、实验要求：

对源程序的内码流进分析语法分析并附有相应的语义子程序制导产生的目标代码。

二、程序设计语言的语义解释

1、程序的数据类型有两种：

好integer和long型，和标准Pascal语言一样用两个字节表示integer型，其表示范围为-32768~+32767，而long型用四个字节表示，其表示范围为：

-214783648~214783647。

2、相同类型的数据运算其结果为该类型的数据，不同类型的数据运算其结果是多字节的类型，即integer和long型混合运算时结果为long型。

3、比较运算和ODD运算的结果是逻辑值，逻辑值也占两个字节用0表示假，-1表示“真”。

4、不同类型的数据进行赋值时，低字节赋给高字节时，自动补足，高字节赋给低字时，高位部分自动忽略，而不考虚其类型不匹配问题。

5、运算符和优先级

运算符优先级

#0

（1入运算栈后

=<><=>=<>2

+-3

*/4

-（单目）+（单目）5

（6入运算栈前

另外运算符“）”和“ODD”不需入运算符栈故没有定义优先级。

实际上它高于“#”，而和入栈后的“（”优先级一样。

6、输入语句及数据用空格隔开，但输入数据个数不得少于read语句中的变量（否则获得随机值）。

7、对于一个输出语句先自动换行，然后输出其值，对于同一个输出语句中的量，用空格隔开。

8．过程允许递归，允许带一个参数也可不带参数。

9．其他语义规则同标准Pascal语言。

三、语义子程序需考虑的问题

1．标识符表的设计

定义标识符有常量标识符、变量标识符和过程标识符。

它们均有符号名，对于常量标识符和变量标识符需要有类型、运行时的地址和定义符号的层数（不同层的同名标识符是不同的对象），对于过程标识符它分有参过程和无参过程，有参过程还需说明参数在符号表的入口，故标识符表的结构为：

符号名、类型、运行时的相对地址、层、属性和参数入口。

2．由于8088指令系统中不提供四字节的乘法和除法指令以及对于integer和long型的输入和输出，故把它们写成相应的子程序并加上一标志。

当调用相应的子程序时，就生成相应的子程序。

3．当PROGRAM匹配时，输出汇编语言定义数据段、堆栈段和代码段的首标志。

4．当“．”匹配时，输出数据段、堆栈段和代码段的结束标志。

5．常量说明填写标识符表，分配运行时的地址，产生运行时把常量放入相应地址的指令。

6．变量说明填写标识符表，分配运行时的地址。

7．过程序说明对于过程标识符和形参标识符均填写标识符表，并统计层数和处理相应的子程序的其他部分，生成进入过程后的分配过程的存储空间，指示数据区的低部和顶部，拷贝区头向量的指令，还要注意因为采用的是一遍扫描，当处理过程序头时，尚不能计算出本过程式所需的存储空间，在这里产生一条调用求数据区长度的指令。

在处理过程结束时，要产生返回分配数据区的指令，产生求出数据区长度的子程序。

另外，在处理本层过程结束后，从标识符表中全部清除属于本层的标识符，以区分下一个并列的子程序的标识符。

8．处理参数时，将参数的入口地址填入过程标识符的参数入口中。

9．在处理分程序时，要区分是0层分程序（即主程序）还是过程，其产生的代码略有不同，还要产生跳过过程代码的指令。

10．将表达式赋给变量的赋值语句根据变量和表达式的类型，产生将运算对象栈中存放的表达式的临时变量地址，取值存入相应的变量指令。

11．过程调用语句，如带有参数应产生将参数的临时变量放入区头向量中参数约定的单元、取新的数据区的低部，拷贝区头向量，和调用相应子程序等指令。

12．只要if语句产生取出条件的逻辑值进行判断的指令为假，跳过相应的语句。

13．while语句先产生标号，然后根据条件判断的指令为假跳出循环，在while语句结束时产生一条无条件转移语句和假转出的标号。

14．read语句先产生将符号串读入缓冲区的指令，然后对于read中的每一个变量调用相应的读数据的子程序。

15．write语句先产生回车指令，然后对于write中的每个表达式调用输出子程序。

16．“（”匹配是入运算符栈，将其运算符的优先级改为1。

17．“）”匹配时生成在运算符栈中全部优先级均大于“（”的运算符，运算指令然后“（”退栈。

18．对于表达式中的常量、常量标识符、变量标识符的匹配时，进入运算对象栈。

19．对于运算符+、-、*、/、+（单目）、-（单目）、=、<、>、<=、>=生成运算符栈中优先级大于等于本运算符优先级的指令，然后将本运算符入栈。

四、证语义子程序的实现方法

采用的方法是在递归子程序识别法的基础上，按制导翻译的原理加上相应的语义动作，由于识别方法本身也是程序逻辑，故在识别程序中直接插入语义分析和代码生成程序代码即可。

语法分析—预测分析法（示例）

一、实验目的和内容

a）实验目的：

通过完成预测分析法的语法分析程序，了解预测分析法分析过程

b）实验内容：

用C++实现针对LL

（1）语言的预测分析程序，该程序能够对输入的语法文件进行分析，自动求得“FIRST”/“FOLLOW”集构造预测分析表，并在实现词法分析的基础上实现语法分析。

c）实验要求：

对输入源程序的内码流用“预测分析法”进行分析，输出语法分析结果：

错误的个数与错误在源程序中的位置。

二、实验程序设计思想

I）程序总体方案选择

为实现实验目标，可以有两种选择方案：

1、手工求“FIRST”/“FOLLOW”集并构造预测分析表。

这种方法简化了编写程序的过程，但是却增加了人工工作强度，而且容易出错。

2、编写适当的函数，实现“FIRST”/“FOLLOW”集的自动求取，进而构造预测分析表。

这种方案虽然在程序编写上有些麻烦，但是却增加了程序的“适应能力”，而且不容易出错。

实验中采用自动求得“FIRST”/“FOLLOW”集构造预测分析表的方案。

II）文法的处理

实现自动求取“FIRST”/“FOLLOW”集首先要解决文法的输入、存储和处理等问题。

文法的处理过程本身就是一个小型的语法分析程序（只不过文法规则比较简单），其文法规则如下：

<文法文件><终结符定义><文法定义>

<终结符定义><注释部分>“<<终结符开始>>”<终结符>“<<终结符结束>>”

<注释部分>“//”任意一行字符串

<终结符>任意满足规定的一行字符串

<文法定义><注释部分>“<<文法开始>>”<文法>“<<文法结束>>”

<文法><非终结符>“->”<规则右部>

<非终结符>“<”任意满足规定的一行字符串“>”

<规则右部><非终结符><规则右部>|<终结符><规则右部>

对于这个文法的分析不必用预测分析法。

利用这个文法的特点：

1、终结符定义和文法定义都有开始和结束标志可以准确定位到定义的开始，而忽略注释部分。

2、每一个非终结符号都有开始（<）结束（>）标志所以可以利用他们取出非终结符

3、每一个非终结符必须出现在文法的左部，由此可以取得所有非终结符