編譯原理課程設(shè)計(jì) (2)

1、<p><b>　　目 錄</b></p><p><b>　　一、需求分析1</b></p><p><b>　　二、系統(tǒng)概論1</b></p><p>　　2．1 編譯器的結(jié)構(gòu)1</p><p>　　2．2 編譯器的實(shí)現(xiàn)2</p>&l

2、t;p>　　2．3 主要完成的工作4</p><p>　　三、LL(1)文法以及屬性文法5</p><p>　　3.1 LL(1)文法及其分析器5</p><p>　　四、輸入文件的結(jié)構(gòu)及詞法7</p><p>　　4.1 詞法工具的使用說(shuō)明7</p><p>　　4.2 輸入文件的語(yǔ)法結(jié)構(gòu)8<

3、;/p><p>　　4.3 輸入文件的詞法結(jié)構(gòu)及其實(shí)現(xiàn)11</p><p>　　五、系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)14</p><p>　　5．1 規(guī)則的存儲(chǔ)結(jié)構(gòu)14</p><p>　　5．2 建立規(guī)則的存儲(chǔ)15</p><p>　　5．3 非終結(jié)符推出空15</p><p>　　5．4 計(jì)算first

4、集16</p><p>　　5．5 計(jì)算follow集16</p><p>　　5．6 計(jì)算predict集17</p><p>　　5．7 判斷是否LL(1)17</p><p>　　5．8 輸出文件中函數(shù)的格式17</p><p><b>　　參考文獻(xiàn)19</b></p>

5、;<p><b>　　一、需求分析</b></p><p>　　編譯器的構(gòu)造工具比如YACC，BISON根據(jù)語(yǔ)言的高級(jí)描述生成語(yǔ)言處理器(編譯器，解釋器，轉(zhuǎn)換器)。根據(jù)用戶輸入的語(yǔ)言的文法，編譯器的構(gòu)造工具可以生成程序來(lái)處理以用戶輸入的文法書(shū)寫(xiě)的文本。隨著計(jì)算機(jī)應(yīng)用范圍的擴(kuò)大，在軟件自動(dòng)生成，文檔處理，特定專業(yè)的語(yǔ)言等領(lǐng)域，編譯器的構(gòu)造工具這一技術(shù)顯得越來(lái)越重要。</p&

6、gt;<p>　　類YACC的編譯器的構(gòu)造工具是基于LALR(1)方法，這一方法在時(shí)間和空間代價(jià)方面是有效的，而且所能解析的語(yǔ)言也覆蓋了大部分語(yǔ)言，因些大多數(shù)的編譯器的編譯器都是針對(duì)LALR(1)的,而很少有針對(duì)LL(1)文法的。</p><p><b>　　二、系統(tǒng)概論</b></p><p>　　2．1 編譯器的結(jié)構(gòu)</p><p

7、>　　不同的編譯器都有自己的組織和工作方式，它們都是根據(jù)源語(yǔ)言的具體特點(diǎn)和對(duì)目標(biāo)語(yǔ)言的具體要求來(lái)決定和設(shè)計(jì)出來(lái)的。因此，并沒(méi)有一種固定的編譯器的結(jié)構(gòu)，但從功能結(jié)構(gòu)幾乎都是一致的。這里說(shuō)的功能結(jié)構(gòu)是指編譯器內(nèi)部都做哪些工作，以及它們彼此之間的關(guān)系。圖1說(shuō)明了一般的編譯程序的功能結(jié)構(gòu)。</p><p>　　2．2 編譯器的實(shí)現(xiàn)</p><p>　　編譯程序是一個(gè)相當(dāng)復(fù)雜的系統(tǒng)程序，通常有

8、上萬(wàn)甚至幾萬(wàn)條指令。隨著編譯技術(shù)的發(fā)展，編譯程序的開(kāi)發(fā)周期也在逐漸縮短，但仍然需要很多人年，而且工作很艱巨，正確性也不易保證。要實(shí)現(xiàn)一個(gè)編譯程序，通常需要做到：</p><p>　　對(duì)源語(yǔ)言的語(yǔ)法和語(yǔ)義要有準(zhǔn)確無(wú)誤的理解，否則難以保證編譯程序的正確性。</p><p>　　對(duì)目標(biāo)語(yǔ)言和編譯技術(shù)也要有很好的了解，否則會(huì)生成質(zhì)量不高的目標(biāo)代碼。</p><p>　　確定

9、對(duì)編譯程序的要求，如搞不搞優(yōu)化，搞優(yōu)化搞到哪一級(jí)？等等。</p><p>　　根據(jù)編譯程序的規(guī)模，確定編譯程序的掃描次數(shù)、每次掃描的具體任務(wù)和所要采用的技術(shù)。</p><p>　　設(shè)計(jì)各遍掃描程序的算法并加以實(shí)現(xiàn)。</p><p>　　一般開(kāi)發(fā)編譯程序有如下幾種可能途徑：</p><p>　　轉(zhuǎn)換法（預(yù)處理法）：</p><

10、;p>　　假如我們要實(shí)現(xiàn)L語(yǔ)言，現(xiàn)在有L’語(yǔ)言的編譯器，那么可以把L語(yǔ)言程序轉(zhuǎn)換成L’語(yǔ)言的程序，再利用L’語(yǔ)言的編譯器實(shí)現(xiàn)L語(yǔ)言，這種方法通常用于語(yǔ)言的擴(kuò)充。如把C++程序轉(zhuǎn)換成C程序，我們用C語(yǔ)言的編譯器進(jìn)行編譯，常見(jiàn)的宏定義和宏使用都屬于這種典型。</p><p><b>　　移植法：</b></p><p>　　假設(shè)在A機(jī)器上已有L語(yǔ)言的編譯程序，想在B

