回我们用函数式编程的方法结合Linq语法建立了一套解析器组合子方案并能成功解析自定义文法的输入字符串。但是上次做成的解析器组合子有个重要的功能没有完成——错误报告。作为编程语言的语法分析器不能在遇到语法错误的时候简单地返回null那样程序员就很难修复代码中的语法错误。我们需要的是准确报告语法错误的位置更进一步是程序中所有的语法错误而不仅仅是头一个。后者要求解析器具有错误恢复的能力即在遇到语法错误之后还能恢复到正常状态继续解析。错误恢复不仅仅可以用在检测出所有的语法错误还可以在存在语法错误的时候仍然提供有意义的解析结果从而用于IDE的智能感知和重构等功能。手写的递归下降语法分析器可以很容易地加入错误恢复但需要针对每一处错误手工编写代码来恢复。像C#官方编译器给出的语法错误信息非常全面、精确、智能全都是手工编写的功劳。又回到我们是懒人这个残酷的事实能不能在让解析器组合子生成的解析器自动具有错误恢复能力呢首先来看上一个版本的四个基本组合子空产生式的Succeed组合子token产生式的AsParser组合子连接运算产生式的SelectMany组合子和并运算产生式的Union组合子。首先Succeed是不会解析失败的所以它没有必要进行错误恢复。现在来看AsParser组合子它的逻辑是读取下一个词素如果词素的单词类型和组合子的参数匹配则解析成功否则解析失败。代码如下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如果要对失败的情形进行错误恢复有两种可行的选择1、假装要解析的Token存在继续解析这种做法相当于在原位置插入了一个单词2、跳过不匹配的单词重新进行解析这种做法相当于删除了一个单词。如果漏写一个分号或者括号插入型错误恢复就能有效地恢复错误如果是多写了一个关键字或标识符造成的错误删除型错误恢复就能有效地恢复。但问题是我们怎么能在组合子的代码中判断出哪种错误恢复更有效呢最优策略是让两种错误恢复的状态都继续解析到末尾然后看哪种恢复状态整体语法错误最少。但是只要有一个字符解析失败就要分支成两个完整解析那么错误一旦多起来这个分支的庞大程度将使得错误恢复无法进行。更何况错误并不仅仅出现在真正的语法错误上我们还要用错误来判断“并”运算组合子的分支问题。请看上一版本Union组合子的代码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在Union中我们先试验第一个parser1能否解析成功如果失败才解析parser2。如果解析器有自动错误恢复的功能那么我们就无法用这种方式判断了因为两条分支遇到错误之后都会继续进行下去。我们可以让两条分支都解析到底然后挑错误较少的分支作为正式解析结果。但同上所述这种做法的分支多得难以置信效率上决定我们不能采用。为了避免效率问题我们需要一种“广度优先”的处理方案。在遇到错误时产生的“插入”和“删除”两条分支要同时进行但要一步一步地进行。这里所谓的一“步”就是指AsParser组合子读取一个词素。我们看到四种基本组合子中只有AsParser组合子会用scanner来真正读取词素其他组合子最终也是要调用到AsParser组合子来进行解析的。我们让两个可能的分支都向前解析一步然后看是否其中一条分支的结果比另外一条更好。所谓更好就是一条分支没有进一步遇到错误而另外一条分支遇到了错误。如果两条分支都没有遇到错误或者都遇到了错误我们就再向前推进一步直到某一步比另外一步更好为止。Union组合子也可以采用同样的策略处理。这是一种贪心算法的策略我们所得到的结果未必是语法错误最少的解析结果但它的效率是可以接受的。那么怎么进行“广度优先”推进呢我们上次引入的组合子当前的组合子无法知道下一个要运行的组合子是什么更无法控制下一个组合子只向前解析一步。为了达到目的我们要引入一种新的组合子函数原型称作CPSContinuation Pass-in Style风格的组合子。不知道大家有多少人听说过CPS这在函数式编程界是一种广为应用的模式在.NET世界里其实也有采用。.NET 4.0引入的Task Parallel Library库中的Task类就是一个典型的CPS设计范例。我举一个简单的例子来介绍一下CPS。如果有两个函数A和B需要按顺序调用用传统方式编程很简单就是直接调用span stylecolor:#000000span stylecolor:#0000ffvoid /spanA() { span stylecolor:#2b91afConsole/span.WriteLine(span stylecolor:#a31515A/span); } span stylecolor:#0000ffvoid /spanB() { span stylecolor:#2b91afConsole/span.WriteLine(span stylecolor:#a31515B/span); } span stylecolor:#0000ffvoid /spanRun() { A(); B(); }/span而如果采用CPS则是把B传递给A这时我们称B是A的continuation或者future。span stylecolor:#000000span stylecolor:#0000ffvoid /spanA(span stylecolor:#2b91afAction /spanfuture) { span stylecolor:#2b91afConsole/span.WriteLine(span stylecolor:#a31515A/span); future(); } span stylecolor:#0000ffvoid /spanB() { span stylecolor:#2b91afConsole/span.WriteLine(span stylecolor:#a31515B/span); } span stylecolor:#0000ffvoid /spanRun() { A(B); } /span乍一看这也不能实现什么特别的事情但其实是很有用的。A获得了自己的future之后可以自行决定如何运行它。比如可以异步地运行。这样我们就在Run()方法中用一种容易理解的方式构建出了一条异步调用序列。.NET 4.0的Task Parallel Library正是这样的风格每个Task类通过ContinueWith方法接受自己的future。而我们的函数式解析其组合子也可以用这种方式让每个Parser函数接受一个future并自行决定如何调用future。这里最关键的思想是实现延迟调用future从而实现“广度优先”的单步解析效果。首先来看看新的Parser类原型警告这一篇里采用的函数式技巧比上一篇还要难懂得多如果看了之后发生头晕嗜睡等症状请休息之后重新看……span stylecolor:#000000span stylecolor:#0000ffpublic delegate /spanspan stylecolor:#2b91afResult/spanT span stylecolor:#2b91afParserFunc/spanT(span stylecolor:#2b91afForkableScanner /spanscanner, span stylecolor:#2b91afParserContext /spancontext); span stylecolor:#0000ffpublic delegate /spanspan stylecolor:#2b91afParserFunc/spanTFuture span stylecolor:#2b91afFuture/spanT, TFuture(T value); span stylecolor:#0000ffpublic abstract class /spanspan stylecolor:#2b91afParser/spanT { span stylecolor:#0000ffpublic abstract /spanspan stylecolor:#2b91afParserFunc/spanTFuture BuildParserTFuture(span stylecolor:#2b91afFuture/spanT, TFuture future); } /spanParserFunc方法和上一篇非常类似但是多了一个ParserContext方法。我们会用这个对象来保存一些错误报告的信息。再来是Future函数的定义Future返回的类型是一个ParserFunc委托对象Future的参数T则是用来让每一个组合子生成的Parser将自己的解析结果T传给它自己的Future用的。注意这次多了一个ParserT抽象类它代替ParserFunc成为组合子的生成对象。它之所以不能声明成一个委托是因为它的BuildParser方法要接受一个额外的泛型类型参数TFuture。接下来每一个解析器组合子都需要继承自ParserT并实现它的BuildParser方法。下面我们就来看一看新的CPS型解析器组合子怎么定义。首先还是G → ε的组合子它永远都能解析成功所以它的逻辑是生成一个ParserFunc将预设的解析结果传递给自己的Future:span stylecolor:#000000span stylecolor:#0000ffpublic class /spanspan stylecolor:#2b91afSucceedParser/spanT : span stylecolor:#2b91afParser/spanT { span stylecolor:#0000ffpublic /spanT Value { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic /spanSucceedParser(T value) { Value value; } span stylecolor:#0000ffpublic override /spanspan stylecolor:#2b91afParserFunc/spanTFuture BuildParserTFuture(span stylecolor:#2b91afFuture/spanT, TFuture future) { span stylecolor:#0000ffreturn /span(scanner, context) future(Value)(scanner, context); } } /span这是第一次实践CPS风格大家一定要注意观察它与上一次传统风格解析器组合子的不同。最关键的一点就是返回的ParserFunc必须要调用BuildParser传进来的future函数传递自己的解析结果。接下来就是重头戏G → t我们要在这个单词解析器组合子中加入期待已久的错误报告和错误恢复功能请看代码span stylecolor:#000000span stylecolor:#0000ffpublic class /spanspan stylecolor:#2b91afTokenParser /span: span stylecolor:#2b91afParser/spanspan stylecolor:#2b91afLexeme/span { span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afToken /spanExpectedToken { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic string /spanMissingCorrection { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic /spanTokenParser(span stylecolor:#2b91afToken /spanexpected) { ExpectedToken expected; MissingCorrection expected.ToString(); } span stylecolor:#0000ffpublic override /spanspan stylecolor:#2b91afParserFunc/spanTFuture BuildParserTFuture(span stylecolor:#2b91afFuture/spanspan stylecolor:#2b91afLexeme/span, TFuture future) { span stylecolor:#2b91afParserFunc/spanTFuture scan span stylecolor:#0000ffnull/span; scan (scanner, context) { span stylecolor:#0000ffvar /spans1 scanner.Fork(); span stylecolor:#0000ffvar /spanl scanner.Read(); span stylecolor:#0000ffint /spantokenIndex; tokenIndex l.TokenIndex; span stylecolor:#0000ffif /span(tokenIndex ExpectedToken.Index) { span stylecolor:#0000ffvar /spanr context.StepResult(0, () future(l)(scanner, context)); span stylecolor:#0000ffreturn /spanr; } span stylecolor:#0000ffelse /span{ span stylecolor:#2b91afLexeme /spancorrectionLexeme l.GetErrorCorrectionLexeme(ExpectedToken.Index, MissingCorrection); span stylecolor:#2b91afErrorCorrection /spaninsertCorrection span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afInsertedErrorCorrection/span(ExpectedToken.ToString(), correctionLexeme.Span); span stylecolor:#0000ffif /span(l.IsEndOfStream) { scanner.Join(s1); span stylecolor:#0000ffreturn /spancontext.StepResult(1, () future(correctionLexeme)(scanner, context), insertCorrection); span stylecolor:#008000//插入 /span} span stylecolor:#0000ffelse /span{ span stylecolor:#2b91afErrorCorrection /spandeleteCorrection span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afDeletedErrorCorrection/span(l); span stylecolor:#0000ffreturn /spancontext.ChooseBest(context.StepResult(1, () future(correctionLexeme)(s1, context), insertCorrection), span stylecolor:#008000//插入 /spancontext.StepResult(1, () scan(scanner, context), deleteCorrection)); span stylecolor:#008000//删除 /span} } }; span stylecolor:#0000ffreturn /spanscan; } }/span大致描述下来就是生成这样一个ParserFunc首先通过Scanner读取下一个词素并判断它是否是期待的单词。如果是则调用context.StepResult(0, …)方法稍后解释如果不是则判断是否遇到的输入流的末尾如果是末尾则只尝试“插入”修复方案因为无法删除“流末尾”单词如果不是末尾则使用context.ChooseBest方法尝试插入和删除两种修复方案。context.StepResult方法就是产生延迟执行future的关键。它的第一个参数表示该结果的“代价”0表示这是一个成功解析的结果1表示是经过错误恢复的结果。第二个参数则是一个延迟执行的委托这个委托只会在我们需要将解析器“推进一步”的时候才会执行我们将future函数的调用放在这里并做成延迟执行的方式就是要等待广度优先一步一步地向前解析时才执行下一步的操作。那么这个context.ChooseBest函数到底是如何实现的呢请看代码span stylecolor:#000000span stylecolor:#0000ffprivate /spanspan stylecolor:#2b91afResult/spanT ChooseBestT(span stylecolor:#2b91afResult/spanT result1, span stylecolor:#2b91afResult/spanT result2, span stylecolor:#0000ffint /spancorrectionDepth) { span stylecolor:#0000ffif /span(result1.Type span stylecolor:#2b91afResultType/span.Stop) { span stylecolor:#0000ffreturn /spanresult1; } span stylecolor:#0000ffif /span(result2.Type span stylecolor:#2b91afResultType/span.Stop) { span stylecolor:#0000ffreturn /spanresult2; } span stylecolor:#0000ffvar /spanstep1 (span stylecolor:#2b91afStepResult/spanT)result1; span stylecolor:#0000ffvar /spanstep2 (span stylecolor:#2b91afStepResult/spanT)result2; span stylecolor:#0000ffif /span(step1.Cost step2.Cost) { span stylecolor:#0000ffreturn /spanstep1; } span stylecolor:#0000ffelse if /span(step1.Cost step2.Cost) { span stylecolor:#0000ffreturn /spanstep2; } span stylecolor:#0000ffelse /span{ span stylecolor:#0000ffreturn new /spanspan stylecolor:#2b91afStepResult/spanT(span stylecolor:#2b91afMath/span.Max(step1.Cost, step2.Cost), () ChooseBest(step1.NextResult, step2.NextResult, correctionDepth 1), span stylecolor:#0000ffnull/span); } }/spanChooseBest方法要比较两个Result的代价并选取代价较小的分支。如果代价一样则通过延迟计算的方法将比较推至下一轮。我们到处采用延迟计算的手段以至于整个单词流都输入之后解析可能仍然没有结束所以Result类有一个集中取得每一步结果的功能在单词流输入完毕后还要继续驱动这些延迟计算直到拿到最终的解析结果。接下来是表示连接运算G → X Y的SelectMany组合子。具体方法是将传入的future作为Y的future再将Y的Parser作为X的future以此将两者连接起来span stylecolor:#000000span stylecolor:#0000ffpublic class /spanspan stylecolor:#2b91afConcatenationParser/spanT1, T2, TR : span stylecolor:#2b91afParser/spanTR { span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afParser/spanT1 ParserLeft { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afFunc/spanT1, span stylecolor:#2b91afParser/spanT2 ParserRightSelector { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afFunc/spanT1, T2, TR Selector { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic /spanConcatenationParser(span stylecolor:#2b91afParser/spanT1 parserLeft, span stylecolor:#2b91afFunc/spanT1, span stylecolor:#2b91afParser/spanT2 parserRightSelector, span stylecolor:#2b91afFunc/spanT1, T2, TR selector) { span stylecolor:#2b91afCodeContract/span.RequiresArgumentNotNull(parserLeft, span stylecolor:#a31515parserLeft/span); span stylecolor:#2b91afCodeContract/span.RequiresArgumentNotNull(parserRightSelector, span stylecolor:#a31515parserRightSelector/span); span stylecolor:#2b91afCodeContract/span.RequiresArgumentNotNull(selector, span stylecolor:#a31515selector/span); ParserLeft parserLeft; ParserRightSelector parserRightSelector; Selector selector; } span stylecolor:#0000ffpublic override /spanspan stylecolor:#2b91afParserFunc/spanTFuture BuildParserTFuture(span stylecolor:#2b91afFuture/spanTR, TFuture future) { span stylecolor:#0000ffreturn /span(scanner, context) ParserLeft.BuildParser( left ParserRightSelector(left).BuildParser( right future(Selector(left, right))))(scanner, context); } } /span最后的并运算则是广度优先同时实验两个传入的Parser即直接用ChooseBest方法选取继续执行的Parserspan stylecolor:#000000span stylecolor:#0000ffpublic class /spanspan stylecolor:#2b91afAlternationParser/spanT : span stylecolor:#2b91afParser/spanT { span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afParser/spanT Parser1 { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afParser/spanT Parser2 { span stylecolor:#0000ffget/span; span stylecolor:#0000ffprivate set/span; } span stylecolor:#0000ffpublic /spanAlternationParser(span stylecolor:#2b91afParser/spanT parser1, span stylecolor:#2b91afParser/spanT parser2) { span stylecolor:#2b91afCodeContract/span.RequiresArgumentNotNull(parser1, span stylecolor:#a31515parser1/span); span stylecolor:#2b91afCodeContract/span.RequiresArgumentNotNull(parser2, span stylecolor:#a31515parser2/span); Parser1 parser1; Parser2 parser2; } span stylecolor:#0000ffpublic override /spanspan stylecolor:#2b91afParserFunc/spanTFuture BuildParserTFuture(span stylecolor:#2b91afFuture/spanT, TFuture future) { span stylecolor:#0000ffreturn /span(scanner, context) { span stylecolor:#0000ffvar /spans1 scanner; span stylecolor:#0000ffvar /spans2 scanner.Fork(); span stylecolor:#0000ffreturn /spancontext.ChooseBest(Parser1.BuildParser(future)(s1, context), Parser2.BuildParser(future)(s2, context)); }; } } /span
