編譯原理語(yǔ)義分析與中間代碼生成試驗(yàn)報(bào)告

本文格式為Word版，下載可任意編輯——編譯原理語(yǔ)義分析與中間代碼生成試驗(yàn)報(bào)告專題6_語(yǔ)法制導(dǎo)翻譯程序設(shè)計(jì)原理與實(shí)現(xiàn)技術(shù)

13281132李若森計(jì)科1301

一、試驗(yàn)?zāi)康?/p>

語(yǔ)法制導(dǎo)的基本概念；目標(biāo)代碼結(jié)構(gòu)分析的基本方法；賦值語(yǔ)句語(yǔ)法制導(dǎo)生成四元式的基本原理和方法；該過(guò)程包括語(yǔ)法分析和語(yǔ)義分析過(guò)程。

二、試驗(yàn)內(nèi)容

2.1試驗(yàn)項(xiàng)目

完成以下描述賦值語(yǔ)句和算術(shù)表達(dá)式文法的語(yǔ)法制導(dǎo)生成中間代碼四元式的過(guò)程。

G[A]:

A→V=E

E→E+T|E-T|TT→T*F|T/F|FF→(E)|iV→i

2.2設(shè)計(jì)說(shuō)明

終結(jié)符號(hào)i為用戶定義的簡(jiǎn)單變量，即標(biāo)識(shí)符的定義。

2.3設(shè)計(jì)要求

(1)設(shè)計(jì)語(yǔ)法制導(dǎo)翻譯過(guò)程，給出每一產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作；

(2)設(shè)計(jì)中間代碼四元式的結(jié)構(gòu)（暫不與符號(hào)表有關(guān)）；

(3)輸入串應(yīng)是詞法分析的輸出二元式序列，即某算術(shù)表達(dá)式“專題1〞的輸出結(jié)果。

輸出為輸入串的四元式序列中間文件；(4)設(shè)計(jì)兩個(gè)測(cè)試用例（盡可能完備），并給出程序執(zhí)行結(jié)果。

2.4任務(wù)分析

重點(diǎn)解決賦值語(yǔ)句文法的改寫和語(yǔ)義動(dòng)作的添加。

三、實(shí)現(xiàn)過(guò)程

3.1擴(kuò)展文法

G[s]:

S→A

A→V=E

E→E+T|E-T|TT→T*F|T/F|FF→(E)|iV→i

3.2非終結(jié)符FOLLOW集