11、機(jī)器上開(kāi)發(fā)一個(gè)L語(yǔ)言的編譯程序。這里有兩種實(shí)現(xiàn)方法：</p><p>　　實(shí)現(xiàn)方法一：最直接的辦法就是將A機(jī)的代碼直接轉(zhuǎn)換成B機(jī)代碼。</p><p>　　實(shí)現(xiàn)方法二：假設(shè)A機(jī)和B機(jī)上都有高級(jí)程序設(shè)計(jì)語(yǔ)言W的編譯程序，并且A機(jī)上的L語(yǔ)言編譯程序是用W語(yǔ)言寫(xiě)的，我們可以修改L編譯程序的后端，即把從中間代碼生成A機(jī)目標(biāo)代碼部分改為生成B機(jī)的目標(biāo)代碼。這種在A機(jī)上產(chǎn)生B機(jī)目標(biāo)代碼的編譯程序稱為交

12、叉編譯程序（Cross Compiler）。</p><p><b>　　自展法：</b></p><p>　　實(shí)現(xiàn)思想：先用目標(biāo)機(jī)的匯編語(yǔ)言或機(jī)器語(yǔ)言書(shū)寫(xiě)源語(yǔ)言的一個(gè)子集的編譯程序，然后再用這個(gè)子集作為書(shū)寫(xiě)語(yǔ)言，實(shí)現(xiàn)源語(yǔ)言的編譯程序。通常這個(gè)過(guò)程會(huì)分成若干步，像滾雪球一樣直到生成預(yù)計(jì)源語(yǔ)言的編譯程序?yàn)橹埂Ｎ覀儼堰@樣的實(shí)現(xiàn)方式稱為自展技術(shù)。</p>&l

13、t;p><b>　　工具法：</b></p><p>　　70年代隨著諸多種類的高級(jí)程序設(shè)計(jì)語(yǔ)言的出現(xiàn)和軟件開(kāi)發(fā)自動(dòng)化技術(shù)的提高，編譯程序的構(gòu)造工具陸續(xù)誕生，如70年代Bell試驗(yàn)室推出的LEX，YACC至今還在廣泛使用。其中LEX是詞法分析器的自動(dòng)生成工具，YACC是語(yǔ)法分析器的自動(dòng)生成工具。然而，這些工具大都是用于編譯器的前端，即與目標(biāo)機(jī)有關(guān)的代碼生成和代碼優(yōu)化部分由于對(duì)語(yǔ)義和目標(biāo)

14、機(jī)形式化描述方面所存在的困難，雖有不少生成工具被研制，但還沒(méi)有廣泛應(yīng)用。</p><p><b>　　自動(dòng)生成法：</b></p><p>　　如果能根據(jù)對(duì)編譯程序的描述，由計(jì)算機(jī)自動(dòng)生成編譯程序，是最理想的方法，但需要對(duì)語(yǔ)言的語(yǔ)法語(yǔ)義有較好的形式化描述工具，才能自動(dòng)生成高質(zhì)量的編譯程序。目前，語(yǔ)法分析的自動(dòng)生成工具比較成熟，如前面提到的YACC等，但是整個(gè)編譯程序的

15、自動(dòng)生成技術(shù)還不是很成熟，雖然有基于屬性文法的編譯程序自動(dòng)生成器和基于指稱語(yǔ)義的編譯程序自動(dòng)生成器，但產(chǎn)生目標(biāo)程序的效率很低，離實(shí)用尚有一段距離，因此，要想真正的實(shí)現(xiàn)自動(dòng)化，必須建立形式化描述理論。</p><p>　　2．3 主要完成的工作</p><p>　　本文所做的工作是用VC要建立一個(gè)針對(duì)LL(1)文法的編譯器的編譯器。本文以定義好的文法書(shū)寫(xiě)的文件作為輸入，其中包括語(yǔ)法及語(yǔ)義動(dòng)作

16、，鑒于輸入文件的所用的文法可以用LL(1)分析，于是對(duì)輸入的文件用遞歸下降的分析方法在內(nèi)存中建立它的存儲(chǔ)結(jié)構(gòu)，然后分別計(jì)算所輸入的文法的非終結(jié)符號(hào)是否可以生成空，每個(gè)非終結(jié)符號(hào)的first集合，每個(gè)非終結(jié)符號(hào)的follow集合，以及每個(gè)規(guī)則的predict集合，接著判斷任意一個(gè)非終結(jié)符號(hào)的任意兩個(gè)規(guī)則的Predict集的交集是不是都為空，如果是則輸入文法可以用遞歸下降法分析，否則不可以，用戶應(yīng)該對(duì)所輸入的文法作適當(dāng)?shù)男薷模蛊錆M足LL(

17、1)文法分析的要求，。如果所輸入的文法可以用遞歸下降法分析，生成相應(yīng)文法的語(yǔ)法分析程序。</p><p>　　三、LL(1)文法以及屬性文法</p><p>　　3.1 LL(1)文法及其分析器</p><p>　　文法分析的基本問(wèn)題之一是確定那些非終結(jié)符號(hào)導(dǎo)(空串)。這一信息很重要，</p><p>　　因?yàn)榭蓪?dǎo)出(空串)的非終結(jié)符號(hào)在語(yǔ)

18、法分析的時(shí)候可能消失?？梢杂靡韵滤?lt;/p><p>　　法判定一個(gè)非終結(jié)符號(hào)是否可以導(dǎo)出(空串)。設(shè)S_Lambda表示可導(dǎo)出(空串)的</p><p>　　非終結(jié)符號(hào)集，則求它的算法如下:</p><p>　　(1).令S_Lambda={Aj|Aj→λ∈Production};</p><p>　　(2).對(duì)每一個(gè)產(chǎn)生式 p: Ap →

19、X1…Xn ， 若X1...Xn ∈S_Lambda</p><p>　　(3).重復(fù)第二步的循環(huán)，直至S_Lambda收斂為止。</p><p>　　文法分析中最的用的技術(shù)是求以下種集合(終結(jié)符集)的技術(shù)，這三種集合的具</p><p>　　體定義如下(其中β ∈ (VN ∪VT) )* ，A ∈ VN):</p><p>　　First

