TinyLisp：一个用于查看 LINQ 表达式实际应用的语言和解析器
一个解析表达式并使用 LINQ 表达式对其进行求值的简单程序。
引言
最近，我一直在更深入地研究Linq Expression树。它们非常棒，但出于某种原因，示例似乎并没有超出创建简单的硬编码表达式并执行它的范围。从学术角度来看，这很好，但由于表达式是硬编码的，它永远不会改变其行为，并且可能就像是用纯C#编写的一样。所以，我尝试了一个小项目来动态创建它们。
为了能够动态创建表达式，我们需要一种方法来更改创建它们的定义。这可以是一个XML文档，但我认为编写一个非常简单的解析器会更好，因为表达式树通常就来源于此。（是的，孩子们，真的！它们不是从鹳那里来的，是时候成熟起来，面对解析器了 ;-）。）
在本文中，我将介绍一种非常简单的表达式语言，我称之为TinyLisp。本文附带的程序会评估用它编写的表达式并显示结果。它在底层使用Linq.Expressions来实现所有这些功能。您可以输入一个表达式，然后查看它是如何解析成抽象语法树，然后转换为Linq表达式树，最后被执行的。
以下是我们即将介绍的内容
- 首先，我们将设计我们的小语言。我们将在一些方面进行简化，以便其余内容可以在一篇文章中完成。
- 然后，我们将编写代码来解析这些表达式。这比您预期的要容易得多。由于我们设计语言的方式，我们实际上可以在一个方法中编写这个解析器。
- 既然我们有了创建抽象语法树的解析器，我们就需要一些东西将它们转换为
Linq.Expression树。我们的语言和Linq之间存在一些细微差别，我们需要弥合，所以我们将需要重写该树。 - 现在我们轻松了！编译和执行Linq表达式是如今孩子们和奶奶们都在做的事情，所以我们只会简要地提及一下。
那么，事不宜迟，让我们来设计那个小语言吧。
语言
我们语言的主要设计目标是使其解析非常容易。我们将通过以一种不太常见的方式编写表达式来实现这一点。这是用我们称之为TinyLisp的语言编写的表达式。
(+ 1 2 3)
它乍一看可能有点奇怪，因为它以前缀表示法编写，这可能需要一些解释。在学校，我们被教导以这种方式编写相同的表达式
1 + 2 + 3
这被称为中缀表示法。加号是运算符，1、2和3是它们操作的操作数。在中缀表示法中，运算符位于两个操作数之间。在前缀表示法中，运算符位于操作数之前，并且它们都用括号括起来。
请注意，在前缀表示法中，我们只需要1个运算符就能处理3个操作数。因为它们都在括号内，所以操作数的数量可以任意多。为了在中缀表示法中做到这一点，您需要将运算符链接在每对操作数之间。这就是为什么我们需要2个加号来处理中缀表示法。这是我提到的我们以后需要弥合的两种表示法的细微差别。
现在看一个用中缀表示法编写的另一个表达式
5 + 4 * 3 + 2 / 1
这对于中缀表示法来说有点棘手。要计算出答案是19，您需要知道除法在乘法之前，乘法在加法之前。关于如何解析中缀表示法有大量的理论，但这会使我们的解析器过于复杂。本文更多地是关于Linq表达式，所以我们希望简化我们的工作。我们将自己应用优先级规则，并添加括号来指示评估顺序。
5 + (4 * 3) + (2 / 1)
这样已经好多了，但如果我们尝试解析它，由于表达式出现的顺序，它仍然会有点复杂。当我们把运算符移到每个（子）表达式的前面时，我们会得到这个，这就是我们想要的 the prefix notation syntax
(+ 5 (* 4 3) (/ 2 1))
现在用户自己放了括号，这为解析器节省了很多思考。除此之外，顺序也非常方便。我们首先得到运算符，然后是操作数，整个表达式都 neatly enclosed within parentheses。这种从左到右的顺序流允许我们的解析器非常简单。
我们语言的EBNF定义现在如下
expression = '(' ( '+' | '-' | '*' | '/' ) [ ['0'..'9'] | expression ]+ ')'
用普通话来说：一个表达式由一个开括号，然后是这些操作数之一+、-、*、/，然后是一个或多个整数或表达式，最后是一个闭括号组成。
作为额外的简化，我们将只处理数字 [0 .. 9]，以及运算符：[+, -, *, /]。这样，我们将遇到的所有内容都只有1个字符长。或者，每一个字符都是一个标记。简而言之，标记就像句子中的一个词。我在这里不详细介绍这些主题，如果您有兴趣，请在此处查看。重点是，我们只需要枚举string中的chars来获得一个标记流。我们可以做到。
解析我们的语言
解析意味着将一个string转换为计算机可以理解的东西：抽象语法树。以我们的例子为例，这个表达式...
"(+ 5 (* 4 3) (/ 2 1))"
...对计算机来说只是一堆chars。它需要被转换成程序可以操作的树状结构。
+
/ | \
5 * '/'
/ \ / \
4 3 2 1
这就是我们的解析器将要做的。但您可能会问，解析器不是很困难吗？嗯，这正是前缀表示法真正派上用场的地方。我们选择的语言设计基本上就是一种树形表示法。每个开括号 '(' 都标志着一个表达式的开始。后面的第一个字符是运算符。然后是一个或多个操作数，它们可以是整数或新的子表达式。最后，表达式以闭括号结束。然后这个（子）表达式就完成了，我们可以返回它。让我们用一些伪代码来写下来
Expression GetExpression:
Check opening parenthesis
Get Operator
Loop:
Get next token
If token = '(' then Operands.Add GetExpression // here we recurse for the
// subexpression
If token = ')' break loop
If token in [0..9] then Operands.Add token
这就是我们将这些前缀表达式读入树所需做的所有事情。听起来可行。下面是C#中的完整代码，在这个简短的介绍之后。
列表中的方法实际上是ExpressionNode类的构造函数。要使用它，可以调用类似这样的东西
ExpressionNode n = new ExpressionNode("(+ 5 4)")
与普通的string不同，实际的代码接受CharStream类型的参数。这个CharStream是我编写的一个简单的包装类，它接受一个string，然后逐个暴露单个char。使用这个类而不是普通的string的原因是，我们使用递归来将string解析成树。当我们从子调用返回时，我们希望继续处理string中子调用离开的位置，而不是它开始的位置。通过按引用传递这个CharStream，我们可以得到完全相同的行为。它还处理一些简单的任务，比如跳过空格。
所以，这是我们的解析器
// constructor to create expression tree by parsing a string
public ExpressionNode(CharStream Stream) {
// keep track of start of current expression within whole expression
this.Start = Stream.Position;
this.StringExpression = Stream.Stream;
// assert that we have a opening parenthesis to start this expression
if (Stream.Current != '(') throw new Exception("a (sub)expression
must always start with a '(' at position " + Stream.Current);
// skip to next char
Stream.MoveNext();
// get the operator which should be here now
if (Operators.Contains(Stream.Current)) this.Operator = Stream.Current;
else throw new Exception("Unexpected character '" +
Stream.Current + "' at position " + Stream.Position +
".\n\nThe first character after the '(' at position " +
this.Start + " that started this (sub)expression
must be its operator [+, -, *, /].");
// loop over the characters in the stream and try to figure them out one by one
while (true) {
// skip to next character
Stream.MoveNext();
// is it a '(' marking the start of new sub expression?
if (Stream.Current == '(') {
// start a new sub expression from here and add that (recurse)
this.Operands.Add(new ExpressionNode(Stream));
continue;
}
// is it a ')' marking end of current expression?
if (Stream.Current == ')') {
// this expression is done, mark ending and break loop
this.End = Stream.Position;
break;
}
// is it an int?
if (Ints.Contains(Stream.Current)) {
// add int and loop to go to next char
this.Operands.Add(new IntNode(Stream.Current));
continue;
}
// If none of the above was true, we have an error.
// Our language does not allow this situation.
throw new Exception("Error, expecting either '(', ')' or [0 .. 9]");
}
}
就是这样。它检查第一个字符是否为'('，然后读取运算符。然后它循环直到闭括号，寻找整数或子表达式。当遇到')'时，它就完成了，并将（子）表达式作为树结构返回。我鼓励您在调试器中逐步执行此代码，以了解其如何协同工作。
重写我们的树
这是我们的树。如果您仔细观察，您会发现我们遇到了一个小问题，因为顶部的'+'运算符有三个参数：5、*和/。在Linq表达式中，这是不允许的，因为它只有BinaryExpression，它接受2个操作数。
+
/ | \
5 * '/' <<< 3 operands for the + operator on this line...
/ \ / \
4 3 2 1
问题在于我们有3个操作数，每个运算符最多只能接受2个。我们可以做的是使用2个运算符，其中一个作为另一个的子节点。上面的运算符剩下1个操作数，下面的2个操作数，总共是我们需要的3个操作数。让我们在树上实践一下
带有3个操作数的顶部+运算符，拆分出一个新的+运算符。这个新的运算符接受最后两个操作数，并成为原始运算符的右操作数。现在每个运算符都有两个操作数，我们就完成了。
+
/ \
5 + <<< this is the new node that was split off
/ \
* '/'
/ \ / \
4 3 2 1
然而，在我们开始编写代码之前，还有另一个问题需要解决。
将我们的语法树转换为Linq表达式树
除了需要为我们的表达式定义一个可以轻松更改之外，我们还需要自己的语法树还有另一个原因。原因是您不能随意组合Linq表达式树。由于构造函数的定义方式，您被迫自下而上地创建它们。例如，我们用来计算表达式的BinaryOperator，我们不能简单地说
BinaryOperator b = new BinaryOperator()
因为您会收到此消息
Error 56 The type 'System.Linq.Expressions.BinaryExpression'
has no constructors defined
根本没有构造函数……但是……那么……它们是从哪里来的？同样，不是从鹳那里来的，表达式来自Expression基类上的static方法。要创建一个用于添加2个数字的BinaryExpression，您需要Expression上的这个static方法
public static BinaryExpression Add(Expression left, Expression right);
然而，问题在于您需要在准备好左右操作数之后才能创建BinaryExpression。通过拥有自己的abstract语法树，我们可以先以任何我们喜欢的方式构建它，然后通过深度优先遍历将其转换为Linq表达式树。当我们到达叶子并向上返回时，我们将拥有所需的os，并且可以自下而上地创建Linq表达式树。
这是我们语法树上的OperatorNode代码，它正是这样做的。这段代码一石二鸟：首先，它重写了我们的树，以便每个运算符只有两个操作数。它通过向下递归并插入节点来实现。然后，在向上返回时，它从该二叉树创建Linq.Expression节点，并返回整个表达式，重写为Linq表达式。
将两者结合在这里的原因是它们非常契合，因为它们都使用深度优先递归来遍历树。先将我们自己的语法转换为二叉树，然后再将其转换为Linq树将是双重工作。以下是代码：。
private Expression ToExpressionInternal(int Child) {
// if this is the last (or only) child, just return that.
// Can't have a binary operator with just 1 operand.
if (Child == Operands.Count - 1) {
return Operands[Child].ToExpression();
} else {
// so we have more than one, let's deal with that case:
// assign the current node to the left operand
Expression left = Operands[Child].ToExpression();
// Recurse down for the remaining child(ren) for the righthand operand.
// If there's more than 1 remaining they'll need to be nested into a tree also
Expression right = ToExpressionInternal(Child + 1);
// we're done recursing down and are now coming back up
// Put left and right together in a BinaryOperator and return that subtree
switch (Operator) {
case '+': return Expression.Add(left, right);
case '-': return Expression.Subtract(left, right);
case '*': return Expression.Multiply(left, right);
case '/': return Expression.Divide(left, right);
default: throw new Exception();
}
}
}
让我为您分析一个运算符有两个操作数的简单情况。
- 代码第一次被外部调用时，
Child = 0，用于处理第一个操作数。 - 这意味着（
0 == 2 -1）为false，它进入“else”分支。 Child 0被放入左操作数。- 为了计算右操作数，该函数以
Child + 1调用自身。- （
1 == 2 - 1）为true，所以它进入true分支。 - 第二个操作数作为
int节点返回。
- （
- 现在右操作数是那个
Int节点。 - 当我们调用
return Expression.Add(left, right);时，两者都被放入一个BinaryExpression中。
对于三个或更多操作数，它将继续将表达式嵌套到右操作数中，直到将它们转换为二叉树。这在调试器中观察比在这里写出来更好，写出来意义不大。
当没有更多节点向下遍历树时，将分配右操作数，并将两者放入BinaryOperator并返回。对于深度树，这将返回到递归调用的地方。对于顶层节点，将返回完整的Linq.Expression。瞧，树就 nicely converted 了！
编译和执行我们的Linq表达式
我们快到了！现在我们所要做的就是将我们的表达式放入一个lambda表达式中，然后编译并执行它。随意地在我的笔记本上按了一些按钮，得到了这个小片段。
// convert to Linq.Expression
Expression eExpression = nExpression.ToExpression();
// put it into a Lambda
Expression<Func<int>> lExpression = Expression.Lambda<Func<int>>(eExpression);
// Compile the lambda
Func<int> fExpression = lExpression.Compile();
第一步调用我们上面描述的代码，并将我们的语法树转换为Linq表达式树。然后我们将其放入一个lambda表达式中。表达式定义了要做什么，但lambda允许您实际去做。这就是lambda的作用，它是调用表达式树的样板代码。它处理参数之类的事情。当我们有了那个Lambda时，我们就调用它上面的Compile()，它返回一个Func<int>。
Func<int>是delegate int的简写。所以现在我们有一个delegate，我们可以调用它来执行我们的表达式。在经历了所有这些工作之后，如果不这样做就太傻了，所以开始吧
// and execute the compiled lambda to see the result
MessageBox.Show(fExpression());
Using the Code
使用该程序非常简单。当您运行它时，您可以在左侧的文本框中输入一个表达式，然后按按钮。程序将解析该表达式，将其转换为Linq表达式树并执行它。它还会并排显示两个表达式树，以便用户可以比较方法。只需在button_click上设置一个断点，然后逐步执行整个解析器和转换例程，应该可以很好地了解解析器和语法树。
这里有一些示例表达式供您开始
(+ 1 2 3) see how the prefix expression can have any
number of operands, where the Linq tree has only
two and needs to be nested
(+ 5 (* 4 3) (/ 2 1)) the expression we used as example
(+123(*456)) see tree rewriting in action again
(+123456789) really see how binary expression are a pretty blunt tool.
Also note that the digits are seen as separate numbers,
not one large number. The parser only looks at separate chars.
(+ 1 2 (* 3 4)) an expression with a subexpression
(+(-(*(/12)34(*56))7)(+89)1)2) some deep expression
这就是全部了。希望您在玩这个的过程中能获得乐趣并学到一些东西。如果您喜欢，请在评论中告诉我，或给我的文章评分。
历史
- 2010年6月12日：首次发布