使用 C# 4.0 实现编程语言
4.92/5 (114投票s)
介绍如何使用 C# 4.0 创建编程语言工具。
介绍
本文档为 C# 程序员介绍了编程语言实现的基本概念。它旨在通过算术求值器和简单的 JavaScript 解释器等多个示例，快速概述使用 C# 4.0 实现编程语言的概念。
本文档附带了一个用 C# 4.0 编写的名为 Jigsaw 的开源库。您可以在 code.google.com/p/jigsaw-library/ 下载 Jigsaw 的最新版本。
Jigsaw 提供了一个高效强大的解析引擎，以及大量的示例语法和求值器。Jigsaw 解析库是 Cat 语言 和后续 Heron 语言 中使用的解析器的演进。
Jigsaw 库根据 MIT 开源许可证授权。如果您需要其他许可证，请通过 cdiggins@gmail.com 与我联系。如果您使用或滥用 Jigsaw，我非常希望能听到您的反馈！
内置 .NET 编译器
在开始之前，我想指出，如果您正在寻找现成的 C# 解释器，您应该考虑 System.CodeDOM.Compiler 命名空间以及以下一个或多个程序集：
- Microsoft.CSharp
- Microsoft.Jscript
- Microsoft.VisualBasic
每个程序集都提供了一个派生自 CodeDomProvider 的类（例如 CSharpCodeProvider），您可以使用它在运行时编译程序集。
下面的函数展示了如何使用 CodeDomProvider 动态生成程序集。
public static Assembly CompileWithProvider(CodeDomProvider provider, params string[] lines)
{
var param = new System.CodeDom.Compiler.CompilerParameters();
var result = provider.CompileAssemblyFromSource(param, lines);
foreach (var e in result.Errors)
Console.WriteLine("Error occured during compilation {0}", e.ToString());
if (result.Errors.Count > 0)
return null;
else
return result.CompiledAssembly;
}
有关如何使用内置 .NET 编译器的更多示例，请参阅 CodeDOMCompilers.cs 文件。
即便如此，我相信您在这里是因为您想学习编程语言实现的“黑魔法”，所以请继续勇敢的读者！
语言工具的解剖结构
大多数语言工具遵循相同的基本架构：
- 词法分析（可选）——此阶段也称为词法扫描、词法分析和扫描。在此阶段，字符序列被转换为标记序列（也称为词素）。此阶段对于某些类型的解析器（例如 LALR）是必需的，而对于其他解析器（例如 PEG）则不是。没有词法分析阶段的解析器（如 Jigsaw）称为无扫描器解析器。
- 语法分析——将线性标记或字符序列转换为称为解析树的树状结构。
- 树转换器（可选）——修改解析树，简化后续步骤。
- 树访问器——访问树中的每个节点并执行某些操作或创建新的数据结构。
节点访问期间发生的事情决定了语言工具的类型。例如：
- 解释器——将节点转换为运行时值或执行基本操作。
- 编译器——将节点转换为机器可执行的表示形式。
- 代码格式化工具——将节点转换为人类可读的形式，例如 ASCII 或 HTML。
- 翻译器——将节点转换为新编程语言的源代码表示。
- 类型检查器——节点被转换为表达式类型的表示形式。这是一种抽象解释。
- 部分求值器——优化阶段，其中某些节点被其求值结果替换（例如，编译时表达式）。
一个有用的简化是：语言工具会操作树。
语法分析
语法分析，或句法分析，用于确定输入字符串是否匹配特定句法形式（语法），并将输入分解为表示句法成分（术语或句法短语）的解析树。
.NET Framework 没有现成的语法分析工具，但有大量第三方语法分析工具可供选择。一些更受欢迎的工具是 ANTLR、YACC 和 BISON。这些工具是解析器生成器，这意味着它们从解析器定义（语法）生成解析器的源代码。
使用代码生成器的一个问题是学习曲线相当陡峭。它们都有自己的语法和规则。我不得不自己实现一个手动编写的解析器，才能理解如何使用这些工具。那时已经太晚了，我已经沉迷于手动编写解析器了。
在本文中，我将使用一个我编写的 C# 解析库，名为 _Jigsaw_。我选择使用手动编写的解析器，因为它更容易理解和调试。Jigsaw 是一个带有记忆的递归下降回溯 PEG 解析器。这听起来很复杂，让我们分解一下它的含义：
- 一个 递归下降解析器 使用一组相互递归的过程来识别语言中的句法元素。
- 一个回溯解析器会按顺序尝试解析一组规则，在遇到选择时，直到其中一个成功。
- 一个带有记忆的解析器是使用查找表缓存（记忆）解析规则中间结果的解析器，这提高了算法的时间复杂度。带有记忆的 PEG 解析器也称为Packrat 解析器。
- PEG（解析表达式语法）解析器识别语法，其中每个规则直接对应于一个模式匹配算法。PEG 的一个更常见的替代方案是预测 LR 解析器（其中有许多），但它们更复杂。
当你第一次了解语法分析时，这些都不特别重要。我的经验是，这些类型的解析器最符合我关于解析器应该如何工作的直觉。
语法
语法是语言语法的正式定义。编写语法有点像编写正则表达式。语法由一个或多个规则组成，这些规则使用规则运算符（也称为组合器）根据其他规则定义。每个规则描述语言中的一个特定句法元素，称为短语。
在 Jigsaw 库中，语法以 PEG（解析表达式语法）的形式表示。在 PEG 语法中，每个规则定义了一个特定句法元素的解析器。
是时候进行一次“非学习”了：如果您之前学习过上下文无关文法（CFG），那么 PEG 有所不同，因为每个规则都描述了如何匹配字符串，而不是如何生成它们（如 CFG 的情况）。一些启示是，PEG 可以有零宽度规则并且是无歧义的。PEG 和 CFG 之间的区别很微妙但很重要。
每个规则都是一个派生自 Rule 的类的实例。它的作用是识别语言中的句法元素（称为术语或短语）。这种识别是在 Match() 函数中完成的，该函数返回一个布尔值，指示匹配是否成功。Match 函数接受一个 ParserState 类的实例，该类包含输入字符串、输入字符串中的位置以及解析树。
您可以从 Grammar 类的静态成员函数创建规则实例。
Grammar.MatchString("fox").Match("fox")); // true
Grammar.MatchString("fox").Match("foxy")); // true
Grammar.MatchString("fox").Match("flying fox")); // false
您可以使用加号 (“+”) 运算符构建仅当一系列子规则成功匹配时才成功的复合规则。
var rule = Grammar.MatchString("cat") + Grammar.MatchString("fish")
rule.Match("catnip"); // false
rule.Match("dogfish"); // false
rule.Match("catfish"); // true
您可以使用管道 (“|”) 运算符构建尝试匹配一系列规则中任何一个的复合规则。
var rule = Grammar.MatchString("cat") | Grammar.MatchString("dog")
rule.Match("catfish"); // true
rule.Match("doggedly"); // true 规则运算符可以组合以创建更复杂的规则。
var rule = (Grammar.MatchString("cat") | Grammar.MatchString("dog")) + Grammar.MatchString("fish")
rule.Match("dogfish"); // true
rule.Match("catfish"); // true
rule.Match("swordfish"); // false
rule.Match("cat"); // false
规则可以使用 Grammar.Opt() 函数定义为可选。
var rule = Grammar.MatchString("cat") +
Grammar.Opt(Grammar.MatchString("fish") |
Grammar.MatchString("nap"));
rule.Match("cat"); // true
rule.Match("catfish"); // true
重复规则也可以使用 Grammar.ZeroOrMore() 和 Grammar.OneOrMore() 创建。例如：
var rule = Grammar.OneOrMore(Grammar.MatchString("badger")) + Grammar.MatchString("snake");
rule.Match("badger badger badger badger snake!"); // true
创建解析树
仅仅识别一个字符串是否属于某个语法对于编写编程语言工具来说并不是特别有用。我们真正想要的是一个代表输入结构的 K 数据结构。
Jigsaw 允许通过将 Grammar.Node 规则嵌入语法来实现这一点。当匹配成功时，这些规则会将 Node 的新实例添加到解析树中。调用 Rule.Parse() 函数将返回一个解析节点列表，每个节点都是一个解析树的根。
节点规则必须使用 Rule.SetName() 函数命名（与其他规则名称可选不同）。此名称用作节点树中关联节点的标签。
以下代码定义了一个用于解析单词的简单语法。
// Define the rules
Rule word = Grammar.Node(Grammar.Pattern(@"\w+")).SetName("word");
Rule ws = Grammar. Pattern(@"\s+");
Rule eos = Grammar.CharSet("!.?");
Rule sentence = Grammar.Node(Grammar.ZeroOrMore(word | ws) +
eos).SetName("sentence");
Rule sentences = Grammar.OneOrMore(sentence + Grammar.Opt(ws));
var nodes = sentences.Parse("Hey! You stole my pen. Hey you stole my pen!");
foreach (var n in nodes) {
Console.WriteLine(n);
foreach (var n2 in n.Nodes)
Console.WriteLine(" " + n2);
}
上述程序的输出是：
sentence:Hey!
word:Hey
sentence:You stole my pen.
word:You
word:stole
word:my
word:pen
sentence:Hey you stole my pen!
word:Hey
word:you
word:stole
word:my
word:pen
记忆（缓存）中间结果
某些递归下降解析器可能需要很长时间来解析某些输入。解决此问题的方法是将中间解析结果缓存到查找表中。这种技术称为记忆。
在 Jigsaw 库中，所有 NodeRule 匹配结果都缓存在 ParserState 对象中存储的字典里。
如果您将 NodeRule.UseCache 常量设置为 false，则可以通过运行 JavaScriptTests 类中的测试来查看解析某些语法需要多长时间。
简化语法：派生自 Grammar 类
在定义语法时，以下几点特别令人头疼：
- 需要在规则创建函数前添加
Grammar前缀。 - 需要显式设置节点规则的名称。
您可以通过在派生自 Grammar 的类中定义所有规则来解决这些问题，并将每个规则声明为公共静态字段。然后，您可以在静态初始化程序中使用 InitGrammar() 函数自动为与字段关联的每个规则分配名称。
您可以按照以下方式简化上一示例中使用的语法：
public class SentenceGrammar : Grammar
{
public static Rule word = Node(Pattern(@"\w+"));
public static Rule ws = Pattern(@"\s+");
public static Rule eos = CharSet("!.?");
public static Rule sentence = Node(ZeroOrMore(word | ws) + eos);
public static Rule sentences = OneOrMore(sentence + Opt(ws));
static SentenceGrammar() {
Grammar.InitGrammar(typeof(SentenceGrammar));
}
}
递归规则
定义为变量或字段的规则不能引用自身或尚未定义的规则。这将在规则定义期间导致空引用。例如，以下语法将在类型初始化期间产生错误：
static Rule Number = Pattern("\d+");
static Rule Operator = Node(MatchCharSet("+-*/"));
static Rule Expr = (MatchString("(") + Expr + ")")| (Expr + Operator + Expr) | Number;
一种解决方案是使用 Recursive() 规则，它接受一个 lambda 表达式，该表达式在运行时返回一个表达式。
static Rule RecExpr = Recursive(() => Expr);
static Rule Number = Pattern("\d+");
static Rule Operator = Node(MatchCharSet("+-*/"));
static Rule Expr = ("(" + RecExpr + ")")| (RecExpr + Operator + RecExpr) | Number;
避免左递归规则
在 PEG 语法中，不允许在序列的最左边位置使用递归规则。这些被称为“左递归”规则，会导致解析器进入无限循环。
例如，考虑用于识别函数调用的语法（例如，f(x) 或 f(x)(y)(z)）：
static Rule UnaryExpr = Node(Number | Identifier);
static Rule ArgList = Node(Parenthesize(CommaList(RecExpr())));
static Rule PostInc = Node(MatchString("++"));
static Rule PostDec = Node(MatchString("--"));
static Rule PostfixOp = Node(ArgList | PostInc | PostDec);
static Rule PostfixExpr = Node((Recursive(() => PostfixOp) + ArgList) | UnaryExpr);
这会导致无限循环并引发堆栈溢出异常。解决方法是将递归规则重写为迭代规则。
static Rule PostfixExpr = Node(UnaryExpr + ZeroOrMore(PostfixOp));
此规则识别所需的表达式，但不幸的是，它会产生一个解析树，这可能会给求值器或编译器带来不必要的复杂性。您可以通过使用解析后转换过程来解决此问题。这将在“编写树转换器”部分进行讨论。
简单的算术语法
将我们迄今为止学到的所有内容结合起来，下面是一个用于解析算术表达式的简单语法：
class ArithmeticGrammar : SharedGrammar
{
new public static Rule Integer = Node(SharedGrammar.Integer);
new public static Rule Float = Node(SharedGrammar.Float);
public static Rule RecExpr = Recursive(() => Expression);
public static Rule ParanExpr = Node(CharToken('(') + RecExpr + WS + CharToken(')'));
public static Rule Number = (Integer | Float) + WS;
public static Rule PrefixOp = Node(MatchStringSet("! - ~"));
public static Rule PrefixExpr = Node(PrefixOp + Recursive(() => SimpleExpr));
public static Rule SimpleExpr = PrefixExpr | Number | ParanExpr;
public static Rule BinaryOp =
Node(MatchStringSet("<= >= == != << >> && || < > & | + - * % / ^"));
public static Rule Expression = Node(SimpleExpr + ZeroOrMore(BinaryOp + WS + SimpleExpr));
static ArithmeticGrammar() { InitGrammar(typeof(ArithmeticGrammar)); }
}
您可能已经注意到，我在这里作弊了，使用了 SharedGrammar 基类。这个类定义了一些额外的常用规则和规则操作，如 WS、Integer、Float 和 CharToken()。我将留给您自行查看代码以了解有哪些可用功能。
求值算术语法解析树
一旦通过解析字符串生成了解析树，我们就会希望将其转换为一个值。这个过程称为求值。
为此，我们创建一个名为 ArithmeticEvaluator 的新类，该类有两个函数：Eval(string s) 和 Eval(node n)。
为了方便起见，这两个函数都返回一个 dynamic 值。当我们声明一个类型为 dynamic 的值时，它会告诉编译器跳过类型检查。取而代之的是，所有操作都在运行时解析。
class ArithmeticEvaluator
{
public static dynamic Eval(string s)
{
return Eval(Grammars.ArithmeticGrammar.Expression.Parse(s)[0]);
}
public static dynamic Eval(Node n)
{
switch (n.Label)
{
case "Number": return Eval(n[0]);
case "Integer": return Int64.Parse(n.Text);
case "Float": return Double.Parse(n.Text);
case "PrefixExpr":
switch (n[0].Text)
{
case "-": return -Eval(n[1]);
case "!": return !Eval(n[1]);
case "~": return ~Eval(n[1]);
default: throw new Exception(n[0].Text);
}
case "ParanExpr": return Eval(n[0]);
case "Expression":
switch (n.Count)
{
case 1:
return Eval(n[0]);
case 3:
switch (n[1].Text)
{
case "+": return Eval(n[0]) + Eval(n[2]);
case "-": return Eval(n[0]) - Eval(n[2]);
case "*": return Eval(n[0]) * Eval(n[2]);
case "/": return Eval(n[0]) / Eval(n[2]);
case "%": return Eval(n[0]) % Eval(n[2]);
case "<<": return Eval(n[0]) << Eval(n[2]);
case ">>": return Eval(n[0]) >> Eval(n[2]);
case "==": return Eval(n[0]) == Eval(n[2]);
case "!=": return Eval(n[0]) != Eval(n[2]);
case "<=": return Eval(n[0]) <= Eval(n[2]);
case ">=": return Eval(n[0]) >= Eval(n[2]);
case "<": return Eval(n[0]) < Eval(n[2]);
case ">": return Eval(n[0]) > Eval(n[2]);
case "&&": return Eval(n[0]) && Eval(n[2]);
case "||": return Eval(n[0]) || Eval(n[2]);
case "&": return Eval(n[0]) & Eval(n[2]);
case "|": return Eval(n[0]) | Eval(n[2]);
default: throw new Exception("Unrecognized operator " + n[1].Text);
}
default:
throw new Exception(String.Format(
"Unexpected number of nodes {0} in expression", n.Count));
}
default:
throw new Exception("Unexpected type of node " + n.Label);
}
}
}
编写 JSON 解析器
JSON 代表JavaScript 对象表示法。它是 JavaScript 语言的一个子集，通常用作文本数据表示语言。它的结构与 XML 类似。
在 Jigsaw 库中，有一个名为 JsonObject 的类，它派生自 DynamicObject，可以从字符串动态创建。这意味着我们可以编写如下代码：
dynamic d = JsonObject.Parse("{ \"answer\" : 42 }");
Console.WriteLine(d.answer);
对于本文档，JsonObject 实现中最有趣的部分是 Parse() 函数。
public static JsonObject Parse(string s)
{
var nodes = JsonGrammar.Object.Parse(s);
return Eval(nodes[0]);
}
要实现解析函数，我们首先需要定义一个 JSON 语法。
public class JsonGrammar : SharedGrammar
{
new public static Rule Integer = Node(SharedGrammar.Integer);
new public static Rule Float = Node(SharedGrammar.Float);
public static Rule Number = Node(Integer | Float);
public static Rule True = Node(MatchString("true"));
public static Rule False = Node(MatchString("false"));
public static Rule Null = Node(MatchString("null"));
public static Rule UnicodeControlChar =
Node(MatchString("\\u") + HexDigit + HexDigit + HexDigit + HexDigit);
public static Rule ControlChar = Node(MatchChar('\\') + CharSet("\"\\/bfnt"));
public static Rule PlainChar = Node(ExceptCharSet("\"\\")); // "
public static Rule Char = Node(UnicodeControlChar | ControlChar | PlainChar);
public static Rule StringChars = Node(ZeroOrMore(Char));
public static Rule String = Node(MatchChar('"') + StringChars + MatchChar('"'));
public static Rule Value =
Node(Recursive(() => String | Number | Object | Array | True | False | Null));
public static Rule Name = Node(String);
public static Rule Pair = Node(Name + WS + CharToken(':') + Value + WS);
public static Rule Members = Node(CommaDelimited(Pair));
public static Rule Elements = Node(CommaDelimited(Value));
public static Rule Array = Node(CharToken('[') + Elements + WS + CharToken(']'));
public static Rule Object = Node(CharToken('{') + Members + WS + CharToken('}'));
static JsonGrammar() { InitGrammar(typeof(JsonGrammar)); }
}
接下来，我们需要编写一个函数，将解析树转换为 JsonObject。我们将遵循与 ArithmeticEvaluator 示例相同的基本形式。我们将只编写一个 Eval() 函数，该函数可以根据参数的标签返回任何有效的 JSON 类型（例如，数字、字符串、数组等）。
public static dynamic Eval(Node n)
{
switch (n.Label)
{
case "Name": return Eval(n[0]);
case "Value": return Eval(n[0]);
case "Number": return Eval(n[0]);
case "Integer": return Int32.Parse(n.Text);
case "Float": return Double.Parse(n.Text);
case "String": return n.Text.Substring(1, n.Text.Length - 2);
case "True": return true;
case "False": return false;
case "Null": return new JsonObject();
case "Array": return n.Nodes.Select(Eval).ToList();
case "Object":
{
var r = new JsonObject();
foreach (var pair in n.Nodes)
{
var name = pair[0].Text;
var value = Eval(pair[1]);
r[name] = value;
}
return r;
}
default:
throw new Exception("Unexpected node type " + n.Label);
}
}
编写简单的 JavaScript 解释器
最简单的解释器不过是求值函数的包装器。与 JSON 和算术求值器不同，编程语言求值器必须管理变量和函数名称。
编写 JavaScript 语法
将 JavaScript 语法派生自 JSON 语法是有意义的。某些规则需要重写，例如定义对象和数组字面量的规则，以便对象和数组中可以放置任意表达式，而不仅仅是字面量。
这是 JavaScript 语法：
public class JavaScriptGrammar : JsonGrammar
{
// Recursive rules defined at the top
public static Rule RecExpr = Recursive(() => Expr);
public static Rule RecStatement = Recursive(() => Statement);
public static Rule Literal =
Recursive(() => String | Integer | Float | Object | Array | True | False | Null);
// Redefine Identifier so that it creates nodes in the parse tree
public new static Rule Identifier = Node(SharedGrammar.Identifier);
// The following rules are redefined from JsonGrmmar because
// arbitrary expressions are allowed, not just literals
public static Rule PairName = Identifier | DoubleQuotedString | SingleQuotedString;
public new static Rule Pair = Node(PairName + WS + CharToken(':') + RecExpr + WS);
public new static Rule Array =
Node(CharToken('[') + CommaDelimited(RecExpr) + WS + CharToken(']'));
public new static Rule Object =
Node(CharToken('{') + CommaDelimited(Pair) + WS + CharToken('}'));
// Function expressions
public static Rule ParamList = Node(Parenthesize(CommaDelimited(Identifier + WS)));
public static Rule NamedFunc = Node(Keyword("function") +
Identifier + WS + ParamList + RecStatement);
public static Rule AnonFunc = Node(Keyword("function") +
ParamList + RecStatement);
public static Rule Function = NamedFunc | AnonFunc;
// Expression rules
public static Rule ArgList = Node(CharToken('(') + CommaDelimited(RecExpr) + CharToken(')'));
public static Rule Index = Node(CharToken('[') + RecExpr + CharToken(']'));
public static Rule Field = Node(CharToken('.') + Identifier);
public static Rule PrefixOp = Node(MatchStringSet("! - ~"));
public static Rule ParenExpr = Node(CharToken('(') + RecExpr + WS + CharToken(')'));
public static Rule NewExpr = Node(Keyword("new") + Recursive(() => PostfixExpr));
public static Rule LeafExpr = ParenExpr | NewExpr | Function | Literal | Identifier;
public static Rule PrefixExpr = Node(PrefixOp + Recursive(() => PrefixOrLeafExpr));
public static Rule PrefixOrLeafExpr = PrefixExpr | LeafExpr;
public static Rule PostfixOp = Field | Index | ArgList;
public static Rule PostfixExpr = Node(PrefixOrLeafExpr + WS + OneOrMore(PostfixOp + WS));
public static Rule UnaryExpr = PostfixExpr | PrefixOrLeafExpr;
public static Rule BinaryOp =
Node(MatchStringSet("<= >= == != << >> && || < > & | + - * % /"));
public static Rule BinaryExpr = Node(UnaryExpr + WS + OneOrMore(BinaryOp + WS + UnaryExpr));
public static Rule AssignOp =
Node(MatchStringSet("&&= ||= >>= <<= += -= *= %= /= &s= |= ^= ="));
public static Rule AssignExpr = Node((Identifier | PostfixExpr) + WS + AssignOp + WS + RecExpr);
public static Rule TertiaryExpr = Node((AssignExpr | BinaryExpr | UnaryExpr) +
WS + CharToken('?') + RecExpr + CharToken(':') + RecExpr + WS);
public static Rule Expr = Node((TertiaryExpr | AssignExpr | BinaryExpr | UnaryExpr) + WS);
// Statement rules
public static Rule Block = Node(CharToken('{') + ZeroOrMore(RecStatement) + CharToken('}'));
public static Rule VarDecl = Node(Keyword("var") + Identifier + WS + Opt(Eq + Expr) + Eos);
public static Rule While = Node(Keyword("while") + Parenthesize(Expr) + RecStatement);
public static Rule For = Node(Keyword("for") +
Parenthesize(VarDecl + Expr + WS + Eos + Expr + WS) + RecStatement);
public static Rule Else = Node(Keyword("else") + RecStatement);
public static Rule If = Node(Keyword("if") + Parenthesize(Expr) + RecStatement + Opt(Else));
public static Rule ExprStatement = Node(Expr + WS + Eos);
public static Rule Return = Node(Keyword("return") + Opt(Expr) + WS + Eos);
public static Rule Empty = Node(WS + Eos);
public static Rule Statement =
Block | For | While | If | Return | VarDecl | ExprStatement | Empty;
// The top-level rule
public static Rule Script = Node(ZeroOrMore(Statement) + WS + End);
// Grammar initialization
static JavaScriptGrammar()
{
InitGrammar(typeof(JavaScriptGrammar));
}
}
编写源代码打印机
给定一个由 JavaScript 解析器生成的解析树，我们可以构建的最简单的工具之一是源代码打印机。这是开发语言以验证解析器是否按预期工作的有用中间步骤。
源代码打印机（或代码格式化工具）打印输入 AST 的格式化表示。这在文本编辑器中或进行源代码到源代码转换时非常有用。
Jigsaw 库中的 Printer 类有助于编写自定义源代码翻译器。通过派生自 Printer，您只需要覆盖 Print() 函数，然后就可以根据收到的节点类型轻松生成输出。
以下代码片段摘自 JavaScriptSourcePrinter 类。
switch (n.Label)
{
case "Script":
return Print(n.Nodes);
case "Statement":
return Print(n[0]);
case "Empty":
return Print(";");
case "Return":
return (n.Count > 0)
? Print("return ").Print(n[0]).Print(";")
: Print("return;");
case "ExprStatement":
return Print(n[0]).Print(";");
case "If":
Print("if (").Print(n[0]).Print(")").Indent().Print(n[1]).Unindent();
return n.Count > 2
? Print(n[2])
: this;
case "Else":
return Print("else").Indent().Print(n[0]).Unindent();
//...
}
编写树转换器
JavaScript 解析器工作良好，尽管在求值过程中，解析树的某些部分将很难处理：
- 链式二元表达式未分离。例如，当
BinaryExpr规则遇到3 + 4 * 5时，它会将一个具有 5 个子节点的节点（3、+、4、*、5）视为一个整体，而不是（3、+、(4、*、5))，后者更容易处理。 - 链式后缀运算符未分离。例如，
f(1)["hello"].field将由PostfixExpr规则解析为（f、（1）、["hello"]、.field），而如果它是（（（f、（1））、["hello"]）、.field）则会更容易。
为了简化求值器，以及可能的其他工具，Jigsaw 库中有一个派生自 TreeTransformer 的类，名为 JSTransformer。此转换器执行多项任务：
- 将后缀表达式转换为以下一种表达式类型：
- FieldExpr——一个表达式后跟一个“.”和一个标识符。例如，“myobject.myfield”。
- IndexExpr——一个表达式后跟一个索引运算符。例如，“myarray[index]”。
- CallExpr——一个表达式后跟一个参数列表。例如，“myfunc(arg0, arg1)”。
- MethodCallExpr——一个
FieldExpr后跟一个参数列表。例如，“myobject.myfunc(arg0, arg1)”。 - 根据优先级规则分离长二元表达式。
- 将命名函数（例如，function f(x) { }）转换为 var 形式的变量声明：var f = function(x) { }。
- 将
while循环转换为for循环。 - 重写特殊赋值运算符，以便求值器仅考虑基本赋值运算符。例如，“a += b”变为“a = a + b”。
- 将只有单个子节点的节点替换为其子节点。
管理环境
当您编写编程语言的求值器时，您必须跟踪与名称（例如，函数名称、变量名称、参数名称）关联的值。值与名称的绑定统称为环境。在 Jigsaw 中，环境由一个名为 VarBindings 的类管理。您可以在 Evaluator 类中看到其用法的示例。
VarBindings 类是一个递归定义的关联列表类。它包含一个名称及其关联的值，以及指向另一个 VarBindings 类的指针。这种环境表示效率不高，但使用起来非常方便。
在 JavaScript 中，当声明一个变量时，它会被添加到变量绑定列表中。当一个“块”超出作用域时，该作用域中声明的所有名称都会被解绑。在 Jigsaw 中，这通过一个名为“EvalScoped”的函数完成。EvalScoped 函数接受另一个函数作为参数。它获取环境的快照，执行函数，然后恢复环境。
public dynamic EvalScoped(Func<dynamic> f)
{
var e = env;
var r = f();
env = e;
return r;
}
在 JavaScript 中，当一个新名称第一次使用时，会自动创建一个绑定。这可能不是一个好的语言设计决策，因为它增加了程序员出错的可能性，但我们在实现中尊重它。此逻辑由一个名为 AddOrCreateBinding() 的函数处理。
JavaScript 函数
与 JSON 不同，在实现 JavaScript 解释器时，我们必须考虑使用什么数据结构来表示函数。在 JavaScript 中，函数是闭包。这意味着函数可以引用在函数外部声明的变量。这些变量称为自由变量。
实现闭包的最简单方法之一是使用函数值声明时环境的副本。当函数应用于其参数（即被调用）时，当前求值器的环境会暂时替换为存储在函数中的版本。
此处显示了 Jigsaw 中使用的 JavaScript 函数的实现。
public class JSFunction
{
public static int FuncCount = 0;
public Node node;
public VarBindings capture;
public Node parms;
public string name = String.Format("_anonymous_{0}", FuncCount++);
public Node body;
public JSFunction(VarBindings c, Node n) {
capture = c;
node = n;
if (n.Count == 3)
{
name = n[0].Text;
parms = n[1];
body = n[2];
}
else
{
parms = n[0];
body = n[1];
}
}
public dynamic Apply(JavaScriptEvaluator e, params dynamic[] args)
{
var restore = e.env;
var originalReturningState = e.isReturning;
dynamic result = null;
try
{
e.env = capture;
e.isReturning = false;
int i = 0;
foreach (var p in parms.Nodes)
e.AddBinding(p.Text, args[i++]);
e.Eval(body);
result = e.result;
}
finally
{
e.result = null;
e.env = restore;
e.isReturning = originalReturningState;
}
return result;
}
}
返回语句
在求值一系列语句并遇到 return 语句时，您需要存储返回值并退出封闭函数。
在 JavaScript 求值器中，我们设置了一个标志（isReturning）。每当执行复合语句（例如，for 循环、while 循环等）时，都会检查此标志，以决定是否应跳过后续语句的执行。我们选择这种方法是因为它易于理解且易于实现。
一个更简单的方法是抛出异常。但是，这会使调试变得困难，并会对性能产生显着负面影响。
更有效的方法是重写解析树，使其在函数末尾只有一个“return”语句。这有点复杂，因为它需要添加额外的变量并重写任何循环条件，但复杂性将从求值函数转移到转换器。
求值函数
JavaScript 求值函数在结构上与 JsonObject.Eval() 函数类似，但有以下区别：
- 节点树被转换为一种更容易求值的形式。
- 变量在一个
VarBindings对象中管理。 - 引入了一种新的数据类型（
JSFunction）。
求值函数太长，无法在此列出，但这是一个有代表性的片段。
case "AnonFunc":
// Creates an unnamed function
return new JSFunction(env, n);
case "Block":
// Execute a sequence of instructions
return EvalScoped(() => EvalNodes(n.Nodes));
case "If":
// Check if the condition is false (or NULL)
if (Eval(n[0]) ?? false)
// Execute first statement
return Eval(n[1]);
else if (n.Count > 2)
// Execute else statement if the condition is false, and it exists
return Eval(n[2]);
else
// By default reutrn the result
return null;
case "VarDecl":
// Variable declaration
// It may or may not be initialized
return AddBinding(n[0].Text, n.Count > 1 ? Eval(n[1]) : null);
case "Empty":
// An empty statement means we do nothing
return null;
case "ExprStatement":
return Eval(n[0]);
扩展原始集
提供的求值器仅实现了基本运算符，并且只有一个内置函数“alert”。内置函数使用 JSPrimitive 类实现，并在初始化求值器时添加到全局环境中。
public JavaScriptEvaluator()
{
// This is where you could add all sorts
// of primitive objects and functions. Or don't. Fine.
AddBinding("alert", new JSPrimitive(args => { Console.WriteLine(args[0]); }));
}
JavaScript 到表达式树编译器
System.Linq.Expressions 命名空间中的 Expression 类（也称为表达式树）是一种在运行时动态创建新函数的便捷方法。通过将解析树转换为表达式树，我们可以使用 Expression.Compile() 函数在运行时创建委托，然后使用 DynamicInvoke() 执行这些委托。
生成表达式树与求值类似，除了不是为每个节点返回一个动态值，而是返回一个 Expression 类的实例。表达式编译器可以派生自 ExpressionCompiler 实用类。
Jigsaw 库中的示例 JavaScript 到表达式编译器 JavaScriptExpressionCompiler 提供了两个编译函数，一个接受 string，另一个接受 Node。
public static Delegate CompileLambda(string s)
{
var nodes = JavaScriptGrammar.AnonFunc.Parse(s);
return CompileLambda(nodes[0]);
}
public static Delegate CompileLambda(Node n)
{
n = JavaScriptTransformer.Transform(n);
var compiler = new JavaScriptExpressionCompiler();
var expr = (LambdaExpression)compiler.ToExpr(n);
if (expr == null) return null;
return expr.Compile();
}
请注意，与求值函数一样，Transform 用于在进入将每个 Node 转换为 Expression 的“ToExpr”函数之前简化解析树。
后续步骤
JavaScript 解释器和表达式编译器未实现许多 JavaScript 功能。为了进一步学习，您可以扩展提供的示例来实现更多功能，或添加您可能感兴趣的编程语言功能。
希望您已经学到了足够的知识，可以开始尝试创建自己的语言。
Jigsaw 库中还包含一些其他示例，您可能会觉得有趣：
- ILCompiler.cs——一个 IL 程序集代码的实现。
- SchemeExpressionCompiler.cs——一个简单的表达式编译器，适用于 Scheme 语言的一小部分。Scheme 是 LISP 的一种方言。
- CatEvaluator.cs——包含 Cat 语言的求值器，Cat 是一种简单的函数式基于堆栈的语言。
结语
本文档仅触及了编程语言实现表面的皮毛。如果您喜欢本文档，并希望了解更多关于编程语言实现的信息，您可能会对得知我正在撰写一本题为“使用 C# 实现编程语言”的书感兴趣。如果您想了解更多信息、成为测试版审阅者，或者只是表示支持，请发送电子邮件至 cdiggins@gmail.com。谢谢！
历史
- 2011 年 10 月 22 日 - 首次提交。
- 2011 年 10 月 23 日 - 从下载包中删除了多余的文件，并添加了下载的缺失链接。
- 2011 年 10 月 28 日 - 在 Tracey Houston 的详细评审下进行了大量编辑。谢谢 Tracey！
- 2011 年 12 月 27 日 - 在 David Haguenauer 的详细评审下进行了大量编辑。谢谢 David，抱歉我花这么长时间才添加它们！