編譯技術實驗指導書

編譯技術實驗指導書

計算機科學與工程學院

編譯技術實驗指導書

前言

《編譯技術》是計算機科學與技術、軟件工程等專業(yè)的一門理論性較強的專業(yè)課,

旨在培養(yǎng)大學生的計算機專業(yè)素質和基本編譯程序設計的能力。通過實驗教學，使

學生加深對所學知識的理解，掌握編譯程序構造原理和實現(xiàn)技術。它的目的和任務

是：讓學生掌握編譯程序的基本原理和實現(xiàn)技術，提高學生對程序設計語言的理解,

讓學生了解將高級程序設計語言源程序翻譯成計算機能處理的目標代碼語言的整個

過程，培養(yǎng)學生的編譯程序設計的能力。編譯程序的設計包括詞法分析程序的設計、

語法分析程序的設計、語義分析程序的設計和中間代碼生成程序的設計等。本實驗

指導書是金成植編著的《編譯程序構造原理和實現(xiàn)技術》的配套教材。編者根據(jù)計

算機課程實踐性強等特點，編寫了本實驗教程，幫助學生有計劃地系統(tǒng)地上機實踐。

根據(jù)教學內(nèi)容和教學目標，實驗指導書設計了八次實驗，實驗學時16學時，每

個實驗2學時。學生應按照實驗指導書的要求，完成指定的實驗任務，并及時提交

實驗報告。要求學生在每次實驗之前做好預習，實驗后按要求寫出實驗報告。在每

次實驗過程中教師要考核學生每次實驗的完成情況。

一、為保證實驗效果學生應做到：

1、遵守實驗室的規(guī)章制度，愛護教學設備。

2、學生必須按時上機下機。

3、禁止做與實驗無關的內(nèi)容，禁止利用實驗學時玩計算機游戲；

4、每次實驗前學生應做好預習，實驗后按時提交實驗報告。

二、實驗報告的要求：

1、明確實驗的目的及要求；

2、記錄下相應編譯階段的程序設計的思想、程序代碼及運行的結果；

3、說明實驗中出現(xiàn)的問題和解決過程；

4、寫出實驗的體會和實驗過程中沒解決的問題。

由于編者水平有限，書中難免有錯，敬請大家批評指正。

遼寧科技大學計算機學院科學系

2009年2月

編譯技術實驗指導書

目錄

實驗一詞法分析器的手工構造...........................................3

實驗二詞法分析器的自動生成...........................................10

實驗三遞歸下降語法分析程序設計.......................................18

實驗四LL⑴語法分析程序設計..........................................22

實驗五LR語法分析器程序設計.....................................27

實驗六說明語句的語法制導翻譯.........................................32

實驗七中間代碼生成程序設計...........................................35

實驗八微小編譯器的設計..............................................37

2

編譯技術實驗指導書

實驗一詞法分析器的手工構造

實驗類型：驗證性

實驗要求：必修

一、實驗目的：

通過本次實驗，使學生掌握詞法分析的構造原理及實現(xiàn)技術，會編寫簡單程序

設計語言的詞法分析器。

二、實驗要求：

1、通過詞法分析基本原理和基本技術的學習，參照給定的詞法分析程序樣例，

驗證一個簡單語言的詞法分析程序，加深對詞法分析基本原理和基本技術的理解。

2、從文件讀入源程序，經(jīng)預處理后進行詞法分析，輸出為單詞串，即由（詞法

信息，語義信息）所組成的二元組序列；有一定檢查詞法錯誤的能力。

2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結構、主要變

量說明、程序清單、調試情況、設計技巧、心得體會。

3、上機時間：2學時。

三、實驗原理

1、詞法分析器的功能和輸出格式

詞法分析器的功能是輸入源程序，輸出單詞的Token序列。詞法分析器的單詞

符號可表示成的二元式（單詞種別碼，單詞符號的屬性值）。本實驗中，基本字、符號

詞采用一詞一類的方式，標識符、常數(shù)采用的是一類一個類碼的方式。

2、單詞的BNF表示

