一種基于BNF范式的LALR(1)語法分析器描述語言的設(shè)計*

李 洋，胥 亮

(1.西安職業(yè)技術(shù)學院，陜西 西安 710077；2.西安衛(wèi)星測控中心，陜西 西安 710032)

一種基于BNF范式的LALR(1)語法分析器描述語言的設(shè)計*

李 洋1，胥 亮2

(1.西安職業(yè)技術(shù)學院，陜西 西安 710077；2.西安衛(wèi)星測控中心，陜西 西安 710032)

常見的LALR(1)語法分析器自動生成系統(tǒng)所支持的程序設(shè)計語言語法復雜，用戶學習困難。以此為出發(fā)點，設(shè)計了一種基于BNF范式的LALR(1)語法分析器描述語言，分析了該語言需滿足的需求，并給出了該語言的文法。該語言文法功能完備，使用簡單，易于學習，為構(gòu)造LALR(1)語法分析器的自動化實現(xiàn)提供了一種思路。

編譯器；YACC；BNF；LALR(1)

編譯器是軟件開發(fā)的一種基礎(chǔ)支撐工具[1]，而語法分析是編譯器設(shè)計中的關(guān)鍵技術(shù)。語法分析方法根據(jù)產(chǎn)生語法樹的方向，可分為自底向上和自頂向下2大類[2]。LR分析法則是自底向上分析法中最重要的分析法之一。根據(jù)分析能力的差異，按從強到弱的順序來區(qū)分，LR分析器包括SLR(1)、LR(1)、LR(0)和LALR(1)分析器[3]。通過對它們的分析能力、分析表規(guī)模及有限狀態(tài)機的規(guī)模等因素進行比較分析發(fā)現(xiàn)，LALR(1)分析法最具有工程應用價值，但是LALR(1)分析法幾乎不能通過手工方式構(gòu)造LALR(1)語法分析器，其語法分析表也不簡單；因此，需要自動生成LALR(1)語法分析器的工具[4]。

目前，較為常見的LALR(1)語法分析器生成系統(tǒng)有YACC、LEMON、CUP和SableCC等，這些系統(tǒng)最主要的優(yōu)點是功能強大，使用這些系統(tǒng)生成的LALR(1)語法分析器具有較大規(guī)模；但是，它們也具有一些不足之處，主要是支持的程序設(shè)計語言語法一般比較復雜，這樣學習的難度會加大，比如LEMON和YACC僅聲明符就超過了20個，即使生成功能比較簡單的語法分析器，也需要投入很多的精力與時間。本文將要介紹的一種基于巴科斯范式(BNF)的LALR(1)語法分析器描述語言，其聲明符僅5個，語法簡潔，較之于YACC和LEMON等系統(tǒng)，語法規(guī)則也較為簡單，十分方便用戶學習。

1 設(shè)計目標

BNF是描述語法規(guī)則的一種形式化方法，是一種用形式化符號精確描述程序設(shè)計語言語法的形式系統(tǒng)。最好的選擇就是使用BNF范式描述目標語言，但是因為BNF范式復雜程度較高，只是簡單的點擊幾個按鈕等無法使用戶獲得目標語法分析器；因此，應當設(shè)計一種可以讓用戶用來描述目標語言的語法分析器的文法，即本文所研究的基于BNF范式的程序設(shè)計語言。

本文根據(jù)YACC和LEMON的文法設(shè)計的語法分析器描述語言，為了保障本文法功能的完備、簡單易學習，還需要具備下述條件。

1)支持使用BNF范式描述目標語法分析器。BNF范式應用的描述語法一般為產(chǎn)生式，產(chǎn)生式也就是表達式，它代表的是語法符號間的推導關(guān)系，終結(jié)符和非終結(jié)符構(gòu)成了語法符號。所以，該語法分析器描述語言的文法需要支持對終結(jié)符、非終結(jié)符和產(chǎn)生式的描述。

2)支持算符優(yōu)先分析法。產(chǎn)生式的數(shù)量與LALR(1)分析法、算符優(yōu)先分析法有著密切關(guān)系，將二者進行結(jié)合將對產(chǎn)生式數(shù)量的削減具有重要意義，還可以減少項目集的數(shù)量，使目標語法分析器簡單化，提高分析速度[5-6]；因此，本語言需要支持算符優(yōu)先分析法，這也就意味著文法主要支持聲明非終結(jié)符、終結(jié)符和產(chǎn)生式的優(yōu)先級別。

