注意:出于好奇,回答这个问题的人中是否有人在C#中实现过解析器?
我已经在C#中实现了几个解析器-手写和工具生成的。
关于解析的一个非常好的入门教程是让我们构建一个编译器 - 它演示了如何构建递归下降解析器; 这些概念很容易从他的语言(我认为是Pascal)翻译成C#,适用于任何有能力的开发人员。这将教你递归下降解析器的工作原理,但手动编写完整的编程语言解析器是完全不切实际的。
如果您决定手写经典递归下降解析器(TinyPG, Coco/R, Irony),则应该考虑使用一些工具来为您生成代码。请记住,现在还有其他编写解析器的方法,通常表现更好-并且具有更简单的定义(例如TDOP解析或Monadic Parsing)。
关于C#是否适用的话题-C#拥有一些最好的文本库。今天许多解析器(在其他语言中)有大量代码来处理Unicode等。我不会对JITted代码发表太多评论,因为它可能会变得非常宗教-但是你应该没问题。IronJS是CLR上的一个解析器/运行时的很好的例子(即使它是用F#编写的),其性能仅次于Google V8。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+Tutorial
同样也可以采用基于组合子的方法实现类似Packrat,方式非常相似,但这次需要在某个地方保留全局的解析状态而不是进行纯函数式的操作。在我(非常基本和临时)的实现中,速度还算不错,但当然像this这样的代码生成器应该表现更好。
好的...从哪里开始呢...
首先,编写一个解析器,这是一个非常广泛的声明,特别是针对你所问的问题。
你的开场白是你想要一个简单的算术“解析器”,但从技术上讲,那不是一个解析器,它是一个词法分析器,类似于你可能用于创建新语言的工具。(http://en.wikipedia.org/wiki/Lexical_analysis) 我理解混淆它们是同一件事情的来源。需要注意的是,如果你要编写语言/脚本解析器,你也需要了解词法分析,这严格来说不是解析,因为你正在解释指令而不是利用它们。
回到解析问题...
如果你正在从一个严格定义的文件结构中提取信息,那么这就是你要做的事情。
通常情况下,你真的不需要为XML / HTML编写解析器,因为已经有很多解析器存在,尤其是如果你正在解析.NET运行时生成的XML,那么你甚至不需要解析,你只需要“序列化”和“反序列化”即可。
然而,为了学习起见,在大多数情况下解析XML(或类似的HTML)非常简单。
如果我们从以下XML开始:
<movies>
<movie id="1">
<name>Tron</name>
</movie>
<movie id="2">
<name>Tron Legacy</name>
</movie>
<movies>
XElement myXML = XElement.Load("mymovies.xml");
接下来,您可以使用 'myXML.Root' 来获取 'movies' 根元素
更有趣的是,您可以轻松使用 Linq 获取嵌套标签:
var myElements = from p in myXML.Root.Elements("movie")
select p;
将会给你一个包含每个元素的变量XElements,每个元素都包含一个“...”,你可以使用类似以下的方式获取它:
foreach(var v in myElements)
{
Console.WriteLine(string.Format("ID {0} = {1}",(int)v.Attributes["id"],(string)v.Element("movie"));
}
如果除了XML之外的其他数据结构,那么恐怕你需要开始学习正则表达式的艺术,像“Regular Expression Coach”这样的工具将会对你有很大帮助(http://weitz.de/regex-coach/),或者使用更现代化的类似工具。
你还需要熟悉.NET正则表达式对象,(http://www.codeproject.com/KB/dotnet/regextutorial.aspx)可以为你提供一个很好的起点。
一旦你知道如何使用正则表达式,那么在大多数情况下,只需逐行读取文件并使用你感到舒适的任何方法来理解它们即可。
几乎可以想象到的任何东西的免费文件格式的良好来源可以在(http://www.wotsit.org/)找到。
就记录而言,我在C#中实现了解析器生成器,只是因为我找不到任何有效的工具或类似于YACC的工具(参见:http://sourceforge.net/projects/naivelangtools/)。
然而,在使用ANTLR一段时间后,我决定选择LALR而不是LL。我知道从理论上讲,LL更容易实现(生成器或解析器),但我简直无法忍受为了表达运算符的优先级(例如*
在“2+5*3”中比+
更重要)而使用一堆表达式的情况。在LL中,您说mult_expr嵌入在add_expr中,这对我来说似乎不太自然。