語(yǔ)法分析器編譯原理課程設(shè)計(jì)報(bào)告`

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