在沉默了数月之后,博主心血来潮想继续介绍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 ;
而对于一个规则来说他可以用若干条产生式来说明他,其中每条产生式之间是
或的关系。
1 oneProductionRight -> oneProductionRight option
2 | oneProductionRight vs
3 | option
4 | vs
5 ;
6
7 someProductionRight -> someProductionRight "|" oneProductionRight
8 | oneProductionRight
9 ;
其他一些规则则说明了一些上文提到的规则,比如开头是一些token的定义等。终于把QParserGenerator的文法文件的结构给介绍完了,在接下来的一篇文章中我们将介绍如何用QParserGenerator来生成一个带括号优先级的四则混合运算计算器,其文法可见
Calculator.txt,QLanguage整个项目的代码可见
https://github.com/lwch/QLanguage/。
posted on 2013-10-09 11:17
lwch 阅读(1413)
评论(0) 编辑 收藏 引用 所属分类:
QLanguage