如何用C#编写解析器？

Question

我如何在C#中编写解析器(递归下降？)？现在我只想要一个解析算术表达式(并读取变量？)的简单解析器.虽然后来我打算写一个xml和html解析器(用于学习目的).我这样做是因为解析器很有用的东西:Web开发,编程语言解释器,内部工具,游戏引擎,地图和平铺编辑​​器等.那么编写解析器的基本理论是什么呢？我该怎么做在C#中实现一个？C#是解析器的正确语言(我曾经在C++中编写了一个简单的算术解析器并且它很有效.JIT编译是否同样适用？).任何有用的资源和文章.最重要的是,代码示例(或代码示例的链接).

注意:出于好奇,有人回答这个问题曾经在C#中实现了解析器吗？

Answer 1

我在C#中实现了几个解析器 - 手工编写和工具生成.

关于解析的一个非常好的入门教程是Let's Build a Compiler - 它演示了如何构建递归下降解析器; 对于任何有能力的开发人员来说,这些概念很容易从他的语言(我认为是Pascal)转换为C#.这将教你如何使用递归下降解析器,但手动编写完整的编程语言解析器是完全不切实际的.

你应该研究一些工具来为你生成代码 - 如果你决定编写一个经典的递归下降解析器(TinyPG,Coco/R,Irony).请记住,还有其他的方式,现在写解析器,通常有更好的表现-和具有容易定义(例如TDOP解析或一元解析).

关于C#是否适合任务的主题 - C#有一些最好的文本库.今天很多解析器(在其他语言中)都有大量的代码来处理Unicode等.我不会对JITted代码做太多评论,因为它可能非常虔诚 - 但是你应该没问题.IronJS是CLR上解析器/运行时的一个很好的例子(尽管它是用F#编写的),它的性能与谷歌V8 相差无几.

附注:与语言解析器相比,标记解析器是完全不同的野兽 - 在大多数情况下,它们是手工编写的 - 并且在扫描器/解析器级别非常简单; 它们通常不是递归下降 - 特别是在XML的情况下,如果不编写递归下降解析器(以避免堆栈溢出,并且因为可以在SAX /推模式中使用'平'解析器),则更好.

Answer 2

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));
    }
}