20、 (β)={a ∈VT|β * a…} ∪ {if β * λthen {λ } else Ø}</p><p>　　Follow(A)={a ∈ VT |S + …Aa…}∪{if S *…A then {#} else Ø }</p><p>　　Predict(A → β)=First (β)， 當(dāng)First(β)不含有 λ </p><

21、p>　　=First(β)-{λ}∪Follow(A)，當(dāng)First(β)含有 λ </p><p>　　其中#表示輸入的結(jié)束符號(hào)，first(β)表示β串所能推導(dǎo)的終極符串的頭終結(jié)符集，如果β能推導(dǎo)出空串，則令First(β)包括 λ。 follow(A)表示所有那些終結(jié)符的集合,這些終極在某個(gè)句型中出現(xiàn)在A的緊后面。這種集合主要用于求predict(A → β )的集合.</p><

22、p>　　LL(1)語(yǔ)法分析方法是一種自頂向下的語(yǔ)法分析方法，它是LL(k)分析方法的特例，其中的k表示向前看k個(gè)符號(hào)的意思。和遞歸下降法有相同的問(wèn)題，即在推導(dǎo)過(guò)程中如何唯一選擇產(chǎn)生式的問(wèn)題，因此，LL（1）語(yǔ)法分析方法與遞歸下降法一樣對(duì)文法做了相同的限制，即：</p><p>　　假設(shè)A的全部產(chǎn)生式為Aα1|α2|……|αn</p><p><b>　　則有：</b&

23、gt;</p><p>　　Predict(A → αi)∩Predict(A → αj)≠ Ø I ≠ j</p><p>　　有了上面的限制條件，可以保證選擇產(chǎn)生式的唯一性，滿足上面條件的文法稱為L(zhǎng)L（1）文法。</p><p>　　LL(1)語(yǔ)法分析程序是由兩部分組成的，第一部分是語(yǔ)法分析表，也稱為L(zhǎng)L(1)分析矩陣。第二部分是語(yǔ)法分析驅(qū)動(dòng)程序。&

24、lt;/p><p>　　LL(1)矩陣的作用是如何選擇語(yǔ)法規(guī)則，它的行表是由所有非終極符組成，它的列表是由所有終極符即特殊符號(hào)（結(jié)束符），矩陣的值有兩種：一種是產(chǎn)生式編號(hào)，另外一種是錯(cuò)誤編號(hào)，其一般形式可定義為：LL(A,a)=k 其中A∈Vn,a∈Vt∪{#},k為規(guī)則編號(hào)[P]或錯(cuò)誤編號(hào)error k。</p><p>　　設(shè)有規(guī)則Aα[k],若a∈Predict(Aα),那么有LL(

25、A,a)=k；若a不屬于任何一個(gè)以A為左部的規(guī)則的Predict集，則LL(A,a)=錯(cuò)誤編號(hào)。</p><p>　　LL(1)分析程序工作原理是首先初始化，即把開(kāi)始符壓入棧中，以后的每步分析必為下面的四種情況之一：</p><p>　　1． 析棧的棧頂元素是終極符，則看其是否與輸入流的頭符相匹配，如果匹配成功，去掉棧頂元素,并讀下一個(gè)單詞；若匹配不成功，則報(bào)錯(cuò)。</p>&

26、lt;p>　　2． 棧頂是非終極符，則用棧頂和輸入流的當(dāng)前單詞去查當(dāng)前矩陣，如果查得的值是產(chǎn)生式編號(hào)，則把對(duì)應(yīng)的產(chǎn)生式右部逆序壓入棧中；如果查得的值為錯(cuò)誤信息，則報(bào)錯(cuò)。</p><p>　　棧已空，輸入流不空，這時(shí)輸入流報(bào)錯(cuò)。</p><p>　　若棧已空，輸入流也空，則語(yǔ)法分析成功。</p><p>　　由上可以看出，LL（1）語(yǔ)法分析驅(qū)動(dòng)程序?qū)τ谌魏挝姆ǘ?/p>

27、是一樣的，所不同的是不同的文法LL（1）矩陣是不相同的。所以構(gòu)造LL(1)語(yǔ)法分析程序關(guān)鍵是如何構(gòu)造文法的LL(1)矩陣。LL（1）的構(gòu)造可以是手工操作的，也可以是自動(dòng)生成的</p><p>　　四、輸入文件的結(jié)構(gòu)及詞法</p><p>　　4.1 詞法工具的使用說(shuō)明</p><p>　　Flex是Lex的的改進(jìn)版本。Lex是詞法分析器的自動(dòng)生成工具，它從基于正規(guī)式

28、的專門(mén)表示構(gòu)造詞法分析器，并已廣泛用于說(shuō)明各種語(yǔ)言的詞法分析器。Flex程序包括三個(gè)部分：</p><p><b>　　聲明</b></p><p><b>　?。ィ?lt;/b></p><p><b>　　翻譯規(guī)則</b></p><p><b>　?。ィ?lt;/b&

29、gt;</p><p><b>　　輔助過(guò)程</b></p><p>　　聲明部分包括變量，顯明常量和正規(guī)定義。顯明常量是表示常量的標(biāo)識(shí)符。</p><p>　　Flex程序的翻譯規(guī)則為形如</p><p><b>　　P1{動(dòng)作1}</b></p><p><b&g

30、t;　　P2 {動(dòng)作2}</b></p><p><b>　　……</b></p><p><b>　　Pn{動(dòng)作n}</b></p><p>　　的語(yǔ)句。這里，每個(gè)Pi是正規(guī)式，每個(gè)動(dòng)作i是描述模式pi匹配單詞時(shí)詞法分析器應(yīng)執(zhí)行的程序段。</p><p>　　第三部分包括了動(dòng)作所

31、需要的輔助過(guò)程。這些過(guò)程也可以分別編譯，然后和詞法分析器一同裝入。</p><p>　　由Flex建立的詞法分析器和分析器聯(lián)系的方式是：詞法分析器被分析器激活時(shí)，開(kāi)始逐個(gè)字符地讀它的剩余輸入，直到它發(fā)現(xiàn)能和正規(guī)式pi匹配的輸入的最長(zhǎng)前綴為止；然后執(zhí)行動(dòng)作i。典型的，動(dòng)作i將把控制返回分析器。如果不是這樣，詞法分析器繼續(xù)尋找下面的單詞，直到有一個(gè)動(dòng)作引起控制回到分析器為止。這種重復(fù)的搜索單詞，直到顯示的返回的方式允

32、許詞法分析器方便的處理空白和注解。</p><p>　　詞法分析器僅返回一個(gè)值（記號(hào)）給分析器。為了傳遞記號(hào)的屬性值，可以將值置于全程變量yylval中</p><p>　　4.2 輸入文件的語(yǔ)法結(jié)構(gòu)</p><p>　　下面是用戶輸入的動(dòng)作文法所采用的語(yǔ)法結(jié)構(gòu),并且該文法可以用LL(1)方法分析。</p><p><b>　　gr

33、ammar: </b></p><p>　　global_prelude_part token_declaration_part rule_part;</p><p>　　global_prelude_part :</p><p>　　global_prelude |</p><p><b>　　empty;</b

34、></p><p>　　global_prelude:</p><p>　　“%prelude” block;</p><p>　　global_prelude主要包括動(dòng)作文法中的動(dòng)作要用到的數(shù)據(jù)結(jié)構(gòu),函數(shù)過(guò)程,全局變量,預(yù)定主常量</p><p><b>　　block:</b></p><p

35、>　　“{” c_code “}” ;</p><p>　　block主要生成動(dòng)作文法中要加入的語(yǔ)義動(dòng)作,以及一個(gè)非終結(jié)符號(hào)的local_prelude</p><p>　　empty:;</p><p>　　token_declaration_part:</p><p>　　“%token” token_declaration

36、_list “}”|</p><p><b>　　empty;</b></p><p>　　token_declaraton_list:</p><p>　　token_declaration “,”tail_token_declaration_list|</p><p>　　token_declaration ;<