FOLLOW(S)={#}FOLLOW(A)={#}FOLLOW(V)={=}

FOLLOW(E)={+,-,),#}

FOLLOW(T)={+,-,*,/,),#}FOLLOW(F)={+,-,*,/,),#}

3.3LR(0)分析器的構(gòu)造

設(shè)DFAM的一個(gè)狀態(tài)為i，該狀態(tài)識(shí)別出的所有活前綴的有效項(xiàng)目集為Ci。則DFAM的狀態(tài)集Q={C0,C1,C2,…,Cn}=C。C稱為文法的LR(0)有效項(xiàng)目集規(guī)范族。

對(duì)Ci有三種操作：

求文法的LR(0)有效項(xiàng)目集規(guī)范族C的算法：

由上述算法可求得有效項(xiàng)目集規(guī)范族C={C0,C1,C2,…,C19}。

3.3.1有效項(xiàng)目規(guī)范簇：

C0={S→·A,A→·V=E,V→·i}C1={S→A·}C2={S→V·=E}C3={V→i·}

C4={S→V=·E,E→·E+T,E→·E-T,E→·T,

T→·T*F,T→·T/F,T→·F,F→·(E),F→·i}

C5={S→V=E·,E→E·+T,E→E·-T}C6={E→T·,T→T·*F,T→T·/F}C7={T→F·}

C8={F→(·E),E→·E+T,E→·E-T,E→·T,

T→·T*F,T→·T/F,T→·F,F→·(E),F→·i}

C9={F→i·}

C10={E→E+·T,T→·T*F,T→·T/F,T→·F,F→·(E),F→·i}C11={E→E-·T,T→·T*F,T→·T/F,T→·F,F→·(E),F→·i}C12={T→T*·F,F→·(E),F→·i}C13={T→T/·F,F→·(E),F→·i}C14={F→(E·),E→E·+T,E→E·-T}C15={E→E+T·,T→T·*F,T→T·/F}C16={E→E-T·,T→T·*F,T→T·/F}C17={T→T*F·}C18={T→T/F·}C19={F→(E)·}

3.3.2沖突項(xiàng)目：

定義：(1)既含移進(jìn)項(xiàng)目,又含歸約項(xiàng)目(2)含有多個(gè)歸約項(xiàng)目

在項(xiàng)目集中存在沖突項(xiàng)目：

C5:C6:C15:C16:沖突可解決，所以語(yǔ)義分析采用SLR(1)分析法分析。

3.4SLR(1)分析法

LR(0)有效項(xiàng)目集規(guī)范族C中，若一個(gè)項(xiàng)目集含有m個(gè)移進(jìn)項(xiàng)目，同時(shí)含n個(gè)歸約項(xiàng)目，即若,FOLLOW(V1),…,FOLLOW(Vn)兩兩互不相交，滿足此條件的文法為SLR(1)文法，可用SLR(1)分析方法解決。

3.5SLR(1)分析器的構(gòu)造

(1)拓廣文法G’(2)構(gòu)造(對(duì)G’)LR(0)有效項(xiàng)目集族C和Go函數(shù)(3)若GO(Ci,a)=Cj，，則置ACTION(i,a)=Sj(4)若，且，，則置ACTION(i,a)=rj

(為第j個(gè)產(chǎn)生式)(5)若，(S為拓廣文法開(kāi)始符號(hào))，則置ACTION(k,#)=acc(6)若GO(Ci,A)=Cj，，置GOTO(i,A)=j(7)其它：空白(error)

3.6SLR(1)分析表

表3-1SLR(1)分析表

3.7語(yǔ)義動(dòng)作添加

S→AA→V=E

E(1)→E(2)+TE(1)→E(2)-TE→T

T(1)→T(2)*FT(1)→T(2)/FT→FF→(E)F→iV→i

{}

{GEN(=,E·PLACE,_,V·PLACE);}

{E(1)·PLACE=NEWTEMP;GEN(+,E(2)·PLACE,T·PLACE,E(1)·PLACE);}{E(1)·PLACE=NEWTEMP;GEN(-,E(2)·PLACE,T·PLACE,E(1)·PLACE);}{E·PLACE=T·PLACE;}

{T(1)·PLACE=NEWTEMP;GEN(*,T(2)·PLACE,F·PLACE,T(1)·PLACE);}{T(1)·PLACE=NEWTEMP;GEN(/,T(2)·PLACE,F·PLACE,T(1)·PLACE);}{T·PLACE=F·PLACE;}{F·PLACE=E·PLACE;}{F·PLACE=ENTRY(i);}{V·PLACE=ENTRY(i);}

3.8主要數(shù)據(jù)結(jié)構(gòu)

pair:

用pair來(lái)存儲(chǔ)單個(gè)二元組。

對(duì)照表由專題1定義。其中，第一個(gè)元素為類型號(hào)，其次個(gè)為元素的值。當(dāng)類型號(hào)小于40時(shí)，代表程序分界符，其次個(gè)元素不存儲(chǔ)有效信息，用“-〞代替；當(dāng)類型號(hào)為40時(shí)，代表標(biāo)識(shí)符，其次個(gè)元素存儲(chǔ)標(biāo)識(shí)符字符串；當(dāng)類型號(hào)為41時(shí)，代表實(shí)數(shù)，其次個(gè)元素存儲(chǔ)的是該實(shí)數(shù)的二進(jìn)制值。

typedefpairPIS;

pair:用pair來(lái)存儲(chǔ)終結(jié)符與非終結(jié)符的離散化值。符號(hào)i=+-*structNode:

用structNode來(lái)存儲(chǔ)四元組，表示(op,arg1,arg2,res)

其中op為操作符，arg1