Pascal语言编译器的方案设计书与实现.docx
《Pascal语言编译器的方案设计书与实现.docx》由会员分享，可在线阅读，更多相关《Pascal语言编译器的方案设计书与实现.docx（22页珍藏版）》请在冰点文库上搜索。
Pascal语言编译器的方案设计书与实现
封面
作者：
PanHongliang
仅供个人学习
Pascal语言编译器的设计与实现
我们设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。
编译程序的输出结果包括词法分析后的二元式序列、变量名表、状态栈分析过程显示及四元式序列程序，整个编译程序分为三部分：
（1）词法分析部分
（2）语法分析处理及四元式生成部分
（3）输出显示部分
一．词法分析器设计
由于我们规定的程序语句中涉及单词较少，故在词法分析阶段忽略了单词输入错误的检查，而将编译程序的重点放在中间代码生成阶段。
词法分析器的功能是输入源程序，输出单词符号。
我们规定输出的单词符号格式为如下的二元式：
（单词种别，单词自身的值）
#defineACC-2
#definesy_if0
#definesy_then1
#definesy_else2
#definesy_while3
#definesy_begin4
#definesy_do5
#definesy_end6
#definea7
#definesemicolon8
#definee9
#definesharp10
#defineS11
#defineL12
#definetempsy15
#defineEA18//Eand
#defineEO19//Eor
#defineplus34
#definesubtract35
#definetimes36
#definedivide37
#definebecomes38
#defineop_and39
#defineop_or40
#defineop_not41
#definerop42
#definelparent48
#definerparent49
#defineident56
#defineintconst57
函数说明
1．读取函数readline（）、readchar（）
词法分析包含从源文件读取字符的操作，但频繁的读文件操作会影响程序执行效率，故实际上是从源程序文件”PAS.dat”中读取一行到输入缓冲区，而词法分析过程中每次读取一个字符时则是通过执行readchar（）从输入缓冲区获得的；若缓冲区已被读空，则再执行readline（）从PAS.dat中读取下一行至输入缓冲区。
2．扫描函数scan（）
扫描函数scan（）的功能是滤除多余空格并对主要单词进行分析处理，将分析得到的二元式存入二元式结果缓冲区。
3．变量处理find（）
变量处理中首先把以字母开头的字母数字串存到spelling[]数组中，然后进行识别。
识别过程是先让它与保留关键字表中的所有关键字进行匹配，若获得成功则说明它为保留关键字，即将其内码值写入二元式结果缓冲区；否则说明其为变量，这时让它与变量名表中的变量进行匹配（变量匹配函数find（）），如果成功，则说明该变量已存在并在二元式结果缓冲区中标记为此变量（值填为该变量在变量名表中的位置），否则将该变量登记到变量名表中，再将这个新变量存入二元式缓存数组中。
4．数字识别number（）
数字识别将识别出的数字填入二元式结果缓存数组。
5．显示函数
显示函数的功能在屏幕上输出词法分析的结果（即二元式序列程序），同时给出二元式个数及源程序行数统计。
二．语法分析器设计
语法分析器的核心是三张SLR分析表以及针对这三张SLR分析表进行语义加工的语义动作。
编译程序中语法分析处理及四元式生成部分主要是以二元式作为输入，并通过SLR分析表对语法分析处理过程进行控制，使四元式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。
在处理if和while语句时，需要进行真值或假值的拉链和返填工作，以便转移目标的正确填入。
1.控制语句的SLR分析表1设计过程如下：
将扩展文法G’
1）S’→S
1）S→ifethenSelseS
2）S→whileedoS
3）S→beginLend
4）S→a
5）L→S
6）L→S。
L
用∈_CLOSURE方法构造LR（0）工程规范簇为：
I0：
S’→·S
S→·ifethenSelseS
S→·whileedoS
S→·beginLend
S→·a。
I1:
S’→S·
I2:
S→if·ethenSelseS
I3:
S→while·edoS
I4:
S→begin·Lend
L→·S
L→·S。
L
S→·ifethenSelseS
S→·whileedoS
S→·beginLend
S→·a
I5:
S→a·
I6:
S→ife·thenSelseS
I7:
S→whilee·doS
I8:
S→beginL·end
I9:
L→S·
L→S·。
L
I10:
S→ifethen·SelseS
S→·ifethenSelseS
S→·whileedoS
S→·beginLend
I11:
S→whileedo·S
S→·ifethenSelseS
S→·whileedoS
S→·beginLend
S→·a
I12:
S→beginLend·
I13:
L→S。
·L
L→·S
L→·S。
L
S→·ifethenSelseS
S→·whileedoS
S→·beginLend
S→·a
I14:
S→ifethenS·elseS
I15:
S→whileedoS·
I16:
L→S。
L·
I17:
S→ifethenS·elseS
S→·ifethenSelseS
S→·whileedoS
S→·beginLend
S→·a
I18:
S→ifethenSelseS·
构造文法G’中非终结符的FOLLOW集如下：
FOLLOW（L）={end}
FOLLOW（S）={else,。
end,#}
在ＬＲ（０）工程规范簇中 ，只有Ｉ9有“移进――归约”冲突， L→S· L→S·L
因为FOLLOW（L）∩FIRST（L）=∮所以可以用ＳＬＲ方法解决以上冲突，最后我们得到的ＳＬＲ分析表如下：
ACTION
GOTO
If
then
else
while
begin
do
end
a
。
e
#
S
L
0
S2
S3
S4
S5
1
1
ACC
2
S6
3
S7
4
S2
S3
S4
S5
9
8
5
R4
R3
R4
R4
6
S10
7
S11
8
S12
9
R5
S13
10
S2
S3
S4
S5
14
11
S2
S3
S4
S5
15
12
R3
R3
R3
R3
13
S2
S3
S4
S5
9
16
14
S17
15
R2
R2
R2
R2
16
R6
17
S2
S3
S4
S5
18
18
R1
R1
R1
R1
staticintaction[19][13]=
/*0*/{{2,-1,-1,3,4,-1,-1,5,-1,-1,10,1,-1},
/*1*/{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,ACC,-1,-1},
/*2*/{-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1},
/*3*/{-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1},
/*4*/{2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,8},
/*5*/{-1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1},
/*6*/{-1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
/*7*/{-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1},
/*8*/{-1,-1,-1,-1,-1,-1,12,-1,-1,-1,-1,-1,-1},
/*9*/{-1,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,-1},
/*10*/{2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1},
/*11*/{2,-1,-1,3,4,-1,-1,5,-1,-1,-1,15,-1},
/*12*/{-1,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1},
/*13*/{2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16},
/*14*/{-1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
/*15*/{-1,-1,102,-1,-1,-1,102,-1,102,-1,102,-1,-1},
/*16*/{-1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1},
/*17*/{2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1},
/*18*/{-1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1}}。
其中，前9列为action值，后2列为goto值；0～16表示17个移进状态（即Si）；-1表示出错；ACC表示分析成功；而100～106对应归约产生式：
2.算术表达式的LR分析表2设计如下：
1）S’→E
2）E→E+E
3）E→E*E
4）E→（E）
5）E→i（过程略）
ACTION
GOTO
I
+
-
*
/
（
）
#
E
0
S3
S2
1
1
S4
S11
S5
S10
ACC
2
S3
S2
6
3
R4
R4
R4
R4
R4
R4
4
S3
S2
7
5
S3
S2
8
6
S4
S11
S5
S10
S9
7
R1
R1
S5
S10
R1
R1
8
R2
R2
R2
R2
R2
R2
9
R3
R3
R3
R3
R3
R3
10
S3
S2
12
11
S3
S2
13
12
R6
R6
R6
R6
R6
R6
13
R5
R5
S5
S10
R5
R5
staticintaction1[14][9]=
/*0*/{{3,-1,-1,-1,-1,2,-1,-1,1},
/*1*/{-1,4,11,5,10,-1,-1,ACC,-1},
/*2*/{3,-1,-1,-1,-1,2,-1,-1,6},
/*3*/{104,104,104,104,104,104,104,104,-1},
/*4*/{3,-1,-1,-1,-1,2,-1,-1,7},
/*5*/{3,-1,-1,-1,-1,2,-1,-1,8},
/*6*/{-1,4,11,5,10,-1,9,-1,-1},
/*7*/{101,101,101,5,10,101,101,101,-1},
/*8*/{102,102,102,102,102,102,102,102,-1},
/*9*/{103,103,103,103,103,103,103,103,-1},
/*10*/{3,-1,-1,-1,-1,2,-1,-1,12},
/*11*/{3,-1,-1,-1,-1,2,-1,-1,13},
/*12*/{106,106,106,106,106,106,106,106,-1},
/*13*/{105,105,105,5,10,105,105,105,-1}}。
3.布尔表达式的SLR分析表3设计如下：
（过程略）
1）S’→B
2）B→i
3）B→iropi
4）B→（B）
5）B→NOTB
6）A→BAND
7）B→AB
8）O→BOR
9）B→OB
ACTION
GOTO
i
Rop
（
）
NOT
AND
OR
#
B
A
O
0
S1
S4
S5
13
7
8
1
S2
R1
R1
R1
R1
2
S3
3
R2
R2
R2
R2
4
S1
S4
S5
11
7
8
5
S1
S4
S5
6
7
8
6
R4
S9
S10
R4
7
S1
S4
S5
14
7
8
8
S1
S4
S5
15
7
8
9
R5
R5
R5
10
R7
R7
R7
11
S12
S9
S10
12
R3
R3
R3
R3
13
S9
S10
ACC
14
R6
S9
S10
R6
15
R8
S9
S10
R8
staticintaction2[16][11]=
/*0*/{{1,-1,4,-1,5,-1,-1,-1,13,7,8},
/*1*/{-1,2,-1,101,-1,101,101,101,-1,-1,-1},
/*2*/{3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
/*3*/{-1,-1,-1,102,-1,102,102,102,-1,-1,-1},
/*4*/{1,-1,4,-1,5,-1,-1,-1,11,7,8},
/*5*/{1,-1,4,-1,5,-1,-1,-1,6,7,8},
/*6*/{-1,-1,-1,104,-1,9,10,104,-1,-1,-1},
/*7*/{1,-1,4,-1,5,-1,-1,-1,14,7,8},
/*8*/{1,-1,4,-1,5,-1,-1,-1,15,7,8},
/*9*/{105,-1,105,-1,105,-1,-1,105,-1,-1,-1},
/*10*/{107,-1,107,-1,107,-1,-1,107,-1,-1,-1},
/*11*/{-1,-1,-1,12,-1,9,10,-1,-1,-1,-1},
/*12*/{-1,103,-1,103,-1,103,103,103,-1,-1,-1},
/*13*/{-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1},
/*14*/{-1,-1,-1,106,-1,9,10,106,-1,-1,-1},
/*15*/{-1,-1,-1,108,-1,9,10,108,-1,-1,-1}}。
LR分析表控制语义加工的实现：
当扫描LR分析表的当前状态为归约状态时，则在调用与该状态对应的产生式进行归约的同时，调用相应的语义子程序进行有关的翻译工作。
现在对LR分析器的分析栈加以扩充，使得每个文法符号之后都跟着它的语义值。
为了清晰起见，我们把这个栈的每一项看成由三部分组成：
状态state，文法符号syl和语义值val。
编译程序实现算术表达式、布尔表达式及程序语句的语义加工时，都是按这种状态栈加工方式进行的。
例如：
（5+3）*6 的分析过程
序号
STATE
Val
syl
input
1
0
-
#
（5+3）*6#
2
02
--
#（
5+3）*6#
3
023
---
#（5
+3）*6#
4
026
--5
#（E
+3）*6#
5
0264
--5-
#（E+
3）*6#
6
02643
--5--
#（E+3
）*6#
7
02647
--5-3
#（E+E
）*6#
8
026
--8
#（E
）*6#
9
0269
--8-
#（E）
*6#
10
01
-8
#E
*6#
11
015
-8-
#E*
*6#
12
0153
-8--
#E*6
#
13
0158
-8-6
#E*E
#
14
01
-48
#E
#
15
ACC
在分析过程中，第（3）步操作后的状态栈为023，根据栈顶状态“3”和现行输入符号“+”（input栏字符串的第一个字符）查分析表ACTION[3，+]=R4，即按第（4）个产生式E→n来进行归约；由于产生式右部仅含一项，故去掉状态栈栈顶“3”；此时2变为新的栈顶状态，再查（2，E）的下一状态s′：
GOTO[2,E]=6，即将状态6和文法符号E压栈，最后得到第（4）步的状态。
第（7）步操作后也是如此，当前状态栈为02647，根据栈顶状态7和现行输入符号“）”查分析表ACTION[7，）]=R1，即按第
（1）个产生式E→E1+E2进行归约；由于产生式右部有三项，故去掉状态栈栈顶的647三项；此时2变为新的栈顶状态，再查（2，E）的下一状态s′：
GOTO[2，E]=6,即将状态6和文法符号E压栈，最后得到第（8）步的状态。
三．中间代码生成器设计：
１．布尔表达式
布尔表达式在程序语言中有两个基本作用：
一是用作控制语句（如if-else或while语句）的条件式；二是用于逻辑演算，计算逻辑值。
布尔表达式是由布尔算符（&&、||、！
）作用于布尔变量（或常数）或关系表达式而形成的。
关系表达式的形式是E1ropE2，其中rop是关系符（如<、≤、=、≠、>或≥），E1和E2是算术式。
在这里，我们只考虑前面给定文法所产生的布尔表达式：
B→B&&B|B||B|!
B|（B）|iropi|i
遵照我们的约定，布尔算符的优先顺序（从高到低）为：
!
、&&、||，并假定&&和||都服从左结合规则。
所有关系符的优先级都是相同的，而且高于任何布尔算符，低于任何算术算符，关系算符不得结合。
表达式的真、假出口的确定：
考虑表达式B1||B2，若B1为真，则立即知道B也为真；因此，B1的真出口也就是整个B的真出口。
若B1?
为假，则B2必须被计值，B2的第一个四元式就是B1的假出口。
当然，B2的真、假出口也就是整个B的真、假出口。
类似的考虑适用于对B1&&B2的翻译，我们将B1||B2和B1&&B2的翻译用下图表示，
在自下而上的分析过程中，一个布尔式的真假出口往往不能在产生四元式的同时就填上。
我们只好把这种未完成的四元式的地址（编号）作为B的语义值暂存起来，待到整个表达式的四元式产生完毕之后再来回填这个未填入的转移目标。
２．条件语句
对条件语句ifeS1elseS2中的布尔表达式e，其作用仅在于控制对S1和S2的选择。
因此，作为转移条件的布尔式e，我们可以赋予它两种“出口”：
一是“真”出T口，出向S1；一是“假”出口，出向S2。
于是，e的代码F条件语句可以翻译成如图的一般形式。
非终结符e具有两项语义值e_TC和e_FC，它们分别指出了尚待回填真、S2的代码假出口的四元式串。
e的“真”出口只有在往回扫描到if时才能知道，而它图3-2条件语句的代码结构的“假”出口则需到处理过S1并且到达else才能明确。
这就是说，必须把e_FC的值传下去，以便到达相应的else时才进行回填。
另外，当S1语句执行完时意味着整个if-else语句也已执行完毕；因此，在S1的编码之后应产生一条无条件转移指令。
这条转移指令将导致程序控制离开整个if-else语句。
但是，在完成S2的翻译之前，这条无条件转移指令的转移目标是不知道的。
甚至，在翻译完S2之后，这条转移指令的转移目标仍无法确定。
这种情形是由于语句的嵌套性所引起的。
例如下面的_语句：
ife1ife2S1elseS2elseS3在S1的代码之后的那条无条件转移指令不仅应跨越S2而且应跨越S3。
这也就是说，转移目标的确定和语句所处的环境密切相关。
３．条件循环语句
条件循环语句whileeS通常被翻译成图的代码结构。
布尔式e的“真”出口出向S代码段的第一个四元式。
紧接S代码段之后应产生一条转向测试e的无条件转移指令。
e的“假”出口将导致程
升级会员 