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