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