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