自己动手开发编译器（八）用Linq编写解析器组合子

cjzhou 2014-01-10

展开全文

上回我们说到手写递归下降语法分析器。手写递归下降的方式是目前很多编译器采用的方式，如果你想写一个商业质量的编译器，这是首选的方法。但是，一个完善的递归下降解析器需要的代码量也不少，如果要进行错误报告、错误恢复等等那代码量就更大了。作为懒人，我们有时想要一些小型语言的解析器，最好写起来像直接写文法的产生式一样，最好连错误报告和错误恢复也一并自动解决，可能吗？在过去很长一段时间，人们采用的方法是使用解析器生成器（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 → X
G → Y

这表示，G既可以产生X也可以产生Y。在解析时无论成功解析X还是Y，都能成功解析出一个G。以上四种基本产生式嵌套使用，就能表示任何上下文无关文法。

下面定义解析器函数的原型委托：

public delegate IResult<T> ParserFunc<out T>(ForkableScanner scanner);

public interface IResult<out T>
{
    T Value { get; }
    ForkableScanner ReturnedScanner { get; }
}

public class Result<T> : IResult<T>
{
    public T Value { get; private set; }
    public ForkableScanner ReturnedScanner { get; private set; }

    public Result(T value, ForkableScanner returnedScanner)
    {
        Value = value;
        ReturnedScanner = returnedScanner;
    }
}

这并不是VBF.Compilers.Parsers.Combinators库最后采用的Parser函数原型，但它非常适合第一次接触解析器组合子的同学们理解。先看第一行委托的结构，它接受一个ForkableScanner作为参数，然后返回一个IResult<T>类型。首先什么是ForkableScanner呢？我们在词法分析篇定义的Scanner类只能不断地向前Read，而在函数式编程风格中，我们需要一个无副作用的Scanner。简而言之，任何一个个ForkableScanner可以随时“Fork”成两个ForkableScanner，而这两个Scanner任何一个向前扫描，都不会影响另外一个，而且他们各自扫描都回得到同样的单词流。这都是为了处理上述“并”运算的解析器，并运算需要两个分支能够互不影响地单独进行。接下来是返回类型IResult<T>，定义成接口是为了能够加上.NET 4泛型协变的“out”关键字。实际类型Result<T>包含一个解析结果T和成功解析之后返回的Scanner，代表余下的输入流。如果返回的整个Result对象为null，则表示解析失败。后面所有解析器组合子最终都是为了生成这样一个委托的对象，一旦生成了这个对象，就可以马上拿来解析了。

有了解析器函数原型，下面就开始一样一样地定义基础组合子。所谓组合子其实都是一些静态方法（本例中这些静态方法都定义在Parsers静态类中）、返回类型就是上面的解析器委托。由于返回类型也是委托，所以这些组合子实际上都是一些高阶函数（返回函数的函数）。在我们的代码中常常是一个lambda表达式。较少使用lambda表达是的同学第一次看下面的代码可能会略微感到头晕，只需要稍微休息一下再重新看即可……

首先是空产生式G → ε，它的组合子是：

public static ParserFunc<T> Succeed<T>(T result)
{
    return scanner => new Result<T>(result, scanner);
}

这个组合子接受一个参数，表示其解析结果。正如前面所介绍，由Succeed组合子生成的解析器，永远都会成功解析，而且会将设定的结果返回。

第二种是接受一个单词的的产生式G → t，我们将它的组合子定义成一个扩展方法：

public static ParserFunc<Lexeme> AsParser(this Token token)
{
    return scanner =>
    {
        var lexeme = scanner.Read();
        if (lexeme.TokenIndex == token.Index)
        {
            return new Result<Lexeme>(lexeme, scanner);
        }
        else
        {
            return null;
        }
    };
}

注意这个组合子生成的解析器是Lexeme（词素）类型的，词素对象是我们在词法分析阶段定义的，里面包含了词素的类型和具体字符串。这个组合子接受一个Token作为参数，而返回的解析器从输入的Scanner中读取下一个词素，如果该词素的单词类型与传入的Token相匹配，就报告解析成功，否则解析失败。

第三种是两个文法的连接G → X Y。我们需要定义一个组合子，接受两个已经存在的ParserFunc函数，返回一个新的ParserFunc，先后调用两个传入的ParserFunc：

