如何用C#编写解析器

我已经用C#实现了几个解析器——手工编写和工具生成。

一个很好的解析入门教程是Let's Build A Compiler，它演示了如何构建递归下降语法分析器；对于任何有能力的开发人员来说，这些概念都很容易从他的语言(我想是Pascal(翻译成C#。这将教您递归下降语法分析器是如何工作的，但手工编写完整的编程语言语法分析器是完全不切实际的。

如果你决心编写一个经典的递归下降语法分析器(TinyPG、Coco/R、Irony(，你应该研究一些工具来为你生成代码。请记住，现在还有其他编写解析器的方法，它们通常性能更好，定义更简单(例如TDOP解析或Monadic解析(。

关于C#是否能胜任这项任务，C#有一些最好的文本库。现在很多解析器(在其他语言中(都有大量的代码来处理Unicode等。我不会对JITted代码发表太多评论，因为它可能会变得非常虔诚——不过你应该没事。IronJS是CLR上的解析器/运行时的一个很好的例子(尽管它是用F#编写的(，它的性能还差于Google V8。

旁注：与语言解析器相比，标记解析器是完全不同的野兽——在大多数情况下，它们是手工编写的——在扫描仪/解析器级别上非常简单；它们通常不是递归下降的，尤其是在XML的情况下，最好不编写递归下降解析器(以避免堆栈溢出，并且因为"平面"解析器可以在SAX/push模式中使用(。

Sprache是一个强大而轻量级的框架，用于在.NET中编写解析器。还有一个Sprache-NuGet包。为了让您了解这个框架，这里有一个示例可以将一个简单的算术表达式解析为.NET表达式树。我想说，真是太神奇了。

using System;
using System.Linq.Expressions;
using Sprache;
namespace LinqyCalculator
{
    static class ExpressionParser
    {
        public static Expression<Func<decimal>> ParseExpression(string text)
        {
            return Lambda.Parse(text);
        }
        static Parser<ExpressionType> Operator(string op, ExpressionType opType)
        {
            return Parse.String(op).Token().Return(opType);
        }
        static readonly Parser<ExpressionType> Add = Operator("+", ExpressionType.AddChecked);
        static readonly Parser<ExpressionType> Subtract = Operator("-", ExpressionType.SubtractChecked);
        static readonly Parser<ExpressionType> Multiply = Operator("*", ExpressionType.MultiplyChecked);
        static readonly Parser<ExpressionType> Divide = Operator("/", ExpressionType.Divide);
        static readonly Parser<Expression> Constant =
            (from d in Parse.Decimal.Token()
             select (Expression)Expression.Constant(decimal.Parse(d))).Named("number");
        static readonly Parser<Expression> Factor =
            ((from lparen in Parse.Char('(')
              from expr in Parse.Ref(() => Expr)
              from rparen in Parse.Char(')')
              select expr).Named("expression")
             .XOr(Constant)).Token();
        static readonly Parser<Expression> Term = Parse.ChainOperator(Multiply.Or(Divide), Factor, Expression.MakeBinary);
        static readonly Parser<Expression> Expr = Parse.ChainOperator(Add.Or(Subtract), Term, Expression.MakeBinary);
        static readonly Parser<Expression<Func<decimal>>> Lambda =
            Expr.End().Select(body => Expression.Lambda<Func<decimal>>(body));
    }
}

C#几乎是一种不错的函数式语言，因此在其中实现Parsec之类的东西并不是什么大不了的事。下面是如何做到这一点的示例之一：http://jparsec.codehaus.org/NParsec+教程

也可以以非常类似的方式实现基于组合子的Packrat，但这一次在某个地方保持全局解析状态，而不是做纯函数的事情。在我的(非常基本和特别的(实现中，它相当快，但当然，像这样的代码生成器必须表现得更好。

我知道我有点迟到了，但我刚刚发布了一个名为Ve-parser的解析器/语法/AST生成器库。你可以在http://veparser.codeplex.com或者通过在Package Manager控制台中键入"Install Package veparser"添加到您的项目中。这个库是一种递归下降分析器，旨在易于使用和灵活。由于其源代码可供您使用，因此您可以从其源代码中学习。我希望它能有所帮助。

在我看来，有一种比传统方法更好的方法来实现解析器，这会使代码更简单、更容易理解，尤其是通过以非常面向对象的方式插入一个新类，可以更容易地扩展您正在解析的任何语言。我写的一篇更大系列的文章集中于这种解析方法，其中包含了C#2.0解析器的完整源代码：http://www.codeproject.com/Articles/492466/Object-Oriented-Parsing-Breaking-With-Tradition-Pa

嗯。。。从哪里开始。。。。

首先，编写一个解析器，这是一个非常宽泛的陈述，尤其是对于您提出的问题。

你的开场白是，你想要一个简单的算术"解析器"，从技术上讲，这不是解析器，而是一个词法分析器，类似于你可以用来创建一种新语言的分析器。(http://en.wikipedia.org/wiki/Lexical_analysis(然而，我完全理解它们是同一事物的困惑可能来自哪里。需要注意的是，如果你也要编写语言/脚本解析器，词汇分析也是你想要理解的，这绝对不是解析，因为你是在解释指令，而不是使用它们。

回到解析问题。。。。

如果你采用一个严格定义的文件结构来从中提取信息，这就是你要做的

一般来说，你真的不必为XML/HTML编写解析器，因为已经有很多解析器了，更重要的是，如果你的解析XML是由.NET运行时生成的，那么你甚至不需要解析，你只需要"串行化"answers"去串行化"。

然而，从学习的角度来看，在大多数情况下，解析XML(或类似于html的任何东西(都是非常直接的。

如果我们从以下XML:开始

    <movies>
      <movie id="1">
        <name>Tron</name>
      </movie>
      <movie id="2">
        <name>Tron Legacy</name>
      </movie>
    <movies>

我们可以将数据加载到XElement中，如下所示：

    XElement myXML = XElement.Load("mymovies.xml");

然后，您可以使用'myXML.root'访问'movies'根元素

然而，有趣的是，你可以很容易地使用Linq来获得嵌套的标签：

    var myElements = from p in myXML.Root.Elements("movie")
                     select p;

将为您提供一个XElements变量，每个XElements包含一个"…"你可以使用之类的东西

    foreach(var v in myElements)
    {
      Console.WriteLine(string.Format("ID {0} = {1}",(int)v.Attributes["id"],(string)v.Element("movie"));
    }

对于除了类似XML的数据结构之外的任何其他东西，恐怕你必须开始学习正则表达式的艺术，像"正则表达式教练"这样的工具将帮助你imensly(http://weitz.de/regex-coach/(或更先进的类似工具之一。

您还需要熟悉.NET正则表达式对象(http://www.codeproject.com/KB/dotnet/regextutorial.aspx(应该会给你一个良好的开端。

一旦你知道你的reg ex东西是如何工作的，那么在大多数情况下，这只是一个简单的案例，每次读取一行文件，并使用你觉得舒服的方法来理解它们。

可以在(http://www.wotsit.org/(

对于记录，我在C#中实现了语法分析器生成器，只是因为我找不到任何能正常工作或与YACC类似的语法分析器生成器(请参阅：http://sourceforge.net/projects/naivelangtools/)。

然而，在经历了一些ANTLR之后，我决定选择LALR而不是LL。我知道理论上LL更容易实现(生成器或解析器(，但我不能只使用表达式堆栈来表达运算符的优先级(就像"2+5*3"中*在+之前(。在LL中，你说mult_expr嵌入在add_expr中，这对我来说并不自然。