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

李 洋，胥 亮

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

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

李 洋1，胥 亮2

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

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

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

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

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

1 設計目標

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

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

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

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

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

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

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

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

[include]

#include “include.h”

$[declare]段聲明

[declare]

%token_type{Token}

%level ADD SUB

%level TIMES DIV

%level LPARE RPARE

[ruler]

program->expr(A)

{

………

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

}

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

{

2.1 包含段的語法

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

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

[include]

#include

using namespace std;

2.2 聲明段的語法

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

2.2.1 聲明終結符、非終結符和產生式的優先級

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

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

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

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

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

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

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

2.2.3 對語句的語法進行注釋

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

聲明格式：$任意字符…

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

2.3 規則段的語法

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

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

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

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

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

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

2.4 關鍵字和標識符

本語言的關鍵字和標識符見表1。

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

3 結語

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

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

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

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

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

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

*西安職業技術學院教學改革基金資助項目(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