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