3)支持嵌入語義動作。在語法分析后，由于編譯器還需實現(xiàn)驗證語言的語義合法性和中間代碼生成等相應的語義動作，因此，還需要在目標語法分析器中嵌入語義動作[7]；所以，為能夠使用戶方便地將產(chǎn)生式對應的語法分析過程與語義動作進行結(jié)合，應在本語言中提供一種方式。

4)語法應簡潔。如果關(guān)鍵字太多會使文法更加復雜，用戶的學習難度也會相應的提升；因此，為能夠減少用戶使用負擔，應當減少不重要的關(guān)鍵字，使本文法語法更加簡潔。

2 基于BNF范式的LALR(1)語法分析器描述語言的語法

本語言的語法采用段式結(jié)構(gòu)，整篇源代碼需包含3個段：包含段、聲明段和規(guī)則段。每個段由段名和段內(nèi)容2部分組成，不同的段可以采用不同的段名進行標識，段名應單獨放置在某一行中的位置，段內(nèi)容是從段名后第1行開始，到下一個段名的前一行或整個文件結(jié)尾處的全部內(nèi)容，段內(nèi)容中包括目標語法分析器特征的描述內(nèi)容。上述3個段的段名依次為[include]、[declare]和[ruler]，3個段在源程序中的次序沒有要求，因為本研究中每個段的功能相對獨立，推薦使用包含段、聲明段和規(guī)則段的次序(基于BNF范式的語法分析器描述語言源程序示例如下所示)，這種段式結(jié)構(gòu)能使源代碼更清晰。

[include]

#include “include.h”

$[declare]段聲明

[declare]

%token_type{Token}

%level ADD SUB

%level TIMES DIV

%level LPARE RPARE

[ruler]

program->expr(A)

{

………

printf(“[ruler]產(chǎn)生式：program->expr(A)”)；

}

expr(A)->expr(B) SUB expr(C) $表達式的減法運算

{

2.1 包含段的語法

用戶將目標語法分析器需要包含的聲明語句與頭文件寫在包含段，在生成目標語法分析器的過程中，在其“.cpp”文件的開頭位置將其完整復制。

比如，用戶期望“IOStream”庫包含于在生成的目標語法分析器“syntaxer”的“.cpp”文件中，最終包含段的內(nèi)容會放在語法分析器“Syntaxer.cpp”文件的開頭位置，可寫作：

[include]

#include

using namespace std;

2.2 聲明段的語法

對目標語法分析器終結(jié)符和非終結(jié)符值的類型和優(yōu)先級進行聲明，即為聲明段起到的主要作用。

2.2.1 聲明終結(jié)符、非終結(jié)符和產(chǎn)生式的優(yōu)先級

聲明格式：%level 終結(jié)符|非終結(jié)符 [分隔符 終結(jié)符|非終結(jié)符…]

%level用來定義目標語法分析器非終結(jié)符、終結(jié)符及產(chǎn)生式的級別，它后面可以帶非終結(jié)符和終結(jié)符，并且非終結(jié)符和終結(jié)符由空格和制表符組成的字符串隔開，非終結(jié)符和終結(jié)符的數(shù)量并不限制，其優(yōu)先級規(guī)則為如下4項：1)如果聲明的終結(jié)符和非終結(jié)符在同一行，那么其優(yōu)先級是不存在差異的；2)后聲明的低于先聲明的行的終結(jié)符和非終結(jié)符的優(yōu)先級；3)如果聲明優(yōu)先級語句不存在，則代表非終結(jié)符、全部終結(jié)符及產(chǎn)生式的優(yōu)先級相同；4)其候選式中優(yōu)先級最高的非終結(jié)符或者是終結(jié)符的優(yōu)先級屬于產(chǎn)生式的優(yōu)先級。

例如，上述源程序中，目標語法分析器的終結(jié)符SUB和ADD低于終結(jié)符DIV和TIMES的優(yōu)先級，但是SUB和ADD具有相同的優(yōu)先級。

2.2.2 目標語法分析器的終結(jié)符和非終結(jié)符類型

聲明格式：%token_type {符號類型}

“%token_type”的主要功能是對目標語法分析器源程序中應用的C++數(shù)據(jù)類型進行說明，由用戶對其類型進行定義。本文要強調(diào)的是聲明語句中必須要有大括號，且在整個源程序中單詞類型聲明不得超過一次。

