编译技术实验指导书

编译技术实验指导书

计算机科学与工程学院

编译技术实验指导书

前言

《编译技术》是计算机科学与技术、软件工程等专业的一门理论性较强的专业课,

旨在培养大学生的计算机专业素质和基本编译程序设计的能力。通过实验教学，使

学生加深对所学知识的理解，掌握编译程序构造原理和实现技术。它的目的和任务

是：让学生掌握编译程序的基本原理和实现技术，提高学生对程序设计语言的理解,

让学生了解将高级程序设计语言源程序翻译成计算机能处理的目标代码语言的整个

过程，培养学生的编译程序设计的能力。编译程序的设计包括词法分析程序的设计、

语法分析程序的设计、语义分析程序的设计和中间代码生成程序的设计等。本实验

指导书是金成植编著的《编译程序构造原理和实现技术》的配套教材。编者根据计

算机课程实践性强等特点，编写了本实验教程，帮助学生有计划地系统地上机实践。

根据教学内容和教学目标，实验指导书设计了八次实验，实验学时16学时，每

个实验2学时。学生应按照实验指导书的要求，完成指定的实验任务，并及时提交

实验报告。要求学生在每次实验之前做好预习，实验后按要求写出实验报告。在每

次实验过程中教师要考核学生每次实验的完成情况。

一、为保证实验效果学生应做到：

1、遵守实验室的规章制度，爱护教学设备。

2、学生必须按时上机下机。

3、禁止做与实验无关的内容，禁止利用实验学时玩计算机游戏；

4、每次实验前学生应做好预习，实验后按时提交实验报告。

二、实验报告的要求：

1、明确实验的目的及要求；

2、记录下相应编译阶段的程序设计的思想、程序代码及运行的结果；

3、说明实验中出现的问题和解决过程；

4、写出实验的体会和实验过程中没解决的问题。

由于编者水平有限，书中难免有错，敬请大家批评指正。

辽宁科技大学计算机学院科学系

2009年2月

编译技术实验指导书

目录

实验一词法分析器的手工构造...........................................3

实验二词法分析器的自动生成...........................................10

实验三递归下降语法分析程序设计.......................................18

实验四LL⑴语法分析程序设计..........................................22

实验五LR语法分析器程序设计.....................................27

实验六说明语句的语法制导翻译.........................................32

实验七中间代码生成程序设计...........................................35

实验八微小编译器的设计..............................................37

2

编译技术实验指导书

实验一词法分析器的手工构造

实验类型：验证性

实验要求：必修

一、实验目的：

通过本次实验，使学生掌握词法分析的构造原理及实现技术，会编写简单程序

设计语言的词法分析器。

二、实验要求：

1、通过词法分析基本原理和基本技术的学习，参照给定的词法分析程序样例，

验证一个简单语言的词法分析程序，加深对词法分析基本原理和基本技术的理解。

2、从文件读入源程序，经预处理后进行词法分析，输出为单词串，即由（词法

信息，语义信息）所组成的二元组序列；有一定检查词法错误的能力。

2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变

量说明、程序清单、调试情况、设计技巧、心得体会。

3、上机时间：2学时。

三、实验原理

1、词法分析器的功能和输出格式

词法分析器的功能是输入源程序，输出单词的Token序列。词法分析器的单词

符号可表示成的二元式（单词种别码，单词符号的属性值）。本实验中，基本字、符号

词采用一词一类的方式，标识符、常数采用的是一类一个类码的方式。

2、单词的BNF表示

＜标识符-＞〈字母〈字母数字串

〈字母数字串-＞〈字母〈字母数字串|〈数字〈字母数字串《下划线（字母数字

串I£

3

编译技术实验指导书

〈无符号整数->〈数字〈数字串

