上回我们说到手写递归下降语法分析器。手写递归下降的方式是目前很多编译器采用的方式如果你想写一个商业质量的编译器这是首选的方法。但是一个完善的递归下降解析器需要的代码量也不少如果要进行错误报告、错误恢复等等那代码量就更大了。作为懒人我们有时想要一些小型语言的解析器最好写起来像直接写文法的产生式一样最好连错误报告和错误恢复也一并自动解决可能吗在过去很长一段时间人们采用的方法是使用解析器生成器parser generator。因为不管是LL递归下降解析还是LR的移进归约解析都可以很容易地用计算机来生成所需的规则。这样的著名工具有yacc、ANTLR等。他们的特点是要用一种专门的语法格式来编写文法产生式然后经过一个翻译程序生成解析器的代码。在函数式语言发展起来之后有些人发现函数式语言的抽象能力非常强甚至能够直接用函数式语言的代码来表达文法的产生式并将解析器“组合”出来这称作解析器组合子parser combinator。如今C#和VB语言也具有函数式语言相当的特征特别是还有Linq助阵以至于在C#和VB中也能享受组合子带来的方式。今天我们就来看看怎么做解析器的组合子。这一篇文字描述可能比较模糊大家一定要认真地看代码动手实验。解析器组合子的基本思想是“组合”首先我们要定义一些最基本的产生式作为基础组合子然后通过组合的方式拼装出最终的解析器来。回想一下正则表达式的定义它有两个基本表达式要素——空表达式和字符表达式以及三个基本运算——并、连接和克林闭包。用基本运算连接基本表达式就能组成任何正则表达式。解析器组合子也需要定义两个基本的产生式和两个基本运算。首先是产生空字符的产生式G → ε这个产生式不产生任何单词换句话说在解析的时候不解析任何单词就能成功解析出一个G。因此这个产生式的解析器永远都能解析成功。接下来是产生一个单词t的产生式G → t产生式产生一个特定单词t表示在解析的时候如果遇到单词t则成功解析出一个G而遇到其他单词则会解析失败。再来定义两个基本运算。首先是连接运算G → X Y产生式先产生X再产生Y表示在解析的时候先成功解析X再成功解析Y就能成功解析出一个G。接下来是并运算G → XG → Y这表示G既可以产生X也可以产生Y。在解析时无论成功解析X还是Y都能成功解析出一个G。以上四种基本产生式嵌套使用就能表示任何上下文无关文法。下面定义解析器函数的原型委托span stylecolor:#000000span stylecolor:#0000ffpublic delegate /spanspan stylecolor:#2b91afIResult/spanT span stylecolor:#2b91afParserFunc/spanspan stylecolor:#0000ffout /spanT(span stylecolor:#2b91afForkableScanner /spanscanner); span stylecolor:#0000ffpublic interface /spanspan stylecolor:#2b91afIResult/spanspan stylecolor:#0000ffout /spanT { T Value { span stylecolor:#0000ffget/span; } span stylecolor:#2b91afForkableScanner /spanReturnedScanner { span stylecolor:#0000ffget/span; } } span stylecolor:#0000ffpublic class /spanspan stylecolor:#2b91afResult/spanT : span stylecolor:#2b91afIResult/spanT { span stylecolor:#0000ffpublic /spanT Value { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afForkableScanner /spanReturnedScanner { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic /spanResult(T value, span stylecolor:#2b91afForkableScanner /spanreturnedScanner) { Value value; ReturnedScanner returnedScanner; } } /span这并不是VBF.Compilers.Parsers.Combinators库最后采用的Parser函数原型但它非常适合第一次接触解析器组合子的同学们理解。先看第一行委托的结构它接受一个ForkableScanner作为参数然后返回一个IResultT类型。首先什么是ForkableScanner呢我们在词法分析篇定义的Scanner类只能不断地向前Read而在函数式编程风格中我们需要一个无副作用的Scanner。简而言之任何一个个ForkableScanner可以随时“Fork”成两个ForkableScanner而这两个Scanner任何一个向前扫描都不会影响另外一个而且他们各自扫描都回得到同样的单词流。这都是为了处理上述“并”运算的解析器并运算需要两个分支能够互不影响地单独进行。接下来是返回类型IResultT定义成接口是为了能够加上.NET 4泛型协变的“out”关键字。实际类型ResultT包含一个解析结果T和成功解析之后返回的Scanner代表余下的输入流。如果返回的整个Result对象为null则表示解析失败。后面所有解析器组合子最终都是为了生成这样一个委托的对象一旦生成了这个对象就可以马上拿来解析了。有了解析器函数原型下面就开始一样一样地定义基础组合子。所谓组合子其实都是一些静态方法本例中这些静态方法都定义在Parsers静态类中、返回类型就是上面的解析器委托。由于返回类型也是委托所以这些组合子实际上都是一些高阶函数返回函数的函数。在我们的代码中常常是一个lambda表达式。较少使用lambda表达是的同学第一次看下面的代码可能会略微感到头晕只需要稍微休息一下再重新看即可……首先是空产生式G → ε它的组合子是span stylecolor:#000000span stylecolor:#0000ffpublic static /spanspan stylecolor:#2b91afParserFunc/spanT SucceedT(T result) { span stylecolor:#0000ffreturn /spanscanner span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afResult/spanT(result, scanner); } /span这个组合子接受一个参数表示其解析结果。正如前面所介绍由Succeed组合子生成的解析器永远都会成功解析而且会将设定的结果返回。第二种是接受一个单词的的产生式G → t我们将它的组合子定义成一个扩展方法span stylecolor:#000000span stylecolor:#0000ffpublic static /spanspan stylecolor:#2b91afParserFunc/spanspan stylecolor:#2b91afLexeme/span AsParser(span stylecolor:#0000ffthis /spanspan stylecolor:#2b91afToken /spantoken) { span stylecolor:#0000ffreturn /spanscanner { span stylecolor:#0000ffvar /spanlexeme scanner.Read(); span stylecolor:#0000ffif /span(lexeme.TokenIndex token.Index) { span stylecolor:#0000ffreturn new /spanspan stylecolor:#2b91afResult/spanspan stylecolor:#2b91afLexeme/span(lexeme, scanner); } span stylecolor:#0000ffelse /span{ span stylecolor:#0000ffreturn null/span; } }; } /span注意这个组合子生成的解析器是Lexeme词素类型的词素对象是我们在词法分析阶段定义的里面包含了词素的类型和具体字符串。这个组合子接受一个Token作为参数而返回的解析器从输入的Scanner中读取下一个词素如果该词素的单词类型与传入的Token相匹配就报告解析成功否则解析失败。第三种是两个文法的连接G → X Y。我们需要定义一个组合子接受两个已经存在的ParserFunc函数返回一个新的ParserFunc先后调用两个传入的ParserFuncspan stylecolor:#000000span stylecolor:#0000ffpublic static /spanspan stylecolor:#2b91afParserFunc/spanspan stylecolor:#2b91afTuple/spanT1, T2 ConcatT1, T2(span stylecolor:#0000ffthis /spanspan stylecolor:#2b91afParserFunc/spanT1 parser1, span stylecolor:#2b91afParserFunc/spanT2 parser2) { span stylecolor:#0000ffreturn /spanscanner { span stylecolor:#0000ffvar /spanresult1 parser1(scanner); span stylecolor:#0000ffif /span(result1 span stylecolor:#0000ffnull/span) span stylecolor:#0000ffreturn null/span; span stylecolor:#0000ffvar /spanresult2 parser2(result1.ReturnedScanner); span stylecolor:#0000ffif /span(result2 span stylecolor:#0000ffnull/span) span stylecolor:#0000ffreturn null/span; span stylecolor:#0000ffreturn new /spanspan stylecolor:#2b91afResult/spanspan stylecolor:#2b91afTuple/spanT1, T2(span stylecolor:#2b91afTuple/span.Create(result1.Value, result2.Value), result2.ReturnedScanner); }; } /span注意我们返回的ParserFunc结果类型是TupleT1, T2因为结果中需要同时包含T1和T2。用这种方式定义的连接运算组合子在实践中非常难用。因为我们的文法常常要包含不止两个符号连接的情形。假如我们的产生式是G → X Y Z那么必须写成 X.Concat(Y.Concat(Z))而它的返回类型是TupleT1, TupleT2, T3如果要取得结果中的Z只能写r.Item2.Item2。实际上miniSharp这样的语言文法中出现7-8个符号连接也不是什么稀奇的事情而如果都用这个组合子的话Tuple嵌套会复杂到把人的眼睛都搞晕掉。所以这时我们想到了——Linq。Linq的“组合子”中有一种叫SelectMany他给我们带来了这种语法糖span stylecolor:#000000span stylecolor:#2b91afList/spanspan stylecolor:#0000ffint/span la span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afList/spanspan stylecolor:#0000ffint/span() { 1, 2, 3 }; span stylecolor:#2b91afList/spanspan stylecolor:#0000ffstring/span lb span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afList/spanspan stylecolor:#0000ffstring/span() { span stylecolor:#a31515a/span, span stylecolor:#a31515b/span, span stylecolor:#a31515c /span}; span stylecolor:#0000ffvar /spanr span stylecolor:#0000fffrom /spana span stylecolor:#0000ffin /spanla span stylecolor:#0000fffrom /spanb span stylecolor:#0000ffin /spanlb span stylecolor:#0000ffselect /spana b; /span它实际可以翻译成span stylecolor:#000000span stylecolor:#0000ffvar /spanr la.SelectMany(a lb.SelectMany(b a b)); /span也就是说连续from语句其实是SelectMany扩展方法的嵌套调用。这种调用方法有把lambda嵌套“打平”的功能非常类似于单子风格中的Bind运算。实际上C#和VB允许在任何自定义类型上扩展SelectMany方法然后就允许用Linq语法的from去调用。有些人非常鄙视语法糖但这个语法糖却是无法替代的这是C#版解析器组合子关键中的关键由此就可以将连接运算定义成一个SelectMany组合子span stylecolor:#000000span stylecolor:#0000ffpublic static /spanspan stylecolor:#2b91afParserFunc/spanTResult SelectManyT1, T2, TResult(span stylecolor:#0000ffthis /spanspan stylecolor:#2b91afParserFunc/spanT1 parser, span stylecolor:#2b91afFunc/spanT1, span stylecolor:#2b91afParserFunc/spanT2 parserSelector, span stylecolor:#2b91afFunc/spanT1, T2, TResult resultSelector) { span stylecolor:#0000ffreturn /spanscanner { span stylecolor:#0000ffvar /spanresult1 parser(scanner); span stylecolor:#0000ffif /span(result1 span stylecolor:#0000ffnull/span) span stylecolor:#0000ffreturn null/span; span stylecolor:#0000ffvar /spanparser2 parserSelector(result1.Value); span stylecolor:#0000ffvar /spanresult2 parser2(result1.ReturnedScanner); span stylecolor:#0000ffif /span(result2 span stylecolor:#0000ffnull/span) span stylecolor:#0000ffreturn null/span; span stylecolor:#0000ffreturn new /spanspan stylecolor:#2b91afResult/spanTResult(resultSelector(result1.Value, result2.Value), result2.ReturnedScanner); }; } /span这个神奇的SelectMany组合子不但消除了嵌套Tuple带来的混乱还允许我们用一个自定义的select语句生成连接运算的结果这在生成语法树的时候尤为方便。我们一会再看例子先继续看最后一种基本组合子。最后一种基本组合子是并运算。并运算要求产生式产生两种可能的分支。对应到解析器组合子上连接运算也要接受两个现成的解析器作为参数但是选择哪一个呢这里我们没有办法做分支预测所以只好采取尝试的办法。有一种尝试的方法就是先试用第一个解析器如果失败了再试用第二个这是一种类似深度优先搜索的办法span stylecolor:#000000span stylecolor:#0000ffpublic static /spanspan stylecolor:#2b91afParserFunc/spanT UnionT(span stylecolor:#0000ffthis /spanspan stylecolor:#2b91afParserFunc/spanT parser1, span stylecolor:#2b91afParserFunc/spanT parser2) { span stylecolor:#0000ffreturn /spanscanner { span stylecolor:#0000ffvar /spanscanner1 scanner; span stylecolor:#0000ffvar /spanscanner2 scanner.Fork(); span stylecolor:#0000ffvar /spanresult1 parser1(scanner1); span stylecolor:#0000ffif /span(result1 ! span stylecolor:#0000ffnull/span) { span stylecolor:#0000ffreturn /spanresult1; } span stylecolor:#0000ffvar /spanresult2 parser2(scanner2); span stylecolor:#0000ffreturn /spanresult2; }; } /span仅仅使用以上四个组合子函数就可以来写Parser了是否还半信半疑呢我们就来写上一次写过的二叉树字符串表示的语法分析器。忘记的同学建议打开上一篇看看。我们把文法再抄一遍N → a ( N, N )N → ε这里面涉及的单词包括字母、左右括号和逗号我们都用词法分析篇的方法将他们定义出来。然后再用解析器组合子组合出上述文法的解析器。完整的代码如下span stylecolor:#000000span stylecolor:#2b91afLexicon /spanbinaryTreeSyntax span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afLexicon/span(); span stylecolor:#2b91afLexerState /spanlex binaryTreeSyntax.DefaultLexer; span stylecolor:#008000//定义词法 /spanspan stylecolor:#2b91afToken /spanLEFTPH lex.DefineToken(span stylecolor:#2b91afRE/span.Symbol(span stylecolor:#a31515(/span)); span stylecolor:#2b91afToken /spanRIGHTPH lex.DefineToken(span stylecolor:#2b91afRE/span.Symbol(span stylecolor:#a31515)/span)); span stylecolor:#2b91afToken /spanCOMMA lex.DefineToken(span stylecolor:#2b91afRE/span.Symbol(span stylecolor:#a31515,/span)); span stylecolor:#2b91afToken /spanLETTER lex.DefineToken(span stylecolor:#2b91afRE/span.Range(span stylecolor:#a31515a/span,span stylecolor:#a31515z/span) | span stylecolor:#2b91afRE/span.Range(span stylecolor:#a31515A/span,span stylecolor:#a31515Z/span)); span stylecolor:#008000//定义语法 /spanspan stylecolor:#2b91afParserFunc/spanspan stylecolor:#2b91afNode/span NodeParser span stylecolor:#0000ffnull/span; NodeParser (span stylecolor:#0000fffrom /spana span stylecolor:#0000ffin /spanLETTER.AsParser() span stylecolor:#0000fffrom /span_1 span stylecolor:#0000ffin /spanLEFTPH.AsParser() span stylecolor:#0000fffrom /spanleft span stylecolor:#0000ffin /spanNodeParser span stylecolor:#0000fffrom /span_2 span stylecolor:#0000ffin /spanCOMMA.AsParser() span stylecolor:#0000fffrom /spanright span stylecolor:#0000ffin /spanNodeParser span stylecolor:#0000fffrom /span_3 span stylecolor:#0000ffin /spanRIGHTPH.AsParser() span stylecolor:#0000ffselect new /spanspan stylecolor:#2b91afNode/span(a.Value[0], left, right)) .Union(span stylecolor:#2b91afParsers/span.Succeedspan stylecolor:#2b91afNode/span(span stylecolor:#0000ffnull/span)); span stylecolor:#008000//运行部分 /spanspan stylecolor:#2b91afForkableScannerBuilder /spanbuilder span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afForkableScannerBuilder/span(binaryTreeSyntax.CreateScannerInfo()); span stylecolor:#0000ffstring /spansource span stylecolor:#a31515A(B(,),C(,))/span; span stylecolor:#2b91afSourceReader /spansr span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afSourceReader/span( span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afStringReader/span(source)); span stylecolor:#2b91afForkableScanner /spanscanner builder.Create(sr); span stylecolor:#0000ffvar /spantree NodeParser(scanner); /span重点来看“定义语法”部分我们来看看产生式都是如何转变为组合子调用的。首先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风格解析器组合子了。敬请期待