例如，上述源程序中，Token型是目標語法分析器的非終結(jié)符與終結(jié)符的值。

2.2.3 對語句的語法進行注釋

對于程序設(shè)計語言來說，注釋是語法成分必不可少的一部分，而合理的注釋對于增強代碼的可讀性也具有重要意義；所以，該語法分析器描述語言也應當可以注釋源程序。其語法如下。

聲明格式：$任意字符…

注釋語句內(nèi)容為從“$”起到所在行末之間的全部字符。

2.3 規(guī)則段的語法

在本段中，用戶可以應用BNF范式對目標語法分析器進行描述，規(guī)定規(guī)則段實現(xiàn)的主要功能，也就是說用戶可以自行任意設(shè)置目標語法分析器的語義動作和產(chǎn)生式，語法的具體表述如下。

聲明格式：非終結(jié)符[別名] -> 終結(jié)符|非終結(jié)符 [別名] [終結(jié)符|非終結(jié)符 [別名]…] {語義動作}

產(chǎn)生式的語法規(guī)則需要遵守BNF范式的語法，多個目標語法分析器的產(chǎn)生式共同組成規(guī)則段內(nèi)容，但與BNF范式之間的差異在于每個產(chǎn)生的最后都有1個語義動作，每個終結(jié)符和非終結(jié)符后都能跟1個別名。

為了方便用戶尋找文法的起始符號，目標語法分析器文法的起始符號需要是規(guī)則段第1個產(chǎn)生式左側(cè)的非終結(jié)符，使產(chǎn)生式之間的推導關(guān)系更清晰。

將由任意數(shù)量且不限大小寫的26個英文字母共同組成的字符串，用小括號括起來便是別名，它可以在對應的語義動作的C++程序中直接被引用，代表的是產(chǎn)生式中不同位置的終結(jié)符和非終結(jié)符。

在歸約時產(chǎn)生式會執(zhí)行1段C++程序，這就是語義動作，這段程序中可以處理及計算別名代表的終結(jié)符和非終結(jié)符的值，從而使語法分析和語義分析緊密結(jié)合起來，讓語義動作執(zhí)行模塊可以包含在生成的目標語法分析器中。

2.4 關(guān)鍵字和標識符

本語言的關(guān)鍵字和標識符見表1。

表1 基于BNF范式的語法分析器描述語言的關(guān)鍵字和標識符表

3 結(jié)語

本文分析了LALR(1)語法分析器難以實現(xiàn)的原因，并通過研究LALR(1)語法分析器自動構(gòu)造實現(xiàn)的需求，給出了一種基于BNF范式的LALR(1)語法分析器設(shè)計語言，為LALR(1)語法分析器的自動化實現(xiàn)提供了一種思路。

[1] 向建華.基于基準劃分的編譯器優(yōu)化自動測試框架[D].北京:北京交通大學,2007.

[2] 蔣立源,康幕寧. 編譯原理[M].2版.西安:西北工業(yè)大學出版社,2000.

[3] 虞森林. LEMON語法分析生成器(LALR(1)類型)源代碼情景分析[M].杭州:浙江大學出版社,2006.

[4] 肖增良,何锫.一種通用高效語法分析器的設(shè)計與實現(xiàn)[J].電腦知識技術(shù),2009(2):432-433

[5] 劉三獻. 基于ANTLR的Gaussian詞法分析器和語法分析器的分析與設(shè)計[D]. 蘭州：蘭州大學,2009.

*西安職業(yè)技術(shù)學院教學改革基金資助項目(XZY2014ZD02)

責任編輯鄭練

TheDesignofaProgrammingLanguageDescribingLALR(1)ParserbasedonBNFParadigm

LI Yang1, XU Liang2

(Xi′an Vocational and Technical College, Xi′an 710077, China；Xi′an Satellite Control Center, Xi′an 710032, China)

The syntax of programming language supported by the common LALR(1) parser generator system is too complex to learn. As a starting point, this paper designs a kind of language describing LALR(1) parser which is based on BNF paradigm. It analyses the demand which the language required to meet, and gives the language grammar. The language grammar is full-featured, simply used and easy to learn, provideing a way to construct the LALR(1) parser generator system.

syntax parser, YACC, BNF, LALR(1)

TP 312

：A

李洋(1984-)，女，講師，碩士，主要從事軟件工程等方面的研究。

2014-12-26