QParserGenerator的文法文件介绍

quasiceo 2013-10-10

展开全文

QParserGenerator的文法文件介绍

在沉默了数月之后，博主心血来潮想继续介绍QParserGenerator，在这里我们将不再继续介绍任何有关于LALR(1)的算法(那东西只会把你的脑子变成一团浆糊)，让我们来看一下QParserGenerator的具体用法。

说到ParserGenerator不得不提的是BNF，应此QParserGenerator也有它自己的BNF，这时有人会问BNF究竟是什么呢？简单的说BNF就是用来描述一种语法的东西，比如在Basic中If后面跟表达式然后是Then中间是语句块末尾必须要有End If等等的一系列描述，更专业的解释我们可以看一下维基百科上的解释。

好了，说完了BNF那让我们来看一下QParserGenerator的BNF到底是长啥样的

%token "%" "token" "start" "|" "-" ">" ";" "[" "]";

%start start;

strings             -> strings "{String}"
                    |  "{String}"
                    ;

vs                  -> vs "{Letter}"
                    |  vs "{String}"
                    |  "{Letter}"
                    |  "{String}"
                    ;

option              -> "[" vs "]"
                    ;

oneProductionRight  -> oneProductionRight option
                    |  oneProductionRight vs
                    |  option
                    |  vs
                    ;

someProductionRight -> someProductionRight "|" oneProductionRight
                    |  oneProductionRight
                    ;

token               -> "%" "token" strings ";"
                    ;

someTokens          -> someTokens token
                    |  token
                    ;

production          -> "{Letter}" "-" ">" someProductionRight ";"
                    ;

someProductions     -> someProductions production
                    |  production
                    ;

start               -> someTokens "%" "start" "{Letter}" ";" someProductions
                    |  "%" "start" "{Letter}" ";" someProductions
                    ;

也许有人会问，不对啊根据维基百科上的说明BNF不应该是长这样的，其实QParserGenerator是一个BNF的生成器，它可以将输入的BNF通过一系列的运算最后生成LALR(1)分析表，为了BNF文件的美观和方便处理我特地把他设计成了这个样子的而已，好了下面我们就以这个BNF文件来说明应该如何来书写BNF文件。

首先可以看到最顶上有一些以%token开头的字符串（在C语言中我们将用双引号括起来的字符序列称为字符串）以及最后的一个分号，其实这里的这些字符串正是BNF中说说的终结符，所以我们规定，所有其他没用%token声明的符号都是非终结符。终结符是用来做移进操作的，在某种特定的语言中他表现为一个token，而非终结符可以理解为一个代词，通常一个非终结符都可以展开为一条或多条规则（产生式）。至于说为什么每条内容后面都会有分号呢，只是为了处理上的方便（消除语法上的冲突？）。
好了，我们把终结符和非终结符这两个专业术语给解释完了，接下来可以看到的是一个以%start开头后跟一个非终结符的语句，他表明了所有规则（产生式）是从哪里开始的（有始无终的节奏-_-||杯具啊）。

最后就是我们的重头了，多空一行也不为过吧。这里有一大堆的产生式，那我们如何来阅读他呢，其实上面已经介绍了有个表明了所有规则开头的非终结符，好那让我们来找一下他所对应的产生式在哪里

start               -> someTokens "%" "start" "{Letter}" ";" someProductions
                    |  "%" "start" "{Letter}" ";" someProductions
                    ;

可以看到所有的规则可分为左半部分和右半部分，左边总是一个非终结符来说明他应该被哪一些规则来替代，而右边则是这些规则的具体内容包含了一些终结符和非终结符序列，中间则用一个箭头符号来分割。在所有的规则中非终结符都是不带引号的，而终结符都是用引号将其括起来的，在终结符中有一些内置的变量来表达一些特定的表达式，这个会在下文中做出说明。当然对于同一个终结符来说我们可以用任意多个规则来说明他，他们都是或的关系，由于BNF中不可能存在且的关系，应此我们并不需要考虑他。

下面让我们来看一下预定义的终结符有哪些，从Parser.cpp的代码中可知预定义的终结符有"{String}"、"{Digit}"、"{Real}"、"{Letter}"。
"{String}"：表示正则表达式\"[^\"]*\"
"{Digit}"：表示正则表达式[0-9]+
"{Real}"：表示正则表达式[0-9]*.[0-9]+
"{Letter}"：表示正则表达式((_[0-9]+)|([_a-zA-Z]+))[_0-9a-zA-Z]*
从这些正则表达式中可见"{String}"表示一个带双引号的字符串，"{Digit}"则表示一个数字，"{Real}"则表示一个浮点数，"{Letter}"则表示一个不带双引号的字符串。当然这些正则表达式写的并不完备，比如"{String}"中没有支持转义等等。

然后让我们来看一下每条规则支持哪些语法，首先从下面几条文法中可知，可用方括号将一些可选项括起来。

1 vs                  -> vs "{Letter}"
2                     |  vs "{String}"
3                     |  "{Letter}"
4                     |  "{String}"
5                     ;
6
7 option              -> "[" vs "]"
8                     ;

而对于一个规则来说他可以用若干条产生式来说明他，其中每条产生式之间是或的关系。

其他一些规则则说明了一些上文提到的规则，比如开头是一些token的定义等。终于把QParserGenerator的文法文件的结构给介绍完了，在接下来的一篇文章中我们将介绍如何用QParserGenerator来生成一个带括号优先级的四则混合运算计算器，其文法可见Calculator.txt，QLanguage整个项目的代码可见https://github.com/lwch/QLanguage/。