37、;/p><p>　　token_declaration: identifier ;</p><p>　　rule_part : rule_list;</p><p>　　rule_list: rule rule_list|</p><p><b>　　rule;&l

38、t;/b></p><p>　　rule : left_hand_side “:” right_hand_side “;”</p><p>　　left_hand_side: nonterminal formal_parameter_spec ;</p><p>　　nonterminal:

39、 identifier;</p><p>　　formal_parameter_spec: empty</p><p>　　|“<” ”%in” parameter_spec_list “> </p><p>　　| “<” “%out” parameter_spec_list“>” </p><p&g

40、t;　　|“<” “%in” parameter_spec_list “%out” parameter_spec_list “>”</p><p>　　%in 參數(shù)用于值傳參數(shù),%out參數(shù)用于引用傳遞</p><p>　　parameter_spec_list: parameter_spec “,” parameter_spec_list |</p>

41、<p>　　parameter_spec;</p><p>　　parameter_spec : parameter_type parameter_name;</p><p>　　parameter_type: identifier ;</p><p>　　parameter_name： pa

42、rameter_name; </p><p>　　right_hand_side: local_prelude_option alternative_list;</p><p>　　local_prelude_option: local_prelude |</p><p><b>　　empty;</b><

43、;/p><p>　　local_prelude: “%prelude” block;</p><p>　　local_prelude的內(nèi)容插入到處理左邊的非終結(jié)符號(hào)的函數(shù)的開(kāi)頭部分.</p><p>　　alternative_list: member_list;</p><p>　　member_li

44、st member member_list;</p><p>　　member : item;</p><p>　　item: symbol | literal |semantic_action;</p><p>　　symbol:

45、 symbol_name actual_parameters_option;</p><p>　　symbol_name: identifier;</p><p>　　actual_parameters_option : actual_parameters</p><p><b>　　|empty;<

46、/b></p><p>　　actual_parameters: “<” actual_parameter_list ”>”;</p><p>　　actual_parameter_list：actual_parameter “,” actual_parameter_list|</p><p>　　actual_parameter

47、;</p><p>　　literal: char_constant;</p><p>　　semantic_action: block;</p><p>　　4.3 輸入文件的詞法結(jié)構(gòu)及其實(shí)現(xiàn)</p><p>　　輸入文件的詞法結(jié)構(gòu)主要包括兩部分,一部分是用戶輸入的規(guī)則的所用到的詞

48、法,另一部分是語(yǔ)義動(dòng)作用到的詞法，語(yǔ)義動(dòng)作用到的詞法是C語(yǔ)言所使用的詞法. 當(dāng)在處理用戶輸入的動(dòng)作文法的時(shí)候,如果遇到了'{',表明遇到了C語(yǔ)言塊,對(duì)'{'的計(jì)數(shù)加1,轉(zhuǎn)入到C語(yǔ)言的詞法分析部分。在C語(yǔ)言的詞法分析部分,若遇到單詞'{',對(duì)'{'的計(jì)數(shù)加1,若遇到'}',則對(duì)'{'的計(jì)數(shù)減1,如果些時(shí)計(jì)數(shù)為零,切換詞法分析程序所匹配的規(guī)則到文

49、法所用的規(guī)則.</p><p>　　下面舉個(gè)例子來(lái)說(shuō)明使用方法。剛打開(kāi)文件匹配的時(shí)候,匹配的是前面沒(méi)有<qq>四個(gè)規(guī)則, 當(dāng)匹配到'{'時(shí),執(zhí)行BEGIN(qq)是就開(kāi)始匹配前面帶有<QQ>的規(guī)則, 如果遇到'}',執(zhí)行BEGIN(0),后面接著開(kāi)始匹配前面沒(méi)有<QQ>的規(guī)則.</p><p><b>　　%x

