一种基于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