＜標識符-＞〈字母〈字母數(shù)字串

〈字母數(shù)字串-＞〈字母〈字母數(shù)字串|〈數(shù)字〈字母數(shù)字串《下劃線（字母數(shù)字

串I￡

3

編譯技術實驗指導書

〈無符號整數(shù)->〈數(shù)字〈數(shù)字串

(數(shù)字串-><數(shù)字〈數(shù)字串|￡

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

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

3、狀態(tài)轉換圖

識別標識符的狀態(tài)轉換圖

.J……\/0"沖母數(shù)字

位------字母TD一非字母數(shù)字一⑥*

識別實常數(shù)和整常數(shù)的狀態(tài)轉換圖

四、實驗內(nèi)容

請參照給定的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];

)；

〃預處理函數(shù)原型

voidpro_process(char*);

//掃描函數(shù)原型

code_valscanner(char*);

〃拼疊函數(shù)原型

voidconcat(char[],char);

〃查保留字表函數(shù)

charreserve(char[]);

//主函數(shù)

voidmain()

(

charbuf[4048]={'\(y};//掃描緩沖區(qū)

〃預處理

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();

)

//掃描函數(shù)，每調用一次，返回一個單詞的二元式。

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;//返回標識符或基本字的二元式

)

〃整常數(shù)或實常數(shù)

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

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

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

if(buf[i]==?){〃實常數(shù)123.

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

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

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

t.code='y';

)

else//整常數(shù)

t.code='x';

strcpy(t.val,token);

returnt;〃返回當前單詞整常數(shù)(123)或實常數(shù)(123.或123.4)的二元式

//實常數(shù)

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;〃返回當前單詞實常數(shù)(.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;〃返回當前單詞的二元式

)

〃拼接函數(shù),原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

)

〃預處理函數(shù)

voidpro_process(char*buf)

