下面文章從C++詞法分析的角度出發(fā)，其實語言是一個句子的集合，而句子是由詞法分析器返回的記號組成的非線性結(jié)構(gòu)，C++語法分析的任務(wù)是在詞法分析基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把詞法符號分解成各類語法單位。

反映句子結(jié)構(gòu)的***方法是樹，常用的有分析樹和語法樹。分析語法結(jié)構(gòu)的基本方法有兩種：自上而下分析方法和自下而上分析方法。自上而下分析從根到葉子建立分析樹，而自下而上分析恰好相反。在這兩種情況下，分析器都是從左到右地掃描輸入，每次讀進(jìn)一個記號。與C++詞法分析類似，語法分析也具有雙重含義：

①規(guī)定句子形成的規(guī)則，也被稱為語法規(guī)則。程序設(shè)計語言的大部分語法規(guī)則可以用上下文無關(guān)文法（ContextFreeGrammar，簡稱CFG）來描述。

②根據(jù)語法規(guī)則識別記號流中的評議結(jié)構(gòu)，也被稱為語法分析。最有效的自上而下和自下而上的分析方法都只能處理上下文無關(guān)文法的子類，如LL文法和LR方法，但是它們已足以應(yīng)付程序設(shè)計評議的絕大多數(shù)語法現(xiàn)象。

一、任務(wù)與目的

1、使用C/C++程序設(shè)計語言和遞歸下降子程序的方法編寫該函數(shù)繪圖語言的C++詞法分析器。并要求設(shè)計一個語法分析器的測試小程序來調(diào)用自己編寫的語法分析器測試各種不同的輸入。

2、語法分析的任務(wù)是在C++詞法分析基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把詞法符號分解成各類語法單位。語法分析所依據(jù)的是語言的語法規(guī)則，語法規(guī)則通常用上下文無關(guān)文法描述。#t#

通過自己動手編寫語法分析器，掌握正規(guī)式與正規(guī)文法、上下文無關(guān)文法（CFG）、有推導(dǎo)的基本概念（推導(dǎo)、分析樹與語法樹、二義性及二義性的消除）、自上而下分析（遞歸下降子程序方法、預(yù)測分析表方法、LL（1）文法）、自下而上分析。理解如何理論聯(lián)系實際以及明白理論與實際的差別。

二、分析與設(shè)計

語法分析程序一般具有如下功能:對單詞符號串進(jìn)行語法分析（根據(jù)語義規(guī)則進(jìn)行推導(dǎo)和規(guī)約），識別出程序中的各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的“程序”。

這里我們采用遞歸下降分析方法：直接以程序的方式模擬產(chǎn)生式產(chǎn)生語言的過程。它的基本設(shè)計思想是：為每一個非終結(jié)符構(gòu)造一個子程序，每一個子程序的過程體中按該產(chǎn)生式的候選項分情況展開，遇到終結(jié)符直接匹配，而遇到非終結(jié)符就調(diào)用相應(yīng)非終結(jié)符的子程序。

該分析從調(diào)用文法開始符號的子程序開始，直到所有非終結(jié)符都展開為終結(jié)符并得到匹配為止。若分析過程中達(dá)到這一步則表明分析成功，否則表明輸入中有語法錯誤。遞歸下降分析對文法的限制是不能有公共左因子和左遞歸。由于文法是遞歸定義的，因此子程序也是遞歸的。

對于規(guī)模比較小的語言，遞歸下降子程序方法是很有效的方法，它簡單靈活，容易構(gòu)造，其缺點是程序與文法直接相關(guān)，對文法的任何改變均需對程序進(jìn)行相應(yīng)的修改。

這里給出C++詞法分析程序大概的設(shè)計方法：

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è)計：

總體結(jié)構(gòu)與模塊劃分