50、qq</b></p><p>　　"%prelude" {</p><p>　　return 90;</p><p><b>　　}</b></p><p>　　"%token" {</p><p>　　return 100;&

51、lt;/p><p><b>　　}</b></p><p>　　"{" {</p><p>　　BEGIN(QQ);</p><p><b>　　}</b></p><p>　　. {</p><

52、p><b>　　} </b></p><p>　　<QQ>[A-Za-z_]+ {</p><p>　　return 101;</p><p><b>　　}</b></p><p>　　<QQ>'+' {</p><p

53、>　　return 102;</p><p><b>　　}</b></p><p>　　<QQ>'-' {</p><p>　　return 103;</p><p><b>　　}</b></p><p>　　<

54、QQ>'*' {</p><p>　　return 104;</p><p><b>　　}</b></p><p>　　<QQ>'/' {</p><p>　　return 105;</p><p><b>

55、;　　}</b></p><p>　　<QQ>'}' {</p><p><b>　　BEGIN(0);</b></p><p><b>　　}</b></p><p>　　<QQ>. {</p>

56、;<p><b>　　}</b></p><p>　　下面是讀用戶輸入文件的詞法,為了對(duì)用戶輸入文件出現(xiàn)錯(cuò)誤的地方進(jìn)行定位,需要在匹配完每個(gè)單詞要對(duì)當(dāng)前的單詞在文法中的位置進(jìn)行定位. 其中yyleng是當(dāng)前匹配單詞的長(zhǎng)度,column是當(dāng)前的列,position是當(dāng)前匹配的字符串在文件中的位置</p><p>　　規(guī)則部分前面加<cc>的部分

57、是用來(lái)c語(yǔ)言的詞法,前面不加<cc>的是規(guī)則的詞法</p><p><b>　　%x cc ccc</b></p><p><b>　　%%</b></p><p>　　"%prelude" { </p><p>　　printf("word:%s,l

58、ength=%d",yytext,yyleng);</p><p>　　position=position+yyleng;</p><p>　　column=column+yyleng;</p><p>　　return PRELUDE_A;</p><p><b>　　}</b></p><

59、;p>　　"%token" { </p><p>　　position=position+yyleng;</p><p>　　column=column+yyleng;</p><p>　　return TOKEN_A;</p><p><b>　　}</b></p>&

60、lt;p>　　"{" { </p><p>　　position+=yyleng;</p><p>　　column+=yyleng;</p><p>　　right_curly=1;</p><p>　　BEGIN(cc);</p><p>　　return LEFT_C

61、URLY; </p><p><b>　　} </b></p><p><b>　　.</b></p><p><b>　　.</b></p><p><b>　　.</b></p><p>　　<cc>&quo

62、t;auto" { </p><p>　　position+=yyleng;</p><p>　　column+=yyleng;</p><p><b>　　}</b></p><p>　　<cc>"break"{</p><p>　　posit

63、ion+=yyleng;</p><p>　　column+=yyleng;</p><p><b>　　}</b></p><p>　　<cc>"case"{</p><p>　　position+=yyleng;</p><p>　　column+=yyle

64、ng;</p><p><b>　　}</b></p><p>　　<cc>"}" {</p><p>　　position+=yyleng;</p><p>　　column+=yyleng;</p><p>　　right_curly--;</

65、p><p>　　if (right_curly==0)</p><p><b>　　{</b></p><p>　　BEGIN(0);//回到原來(lái)的部分</p><p>　　return RIGHT_CURLY; </p><p><b>

66、;　　}</b></p><p><b>　　}</b></p><p><b>　　五、系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)</b></p><p>　　5．1 規(guī)則的存儲(chǔ)結(jié)構(gòu)</p><p>　　下面這個(gè)數(shù)組結(jié)構(gòu)存儲(chǔ)的是一個(gè)非終結(jié)符號(hào)所對(duì)應(yīng)的所有的規(guī)則</p><p>　　clas

