解析器组合子的基本思想是“组合”,首先我们要定义一些最基本的产生式作为基础组合子,然后通过组合的方式拼装出最终的解析器来。回想一下正则表达式的定义,它有两个基本表达式要素——空表达式和字符表达式,以及三个基本运算——并、连接和克林闭包。用基本运算连接基本表达式,就能组成任何正则表达式。解析器组合子也需要定义两个基本的产生式和两个基本运算。
首先是产生空字符的产生式:
G → ε
这个产生式不产生任何单词,换句话说在解析的时候,不解析任何单词就能成功解析出一个G。因此这个产生式的解析器永远都能解析成功。
接下来是产生一个单词t的产生式:
G → t
产生式产生一个特定单词t,表示在解析的时候,如果遇到单词t,则成功解析出一个G,而遇到其他单词则会解析失败。
再来定义两个基本运算。首先是连接运算:
G → X Y
产生式先产生X再产生Y,表示在解析的时候先成功解析X,再成功解析Y,就能成功解析出一个G。
接下来是并运算:
G → X G → Y
这表示,G既可以产生X也可以产生Y。在解析时无论成功解析X还是Y,都能成功解析出一个G。以上四种基本产生式嵌套使用,就能表示任何上下文无关文法。
下面定义解析器函数的原型委托:
public delegate IResult
这并不是VBF.Compilers.Parsers.Combinators库最后采用的Parser函数原型,但它非常适合第一次接触解析器组合子的同学们理解。先看第一行委托的结构,它接受一个ForkableScanner作为参数,然后返回一个IResult
有了解析器函数原型,下面就开始一样一样地定义基础组合子。所谓组合子其实都是一些静态方法(本例中这些静态方法都定义在Parsers静态类中)、返回类型就是上面的解析器委托。由于返回类型也是委托,所以这些组合子实际上都是一些高阶函数(返回函数的函数)。在我们的代码中常常是一个lambda表达式。较少使用lambda表达是的同学第一次看下面的代码可能会略微感到头晕,只需要稍微休息一下再重新看即可……
首先是空产生式G → ε,它的组合子是:
public static ParserFunc
这个组合子接受一个参数,表示其解析结果。正如前面所介绍,由Succeed组合子生成的解析器,永远都会成功解析,而且会将设定的结果返回。
第二种是接受一个单词的的产生式G → t,我们将它的组合子定义成一个扩展方法:
public static ParserFunc
注意这个组合子生成的解析器是Lexeme(词素)类型的,词素对象是我们在词法分析阶段定义的,里面包含了词素的类型和具体字符串。这个组合子接受一个Token作为参数,而返回的解析器从输入的Scanner中读取下一个词素,如果该词素的单词类型与传入的Token相匹配,就报告解析成功,否则解析失败。
第三种是两个文法的连接G → X Y。我们需要定义一个组合子,接受两个已经存在的ParserFunc函数,返回一个新的ParserFunc,先后调用两个传入的ParserFunc:
public static ParserFunc
注意我们返回的ParserFunc结果类型是Tuple
用这种方式定义的连接运算组合子,在实践中非常难用。因为我们的文法常常要包含不止两个符号连接的情形。假如我们的产生式是G → X Y Z,那么必须写成 X.Concat(Y.Concat(Z)),而它的返回类型是Tuple
List
它实际可以翻译成:
var r = la.SelectMany(a => lb.SelectMany(b => a + b));
也就是说,连续from语句,其实是SelectMany扩展方法的嵌套调用。这种调用方法有把lambda嵌套“打平”的功能,非常类似于单子风格中的Bind运算。实际上C#和VB允许在任何自定义类型上扩展SelectMany方法,然后就允许用Linq语法的from去调用。有些人非常鄙视语法糖,但这个语法糖却是无法替代的,这是C#版解析器组合子关键中的关键!由此就可以将连接运算定义成一个SelectMany组合子:
public static ParserFunc SelectMany
这个神奇的SelectMany组合子不但消除了嵌套Tuple带来的混乱,还允许我们用一个自定义的select语句生成连接运算的结果,这在生成语法树的时候尤为方便。我们一会再看例子,先继续看最后一种基本组合子。
最后一种基本组合子是并运算。并运算要求产生式产生两种可能的分支。对应到解析器组合子上,连接运算也要接受两个现成的解析器作为参数,但是选择哪一个呢?这里我们没有办法做分支预测,所以只好采取尝试的办法。有一种尝试的方法就是先试用第一个解析器,如果失败了,再试用第二个,这是一种类似深度优先搜索的办法:
public static ParserFunc
其中scanner的Join方法可以使传入的scanner对象与Fork形成的一条分支合并,相当于选定了两个分支中的一条分支。(这个用法在今后的VBF中可能会改变,因为性能较低,我正在重构它)。
仅仅使用以上四个组合子函数,就可以来写Parser了!是否还半信半疑呢?我们就来写上一次写过的二叉树字符串表示的语法分析器。忘记的同学建议打开上一篇看看。我们把文法再抄一遍:
N → a ( N, N ) N → ε
这里面涉及的单词包括字母、左右括号和逗号,我们都用词法分析篇的方法将他们定义出来。然后再用解析器组合子组合出上述文法的解析器。完整的代码如下:
Lexicon binaryTreeSyntax = new Lexicon(); LexerState lex = binaryTreeSyntax.DefaultLexer; //定义词法 Token LEFTPH = lex.DefineToken(RE.Symbol('(')); Token RIGHTPH = lex.DefineToken(RE.Symbol(')')); Token COMMA = lex.DefineToken(RE.Symbol(',')); Token LETTER = lex.DefineToken(RE.Range('a','z') | RE.Range('A','Z')); //定义语法 ParserFunc
重点来看“定义语法”部分,我们来看看产生式都是如何转变为组合子调用的。首先,N → ε转化为了一句Parsers.Succeed调用,代表总能解析成功,而且不消耗输入单词的解析器。然后是N → a ( N, N ),连续的连接转化为一连串Linq的from子句。而其中出现了终结符的地方,则通过AsParser扩展方法将Token转化为Parser。最后再用一个Union组合子将两个N产生式组合到一起,中间我们还看到了用select子句方便地构造想要的解析结果能力。再一次,赞叹SelectMany的神奇力量!初看起来,Linq用来写文法感觉怪怪的,但是习惯了之后,可以非常快速地将各种产生式以Linq语句的方式表达出来。
解析器组合子最大的优点就是无论实现还是使用都非常简洁,高度体现了函数式编程的优势。但它最大的缺点是难以调试。倘若大家用解析器组合子组合出来的解析器有错误,无法获得想要的解析结果,那可就麻烦了。大家可以试试用Visual Studio的调试器跟踪一下解析器组合子,会发现它的跳转非常频繁,而且根本看不出当前在干什么(因为运行时已经生成了Lambda函数,无法获得组合子传入的参数),也无法看出下一步会运行什么。所以,采用解析器组合子唯一确保正确的做法,就是编写足够的测试用例。
还有一个重要的问题要解决——语法错误。大家可以试一试输入一个不符合语法的字符串,比如去掉一个括号,看看会是什么结果?答案是直接返回null——和一开始的设定一样。无法知道错误出在了哪里。作为编程语言的解析器,不仅应该能报告错误出现的位置,而且还应该能自动进行某种错误恢复,这样就可以继续完成解析,从而获得所有的语法错误,而不仅仅是头一个。这个功能非常重要,但我们今天设计的解析器组合子结构却非常不擅长进行错误报告和恢复。比如说Union组合子,干脆就是通过解析错误来判断要不要采用这个分支,如果每个分支都错了,它又如何决定报告哪条分支的错误呢?可以设定一些规则,但是我们想要更好、更智能的错误报告和恢复功能。这就留到下一篇,正式介绍VBF库中采用的CPS风格解析器组合子了。敬请期待!
希望大家继续关注我的VBF项目:http://github.com/Ninputer/VBF 和我的微博:http://weibo.com/ninputer 多谢大家支持!
最新评论