語(yǔ)法分析器概述
從詞法分析的角度看，語(yǔ)言是一個(gè)單詞的集合，稱(chēng)之為正規(guī)集，單詞是由一個(gè)個(gè)字符組成的線性結(jié)構(gòu)；從語(yǔ)法分析的角度看，語(yǔ)言是一個(gè)句子的集合，而句子是由詞法分析器返回的記號(hào)組成的非線性結(jié)構(gòu)。反映句子結(jié)構(gòu)的最好方法是樹(shù)，常用的有分析樹(shù)和語(yǔ)法樹(shù)。分析語(yǔ)法結(jié)構(gòu)的基本方法有兩種：自上而下分析方法和自下而上分析方法。自上而下分析從根到葉子建立分析樹(shù)，而自下而上分析恰好相反。在這兩種情況下，分析器都是從左到右地掃描輸入，每次讀進(jìn)一個(gè)記號(hào)。
與詞法分析類(lèi)似，語(yǔ)法分析也具有雙重含義：
①規(guī)定句子形成的規(guī)則，也被稱(chēng)為語(yǔ)法規(guī)則。程序設(shè)計(jì)語(yǔ)言的大部分語(yǔ)法規(guī)則可以用上下文無(wú)關(guān)文法（Context Free Grammar，簡(jiǎn)稱(chēng)CFG）來(lái)描述。
②根據(jù)語(yǔ)法規(guī)則識(shí)別記號(hào)流中的評(píng)議結(jié)構(gòu)，也被稱(chēng)為語(yǔ)法分析。最有效的自上而下和自下而上的分析方法都只能處理上下文無(wú)關(guān)文法的子類(lèi)，如LL文法和LR方法，但是它們已足以應(yīng)付程序設(shè)計(jì)評(píng)議的絕大多數(shù)語(yǔ)法現(xiàn)象。
一、任務(wù)與目的
·上機(jī)任務(wù)：
1、使用C/C++程序設(shè)計(jì)語(yǔ)言和遞歸下降子程序的方法編寫(xiě)該函數(shù)繪圖語(yǔ)言的詞法分析器。并要求設(shè)計(jì)一個(gè)語(yǔ)法分析器的測(cè)試小程序來(lái)調(diào)用自己編寫(xiě)的語(yǔ)法分析器測(cè)試各種不同的輸入。
2、語(yǔ)法分析的任務(wù)是在詞法分析基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把詞法符號(hào)分解成各類(lèi)語(yǔ)法單位。語(yǔ)法分析所依據(jù)的是語(yǔ)言的語(yǔ)法規(guī)則，語(yǔ)法規(guī)則通常用上下文無(wú)關(guān)文法描述。
·上機(jī)目的：
通過(guò)自己動(dòng)手編寫(xiě)語(yǔ)法分析器，掌握正規(guī)式與正規(guī)文法、上下文無(wú)關(guān)文法（CFG）、有推導(dǎo)的基本概念（推導(dǎo)、分析樹(shù)與語(yǔ)法樹(shù)、二義性及二義性的消除）、自上而下分析（遞歸下降子程序方法、預(yù)測(cè)分析表方法、LL（1）文法）、自下而上分析。理解如何理論聯(lián)系實(shí)際以及明白理論與實(shí)際的差別。
二、分析與設(shè)計(jì)
語(yǔ)法分析程序一般具有如下功能: 對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析（根據(jù)語(yǔ)義規(guī)則進(jìn)行推導(dǎo)和規(guī)約），識(shí)別出程序中的各類(lèi)語(yǔ)法單位，最終判斷輸入串是否構(gòu)成語(yǔ)法上正確的“程序”。
這里我們采用遞歸下降分析方法：直接以程序的方式模擬產(chǎn)生式產(chǎn)生語(yǔ)言的過(guò)程。它的基本設(shè)計(jì)思想是：為每一個(gè)非終結(jié)符構(gòu)造一個(gè)子程序，每一個(gè)子程序的過(guò)程體中按該產(chǎn)生式的候選項(xiàng)分情況展開(kāi)，遇到終結(jié)符直接匹配，而遇到非終結(jié)符就調(diào)用相應(yīng)非終結(jié)符的子程序。該分析從調(diào)用文法開(kāi)始符號(hào)的子程序開(kāi)始，直到所有非終結(jié)符都展開(kāi)為終結(jié)符并得到匹配為止。若分析過(guò)程中達(dá)到這一步則表明分析成功，否則表明輸入中有語(yǔ)法錯(cuò)誤。遞歸下降分析對(duì)文法的限制是不能有公共左因子和左遞歸。由于文法是遞歸定義的，因此子程序也是遞歸的。
對(duì)于規(guī)模比較小的語(yǔ)言，遞歸下降子程序方法是很有效的方法，它簡(jiǎn)單靈活，容易構(gòu)造，其缺點(diǎn)是程序與文法直接相關(guān)，對(duì)文法的任何改變均需對(duì)程序進(jìn)行相應(yīng)的修改。
這里給出詞法分析程序大概的設(shè)計(jì)方法：
1、根據(jù)要求寫(xiě)出語(yǔ)法分析的上下文無(wú)關(guān)文法G；
2、消除上下文無(wú)關(guān)文法G的二義性；
3、消除上下文無(wú)關(guān)文法G的（直接）左遞歸，并提取左因子；
4、構(gòu)造文法的狀態(tài)轉(zhuǎn)換圖并且簡(jiǎn)化；
5、將轉(zhuǎn)換圖轉(zhuǎn)化為EBNF表示；
6、從EBNF構(gòu)造遞歸下降子程序；
以下是較為詳細(xì)的設(shè)計(jì)：
①總體結(jié)構(gòu)與模塊劃分
| 語(yǔ)法測(cè)試模塊(parsermain.cpp) | 語(yǔ)法分析器模塊(parser.h & parser.cpp) 繪圖語(yǔ)言解釋器入口 遞歸子程序集 先序遍歷并打印表達(dá)式的語(yǔ)法樹(shù) 出錯(cuò)處理模塊 | 詞法分析器模塊(scanner.h & scanner.cpp) 初使化詞法分析器 識(shí)別出具有獨(dú)立意義的最小語(yǔ)法單位 輔助性模塊 |
|
|
②重要數(shù)據(jù)結(jié)構(gòu)
·語(yǔ)法樹(shù)節(jié)點(diǎn)類(lèi)型
| struct ExprNode { // 語(yǔ)法樹(shù)節(jié)點(diǎn)類(lèi)型 enum Token_Type OpCode; union { struct { ExprNode *Left, *Right; } CaseOperator; struct { ExprNode *Child; FuncPtr MathFuncPtr; } CaseFunc; double CaseConst; double *CaseParmPtr; } Content; }; |
③關(guān)鍵思想與算法
·改寫(xiě)二義文法為非二義文法的方法：通過(guò)引入新的非終結(jié)符，使原來(lái)分辨不清的結(jié)構(gòu)受到約束，從而使得對(duì)任何一個(gè)句子，僅能構(gòu)造一棵分析樹(shù)。
·消除直接左遞歸算法
| 輸入：文法G中所有的A產(chǎn)生成 輸出：等價(jià)的不含直接左遞歸的文法G’ 方法：首先，整理A產(chǎn)生式為如下形式： AàAa1|Aa2|…|Aam|p1|p2|…|pn 其中，ai非空，pj均不以A開(kāi)始，然后用下述產(chǎn)生式代替A產(chǎn)生式： Aàp1A’| p2A’|…|pnA’ A’à a1A’| a2A’|…|amA’|e |
·消除左遞歸算法
| 輸入：無(wú)回路文法G 輸出：無(wú)左遞歸的等價(jià)文法G’ 方法：將非終結(jié)符合理排序：A1，A2，…，An，然后運(yùn)用下述過(guò)程： | for i in 2..n loop for j in 1..i-1 loop 用AjàQ1|Q2|…|Qk的右部替換每個(gè)形如AiàAj產(chǎn)生式中的Aj，得到新產(chǎn)生式： AiàQ1r|Q2r|…|Qkr； 消除Ai產(chǎn)生式中的直接左遞歸； end loop; end loop; |
|
·提取文法左因子算法：
| 輸入：文法G 輸出：等價(jià)的無(wú)左因子文法G’ 方法：為每個(gè)產(chǎn)生式A，找出其候選項(xiàng)中最長(zhǎng)公共前綴a，重排A產(chǎn)生式如下，其中r是不以a為前綴的其他候選項(xiàng)。 Aàap1|ap2|…|apn|r 并用下述產(chǎn)生式替代之。 AàaA’|r A’àp1|p2|…|pn 重復(fù)此過(guò)程，直到所有A產(chǎn)生式的候選項(xiàng)中均不再有公共前綴。 |
·構(gòu)造遞歸下降子程序的方法：
| ①構(gòu)造文法的狀態(tài)轉(zhuǎn)換圖并且簡(jiǎn)化； ②將轉(zhuǎn)換圖轉(zhuǎn)化為EBNF表示； ③從EBNF構(gòu)造遞歸下降子程序； |
三、測(cè)試?yán)淘O(shè)計(jì)
·測(cè)試程序（parsermain.cpp）
| #include <stdio.h> #include "parser.h" extern void Parser(char *SrcFilePtr); int main(){ Parser("test.txt"); return 0; } |
·測(cè)試數(shù)據(jù)（test.txt）
| // test data for t from -100 to 100 step 1 draw (t, 0); |
四、測(cè)試結(jié)果及分析
·測(cè)試環(huán)境
·軟件平臺(tái)：
OS 名稱(chēng) Microsoft Windows XP Professional
OS版本 5.1.2600 Service Pack 2 內(nèi)部版本號(hào) 2600
OS 制造商 Microsoft Corporation
開(kāi)發(fā)環(huán)境 Microsoft .NET Framework版本 3.5
Microsoft Visual Studio 2008版本 9.0.21022.8 RTM
Microsoft Visual C++ 2008版本91899-270-3541886-60490
·硬件平臺(tái):
系統(tǒng)類(lèi)型 基于 X86 的 PC
處理器#1 x86 Family 6 Model 15 Stepping 13 GenuineIntel ~1994 Mhz
處理器#2 x86 Family 6 Model 15 Stepping 13 GenuineIntel ~1994 Mhz
總的物理內(nèi)存 1,024.00 MB X 2, DDRII 667Mhz
BIOS 版本/日期 Phoenix Technologies LTD R1100Q0, 2007-10-18
·測(cè)試結(jié)果
·結(jié)果分析
這里需要說(shuō)明的一點(diǎn)是：因?yàn)檎Z(yǔ)法分析器只是是整個(gè)編譯器的一部分，所以在測(cè)試語(yǔ)法分析器時(shí)一定要加上如下的宏：
| //-------------------------parser.cpp----------------------------- #include "parser.h" #define PARSER_DEBUG …… |
五、總結(jié)與體會(huì)
語(yǔ)法分析是編譯器的重要階段之一，可以認(rèn)為是語(yǔ)法制導(dǎo)翻譯模式編譯器的核心。語(yǔ)法分析也有雙重含義：根據(jù)一定的規(guī)則構(gòu)成語(yǔ)言的各種結(jié)構(gòu)，即語(yǔ)法規(guī)則；根據(jù)語(yǔ)法規(guī)則識(shí)別輸入序列（記號(hào)流）中的語(yǔ)言結(jié)構(gòu)，即語(yǔ)法法分析。同詞法分析比較，語(yǔ)法分析的不是記號(hào)，而是組成語(yǔ)言的句子，從結(jié)構(gòu)上講不是線性的而是層次的，表征這種結(jié)構(gòu)的最好方法是樹(shù)，從而使得語(yǔ)法的分析就有了從根到葉子和從葉子到根兩種分析方法。由于語(yǔ)言結(jié)構(gòu)的復(fù)雜性，語(yǔ)法規(guī)則的描述也相應(yīng)困難。
在上機(jī)實(shí)踐中我們也發(fā)現(xiàn)：對(duì)于規(guī)模比較小的語(yǔ)言，遞歸下降子程序方法是很有效的方法，它簡(jiǎn)單靈活，容易構(gòu)造，其缺點(diǎn)是程序與文法直接相關(guān)，對(duì)文法的任何改變均需對(duì)程序進(jìn)行相應(yīng)的修改。
附:源代碼清單