編譯原理課程設(shè)計 (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 編譯器的實現(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 詞法工具的使用說明7</p><p>　　4.2 輸入文件的語法結(jié)構(gòu)8<

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

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

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

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

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

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

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

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

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

12、叉編譯程序（Cross Compiler）。</p><p><b>　　自展法：</b></p><p>　　實現(xiàn)思想：先用目標機的匯編語言或機器語言書寫源語言的一個子集的編譯程序，然后再用這個子集作為書寫語言，實現(xiàn)源語言的編譯程序。通常這個過程會分成若干步，像滾雪球一樣直到生成預(yù)計源語言的編譯程序為止。我們把這樣的實現(xiàn)方式稱為自展技術(shù)。</p>&l

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

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

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

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

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

18、法分析的時候可能消失?？梢杂靡韵滤?lt;/p><p>　　法判定一個非終結(jié)符號是否可以導(dǎo)出(空串)。設(shè)S_Lambda表示可導(dǎo)出(空串)的</p><p>　　非終結(jié)符號集，則求它的算法如下:</p><p>　　(1).令S_Lambda={Aj|Aj→λ∈Production};</p><p>　　(2).對每一個產(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é)束符號，first(β)表示β串所能推導(dǎo)的終極符串的頭終結(jié)符集，如果β能推導(dǎo)出空串，則令First(β)包括 λ。 follow(A)表示所有那些終結(jié)符的集合,這些終極在某個句型中出現(xiàn)在A的緊后面。這種集合主要用于求predict(A → β )的集合.</p><

22、p>　　LL(1)語法分析方法是一種自頂向下的語法分析方法，它是LL(k)分析方法的特例，其中的k表示向前看k個符號的意思。和遞歸下降法有相同的問題，即在推導(dǎo)過程中如何唯一選擇產(chǎn)生式的問題，因此，LL（1）語法分析方法與遞歸下降法一樣對文法做了相同的限制，即：</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)生式的唯一性，滿足上面條件的文法稱為LL（1）文法。</p><p>　　LL(1)語法分析程序是由兩部分組成的，第一部分是語法分析表，也稱為LL(1)分析矩陣。第二部分是語法分析驅(qū)動程序。&

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

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

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

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

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

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

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

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

32、許詞法分析器方便的處理空白和注解。</p><p>　　詞法分析器僅返回一個值（記號）給分析器。為了傳遞記號的屬性值，可以將值置于全程變量yylval中</p><p>　　4.2 輸入文件的語法結(jié)構(gòu)</p><p>　　下面是用戶輸入的動作文法所采用的語法結(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主要包括動作文法中的動作要用到的數(shù)據(jù)結(jié)構(gòu),函數(shù)過程,全局變量,預(yù)定主常量</p><p><b>　　block:</b></p><p

35、>　　“{” c_code “}” ;</p><p>　　block主要生成動作文法中要加入的語義動作,以及一個非終結(jié)符號的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é)符號的函數(shù)的開頭部分.</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)及其實現(xiàn)</p><p>　　輸入文件的詞法結(jié)構(gòu)主要包括兩部分,一部分是用戶輸入的規(guī)則的所用到的詞

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

49、法所用的規(guī)則.</p><p>　　下面舉個例子來說明使用方法。剛打開文件匹配的時候,匹配的是前面沒有<qq>四個規(guī)則, 當(dāng)匹配到'{'時,執(zhí)行BEGIN(qq)是就開始匹配前面帶有<QQ>的規(guī)則, 如果遇到'}',執(zhí)行BEGIN(0),后面接著開始匹配前面沒有<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>　　下面是讀用戶輸入文件的詞法,為了對用戶輸入文件出現(xiàn)錯誤的地方進行定位,需要在匹配完每個單詞要對當(dāng)前的單詞在文法中的位置進行定位. 其中yyleng是當(dāng)前匹配單詞的長度,column是當(dāng)前的列,position是當(dāng)前匹配的字符串在文件中的位置</p><p>　　規(guī)則部分前面加<cc>的部分

57、是用來c語言的詞法,前面不加<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);//回到原來的部分</p><p>　　return RIGHT_CURLY; </p><p><b>

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

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

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

69、gt;<p>　　指針數(shù)組,每個指針指向一個CObList對象。每個對象存儲這個非終結(jié)符號的一個規(guī)則。</p><p>　　CPtrArray right_parts;</p><p>　　// 這一規(guī)則所對應(yīng)的local_prelude_block在文件中的定位 如果這兩個值為-1的話,就是說這個非終結(jié)符沒有這樣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)前的計算結(jié)果第i個規(guī)則未知能否生成空,能生成空,不能生成空</p><p>　　int *status;</p><p>　　當(dāng)前已有多少個規(guī)則已有確定的結(jié)果</p><p>　　int finished_rules; </p><p>　　

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

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

74、;</p><p>　　存儲一個非終結(jié)符號可能的參數(shù)</p><p>　　CStringArray actual_parameters; </p><p>　　//如果類型是語義動作,存儲在文件中的起始與結(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é)符時所對應(yīng)的值||也有可能是一個終結(jié)字符</p><p>　　int value; </p><p><b>　　};</b></p><p>　　5．2 建立規(guī)則的存儲</p><p>　　根據(jù)計算可得輸入文件的文法是滿足LL(1)分析方法的文法, 對該文法寫一個遞歸下降分析程序,建立對這

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

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

79、</p><p>　　6.i=i+1,如果i==rules.GetSize()轉(zhuǎn)3,否則轉(zhuǎn)4</p><p>　　5．4 計算first集</p><p>　　1.初始化所有的非終結(jié)符號的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個非終結(jié)符號的每個規(guī)則的右部。如果遇到一個終結(jié)符號,則把這個非終結(jié)符號加到第i個非終結(jié)符號的first集中,加入后若改變這個非終結(jié)符號first集則置changed為1,接著分析其它規(guī)則;

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

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

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

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

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

86、法系統(tǒng)中的一條規(guī)則,假設(shè)計算所得</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>　　處理這個非

90、終結(jié)符號所對應(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不屬于這個非終結(jié)符任何一個規(guī)則的//select集,就出錯</p><p><b>　　}六、課程設(shè)計總結(jié)</b></p&g

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

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

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