67、s CRule </p><p><b>　　{</b></p><p><b>　　public:</b></p><p>　　in_parameters,out_parameters 這個(gè)非終結(jié)符號(hào)所對(duì)應(yīng)輸入與輸出參數(shù)集合, in_parameters是值參 out_parameters是引用參數(shù)其//中每個(gè)數(shù)組的第

68、i(i%2=0)表示類型; (i%2=1)表示這個(gè)串是參數(shù)名</p><p>　　CStringArray in_parameters,out_parameters; </p><p>　　int initialized; </p><p>　　表示這個(gè)非終結(jié)符號(hào)名字</p><p>　　CString nonterminal;</p&

69、gt;<p>　　指針數(shù)組,每個(gè)指針指向一個(gè)CObList對(duì)象。每個(gè)對(duì)象存儲(chǔ)這個(gè)非終結(jié)符號(hào)的一個(gè)規(guī)則。</p><p>　　CPtrArray right_parts;</p><p>　　// 這一規(guī)則所對(duì)應(yīng)的local_prelude_block在文件中的定位 如果這兩個(gè)值為-1的話,就是說(shuō)這個(gè)非終結(jié)符沒(méi)有這樣local_prelude_block。否則有</p&g

70、t;<p>　　int local_prelude_block_begin_position;</p><p>　　int local_prelude_block_end_position;</p><p>　　int local_prelude_block_begin_line ;</p><p>　　int local_prelude_block_

71、begin_column;</p><p>　　p[i]=0,1,2分別表示當(dāng)前的計(jì)算結(jié)果第i個(gè)規(guī)則未知能否生成空,能生成空,不能生成空</p><p>　　int *status;</p><p>　　當(dāng)前已有多少個(gè)規(guī)則已有確定的結(jié)果</p><p>　　int finished_rules; </p><p>　　

72、select_set[i]表示這個(gè)非終結(jié)符號(hào)的第i個(gè)規(guī)則的select集</p><p>　　CDWordArray *select;</p><p><b>　　};</b></p><p>　　class CRightSymbol </p><p><b>　　{</b></p>

73、<p>　　這個(gè)數(shù)組結(jié)構(gòu)用來(lái)存儲(chǔ)規(guī)則右部的一個(gè)符號(hào)的信息</p><p><b>　　public:</b></p><p>　　表示這個(gè)類存儲(chǔ)的是字符,語(yǔ)義動(dòng)作,還是TOKEN_A(用戶定義的符號(hào)串常量),CHARACTER,SEMANTIC_ACTION</p><p><b>　　int type;</b>

74、;</p><p>　　存儲(chǔ)一個(gè)非終結(jié)符號(hào)可能的參數(shù)</p><p>　　CStringArray actual_parameters; </p><p>　　//如果類型是語(yǔ)義動(dòng)作,存儲(chǔ)在文件中的起始與結(jié)束地址。</p><p>　　int semantic_action_begin_line,semantic_action_begin_c

75、olumn;</p><p>　　int semantic_action_end_line,semantic_action_end_column;</p><p>　　int,semantic_action_end_position;</p><p>　　int semantic_action_begin_position</p><p>　

76、　//如果是token和非終結(jié)符時(shí)所對(duì)應(yīng)的值||也有可能是一個(gè)終結(jié)字符</p><p>　　int value; </p><p><b>　　};</b></p><p>　　5．2 建立規(guī)則的存儲(chǔ)</p><p>　　根據(jù)計(jì)算可得輸入文件的文法是滿足LL(1)分析方法的文法, 對(duì)該文法寫(xiě)一個(gè)遞歸下降分析程序,建立對(duì)這

77、些規(guī)則的存儲(chǔ)。</p><p>　　5．3 非終結(jié)符推出空</p><p>　　1.初始化所有的非終結(jié)符號(hào)以及每個(gè)非終結(jié)符號(hào)的所有規(guī)則未知其能否生成空.</p><p>　　2.置迭代標(biāo)志為1,i=0</p><p>　　3.如果迭代標(biāo)志為1轉(zhuǎn)4,否則計(jì)算結(jié)束</p><p>　　4.如果第i個(gè)非終結(jié)符號(hào)已計(jì)算得到能生

78、成空或生不成空則轉(zhuǎn)6</p><p>　　5.分析第i個(gè)非終結(jié)符號(hào)的每一個(gè)沒(méi)有確定其是否能生成空的規(guī)則:如果這個(gè)規(guī)則右部為空,或全部是已確定能推出空的非終結(jié)符號(hào),則標(biāo)記第i個(gè)非終結(jié)符號(hào)可以生成空,并置迭代表記為1,轉(zhuǎn)6;如果這個(gè)規(guī)則的分析中遇到了非終結(jié)符號(hào)或遇到了已確定不能生成空的非終結(jié)符號(hào),則標(biāo)記該規(guī)則不能推出空,當(dāng)這個(gè)規(guī)則第i個(gè)非終結(jié)符號(hào)的最后一個(gè)不能確定生成空的規(guī)則,則標(biāo)記第I個(gè)非終結(jié)符號(hào)不能生成空.轉(zhuǎn)6.

79、</p><p>　　6.i=i+1,如果i==rules.GetSize()轉(zhuǎn)3,否則轉(zhuǎn)4</p><p>　　5．4 計(jì)算first集</p><p>　　1.初始化所有的非終結(jié)符號(hào)的first集為空;</p><p>　　2.置changed=1</p><p>　　3.如果changed為1,轉(zhuǎn)4,否則轉(zhuǎn)結(jié)束.

80、</p><p>　　4.changed=0;i=0;</p><p>　　5.如果i<rules.GetSize()轉(zhuǎn)6,否則轉(zhuǎn)3</p><p>　　6.從左到右分析第i個(gè)非終結(jié)符號(hào)的每個(gè)規(guī)則的右部。如果遇到一個(gè)終結(jié)符號(hào),則把這個(gè)非終結(jié)符號(hào)加到第i個(gè)非終結(jié)符號(hào)的first集中,加入后若改變這個(gè)非終結(jié)符號(hào)first集則置changed為1,接著分析其它規(guī)則;

81、如果遇到一個(gè)非終結(jié)符號(hào)則把這個(gè)非終結(jié)符號(hào)的first集并到第i個(gè)非終結(jié)符號(hào)的first集當(dāng)中,此時(shí)若改變了第i個(gè)非終結(jié)符號(hào)的first集置,changed為1,若這個(gè)規(guī)則可以導(dǎo)出空,則繼續(xù)分析這個(gè)規(guī)則的后面的符號(hào)。</p><p>　　7.i=i+1,轉(zhuǎn)5</p><p>　　5．5 計(jì)算follow集</p><p>　　1.初始化所有的非終結(jié)符號(hào)的follow集

82、為空;</p><p>　　2.置changed=1</p><p>　　3.如果changed為1,轉(zhuǎn)4,否則計(jì)算結(jié)束.</p><p>　　4.changed=0;i=0;</p><p>　　5.如果i<rules.GetSize()轉(zhuǎn)6,否則轉(zhuǎn)3</p><p>　　6.從左到右分析第i個(gè)非終結(jié)符號(hào)的每個(gè)

83、規(guī)則的右部。對(duì)于在這個(gè)規(guī)則右部的每一個(gè)非終結(jié)符號(hào) 1)計(jì)算這個(gè)符號(hào)后面符號(hào)串的first集,把它并入到這個(gè)符號(hào)的follow集,如果并運(yùn)算改變了這個(gè)符號(hào)的follow集,則置changed為1; 2)計(jì)算這個(gè)符號(hào)后面的符號(hào)串能否推出空,若能推出空,則把第i個(gè)非終結(jié)符號(hào)的follow集并入到這個(gè)非終結(jié)符號(hào)的follow集,如果改變了這個(gè)非終結(jié)符號(hào)的follow集,</p><p>　　則置changed為1.&l