(数字串-><数字〈数字串|£

<运算符->+I*I++I=

界符->,1；1(1)1#

3、状态转换图

识别标识符的状态转换图

.J……\/0"冲母数字

位------字母TD一非字母数字一⑥*

识别实常数和整常数的状态转换图

四、实验内容

请参照给定的C词法分析程序的样例，编写下列给定的源程序的VC++词法分

析程序，屏幕显示结果。

4

编译技术实验指导书

begin

integerr;

r=r+10;

end

五、词法分析器的手工构造样例程序

#include<iostream.h>

#include<fstream.h>

#include<string.h>

#include<stdlib.h>

#include<conio.h>

constshortWORDLEN=20;

structcode_val{

charcode;

charval[WORDLEN];

)；

〃预处理函数原型

voidpro_process(char*);

//扫描函数原型

code_valscanner(char*);

〃拼叠函数原型

voidconcat(char[],char);

〃查保留字表函数

charreserve(char[]);

//主函数

voidmain()

(

charbuf[4048]={'\(y};//扫描缓冲区

〃预处理

pro_process(buf)；

〃显示buf

cout«buf«endl;

〃单词识别

ofstreamcoutf("Lex_r.txtn,ios::out);

code_valt;〃临时变量

do{

t=scanner(buf);〃调用一次扫描器获得一个单词二元式

cout«t.codevv'\fvvt.valv<endl;〃屏幕显示单词二元式

5

编译技术实验指导书

coutf<<t.code<<'\t'<<t.val<<endl;〃单词二元式输出至文件

}while(t.code!='#');

cout«"Endoflexicalanalysis!"«endl;

getch();

)

//扫描函数，每调用一次，返回一个单词的二元式。

structcode_valscanner(char*buf)

(

staticinti=0;//buf指针

structcode_valt={'\0',"NUL"};〃临时变量

chartoken「WORDLEN]="";〃用于拼接单词

//去除前导空格

while(buffi]=='')i++;

//开始识别单词

〃标识符或基本字

if(buf[i]>='a'&&buf[i]<='z'){

while(buf[i]>='a'&&buf[i]<='z'||buf[i]>=,0,&&buf[i]<='9')

concat(token,buf[i++]);

t.code=reserve(token);〃查保留字表

if(t.code=='i')strcpy(t.val,token);〃是标识符

returnt;//返回标识符或基本字的二元式

)

〃整常数或实常数

if(buf[i]>='O'&&buf[i]<='9'){

while(buf[i]>='0'&&buf[i]<='9')

concat(token,buf[i++]);

if(buf[i]==?){〃实常数123.

concat(token,buf[i++]);

while(buf[i]>='0'&&buf[i]<='9')//123.4

concat(token,buf[i++]);

t.code='y';

)

else//整常数

t.code='x';

strcpy(t.val,token);

returnt;〃返回当前单词整常数(123)或实常数(123.或123.4)的二元式

//实常数

6

编译技术实验指导书

if(buf[i]==7){

concat(token,buf[i++]);

if(buf[i]>='0'&&buf[i]<=9){

whiIe(buf[i]>=<0,&&buf[i]<=,9,)

concat(token,buf[i++]);

t.code=,y,;

strcpy(t.val,token);

returnt;〃返回当前单词实常数(.123)的二元式

)

e1se{〃单个.错误词形

cout«HErrorword>"«token«endl;

exit(O);

)

)

〃其余单词

switch(buf[i]){

case

t.code=\,;

break;

case

t.code-

break;

case

t.code=,(r；

break;

casey：

t.code=y；

break;

case

t.code=,=,;

break;

case

if(buf[++i]==,+,)

t.code='$,;

else{

t.code=*+';

i--；

7

编译技术实验指导书

break;

case

t.code='*';

break;

case#:

t.code=,#1;

break;

default://错误字符

cout«"Errorchar>"«buf[i]«endl;

exit(O);

}//endofswitch

i++；〃指向下个单词

returnt;〃返回当前单词的二元式

)

〃拼接函数,原token=nBEGK,buf[i++]=T,调用后token二"BEGI”。

voidconcat(chartoken[],charc)

(

for(inti=0;token[i];i++);

token[i]=c;

token[++i]=,\0,;

)

charreserve(chartoken[])

{

constchar*table[]={"begin","end","integer","real1'};

constcharcode[]={n{}ac"};

for(inti=0;i<(int)strlen(code);i++)

if(strcmp(token,table[i])==0)returncode[i];

returnT;//标识符的单词种别为T

)

〃预处理函数

voidpro_process(char*buf)

(

ifstreamcinf(nsource.txt'\ios::in);

inti=0;charold_c二'\0',cur_c;〃计数器，前一个字符，当前字符。

boolin_comment=false;//状态标志，false表示当前字符未处于注释中。

while(cinf.read(&cur_c,sizeof(char))){〃从文件读一个字符

switch(in_comment){

casefalse:

8

编译技术实验指导书

if(old_c==7&&cur_c=="){〃进入注释

〃去除已存入扫描缓冲区的字符7

in_comment=true;

)

else{

if(old_c==*\V&&cur_c==,\n,)//去除续行符Y包括后续换行符。

i--;〃去除已存入必描缓冲区的字符、

else{

if(cur_c>=A&&cur_c<=,Z,)cur_c+=32;〃大写变小写

if(cur_c==,\t|||cur_c==,\n,)cur_c="空格

buf[i++]=cur_c;

)

)

break;

casetrue:

if(old_c=='*'&&cur_c==7')〃离开注释

in_comment=false;

}//endofswitch

old_c=cur_c;〃保留前一个字符

}//endofwhile

buf[i]=1#1;

9

编译技术实验指导书

实验二词法分析器的自动生成

实验类型：验证性

实验要求：必修

一、实验目的

通过本次实验，使学生掌握利用状态转换矩阵实现状态迁移，从而实现词法分

析器的自动生成，完成对一个简单程序的单词的识别。

二、实验要求

1、构造描述每个单词的正规式，根据正规式Pi构造最终形成识别全部单词的

NFAMo对NFAM确定化构造DFAM'o利用DFAM职别一个简单程序设计语言的

单词，屏幕输出单词的二元组序列。

2、提交实验报告，报告内容如下：

目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设

计技巧、心得体会。

3、上机时间：2学时。

三、实验原理

1、自动生成过程概述

①构造描述每个单词的正规式Pi(lWiWN)。

②根据正规式Pi构造NFAMi(lWiWN),假定初态均为0。在构造NFAMi的同

时，逐步并且最终形成识别全部单词的NFAM。

③NFAM确定化

④重新标记，构造DFAM、

2、实例(模型语言的词法)

①模型语言字符集

10

编译技术实验指导书

②模型语言单词集

基本字:begin>end、integer>real

标识符：以字母开始的数字字母串

无符号整常数：数字串

运算符：+、*、++、=

界符：，、；、(、)、#

③单词编码

基本字:begin('{',"NUL"}>end(')',"NUL")>integer('a',"NUL")、real('c',"NUL")

标识符：('i',字符串)

无符号整常数：(尺,字符串)

运算符：=C=7NUL")、+('+',"NUL"),*('*',"NUL")、++('$',"NUL")

界符:,(',',"NUL")>"NUL")>(('(',"NUL"))(')',"NUL").#('#',"NUL")

3、实例解

①构造正规式

(令a=a|b|c|d|……|z,0=0|1|2|3|4|5|6|7|8|9)

标识符：a(a|P)*

无符号整常数：BB*

运算符：单词本身(例士的正规式为七，"++”的正规式为“++”)

界符：单词本身(例丫的正规式为：)

基本字通常是由字母构成，符合标识符规则，将基本字作为一种特殊标识。

②构造NFAM

11

编译技术实验指导书

③NFAM确定化

IlaIP1=1+I*I,I；KI)I#

{0}{1,12,13){2,1415}{3}[4,5}⑹{7}⑻{9}{10}{11}

{1,12,13){12,13}(12,13)

{2,14,15)(14,15)

13!

{4,5}{16}

⑹

{7}

⑻

{9}

{10}

{11}

(12,13){12,13)(12,13)

{14,15){14,15)

]⑹

12

编译技术实验指导书

④重新标记，构造DFAM，

*

状态/字符a=+()#

012345678910

11111

212

3

413

5

6

7

8

9

10

111111

1212

13

四、实验内容

参照给定算法，构造一个识别简单程序设计语言单词的DFA。

五、扫描器控制程序的实现算法

#include<iostream.h>

#include<fstream.h>

#include<string.h>

#include<stdlib.h>

#include<conio.h>

constshortWORDLEN=20;

structcode_val{

charcode;charval[WORDLEN];

);

//单词编码表

constchar*tablen={"begin","end","integer","real",

constcharcode[]="{}ac=+$*,;()#";

//DFA列字符

constcharCOL_CHAR[]="aO=+*,;()#

//状态转换矩阵(DFA)

13

编译技术实验指导书

constintDFA[][11]={//strlen("aO=+*,;(}#")=11

(1,2,3,4,5,6,7,8,9,10,0),

{0,12},

{0},

{0,0,0,13),

{0},

{0},

{0},

{0},

⑼，

{0},

{0,12},

{0}

)；

〃预处理函数原型

voidpro_process(char*);

//扫描函数原型

code_valscanner(char*);

//主函数

voidmain()

{

charbuf[4048]={,\0,};〃扫描缓冲区

〃预处理

pro_process(buf)；

〃显示buf

cout«buf«endl;

〃单词识别

ofstreamcoutf(nLex_r.txtn,ios::out);

code_valt;〃临时变量

do{

t=scanner(buf);//调用一次扫描器获得一个单词二元式

coutvvt.code<v'\tVvt.val<vendl;〃在屏幕显示单词二元式

coutf<<t.code<<Af<<t.val<<endl;〃将单词二元式输出至文件

}while(t.code!=,#*);

cout«"Endoflexicalanalysis!0«endl;

getch();

14

编译技术实验指导书

intcol(char);//转换函数

voidconcat(char口,char);//拼接函数原型

charsearch_table(char[]);〃查单词二元式编码表函数

structcode_valscanner(char*buf)〃扫描函数，每调用一次，返回一个单词的二元式。

(

staticinti=0;//buf指针

structcode.valt={10hNUL”};//临时变量

chartoken「WORDLEN]=";〃用于拼接单词

〃去除前导空格

while(buffi]=-f)i++;

〃开始识别单词

intcur_state=O;

while(DFA[cur_state][col(buf[i])D{〃存在后继状态

concat(token,buf[i])；〃拼接

cur_state=DFA[cur_state][col(buf[i])];〃进入下一状态

if(buf[++i]=='O)break;〃指向下一字符，判缓冲区内字符是否处理完。

)

〃判断当前状态是否是终态，若为非终态报错，终止程序运行。在本例中不存在此情

况，故略。

t.code=search_table(token);〃查单词二元式编码表

if(t.code==,?,){

if(token[0]>=,a,&&token[0]<=,z,)

t.code=,r；

else

t.code=,x,;

strcpy(t.val,token);

)

returnt;〃返回当前单词的二元式

)

〃转换函数

intcol(charc)

(

if(c>=,a,&&c<=,z,)c=,a,;

if(c>='0'&&c<=9)c=O;

//constcharCOL_CHAR[]=HaO=+*,;()#"；

for(inti=0;i<=(int)strlen(COL_CHAR);i++)

if(c==COL_CHAR[i])returni;

15

编译技术实验指导书

cout«"Errorchar>"<vcvvendl;exit(O);〃程序终止运行

)

〃拼接函数,原token=MBEG",buf[i++]=T,调用后token=“BEGI”。

voidconcat(chartoken[],charc)

(

for(inti=0;token[i];i++);

tokenfi]=c;

token[++i]=,\0,;

)

charsearch_table(chartoken口)〃根据token内容查单词二元式编码表，返回单词种别。

(

//constchar*table[]={

//“begin”,“end”Jinteger”

//)；

//constcharcode[]=',{}ac=+$*,

fbr(inti=0;i<(int)strlen(code);i++)

if(strcmp(token,tablefi])=0)returncodefi];

return?;〃'?'表示查表无果

)

〃预处理函数

voidpro_process(char*buf)

(

ifstreamcinf(nsource.txtn,ios::in);

inti=0;charold_c='\0',cur_c;〃计数器，前一个字符，当前字符。

boolin_comment=false;〃状态标志，false表示当前字符未处于注释中。

while(cinf.read(&cur_c,sizeof(char))){〃从文件读一个字符

switch(in_comment){

casefalse:

if(old_c==7'&&cur_c=='*'){〃进入注释

i-;//去除已存入扫描缓冲区的字符7

in_comment=true;

)

else{

if(old_c==,\\,&&cur_c=Kn)//去除续行符Y包括后续换行符。

「;//去除已存入石描缓冲区的字符、

else(

if(cur_c>='A'&&cur_c<=,Z,)cur_c+=32;

if(cur_c==,\t|||cur_c==,\n,)cur_c+〃空格

16

编译技术实验指导书

buf[i++]=cur_c;

}

)

break;

casetrue:

if(old_c=='*'&&cur_c==7')〃离开注释

in_comment=false;

}//endofswitch

old_c=cur_c;〃保留前一个字符

}//endofwhile

buf[i]=T;

17

编译技术实验指导书

实验三递归下降语法分析程序设计

实验类型：验证性

实验要求：必修

一、实验目的：

通过本次实验，使学生掌握递归下降分析的原理及实现技术，会编写简单程序

的递归下降语法分析程序。

二、实验要求：

1、根据递归下降分析算法和给定的C语法分析程序的样例，编写指定的源程序

的VC++语法分析程序，屏幕显示结果。

2、有运行实例。即对于给定的文法和一个源程序，所编语法分析程序能正确判

断此程序语法是否正确，有语法错误的要给出错误提示。

3、提交实验报告，报告内容如下：

目的、要求、算法描述、程序结构、主要变量名说明、程序清单、调试情况、

设计技巧、心得体会。

4、上机时间：2学时。

三、实验原理和说明

1、递归下降分析法的功能

语法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过

程。

2、递归下降分析法的前提

给定文法必须是LL(1)文法，若不是需改造文法：消除二义性、消除左递归、

提取左因子，确保文法为LL(1)文法。

3、递归下降分析法设计思想及算法

为G[S]的每个非终结符号U构造一个递归函数。

18

编译技术实验指导书

假设产生式形如:Af01|p2|...|pn,则按下面的方法编写子函数A()：

procedureA()

beginiftokenePredict(Ap—>1)then0(pi)else

iftokenePredict(AP^2)then0(P2)else

iftokenePredict(Ap^n)then0(pn)else

err()

end

其中对pi=X1X2…Xn,6(pi)=9,(Xl);0,(X2);-;0,(Xn);

如果XGVN,exx)=X

如果XGVT,e,(X)=Match(X)

如果X=£,9(e)=skip(空语句)

四、实验内容

根据递归下降分析算法和给定的C语法分析程序的样例，编写教材P86页3给

定的文法G的递归下降语法分析程序，分析“(a,(a,a))#”是否为该文法的句子，

屏幕显示结果。

五、递归下降分析算法

对给定文法G：

E-TE'

E'-*+TE'|£

TfFT

T'f*FT|e

F-(E)|i|x|y

对应的递归下降分析算法如下：

19

编译技术实验指导书

voidE(void){//E~TE'

if(t.code=='i'||t.code=='x'||t.code=='y'||t.code=='('){IIif(t.codeWfirst(T))

T()；E1();

}else{coutf«endl«"ErrinE()>"«t.code«endl;exit(0);

voidEl(void)//E'-+TE'|e

(

if(t.code=='+'){

cinf»t.code»t.val;

coutf«t.code;//读一个单词的二元

式并输出单词种别

T()；E1();

)

elseif(!(t.code=='#'||t.code==')'))//if(!t.codeefollow(E'))

coutf«endl«"ErrinEl()>"«endl«t.code;

)

voidT(void)//T-FT'

(

if(t.code=='i'||t.code=='x'||t.code=='y'||t.code=='('){

//if(t.codeGfirst(F))

F()；T1();

)

else{

coutf«endl«"ErrinT()>"«t.code«endl;exit(0);

voidTl(void)//T'-*FT'|e

(

if(t.code=-*'){

cinf»t.code»t.val;coutf«t.code;//读一个单词的二元

式并输出单词种别

F()；T1();

)

elseif(!(t.code=-#'||t.code=-)'||t.code=-+')){//if(!t.codeefollow(T'))

coutf«endl«"ErrinT1()>"«t.code«endl;exit(0);

20

编译技术实验指导书

voidF(void)//F-(E)|i|x|y

if(t.code==,i,||t.code=,x,||t.code=,y,){

cinfi»t.code»t.val;coutf«t.code;〃读一个单词的二元

式并输出单词种别

)

elseif(t.code=-f){

cinf»t.code»t.val;coutf«t.code;〃读一个单词的二元

式并输出单词种别

E()；

if(t.code=,),){

cinf»t.code»t.val;coutf«t.code;〃读一个单词

的二元式并输出单词种别

)

else{

coutf«"ErrinF1>n«t.code«endl;exit(0);

else{

coutf«endl«nErrinF2>"«t.code«endl;exit(0);

21

编译技术实验指导书

实验四LL(1)语法分析程序设计

实验类型：验证性

实验要求：必修

一、实验目的

通过本次实验，使学生掌握LL(1)语法分析的原理及实现技术，会编写简单程序

的LL(1)语法分析程序。

二、实验要求

1、应用LL(1)分析法设计一个简单程序的语法分析器。

2、提交实验报告，报告内容包括实验目的、要求、算法描述、程序结构、主要

变量名说明、程序清单、调试情况、设计技巧、心得体会。

3、上机时间：2学时。

三、数据结构及算法描述

1、数据结构

M:二维数组，存放预测分析表。

stack:符号栈，初始时为"#S"(S为开始符号)。

X:表示栈顶符号

t.code:当前处理单词种别

2、算法描述

预测分析控制程序任何时刻的动作，都按照栈顶符号X和当前输入符号t.code

行事(X-Pop(stack))，控制程序每次执行下述三种可能的动作之一。

若X和t.code均为则分析成功，输入串为合法句子，终止分析过程。

若X是终结符，并且X和t.code相等，表示期望的终结符号和输入符号相等，

则读入下一个单词二元式；若X和t.code不相等，则报错。

若X是非终结符，则查预测分析表。若M[X][t.code]存放着一条关于X的一个

22

编译技术实验指导书

产生式，那么把产生式右部符号串按反序压入stack栈。若右部符号串为空字£,则

意味着无任何文法符号进栈；否则出错。

四、实验内容：

对给定文法G：

0.E一TD

1.D一+TD

2.D->£

3.T—FS

4.S—*FS

5.S―>£

6.F—(E)

7.FT

8.F—'X

9.F—y

应用LL(1)分析法设计一个由单词种别构成的源程序“i+i#”的语法分析器。

五、预测分析控制程序样例

#include<fstream.h>

#include<iostream.h>

#include<stdlib.h>

#include<string.h>

structcode_val{

charcode;charval[20];};

constchar*p[]={〃指向产生式右部符号串

"TD","+TD","","FS","*FS","","(E)","i","x","y"

)；

constcharT[]="+*()ixy#";//分析表的列符

constcharNT[]="EDTSF";〃分析表的行符，行符为EE'TT'Fo

constintM[][8]={

/*在预测分析表M中存放指针数组p的下标x,设M[i][j]=x,通过p[M[i][j]]=p[x]

获取右部符号串。*/

{-1,-1,0,-1,0,0,0,-1},/似0]指向第0个产生式右部符号串口》”，-1表示出错。

{1,-1,-1,2,-1,-1,-1,2),

{-1,-1,3,-1,3,3,3,-1),

{5,4,-1,5,-1,-1,-1,5),

23

编译技术实验指导书

{-1,-1,6,-1,7,8,9,-1)

)；

〃函数原型

intlin(char);//非终结符转换为行号

intcol(char);〃终结转换为列号

boolisNT(char);//isNT判断是否是非终结符

boolisT(char);//isT判断是否是终结符。

voidmain(void){

inti,j=0;

ifstreamcinf(nlex_r.txtn,ios::in);//从文件lex_r.txt输入数据

ofstreamcout("par_r.txt\ios::out);〃结果输出至文件par_r.txt(cout重定义)

structcode_valt;〃定义结构变量，存放单词二元式。

cinf»t.code»t.val;//读一个单词的二元式

charstack[20]={,#,；E,}；inttop=l;〃栈赋初值

charX='〃用于显示，并非必要。

coutvv”step”vv«vv”stack”v<rVv”X”vvr<v"t.code”vvendl;//用于显示，并非必

要。

coutvvjvv);〃用于显示，并非必要。

while(l){

coutvv'f;〃用于显示，并非必要。

for(i=0;i<=top;i++)cout«stack[i];〃用于显示，并非必要。

cout«Hv<W\t?vvt.code<<endl;〃用于显示，并非必要。

X=stack[top-];〃出栈

cout«++j«,),«,\t,;〃用于显示，并非必要。

for(i=0;i<=top;i++)cout«stackfi];〃用于显示，并非必要。

cout«,\t,«X«,\t,«t.code«endl;〃用于显示，并非必要。

if(X='#'){

if(X==t.code){

cout«n\tAccH«endl;break;〃跳出循环

else{

cout«"Errin#>,,<<X«,\t'«t.code«endl;exit(0);

}//endofif(X==#)

if(isT(X)){//是否是终结符

if(X==t.code)

cinf»t.code»t.val;〃读下一单词二元式

else{

24

编译技术实验指导书

cout«"ErrinT>"«X«,\t,«t.code«endl;exit(0);

continue;

}//endofif(isT(X))

if(isNT(X)){〃是否是非终结符

if(M[lin(X)][col(t.code)]=—1){

cout«nErrinNT>',«X«,\t,«t.code«endl;exit(0);

)

else{

for(i=strien(p[M[lin(X)][col(t.code)]])-l;i>=0;i-)

stack[4-+top]=*(p[M[lin(X)][col(t.code)]]+i);

)

continue;

}//endofif(isNT(X))

cout«"Errinmain()>"«X«endl;exit(O);

}//endofwhile

}//endofmain

intlin(charc)〃将EDTSF分别转换为01234

for(inti=O;i<(int)strlen(NT);i++)

if(c=NT[i])retumi;

cout«HErrinlin()>,r«c«endl;exit(0);

)

intcol(charc)〃将+*()ixy#分别转换为01234567

for(inti=O;i<(int)strlen(T);i++)

if(c==T[i])retuiTii;

cout«"Errincol()>,,«c«endl;exit(0);

boolisNT(charc)〃是否是非终结符

for(inti=O;i<(int)strlen(NT);i++)

if(c=NT[i])returntrue;

returnfalse;

boolisT(charc)〃是否是终结符（不包括#）

for(inti=O;i<(int)strlen(T)-1;i++)

25

编译技术实验指导书

if(c=T[i])returntrue;

returnfalse;

26

编译技术实验指导书

实验五LR语法分析器程序设计

实验类型：验证性

实验要求：必修

一、实验目的：

通过本次实验，使学生掌握LR语法分析的原理及实现技术，会编写简单程序的

LR语法分析程序。

二、实验要求：

1、根据LR语法分析算法，编写一个LR语法分析程序。

2、有运行实例。即对于给定的文法和一个源程序，所编语法分析程序能正确判

断此程序语法是否正确，有语法错误的要给出错误提示。

3、提交实验报告，报告内容如下：

目的、要求、算法描述、程序结构、主要变量名说明、程序清单、调试情况、

设计技巧、心得体会。

4、上机时间：2学时。

三、实验的数据结构和算法描述

1、数据结构

①LR分析表

②状态栈

在归约时，控制程序应按原路径折回，故在分析过程中需将所经历的状态记录

下来，以便获得折回点。设置状态栈，用于记录分析过程中所经历的状态，即路径。

③符号栈

用于记录路径的符号，它和状态栈等高。符号栈的设置是为了便于说明，实际

语法分析器无符号栈。

④产生式右部符号串长度

27

编译技术实验指导书

因每个状态仅识别一个符号，退回的状态数和构成句柄的字符数相等，故需存

储产生式右部符号串长度。

⑤产生式左部符号

归约后，根据左部符号进入下一状态。

2、算法描述

分析表用二维数组M存储，栈顶状态用Stop表示，当前输入符号用t.code表示,

控制程序的算法归纳如下：

①移进

若M[Stop][t.code]=sj,说明句柄尚未形成，应执行移进操作。s表示移进，j为

状态号，将j移入状态栈，将t.code移入符号栈，j成为新的栈顶状态Stop。读下一

个单词。

②归约

若M[Stop][t.code]=rk,说明句柄已出现在栈顶，应该用编号为k的产生式A-

B进行归约。假设，LEN(B)=r,M[Stop-r][A]=j。首先将栈顶r个元素出栈，然后将

j和A分别移入状态栈和符号栈，j成为新的栈顶状态Stop。当前处理单词不变。

③接受

M[Stop][t.code]=Acc,表示输入串是一个合法句子，程序终止运行。

④出错

M「Stop][t.code]=空白，表示出错，最简单处理为程序终止运行。

四、实验内容

1、验证教材Pn2-“4的LR分析器的控制程序。

2、完成1的要求后，可对教材中的算法进行改进，如规则的存储形式，指针top

的修正等。

3、也可对本章习题中1、2、3、4题中提供的文法进行分析。

五、LR语法分析器的控制程序样例

28

编译技术实验指导书

#include<fstream.h>

#include<iostream.h>

ftinclude<stdlib.h>

Sinclude<string.h>

structcode_val{

charcode;charval[20];

)；

struct{

void*addr;//标号或变量的地址

charidf5];〃标识符名

unsignedcat:4;//种属（4个二进制位）

unsignedtype:4;//类型（4个二进制位）

}sym_table[NS];

constchar*p[]={〃产生式

"S'S","S-V","V-V,i”,〃Vfai”,〃V-ci”

｝；

constcharTNT[]=",iac#SV";〃LR分析表列的字符

constintM[][9]={//LR分析表数字化，

列字符+*（）i#ETF用数字012345678标识。

{0,0,4,0,5,0,1,2,3},〃。表示出错，s4用4表示。

{6,0,0,0,0,99},//Acc用99表示

{-2,7,0,-2,0,-2},//r2用-2表示

{-4,-4,0,-4,0,-4),

{0,0,4,0,5,0,8,2,3),

{-6,-6,0,-6,0,-6),

{0,0,4,0,5,0,0,9,3),

{0,0,4,0,5,0,0,0,10),

(6,0,0,11},

{-1,7,0,-1,0,-1),

{-3,-3,0,-3,0,-3),

{-5,-5,0,-5,0,-5)

}；

intcol(char);〃列定位函数原型

voidmain()

(

intstate[50]={0};〃状态栈初值

29

编译技术实验指导书

charsymbol[50]={'#'};〃符号栈初值

charwval[50]={};

语义栈的定义

inttop=0;〃栈顶指针初值

ofstreamcout("par_r.txt");〃语法分析结果输出至文件par_r.txt

ifstreamcin("lex_r.txt");//从lex_r.txt中输入词法分析结果

structcode_valt;〃结构变量，存放单词二元式。

cin>>t.code>>t.val;〃读一单词

intaction;

inti,j=0;〃输出时使用的计数器，并非必要。

cout«*step，/«，\t*«*状态栈"<<、'<<"符号栈"«、'<<"输入符号

〃《endl;〃输出标题并非必要。

do{

cout<<j++«")"<<<\t';〃输出step,并非必要。

for(i=0;i<=top;i++)cout«state[i];cout«，\t";〃输出状态栈内容,

并非必要。

for(i=0;iOtop;i++)cout«symbol[i];〃输出符号栈内容,并非必要。

cout<<<\t'<<t.code<<endl;〃输出当前输入符号(单词种

别)，并非必要。

action=M[state[top]][col(t.code)];

if(action>0&&action!=99){〃移进

state[++top]=action;

symbol[top]=t.code;

wval[top]=t.val;

cin»t.code»t.val;

〃读一单词

)

elseif(action<0){〃归约

if(strcmp(p[-action]+3,"£"))〃£产生式的右部符号串长度

为0,无需退栈。

top=top-(strlen(p[-action])-3);〃"一"为汉字，占二字节,故减

3o

state[top+l]=M[state[top]][col(p[-action][0])];〃产生式左

部符号

symbol[++top]=p[-action][0];

调语义子程序；

)

elseif(action==99){//接受

30

编译技术实验指导书

cout<<，\t*<</，Accz/«endl;

输出符号表；

break;

)

else{〃出错

cout<<，，ErrinmainO>，/<<action<<endl;

break;

)

}while(1);

)

intcol(charc)〃将字符+*()i#ETF分别转换为数字012345678

{

for(inti=0;i<(int)strlen(TNT);i++)

if(c==TNT[i])returni;

cout<<?/Errincolchar>/z«c<<endl;

exit(O);〃终止程序运行

31

编译技术实验指导书

实验六说明语句的语法制导翻译

实验类型：验证性

实验要求：必修

一、实验目的：

通过本次实验，使学生掌握说明语句的语法制导翻译的原理及实现技术，将变

量的相关信息填入符号表。

二、实验要求：

1、根据说明语句的翻译的基本原理和实现技术，编写一个语义分析程序，将变

量的名字，种属、类型等信息填入符号表。

2、提交实验报告，报告内容包括实验的目的、要求、算法描述、程序结构、主

要变量名说明、程序清单、调试情况、设计技巧、心得体会。

3、上机时间：2学时。

三、实验原理

说明语句的语法制导翻译不产生中间代码，而是将变量的名字，种属、类型等

32

编译技术实验指导书

信息填入符号表。

1、符号表的结构

符号表由一个结构数组构成，模型语言的符号表定义如下:

struct｛

vo