public static ParserFunc<Tuple<T1, T2>> Concat<T1, T2>(this ParserFunc<T1> parser1, ParserFunc<T2> parser2)
{

    return scanner =>
    {
        var result1 = parser1(scanner);

        if (result1 == null) return null;

        var result2 = parser2(result1.ReturnedScanner);

        if (result2 == null) return null;

        return new Result<Tuple<T1, T2>>(Tuple.Create(result1.Value, result2.Value), result2.ReturnedScanner);
    };
}

注意我们返回的ParserFunc结果类型是Tuple<T1, T2>，因为结果中需要同时包含T1和T2。

用这种方式定义的连接运算组合子，在实践中非常难用。因为我们的文法常常要包含不止两个符号连接的情形。假如我们的产生式是G → X Y Z，那么必须写成 X.Concat(Y.Concat(Z))，而它的返回类型是Tuple<T1, Tuple<T2, T3>>，如果要取得结果中的Z，只能写r.Item2.Item2。实际上miniSharp这样的语言，文法中出现7-8个符号连接也不是什么稀奇的事情，而如果都用这个组合子的话，Tuple嵌套会复杂到把人的眼睛都搞晕掉。所以这时我们想到了——Linq。Linq的“组合子”中，有一种叫SelectMany，他给我们带来了这种语法糖：

List<int> la = new List<int>() { 1, 2, 3 };
List<string> lb = new List<string>() { "a", "b", "c" };

var r = from a in la
        from b in lb
        select a + b;

它实际可以翻译成：

var r = la.SelectMany(a => lb.SelectMany(b => a + b));

也就是说，连续from语句，其实是SelectMany扩展方法的嵌套调用。这种调用方法有把lambda嵌套“打平”的功能，非常类似于单子风格中的Bind运算。实际上C#和VB允许在任何自定义类型上扩展SelectMany方法，然后就允许用Linq语法的from去调用。有些人非常鄙视语法糖，但这个语法糖却是无法替代的，这是C#版解析器组合子关键中的关键！由此就可以将连接运算定义成一个SelectMany组合子：

public static ParserFunc<TResult> SelectMany<T1, T2, TResult>(this ParserFunc<T1> parser,
    Func<T1, ParserFunc<T2>> parserSelector, Func<T1, T2, TResult> resultSelector)
{

    return scanner =>
    {
        var result1 = parser(scanner);

        if (result1 == null) return null;

        var parser2 = parserSelector(result1.Value);

        var result2 = parser2(result1.ReturnedScanner);

        if (result2 == null) return null;

        return new Result<TResult>(resultSelector(result1.Value, result2.Value), result2.ReturnedScanner);
    };
}

这个神奇的SelectMany组合子不但消除了嵌套Tuple带来的混乱，还允许我们用一个自定义的select语句生成连接运算的结果，这在生成语法树的时候尤为方便。我们一会再看例子，先继续看最后一种基本组合子。

最后一种基本组合子是并运算。并运算要求产生式产生两种可能的分支。对应到解析器组合子上，连接运算也要接受两个现成的解析器作为参数，但是选择哪一个呢？这里我们没有办法做分支预测，所以只好采取尝试的办法。有一种尝试的方法就是先试用第一个解析器，如果失败了，再试用第二个，这是一种类似深度优先搜索的办法：

public static ParserFunc<T> Union<T>(this ParserFunc<T> parser1, ParserFunc<T> parser2)
{
    return scanner =>
    {
        var scanner1 = scanner;
        var scanner2 = scanner.Fork();

        var result1 = parser1(scanner1);
        if (result1 != null)
        {

            return result1;
        }

        var result2 = parser2(scanner2);

        return result2;
    };
}

仅仅使用以上四个组合子函数，就可以来写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<Node> NodeParser = null;
NodeParser = 
    (from a in LETTER.AsParser()
     from _1 in LEFTPH.AsParser()
     from left in NodeParser
     from _2 in COMMA.AsParser()
     from right in NodeParser
     from _3 in RIGHTPH.AsParser()
     select new Node(a.Value[0], left, right))
    .Union(Parsers.Succeed<Node>(null));


//运行部分
ForkableScannerBuilder builder = 
    new ForkableScannerBuilder(binaryTreeSyntax.CreateScannerInfo());

string source = "A(B(,),C(,))";
SourceReader sr = new SourceReader(
    new StringReader(source));

ForkableScanner scanner = builder.Create(sr);

var tree = NodeParser(scanner);

重点来看“定义语法”部分，我们来看看产生式都是如何转变为组合子调用的。首先，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项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！