84、t;/p><p>　　7.i=i+1,轉(zhuǎn)5</p><p>　　5．6 計(jì)算predict集</p><p>　　每個(gè)規(guī)則的predict計(jì)算如下:如果這個(gè)非終結(jié)符號(hào)右部的串能導(dǎo)出空,則這個(gè)規(guī)則的predict集為這個(gè)規(guī)則左部非終結(jié)符號(hào)follow集并上這個(gè)規(guī)則右部串的first集,并去掉空串;如果這個(gè)規(guī)則的右部導(dǎo)不出空,則這個(gè)規(guī)則的predict集為這個(gè)規(guī)則右部串的f

85、irst集.</p><p>　　5．7 判斷是否LL(1)</p><p>　　計(jì)算任意一個(gè)非終結(jié)符號(hào)的任意兩個(gè)規(guī)則的predict集的交集是不是為空。如果存在某一個(gè)非終結(jié)符號(hào)的某兩個(gè)規(guī)則的predict集的交集為不為空,則該文法不能用LL(1)方法分析。</p><p>　　5．8 輸出文件中函數(shù)的格式</p><p>　　下面是某動(dòng)作文

86、法系統(tǒng)中的一條規(guī)則,假設(shè)計(jì)算所得</p><p>　　select(expr_list:expression expr_tail)={IDENTIFIER ,NUM ,'('}</p><p>　　select(expr_list:)={'B'}</p><p>　　expr_list<%out P_WRITEPARAMETER

87、 p_writeparameter> :</p><p><b>　　{</b></p><p>　　p_writeparameter=(P_WRITEPARAMETER)new struct</p><p>　　writeparameter;</p><p>　　P_EXPRESSION &p_expr=

88、p_writeparameter->p_expr;</p><p>　　P_WRITEPARAMETER &p_wp=p_writeparameter->next;</p><p><b>　　}</b></p><p>　　expression <p_expr> expr_tail<p_write_par

89、ameters_tail></p><p><b>　　|</b></p><p><b>　　{ </b></p><p>　　p_writeparameter=NULL;</p><p><b>　　};</b></p><p>　　處理這個(gè)非

90、終結(jié)符號(hào)所對(duì)應(yīng)的程序如下：</p><p>　　int expr_list (P_WRITEPARAMETERp_writeparameter,int &tok)</p><p><b>　　{ </b></p><p>　　//根據(jù)select集選擇規(guī)則1</p><p>　　if (tok==IDENTIF

91、IER||tok==NUM||tok=='(')</p><p><b>　　{</b></p><p>　　p_writeparameter= (P_WRITEPARAMETER) new struct writeparameter;</p><p>　　P_EXPRESSION &p_expr=p_writepar

92、ameter->p_expr;</p><p>　　P_WRITEPARAMETER &p_wp=p_writeparameter->next;</p><p>　　ret=expression (p_expr ,tok );</p><p>　　if (ret==0)</p><p><b>　　return

93、0;</b></p><p>　　ret=expr_tail (p_write_parameters_tail ,tok );</p><p>　　if (ret==0)</p><p><b>　　return 0;</b></p><p><b>　　return 1;</b><

94、;/p><p><b>　　}</b></p><p>　　//根據(jù)select選把規(guī)則2 </p><p>　　if (tok=='B' )</p><p><b>　　{ </b></p><p>　　p_writeparameter=NULL;<

95、/p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　return 0;// 如果參數(shù)tok不屬于這個(gè)非終結(jié)符任何一個(gè)規(guī)則的//select集,就出錯(cuò)</p><p><b>　　}六、課程設(shè)計(jì)總結(jié)</b></p&g

96、t;<p>　　經(jīng)過(guò)兩個(gè)星期的編譯原理課程設(shè)計(jì)，本人在老師以及同學(xué)的指導(dǎo)下，順利完成該課程設(shè)計(jì)。通過(guò)該課程設(shè)計(jì)，收獲頗多。</p><p>　　一、 對(duì)實(shí)驗(yàn)原理有更深的理解</p><p>　　二、 對(duì)該理論在實(shí)踐中的應(yīng)用有深刻的理解</p><p>　　三、 激發(fā)了學(xué)習(xí)的積極性</p><p>　　四、 理解了該知識(shí)點(diǎn)以及學(xué)科

97、之間的融合滲透</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] <<編譯程序構(gòu)造原理和實(shí)現(xiàn)技術(shù)>> ISBN 7-04-007492-3 金成植 高等教育出版社 2001.6 第二版</p><p>　　[2] 《程序設(shè)計(jì)語(yǔ)言編譯原理》 ISBN 7-118-02207-1 陳火旺 劉春林 譚慶

98、平 趙克佳 劉越 國(guó)防科技大學(xué)出版社</p><p>　　實(shí) 例 </p><p>　　下面這個(gè)例子輸入的是一個(gè)語(yǔ)言動(dòng)作文法,該動(dòng)作文法是要建立對(duì)這個(gè)文法的語(yǔ)言在內(nèi)存中的存儲(chǔ)， 以便作更進(jìn)一步的處理。一個(gè)這樣的文件是用一個(gè)語(yǔ)句鏈表存儲(chǔ),讀語(yǔ)句的參數(shù)是用一個(gè)字符串?dāng)?shù)組存儲(chǔ);write語(yǔ)句的表達(dá)式序列用表達(dá)式鏈存儲(chǔ)</p><p><b>　　%

99、prelude </b></p><p><b>　　{</b></p><p>　　struct expression </p><p>　　{ char op;//0:integer 1:variable name '+' or '-'</p><p><b>

100、;　　union {</b></p><p>　　struct expression *left,*right;//two //sub-expressions</p><p>　　int value;//constant</p><p>　　CString var_name; //variable name </p><p>&l

101、t;b>　　} node; </b></p><p>　　}; //用來(lái)存儲(chǔ)一個(gè)表達(dá)式</p><p>　　typedef struct expression EXPRESSION,*P_EXPRESSION;</p><p>　　struct writeparameter</p><p><b>　　{&l

102、t;/b></p><p>　　P_EXPRESSION *p_expr;</p><p>　　struct writeparameter *next; </p><p><b>　　};</b></p><p>　　typedef struct writeparameter</p><p

