語法分析器編譯原理課程設(shè)計報告`

LL(1)語法分析器一、課程設(shè)計的目的通過課程設(shè)計進一步理解高級語言在計算機中的執(zhí)行過程，加深對編譯原理中重點算法和編譯技術(shù)的理解，提高自己的編程能力，培養(yǎng)好的程序設(shè)計風格。同時通過某種可視化編程語言的應(yīng)用，具備初步的Windows環(huán)境下的編程思想。解和掌握LL(1)語法分析方法的基本原理；根據(jù)給出的LL(1)文法，掌握LL(1)分析表的構(gòu)造及分析過程的實現(xiàn)。二、課程設(shè)計的要求及其方法語法分析程序要求實現(xiàn)sample語言中幾種最常見的、基本的語法單位的分析：算術(shù)表達式，邏輯表達式，賦值語句，if語句，for語句，while語句，repeat語句等，各個語法單位的定義如下： Sample語言的定義<字符>::=<字母>|<數(shù)字>|<界符><字母>::=a|b|c…|z|A|B|C…|Z<數(shù)字>::=0|1|2|3…|9<單界符>::=+|-|*|/|=|<|>|(|)|[|]|:\;|,|’|_|.單詞集的定義(1)<單詞集>::=<保留字>|<雙界符>|<標識符>|<常數(shù)>|<單界符>(2)<保留字>::=and|array|begin|bool|call|case|case|char|const|do|dlse|end|false|for|if|input|integer|not|of|or|output|program|read|real|repeat|set|then|to|true|until|var|while|write (3)<雙界符>::=/*|*/|<=|>=|<>|:= (4)<標識符>::=<字母>|<標識符><數(shù)字>|<標符><字母> (5)<常數(shù)>::=<整數(shù)>|<布爾常數(shù)>|<字符常數(shù)>|常數(shù)標識符>|<實數(shù)> (6)<整數(shù)>::=<數(shù)字>|<整數(shù)><數(shù)字> (7)<布爾常數(shù)>::=true|false (8)<字符常數(shù)>::=’除’以外的任意字符串’ (9)<常數(shù)標識符>::=<標識符> (10)<實數(shù)>::=<整數(shù)>.<整數(shù)>數(shù)據(jù)類型的定義(1)<簡單類型>:==integer|bool|char|real表達式的定義 (1)<表達式>::=<算術(shù)表達式>|<邏輯表達式> (2)<算術(shù)表達式>::=<項>+-<算術(shù)表達式>|+-<項>|<項> (3)<項>:==<項>*<因子>|<項>/<因子>|<因子> (4)<因子>::=<算術(shù)量> (5)<算術(shù)量>::=<標識符>|<整數(shù)> (6)<邏輯表達式>::=<布爾項>or<邏輯表達式>|<布爾項> (7)<布爾項>::=<布爾因子>and<布爾項>|<布爾因子> (8)<布爾因子>::=<布爾量>|not<布爾因子> (9)<布爾量>::=<邏輯表達式>|<布爾常數(shù)>|<標識符>|<算術(shù)表達式><關(guān)系符><算術(shù)表達式> (10)<關(guān)系符>::=<|>|<>|<=|>=|=語句的定義 (1)<語句>::=<說明語句>|<執(zhí)行語句> (2)<說明語句>::=<常數(shù)說明><變量說明> (3)<常量說明>::=const<常數(shù)定義>|ε (4)<常數(shù)定義>::=標識符=<常數(shù)>;<常數(shù)定義>|標識符=<常數(shù)>;<變量說明>::=var<變量定義>|ε<變量定義>::=<標識符表>:<類型>;|<標識符表>:<類型>;<變量定義><標識符表>::=<標識符>,<標識符表>|<標識符><執(zhí)行語句>::=<簡單句>|<結(jié)構(gòu)句><簡單句>::=<賦值句><賦值句>::=<變量>:=<表達式><變量>::=<標識符><結(jié)構(gòu)語句>::=<復(fù)合句>|<if語句>|<while語句>|<for語句>|<repeat語句><復(fù)合句>::=begin<語句表>end<語句表>::=<執(zhí)行句>;<語句表>|<執(zhí)行句><if語句>::=if<布爾表達式>then<執(zhí)行句><if語句>::=if<布爾表達式>then<執(zhí)行句1>else<執(zhí)行句2><while語句>::=while<布爾表達式>do<執(zhí)行句><for語句>::=for<標識符>::=<算術(shù)表達式1>to<算術(shù)表達式2>do<執(zhí)行句><repeat語句>::=repeat<執(zhí)行句>until<布爾表達式>程序定義(1)<程序>::=program<標識符>;<分程序> (2)<分程序>::=<常量說明><變量說明><復(fù)合句>本次語法分析器課程設(shè)計采用LL（1）自頂向下析法來實現(xiàn)。三、課程設(shè)計的內(nèi)容根據(jù)下面LL(1)文法，對輸入串w:(i+i)*(i+i)+i*i進行LL(1)分析,要求如下：先建立LL（1）分析表；分析輸入串，判斷是否是語法上正確的句子，若正確則輸出整個自頂向下分析過程。若是在語法上不正確則報錯。四、實現(xiàn)原理語法分析的任務(wù)是在詞法分析的基礎(chǔ)上，主要任務(wù)是接受詞法分析程序識別出來的單詞符號,判斷它們是否由某種語言的文法產(chǎn)生,即判斷被識別符號串是否為某語法成分.除此之外,還要進行語法檢查,為后面的語義分析和代碼生成做準備.根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法范疇。實現(xiàn)Sample語言中幾種最常見的,基本的語法單位的分析:算術(shù)表達式.邏輯表達式,賦執(zhí)語句,IF語句,FOR語句,WHLIE語句REPEAT語句等:通過語法分析，可以確定整個輸入串是否構(gòu)成語法上正確的“程序”。語法分析階段遵循的是語言的語法規(guī)則。該語法分析器的主要組成即常量說明的函數(shù)（const），變量說明的函數(shù)（varst），以及可執(zhí)行語句的分析（ST_SORT），各個子函數(shù)又調(diào)用相應(yīng)的函數(shù)，完成語法分析任務(wù)。由于詞法分析和語法分析的聯(lián)系，在編寫語法分析程序的過程當中，要聯(lián)系到詞法分析中相應(yīng)的變量，如設(shè)置一個指向Token表的頭指針，方便讀入單詞進行語法分析。語法分析的任務(wù)就是根據(jù)語言的語法定義判斷輸入的TOKEN文件是否符合語法規(guī)則的定義,如果符合某個語法成分的定義,就是正確的定義.語法分析的過程就是不斷地讀入TOKEN文件中的單詞,根據(jù)不同的語法單位,使用不同的方法進行分析,直到TOKEN文件的結(jié)束.源程序的組織結(jié)構(gòu)是,程序頭部,說明部分和可執(zhí)行部分.遞歸下降分析器是當一個分析滿足LL(1)條件時,就為他構(gòu)造一個不帶回溯的自上而下分析程序,這個分析程序是由一組遞歸過程組成的每個過程對應(yīng)文法的一個非終結(jié)符通過語法分析,可以建立相應(yīng)的語法樹.根據(jù)建立語法樹方式的不同,可以把語法分析過程分為兩大類,即自頂向下和自底向上的分析方法.顧名思義,自頂向下的語法分析程序是沿著從樹根到樹葉的方向建立,而自底向上的方法則是沿著從樹葉到樹根的方向建立五、算法實現(xiàn)流程圖詞法分析程序把源程序變成TOKEN串,存放在TOKEN文件中.語法分析的任務(wù)就是根據(jù)語言的語法定義(產(chǎn)生式)判斷輸入的token文件是否符合語法規(guī)則的定義,如果符合某個語法成分的定義,就是正確的定義.語法分析的過程就是不斷地讀入token文件中的單詞，根據(jù)不同的語法單位（語句），使用不同的方法進行分析，直到token文件的結(jié)束。源程序的組織結(jié)構(gòu)（去掉了注釋等無用部分）是：程序頭部，說明部分和可執(zhí)行部分，所以要分別進行處理。在語法分析過程中,各種語句的處理可以采用不同的語法分析方法:一是對各個語句和布爾表達式采用遞歸下降翻譯法,二是對算術(shù)表達式采用自底向上的算符優(yōu)先分析方法.根據(jù)采用的語法分析方法的不同,就得到不同的詳細數(shù)據(jù)流圖.如下圖是使用算符優(yōu)先分析方法的數(shù)據(jù)流.六、測試數(shù)據(jù)w:(i+i)*(i+i)+i*I七、結(jié)果輸出及其分析、在次語法分析器中我們所給的測試數(shù)據(jù)是對輸入串w:(i+i)*(i+i)+i*i進行LL(1)分析.當次串滿足我們所給出的文法的時候，就按照上面的格式進行輸出。當我們所給出的輸入穿不滿足我們所給出的文法是則包錯誤.例如:給出輸入串w:kjads245dfkjd212,顯然我們所給出的串不滿足所給出的文法.則報錯.顯示有：“按任意鍵繼續(xù)”字樣。八、軟件運行環(huán)境及限制本程序以VisualC++為開發(fā)環(huán)境，其功能是對C語言源程序進行語法分析。本程序?qū)υ闯绦蛑兴行畔ⅲòǔ鲥e信息）均用鏈表表示。這樣可為后續(xù)程序的開發(fā)提供比較好的接口。九、參考文獻〈〈程序設(shè)計語言編譯原理〉〉第3版陳火旺等編著國防工