(

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

inti=0;charold_c二'\0',cur_c;〃計數(shù)器，前一個字符，當前字符。

boolin_comment=false;//狀態(tài)標志，false表示當前字符未處于注釋中。

while(cinf.read(&cur_c,sizeof(char))){〃從文件讀一個字符

switch(in_comment){

casefalse:

8

編譯技術實驗指導書

if(old_c==7&&cur_c=="){〃進入注釋

〃去除已存入掃描緩沖區(qū)的字符7

in_comment=true;

)

else{

if(old_c==*\V&&cur_c==,\n,)//去除續(xù)行符Y包括后續(xù)換行符。

i--;〃去除已存入必描緩沖區(qū)的字符、

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

編譯技術實驗指導書

實驗二詞法分析器的自動生成

實驗類型：驗證性

實驗要求：必修

一、實驗目的

通過本次實驗，使學生掌握利用狀態(tài)轉換矩陣實現(xiàn)狀態(tài)遷移，從而實現(xiàn)詞法分

析器的自動生成，完成對一個簡單程序的單詞的識別。

二、實驗要求

1、構造描述每個單詞的正規(guī)式，根據(jù)正規(guī)式Pi構造最終形成識別全部單詞的

NFAMo對NFAM確定化構造DFAM'o利用DFAM職別一個簡單程序設計語言的

單詞，屏幕輸出單詞的二元組序列。

2、提交實驗報告，報告內(nèi)容如下：

目的、要求、算法描述、程序結構、主要變量說明、程序清單、調試情況、設

計技巧、心得體會。

3、上機時間：2學時。

三、實驗原理

1、自動生成過程概述

①構造描述每個單詞的正規(guī)式Pi(lWiWN)。

②根據(jù)正規(guī)式Pi構造NFAMi(lWiWN),假定初態(tài)均為0。在構造NFAMi的同

時，逐步并且最終形成識別全部單詞的NFAM。

③NFAM確定化

④重新標記，構造DFAM、

2、實例(模型語言的詞法)

①模型語言字符集

10

編譯技術實驗指導書

②模型語言單詞集

基本字:begin>end、integer>real

標識符：以字母開始的數(shù)字字母串

無符號整常數(shù)：數(shù)字串

運算符：+、*、++、=

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

③單詞編碼

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

標識符：('i',字符串)

無符號整常數(shù)：(尺,字符串)

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

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

3、實例解

①構造正規(guī)式

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

標識符：a(a|P)*

無符號整常數(shù)：BB*

運算符：單詞本身(例士的正規(guī)式為七，"++”的正規(guī)式為“++”)

界符：單詞本身(例丫的正規(guī)式為：)

基本字通常是由字母構成，符合標識符規(guī)則，將基本字作為一種特殊標識。

②構造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，

*

狀態(tài)/字符a=+()#

012345678910

11111

212

3

413

5

6

7

8

9

10

111111

1212

13

四、實驗內(nèi)容

參照給定算法，構造一個識別簡單程序設計語言單詞的DFA。

五、掃描器控制程序的實現(xiàn)算法

#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=+*,;()#

//狀態(tài)轉換矩陣(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}

)；

〃預處理函數(shù)原型

voidpro_process(char*);

//掃描函數(shù)原型

code_valscanner(char*);

//主函數(shù)

voidmain()

{

charbuf[4048]={,\0,};〃掃描緩沖區(qū)

〃預處理

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);//轉換函數(shù)

voidconcat(char口,char);//拼接函數(shù)原型

charsearch_table(char[]);〃查單詞二元式編碼表函數(shù)

structcode_valscanner(char*buf)〃掃描函數(shù)，每調用一次，返回一個單詞的二元式。

(

staticinti=0;//buf指針

structcode.valt={10hNUL”};//臨時變量

chartoken「WORDLEN]=";〃用于拼接單詞

〃去除前導空格

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

〃開始識別單詞

intcur_state=O;

while(DFA[cur_state][col(buf[i])D{〃存在后繼狀態(tài)

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

cur_state=DFA[cur_state][col(buf[i])];〃進入下一狀態(tài)

if(buf[++i]=='O)break;〃指向下一字符，判緩沖區(qū)內(nèi)字符是否處理完。

)

〃判斷當前狀態(tài)是否是終態(tài)，若為非終態(tài)報錯，終止程序運行。在本例中不存在此情

況，故略。

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;〃返回當前單詞的二元式

)

〃轉換函數(shù)

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);〃程序終止運行

)

〃拼接函數(shù),原token=MBEG",buf[i++]=T,調用后token=“BEGI”。

voidconcat(chartoken[],charc)

(

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

tokenfi]=c;

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

)

charsearch_table(chartoken口)〃根據(jù)token內(nèi)容查單詞二元式編碼表，返回單詞種別。

(

//constchar*table[]={

//“begin”,“end”Jinteger”

//)；

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

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

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

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

)

〃預處理函數(shù)

voidpro_process(char*buf)

(

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

inti=0;charold_c='\0',cur_c;〃計數(shù)器，前一個字符，當前字符。

boolin_comment=false;〃狀態(tài)標志，false表示當前字符未處于注釋中。

while(cinf.read(&cur_c,sizeof(char))){〃從文件讀一個字符

switch(in_comment){

casefalse:

if(old_c==7'&&cur_c=='*'){〃進入注釋

i-;//去除已存入掃描緩沖區(qū)的字符7

in_comment=true;

)

else{

if(old_c==,\\,&&cur_c=Kn)//去除續(xù)行符Y包括后續(xù)換行符。

「;//去除已存入石描緩沖區(qū)的字符、

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

編譯技術實驗指導書

實驗三遞歸下降語法分析程序設計

實驗類型：驗證性

實驗要求：必修

一、實驗目的：

通過本次實驗，使學生掌握遞歸下降分析的原理及實現(xiàn)技術，會編寫簡單程序

的遞歸下降語法分析程序。

二、實驗要求：

1、根據(jù)遞歸下降分析算法和給定的C語法分析程序的樣例，編寫指定的源程序

的VC++語法分析程序，屏幕顯示結果。

2、有運行實例。即對于給定的文法和一個源程序，所編語法分析程序能正確判

斷此程序語法是否正確，有語法錯誤的要給出錯誤提示。

3、提交實驗報告，報告內(nèi)容如下：

目的、要求、算法描述、程序結構、主要變量名說明、程序清單、調試情況、

設計技巧、心得體會。

4、上機時間：2學時。

三、實驗原理和說明

1、遞歸下降分析法的功能

語法分析器的功能是利用函數(shù)之間的遞歸調用模擬語法樹自上而下的構造過

程。

2、遞歸下降分析法的前提

給定文法必須是LL(1)文法，若不是需改造文法：消除二義性、消除左遞歸、

提取左因子，確保文法為LL(1)文法。

3、遞歸下降分析法設計思想及算法

為G[S]的每個非終結符號U構造一個遞歸函數(shù)。

18

編譯技術實驗指導書

假設產(chǎn)生式形如:Af01|p2|...|pn,則按下面的方法編寫子函數(shù)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(空語句)

四、實驗內(nèi)容

根據(jù)遞歸下降分析算法和給定的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)語法分析的原理及實現(xiàn)技術，會編寫簡單程序

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

二、實驗要求

1、應用LL(1)分析法設計一個簡單程序的語法分析器。

2、提交實驗報告，報告內(nèi)容包括實驗目的、要求、算法描述、程序結構、主要

變量名說明、程序清單、調試情況、設計技巧、心得體會。

3、上機時間：2學時。

三、數(shù)據(jù)結構及算法描述

1、數(shù)據(jù)結構

M:二維數(shù)組，存放預測分析表。

stack:符號棧，初始時為"#S"(S為開始符號)。

X:表示棧頂符號

t.code:當前處理單詞種別

2、算法描述

預測分析控制程序任何時刻的動作，都按照棧頂符號X和當前輸入符號t.code

行事(X-Pop(stack))，控制程序每次執(zhí)行下述三種可能的動作之一。

若X和t.code均為則分析成功，輸入串為合法句子，終止分析過程。

若X是終結符，并且X和t.code相等，表示期望的終結符號和輸入符號相等，

則讀入下一個單詞二元式；若X和t.code不相等，則報錯。

若X是非終結符，則查預測分析表。若M[X][t.code]存放著一條關于X的一個

22

編譯技術實驗指導書

產(chǎn)生式，那么把產(chǎn)生式右部符號串按反序壓入stack棧。若右部符號串為空字￡,則

意味著無任何文法符號進棧；否則出錯。

四、實驗內(nèi)容：

對給定文法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[]={〃指向產(chǎn)生式右部符號串

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

)；

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

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

constintM[][8]={

/*在預測分析表M中存放指針數(shù)組p的下標x,設M[i][j]=x,通過p[M[i][j]]=p[x]

獲取右部符號串。*/

{-1,-1,0,-1,0,0,0,-1},/似0]指向第0個產(chǎn)生式右部符號串口》”，-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)

)；

〃函數(shù)原型

intlin(char);//非終結符轉換為行號

intcol(char);〃終結轉換為列號

boolisNT(char);//isNT判斷是否是非終結符

boolisT(char);//isT判斷是否是終結符。

voidmain(void){

inti,j=0;

ifstreamcinf(nlex_r.txtn,ios::in);//從文件lex_r.txt輸入數(shù)據(jù)

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;〃跳出循環(huán)

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語法分析的原理及實現(xiàn)技術，會編寫簡單程序的

LR語法分析程序。

二、實驗要求：

1、根據(jù)LR語法分析算法，編寫一個LR語法分析程序。

2、有運行實例。即對于給定的文法和一個源程序，所編語法分析程序能正確判

斷此程序語法是否正確，有語法錯誤的要給出錯誤提示。

3、提交實驗報告，報告內(nèi)容如下：

目的、要求、算法描述、程序結構、主要變量名說明、程序清單、調試情況、

設計技巧、心得體會。

4、上機時間：2學時。

三、實驗的數(shù)據(jù)結構和算法描述

1、數(shù)據(jù)結構

①LR分析表

②狀態(tài)棧

在歸約時，控制程序應按原路徑折回，故在分析過程中需將所經(jīng)歷的狀態(tài)記錄

下來，以便獲得折回點。設置狀態(tài)棧，用于記錄分析過程中所經(jīng)歷的狀態(tài)，即路徑。

③符號棧

用于記錄路徑的符號，它和狀態(tài)棧等高。符號棧的設置是為了便于說明，實際

語法分析器無符號棧。

④產(chǎn)生式右部符號串長度

27

編譯技術實驗指導書

因每個狀態(tài)僅識別一個符號，退回的狀態(tài)數(shù)和構成句柄的字符數(shù)相等，故需存

儲產(chǎn)生式右部符號串長度。

⑤產(chǎn)生式左部符號

歸約后，根據(jù)左部符號進入下一狀態(tài)。

2、算法描述

分析表用二維數(shù)組M存儲，棧頂狀態(tài)用Stop表示，當前輸入符號用t.code表示,

控制程序的算法歸納如下：

①移進

若M[Stop][t.code]=sj,說明句柄尚未形成，應執(zhí)行移進操作。s表示移進，j為

狀態(tài)號，將j移入狀態(tài)棧，將t.code移入符號棧，j成為新的棧頂狀態(tài)Stop。讀下一

個單詞。

②歸約

若M[Stop][t.code]=rk,說明句柄已出現(xiàn)在棧頂，應該用編號為k的產(chǎn)生式A-

B進行歸約。假設，LEN(B)=r,M[Stop-r][A]=j。首先將棧頂r個元素出棧，然后將

j和A分別移入狀態(tài)棧和符號棧，j成為新的棧頂狀態(tài)Stop。當前處理單詞不變。

③接受

M[Stop][t.code]=Acc,表示輸入串是一個合法句子，程序終止運行。

④出錯

M「Stop][t.code]=空白，表示出錯，最簡單處理為程序終止運行。

四、實驗內(nèi)容

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

2、完成1的要求后，可對教材中的算法進行改進，如規(guī)則的存儲形式，指針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[]={〃產(chǎn)生式

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

｝；

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

constintM[][9]={//LR分析表數(shù)字化，

列字符+*（）i#ETF用數(shù)字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);〃列定位函數(shù)原型

voidmain()

(

intstate[50]={0};〃狀態(tài)棧初值

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;〃輸出時使用的計數(shù)器，并非必要。

cout?*step，/?，\t*?*狀態(tài)棧"<<、'<<"符號棧"?、'<<"輸入符號

〃《endl;〃輸出標題并非必要。

do{

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

for(i=0;i<=top;i++)cout?state[i];cout?，\t";〃輸出狀態(tài)棧內(nèi)容,

并非必要。

for(i=0;iOtop;i++)cout?symbol[i];〃輸出符號棧內(nè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,"￡"))〃￡產(chǎn)生式的右部符號串長度

為0,無需退棧。

top=top-(strlen(p[-action])-3);〃"一"為漢字，占二字節(jié),故減

3o

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

部符號

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分別轉換為數(shù)字012345678

{

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

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

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

exit(O);〃終止程序運行

31

編譯技術實驗指導書

實驗六說明語句的語法制導翻譯

實驗類型：驗證性

實驗要求：必修

一、實驗目的：

通過本次實驗，使學生掌握說明語句的語法制導翻譯的原理及實現(xiàn)技術，將變

量的相關信息填入符號表。

二、實驗要求：

1、根據(jù)說明語句的翻譯的基本原理和實現(xiàn)技術，編寫一個語義分析程序，將變

量的名字，種屬、類型等信息填入符號表。

2、提交實驗報告，報告內(nèi)容包括實驗的目的、要求、算法描述、程序結構、主

要變量名說明、程序清單、調試情況、設計技巧、心得體會。

3、上機時間：2學時。

三、實驗原理

說明語句的語法制導翻譯不產(chǎn)生中間代碼，而是將變量的名字，種屬、類型等

32

編譯技術實驗指導書

信息填入符號表。

1、符號表的結構

符號表由一個結構數(shù)組構成，模型語言的符號表定義如下:

struct｛

vo