随笔-91  评论-137  文章-0  trackbacks-0
在沉默了数月之后,博主心血来潮想继续介绍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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理