103、>　　WRITEPARAMETER,*P_WRITEPARAMETER;</p><p>　　struct assign {</p><p>　　CString id;</p><p>　　struct expression * p_exp;</p><p><b>　　};</b></p><

104、;p>　　typedef struct assign ASSIGN; </p><p>　　struct statement{</p><p>　　int type;//0:read 1:write 2:assign</p><p><b>　　union { </b></p><p>　　CStringArr

105、ay parameters;//parameters of readASSIGN assign; //assign sentence </p><p>　　P_WRITEPARAMETERS p_writeparameters;//</p><p>　　} value; </p><p>　　struct state

106、ment *next;</p><p><b>　　}; //</b></p><p>　　typedef struct statement STATEMENT,*P_STATEMENT; </p><p><b>　　}</b></p><p>　　%token BEGIN,END,RE

107、AD,WRITE,IDENTIFIER,NUM;</p><p>　　program<%out P_STATEMENT p_statement>:BEGIN statement_list</p><p>　　< p_statement>END;</p><p>　　statement_list<%out P_STATEMENT p_st

108、atement>:</p><p>　　statement <p_statement></p><p><b>　　{</b></p><p>　　P_STATEMENT &next=p_statement->next;</p><p><b>　　}</b><

109、/p><p>　　statement_tail<next>;</p><p>　　statement_tail<%out P_STATEMENT p_statement>:statement <p_statement></p><p><b>　　{</b></p><p>　　P_STA

110、TEMENT &tail=p_statement->next;</p><p><b>　　}</b></p><p>　　statement_tail<tail></p><p><b>　　| {</b></p><p>　　p_statement=NULL;</

111、p><p><b>　　}；</b></p><p>　　statement<%out P_STATEMENT p_statement>:IDENTIFIER</p><p><b>　　{ </b></p><p>　　p_statement=new struct statement;&

112、lt;/p><p>　　p_statement->type=2;</p><p>　　p_statement->value.assign.id.Copy(yytext);</p><p>　　P_EXPRESSION &p_exp=p_statement->value.assign.p_exp; </p><p><

113、;b>　　}</b></p><p>　　':' '=' expression<p_exp> ';'|</p><p><b>　　READ {</b></p><p>　　p_statement=new struct statement;</p>

114、<p>　　p_statement->type=0;//read sentence </p><p>　　CStringArray &parameters=p_statement->value.parameters;</p><p><b>　　} </b></p><p>　　'(' id_lis

115、t< parameters> ')' ';'|</p><p><b>　　WRITE </b></p><p><b>　　{</b></p><p>　　p_statement=new struct statement;</p><p>　　p_s

116、tatement->type=1;//write sentence</p><p>　　P_WRITEPARAMETER&p_writeparameter=p_statement-></p><p>　　value.p_writeparameters;</p><p><b>　　}</b></p><p

117、>　　'('expr_list<p_writeparameter>')' ';' ；</p><p>　　id_list<%out CStringArray parameters>:IDENTIFIER </p><p><b>　　{</b></p><p>　　p

118、arameters.Add(yytext); </p><p><b>　　}</b></p><p>　　id_tail<parameters>;</p><p>　　id_tail<%out CStringArray parameters>:',' IDENTIFIER </p>&l

119、t;p><b>　　{</b></p><p>　　parameters.Add(yytext); </p><p><b>　　}</b></p><p>　　id_tail <parameters></p><p><b>　　| ;</b></p&

120、gt;<p>　　expr_list<%out P_WRITEPARAMETER p_writeparameter> :</p><p><b>　　{</b></p><p>　　p_writeparameter= (P_WRITEPARAMETER) new struct writeparameter;</p><p&

121、gt;　　P_EXPRESSION &p_expr=p_writeparameter->p_expr;</p><p>　　P_WRITEPARAMETER &p_wp=p_writeparameter->next;</p><p><b>　　}</b></p><p>　　expression <p_exp

122、r> expr_tail<p_write_parameters_tail>;</p><p>　　expr_tail<%out P_WRITEPARAMETER p_writeparameter> :</p><p><b>　　{</b></p><p>　　p_writeparameter= new WRITE

123、PARAMETER;</p><p>　　P_EXPRESSION &p_expr=p_writeparameter->p_expr;</p><p>　　P_WRITEPARAMETER &p_wp=p_writeparameter->p_next;</p><p><b>　　}</b></p>&

124、lt;p>　　',' expression <p_expr> expr_tail <p_wp></p><p><b>　　|</b></p><p><b>　　{</b></p><p>　　p_writeparameter=NULL;</p><p&g

125、t;<b>　　}；</b></p><p>　　expression<%out P_EXPRESSION p_expr> : </p><p><b>　　{</b></p><p>　　P_EXPRESSION p_temp;</p><p>　　P_EXPRESSION p_tem

126、p1;</p><p><b>　　}</b></p><p>　　primary<p_temp>primary_tail<p_temp1>;</p><p>　　primary_tail<%out P_EXPRESSION p_expr>:</p><p><b>　　%p

127、relude</b></p><p><b>　　{</b></p><p>　　P_EXPRESSION p_temp1,p_temp2,p_temp3;</p><p><b>　　}</b></p><p>　　add_op <p_temp1> primary <

128、p_temp2></p><p>　　primary_tail<p_temp3></p><p><b>　　{</b></p><p>　　if (p_temp3==NULL)</p><p><b>　　{ </b></p><p>　　p_tmep1-

129、>node.right=p_temp2;</p><p>　　p_expr=p_temp1;</p><p><b>　　}</b></p><p><b>　　else{ </b></p><p>　　p_temp3->node.left=p_temp2;</p>&l

130、t;p>　　p_temp1->node.right=t_temp3;</p><p>　　p_expr=p_temp1;</p><p><b>　　}</b></p><p><b>　　}|</b></p><p><b>　　{</b></p>