語法分析器概述
從詞法分析的角度看，語言是一個單詞的集合，稱之為正規(guī)集，單詞是由一個個字符組成的線性結(jié)構(gòu)；從語法分析的角度看，語言是一個句子的集合，而句子是由詞法分析器返回的記號組成的非線性結(jié)構(gòu)。反映句子結(jié)構(gòu)的最好方法是樹，常用的有分析樹和語法樹。分析語法結(jié)構(gòu)的基本方法有兩種：自上而下分析方法和自下而上分析方法。自上而下分析從根到葉子建立分析樹，而自下而上分析恰好相反。在這兩種情況下，分析器都是從左到右地掃描輸入，每次讀進一個記號。
與詞法分析類似，語法分析也具有雙重含義：
①規(guī)定句子形成的規(guī)則，也被稱為語法規(guī)則。程序設計語言的大部分語法規(guī)則可以用上下文無關(guān)文法（Context Free Grammar，簡稱CFG）來描述。
②根據(jù)語法規(guī)則識別記號流中的評議結(jié)構(gòu)，也被稱為語法分析。最有效的自上而下和自下而上的分析方法都只能處理上下文無關(guān)文法的子類，如LL文法和LR方法，但是它們已足以應付程序設計評議的絕大多數(shù)語法現(xiàn)象。
一、任務與目的
·上機任務：
1、使用C/C++程序設計語言和遞歸下降子程序的方法編寫該函數(shù)繪圖語言的詞法分析器。并要求設計一個語法分析器的測試小程序來調(diào)用自己編寫的語法分析器測試各種不同的輸入。
2、語法分析的任務是在詞法分析基礎上，根據(jù)語言的語法規(guī)則，把詞法符號分解成各類語法單位。語法分析所依據(jù)的是語言的語法規(guī)則，語法規(guī)則通常用上下文無關(guān)文法描述。
·上機目的：
通過自己動手編寫語法分析器，掌握正規(guī)式與正規(guī)文法、上下文無關(guān)文法（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)造，其缺點是程序與文法直接相關(guān)，對文法的任何改變均需對程序進行相應的修改。
這里給出詞法分析程序大概的設計方法：
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)造遞歸下降子程序；
以下是較為詳細的設計：
①總體結(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; }; |
③關(guān)鍵思想與算法
·改寫二義文法為非二義文法的方法：通過引入新的非終結(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)造，其缺點是程序與文法直接相關(guān)，對文法的任何改變均需對程序進行相應的修改。
附:源代碼清單