为什么我的递归下降解析器是右关联的
Why is my recursive descent parser right-associative
我正在编写我自己的编程语言，并且我已经完成了分词器（词法分析器）。但是对于解析，我在编写递归下降解析器时遇到了麻烦。好像是右结合，什么时候该左结合，不知道为什么。例如，它将 1-2-3 解析为 1-(2-3)，而不是正确的 (1-2)-3.
我已经删除了大部分其他代码，只留下可重现的代码：
using System.Collections.Generic;
namespace Phi
{
public enum TokenType
{
Plus, // '+'
Minus, // '-'
IntegerLiteral,
}
public interface INode
{
// Commented out as they aren't relevant
//NodeType GetNodeType();
//void Print(string indent, bool last);
}
class Program
{
static void Main(string[] args)
{
List<Token> tokens = new List<Token>()
{
new Token(TokenType.IntegerLiteral, "1"),
new Token(TokenType.Minus, ""),
new Token(TokenType.IntegerLiteral, "2"),
new Token(TokenType.Minus, ""),
new Token(TokenType.IntegerLiteral, "3"),
};
int consumed = ParseAdditiveExpression(tokens, out INode root);
}
private static int ParseAdditiveExpression(List<Token> block, out INode node)
{
// <additiveExpr> ::= <multiplicativeExpr> <additiveExprPrime>
int consumed = ParseMultiplicataveExpression(block, out INode left);
consumed += ParseAdditiveExpressionPrime(GetListSubset(block, consumed), out INode right);
if (block[1].Type == TokenType.Plus)
node = (right == null) ? left : new AdditionNode(left, right);
else
node = (right == null) ? left : new SubtractionNode(left, right);
return consumed;
}
private static int ParseAdditiveExpressionPrime(List<Token> block, out INode node)
{
// <additiveExprPrime> ::= "+" <multiplicataveExpr> <additiveExprPrime>
// ::= "-" <multiplicativeExpr> <additiveExprPrime>
// ::= epsilon
node = null;
if (block.Count == 0)
return 0;
if (block[0].Type != TokenType.Plus && block[0].Type != TokenType.Minus)
return 0;
int consumed = 1 + ParseMultiplicataveExpression(GetListSubset(block, 1), out INode left);
consumed += ParseAdditiveExpressionPrime(GetListSubset(block, consumed), out INode right);
if (block[0].Type == TokenType.Plus)
node = (right == null) ? left : new AdditionNode(left, right);
else
node = (right == null) ? left : new SubtractionNode(left, right);
return consumed;
}
private static int ParseMultiplicataveExpression(List<Token> block, out INode node)
{
// <multiplicativeExpr> ::= <castExpr> <multiplicativeExprPrime>
// unimplemented; all blocks are `Count == 1` with an integer
node = new IntegerLiteralNode(block[0].Value);
return 1;
}
private static List<T> GetListSubset<T>(List<T> list, int start)
{
return list.GetRange(start, list.Count - start);
}
}
}
至于AdditionNode、SubtractionNode、MultiplicationNode的定义都是一样的，只是为了语义。为简洁起见，这里只是 AdditionNode:
namespace Phi
{
public class AdditionNode : INode
{
public AdditionNode(INode left, INode right)
{
Left = left;
Right = right;
}
public INode Left { get; }
public INode Right { get; }
// Print and GetNodeType have been removed as they aren't relevant
}
}
至于我的问题，当我运行 Phi.Program，如开头所说，它是用错误的关联性解析的。这是 ParseAdditiveExpression 完成后的 root:
如您所见，它将 2 与 3 分组，而不是 1。为什么要这样做？
正如我在评论中指出的那样，问题是您混淆了二元运算符 的 最右边的 child 和 最右边的 child 加法素数。二元运算符最右边的 child 是一个 表达式 。 additiveprime 的最右侧是一个 additiveprime，因此仅根据“树节点类型”我们必须得出结论，您构建了错误的解析树。
跟踪每个解析工件的“逻辑类型”是一种用于查找解析器错误的强大技术。另一个我喜欢但不幸未被充分利用的方法是 将程序中的每个标记都归因于一个解析树节点 。如果这样做，您很快就会意识到运算符的标记在逻辑上位于 两个 位置：在二元运算符中，以及最右边的 child。这也告诉我们出了点问题。
没有帮助的是您的解析基础结构是传递数字和输出参数的一团糟。 您的解析器缺乏纪律。您的解析器代码看起来像 计数标记 是解析器所做的最重要的事情，其他一切都是偶然的。
解析是一个非常棘手的问题，解析器方法应该做一件事，只做一件事，并且做得完美。解析器的结构，以及每个方法的结构，应该直接反映被解析的语法。解析器中应该几乎没有整数运算，因为解析是关于构建解析树，而不是计算标记。
我以构建递归下降解析器为生。让我向您展示我将如何构建此解析器，如果我出于自己的目的快速构建它的话。 （如果我是为生产应用程序构建它，它在很多方面都会有所不同，但我们在这里很容易理解。）
好的，让我们开始吧。第一件事是：当你卡在一个问题上时，解决一个更简单的问题。让我们用以下方式简化问题：
- 假设令牌流是一个well-formed程序。没有错误检测。
- 令牌是字符串。
- 语法是：
E ::= T E', E' ::= + T E' | nil，T是一个由单个标记组成的术语。
好的。 首先创建代表这些事物的类型。
sealed class Term : ParseTree
{
public string Value { get; private set; }
public Term(string value) { this.Value = value; }
public override string ToString() { return this.Value; }
}
sealed class Additive : ParseTree
{
public ParseTree Term { get; private set; }
public ParseTree Prime { get; private set; }
public Additive(ParseTree term, ParseTree prime) {
this.Term = term;
this.Prime = prime;
}
public override string ToString() { return "" + this.Term + this.Prime; }
}
sealed class AdditivePrime : ParseTree
{
public string Operator { get; private set; }
public ParseTree Term { get; private set; }
public ParseTree Prime { get; private set; }
public AdditivePrime(string op, ParseTree term, ParseTree prime) {
this.Operator = op;
this.Term = term;
this.Prime = prime;
}
public override string ToString() { return this.Operator + this.Term + this.Prime; }
}
sealed class Nil : ParseTree
{
public override string ToString() { return ""; }
}
注意几点：
- 摘要class是摘要。
- 混凝土 class 已密封。
- 一切都是不可变的。
- 一切都知道如何打印自己。
- 没有空值！ 没有空值。空值会导致崩溃。您有一个名为 nil 的产生式，因此创建一个名为
Nil 的类型来表示它。
下一步：从用户的角度来看，我们希望解析器看起来像什么？我们想要一个标记序列进入，我们想要一个解析树出来。伟大的。所以public表面应该是：
sealed class Parser
{
public Parser(List<string> tokens) { ... }
public ParseTree Parse() { ... }
}
如果我们做对了所有事情，那么调用站点将如下所示：
public static void Main()
{
var tokens = new List<string>() { "1" , "+" , "2" , "+" , "3" , "+" , "4"};
var parser = new Parser(tokens);
var result = parser.Parse();
System.Console.WriteLine(result);
}
超级棒。现在我们要做的就是实现它。
解析器跟踪标记列表和正在考虑的当前标记。 不要在不同的方法之间随意修改这些信息。它在逻辑上是解析器的一部分，因此将其保留在解析器中。
public sealed class Parser
{
private List<string> tokens;
private int current;
public Parser(List<string> tokens)
{
this.tokens = tokens;
this.current = 0;
}
该语言目前仅包含加法表达式，因此：
public ParseTree Parse()
{
return ParseAdditive();
}
太好了，我们已经完成了解析器的两个成员。现在，ParseAdditive 做什么？ 它按照锡盒上的说明进行操作。它解析一个加法表达式，该表达式具有语法 E:: T E'，所以这就是它现在所做的以及它所做的所有事情。
private ParseTree ParseAdditive()
{
var term = ParseTerm();
var prime = ParseAdditivePrime();
return new Additive(term, prime);
}
如果您的解析器方法看起来不是非常简单，那么您做错了什么。递归下降解析器的全部要点是易于理解和易于实现。
现在我们可以看看如何实现ParseTerm()；它只消耗一个令牌：
private string Consume()
{
var t = this.tokens[this.current];
this.current += 1;
return t;
}
private ParseTree ParseTerm() {
return new Term(Consume());
}
同样，我们假设令牌流格式正确。当然，如果它是 ill-formed，这会崩溃，但这是另一天的问题。
最后，最后一个有点难，因为有两种情况。
private bool OutOfTokens()
{
return this.current >= this.tokens.Count;
}
private ParseTree ParseAdditivePrime()
{
if (OutOfTokens())
return new Nil();
var op = Consume();
var term = ParseTerm();
var prime = ParseAdditivePrime();
return new AdditivePrime(op, term, prime);
}
这么简单。同样，您的所有方法都应该与它们所做的完全一样。
注意我没有写
private ParseTree ParseAdditivePrime()
{
if (this.current >= this.tokens.Count)
return new Nil();
让程序的文本像它正在执行的操作一样阅读。我们想知道什么？ 我们的代币用完了吗？所以说。不要让 reader -- 你自己 -- 必须考虑哦，我的意思是 > 或 < 或 <= 还是...只是不要。解决问题一次，将解决方案放在名字好听的方法中，然后调用te 方法。您未来的自己会感谢过去的自己的照顾。
另请注意，我没有编写 C# 7 super slick：
private ParseTree ParseAdditivePrime() =>
OutOfTokens() ? new Nil() : new AdditivePrime(Consume(), ParseTerm(), ParseAdditivePrime());
您 可以 将您的解析器方法编写为 one-liners 这表明您已经设计了一个好的解析器，但这并不意味着您 应该。如果将解析器保持在顺序语句形式而不是华而不实的小 one-liners，通常更容易理解和调试解析器。运用良好的判断力。
好的，我们已经解决了更简单的问题！现在让我们解决一个稍微更难的问题。我们已经解决了解析语法E ::= T E', E' ::= + T E' | nil，但是我们想要解析的语法是B :: T | B + T.
请注意，我没有混淆 E，它是 term-and-suffix，而 B 是 T 或 B、一个 + 和一个 T。由于B和E不同，所以用不同的类型来表示。
让我们为 B 创建一个类型：
sealed class Binary : ParseTree
{
public ParseTree Left { get; private set; }
public string Operator { get; private set; }
public ParseTree Right { get; private set; }
public Binary(ParseTree left, string op, ParseTree right)
{
this.Left = left;
this.Operator = op;
this.Right = right;
}
public override string ToString()
{
return "(" + Left + Operator + Right + ")";
}
}
请注意，我在输出中添加了括号作为视觉辅助，以帮助我们看到它是左关联的。
现在，假设我们手头有一个 Additive，我们需要一个 Binary。 我们要怎么做？
加法总是一个项和一个素数。所以有两种情况。素数要么为零，要么不是。
如果质数为零，那么我们就完成了：在需要 Binary 的地方，Term 是可以接受的，因此我们可以将项传回。
如果素数不为零则素数为op, term, prime。 我们必须以某种方式从中得到一个 Binary。二进制文件需要三样东西。 记住，我们将每个令牌都归于一个节点，所以这将帮助我们弄清楚。
- 我们从加法中得到了左项。
- 我们有来自素数的 op。
- 我们从质数中得到了正确的任期。
但这就把质数的质数抛在脑后了！我们需要为此做点什么。让我们推理一下。同样，有两种情况：
- 如果质数的质数为零，则结果为二进制。
- 如果素数的素数不为零，那么结果是一个新的二进制，左边是旧的二进制，并且... 等一下，这与我们刚才描述的算法相同用于将加法转换为二进制.
我们刚刚发现这个算法是递归的，一旦你意识到写起来很简单：
private static ParseTree AdditiveToBinary(ParseTree left, ParseTree prime)
{
if (prime is Nil) return left;
var reallyprime = (AdditivePrime) prime;
var binary = new Binary(left, reallyprime.Operator, reallyprime.Term);
return AdditiveToBinary(binary, reallyprime.Prime);
}
现在我们修改 ParseAdditive:
private ParseTree ParseAdditive()
{
var term = ParseTerm();
var prime = ParseAdditivePrime();
return AdditiveToBinary(term, prime);
}
和运行它：
(((1+2)+3)+4)
我们完成了。
嗯，不完全是。 ParseAdditive 不再像罐头上所说的那样做！它说 ParseAdditive 但它 returns 一个 Binary.
事实上...我们真的需要Additive吗？我们可以从解析器中完全消除它吗？事实上我们可以；我们现在 从不创建 Additive 的实例，因此可以将其删除，并且 ParseAdditive 可以重命名 ParseBinary.
在使用“解决一个更简单的问题”的技术构建程序时，经常会发生这种情况。您最终能够扔掉您之前的工作，这是 很棒 。删除的代码没有错误。
- 练习：将运算符表示为字符串很恶心。制作一个类似于
Term的Operator class，以及一个解析运算符的方法。 不断提高解析器的抽象级别，使其远离具体字符串并进入解析器的业务领域。与代币类似；它们不应该是字符串。
- 练习：我们已经解决了一个稍微难一点的问题，所以请继续。你现在可以加乘法了吗？
- 练习：你能解析一种混合了左右结合运算符的语言吗？
一些额外的想法：
我猜你这样做是为了自己的乐趣，还是为了学校作业。 不要将我的作品复制粘贴到您的作业中。那是学术造假。 如果作品不完全属于您自己，请记住在提交时正确注明所有作品的属性。
如果您只是为了好玩，那就尽情享受设计语言的乐趣吧！这是一个很好的爱好，如果你真的很幸运，总有一天会有人付钱让你去做。
你在设计自己的语言，所以你不必重蹈过去的覆辙。例如，我注意到您的评论表明您将添加强制转换表达式。如果您喜欢 C、C++、C#、Java 等，欢迎来到痛苦的世界。所有这些语言都必须让它们的解析器消除 (x)+y 之间的歧义，意思是“对 y 应用一元加号并将其转换为 x”，以及“将数量 (x) 添加到 y”。这是一个很大的痛苦。考虑一种更好的强制转换语法，例如 as 运算符。另外，检查演员表的含义；在 C# 中，强制转换意味着两者都“生成表示相同值的不同类型的实例”和“我断言这个东西的 运行time 类型与其编译时类型不同；如果我错了就抛出”。这些操作完全不同，但它们具有相同的语法。所有的语言都是对以前语言的回应，好好想想自己喜欢什么因为熟悉 vs 因为好.
我正在编写我自己的编程语言，并且我已经完成了分词器（词法分析器）。但是对于解析，我在编写递归下降解析器时遇到了麻烦。好像是右结合，什么时候该左结合，不知道为什么。例如，它将 1-2-3 解析为 1-(2-3)，而不是正确的 (1-2)-3.
我已经删除了大部分其他代码，只留下可重现的代码：
using System.Collections.Generic;
namespace Phi
{
public enum TokenType
{
Plus, // '+'
Minus, // '-'
IntegerLiteral,
}
public interface INode
{
// Commented out as they aren't relevant
//NodeType GetNodeType();
//void Print(string indent, bool last);
}
class Program
{
static void Main(string[] args)
{
List<Token> tokens = new List<Token>()
{
new Token(TokenType.IntegerLiteral, "1"),
new Token(TokenType.Minus, ""),
new Token(TokenType.IntegerLiteral, "2"),
new Token(TokenType.Minus, ""),
new Token(TokenType.IntegerLiteral, "3"),
};
int consumed = ParseAdditiveExpression(tokens, out INode root);
}
private static int ParseAdditiveExpression(List<Token> block, out INode node)
{
// <additiveExpr> ::= <multiplicativeExpr> <additiveExprPrime>
int consumed = ParseMultiplicataveExpression(block, out INode left);
consumed += ParseAdditiveExpressionPrime(GetListSubset(block, consumed), out INode right);
if (block[1].Type == TokenType.Plus)
node = (right == null) ? left : new AdditionNode(left, right);
else
node = (right == null) ? left : new SubtractionNode(left, right);
return consumed;
}
private static int ParseAdditiveExpressionPrime(List<Token> block, out INode node)
{
// <additiveExprPrime> ::= "+" <multiplicataveExpr> <additiveExprPrime>
// ::= "-" <multiplicativeExpr> <additiveExprPrime>
// ::= epsilon
node = null;
if (block.Count == 0)
return 0;
if (block[0].Type != TokenType.Plus && block[0].Type != TokenType.Minus)
return 0;
int consumed = 1 + ParseMultiplicataveExpression(GetListSubset(block, 1), out INode left);
consumed += ParseAdditiveExpressionPrime(GetListSubset(block, consumed), out INode right);
if (block[0].Type == TokenType.Plus)
node = (right == null) ? left : new AdditionNode(left, right);
else
node = (right == null) ? left : new SubtractionNode(left, right);
return consumed;
}
private static int ParseMultiplicataveExpression(List<Token> block, out INode node)
{
// <multiplicativeExpr> ::= <castExpr> <multiplicativeExprPrime>
// unimplemented; all blocks are `Count == 1` with an integer
node = new IntegerLiteralNode(block[0].Value);
return 1;
}
private static List<T> GetListSubset<T>(List<T> list, int start)
{
return list.GetRange(start, list.Count - start);
}
}
}
至于AdditionNode、SubtractionNode、MultiplicationNode的定义都是一样的，只是为了语义。为简洁起见，这里只是 AdditionNode:
namespace Phi
{
public class AdditionNode : INode
{
public AdditionNode(INode left, INode right)
{
Left = left;
Right = right;
}
public INode Left { get; }
public INode Right { get; }
// Print and GetNodeType have been removed as they aren't relevant
}
}
至于我的问题，当我运行 Phi.Program，如开头所说，它是用错误的关联性解析的。这是 ParseAdditiveExpression 完成后的 root:
如您所见，它将 2 与 3 分组，而不是 1。为什么要这样做？
正如我在评论中指出的那样，问题是您混淆了二元运算符 的 最右边的 child 和 最右边的 child 加法素数。二元运算符最右边的 child 是一个 表达式 。 additiveprime 的最右侧是一个 additiveprime，因此仅根据“树节点类型”我们必须得出结论，您构建了错误的解析树。
跟踪每个解析工件的“逻辑类型”是一种用于查找解析器错误的强大技术。另一个我喜欢但不幸未被充分利用的方法是 将程序中的每个标记都归因于一个解析树节点 。如果这样做，您很快就会意识到运算符的标记在逻辑上位于 两个 位置：在二元运算符中，以及最右边的 child。这也告诉我们出了点问题。
没有帮助的是您的解析基础结构是传递数字和输出参数的一团糟。 您的解析器缺乏纪律。您的解析器代码看起来像 计数标记 是解析器所做的最重要的事情，其他一切都是偶然的。
解析是一个非常棘手的问题，解析器方法应该做一件事，只做一件事，并且做得完美。解析器的结构，以及每个方法的结构，应该直接反映被解析的语法。解析器中应该几乎没有整数运算，因为解析是关于构建解析树，而不是计算标记。
我以构建递归下降解析器为生。让我向您展示我将如何构建此解析器，如果我出于自己的目的快速构建它的话。 （如果我是为生产应用程序构建它，它在很多方面都会有所不同，但我们在这里很容易理解。）
好的，让我们开始吧。第一件事是：当你卡在一个问题上时，解决一个更简单的问题。让我们用以下方式简化问题：
- 假设令牌流是一个well-formed程序。没有错误检测。
- 令牌是字符串。
- 语法是：
E ::= T E', E' ::= + T E' | nil，T是一个由单个标记组成的术语。
好的。 首先创建代表这些事物的类型。
sealed class Term : ParseTree
{
public string Value { get; private set; }
public Term(string value) { this.Value = value; }
public override string ToString() { return this.Value; }
}
sealed class Additive : ParseTree
{
public ParseTree Term { get; private set; }
public ParseTree Prime { get; private set; }
public Additive(ParseTree term, ParseTree prime) {
this.Term = term;
this.Prime = prime;
}
public override string ToString() { return "" + this.Term + this.Prime; }
}
sealed class AdditivePrime : ParseTree
{
public string Operator { get; private set; }
public ParseTree Term { get; private set; }
public ParseTree Prime { get; private set; }
public AdditivePrime(string op, ParseTree term, ParseTree prime) {
this.Operator = op;
this.Term = term;
this.Prime = prime;
}
public override string ToString() { return this.Operator + this.Term + this.Prime; }
}
sealed class Nil : ParseTree
{
public override string ToString() { return ""; }
}
注意几点：
- 摘要class是摘要。
- 混凝土 class 已密封。
- 一切都是不可变的。
- 一切都知道如何打印自己。
- 没有空值！ 没有空值。空值会导致崩溃。您有一个名为 nil 的产生式，因此创建一个名为
Nil的类型来表示它。
下一步：从用户的角度来看，我们希望解析器看起来像什么？我们想要一个标记序列进入，我们想要一个解析树出来。伟大的。所以public表面应该是：
sealed class Parser
{
public Parser(List<string> tokens) { ... }
public ParseTree Parse() { ... }
}
如果我们做对了所有事情，那么调用站点将如下所示：
public static void Main()
{
var tokens = new List<string>() { "1" , "+" , "2" , "+" , "3" , "+" , "4"};
var parser = new Parser(tokens);
var result = parser.Parse();
System.Console.WriteLine(result);
}
超级棒。现在我们要做的就是实现它。
解析器跟踪标记列表和正在考虑的当前标记。 不要在不同的方法之间随意修改这些信息。它在逻辑上是解析器的一部分，因此将其保留在解析器中。
public sealed class Parser
{
private List<string> tokens;
private int current;
public Parser(List<string> tokens)
{
this.tokens = tokens;
this.current = 0;
}
该语言目前仅包含加法表达式，因此：
public ParseTree Parse()
{
return ParseAdditive();
}
太好了，我们已经完成了解析器的两个成员。现在，ParseAdditive 做什么？ 它按照锡盒上的说明进行操作。它解析一个加法表达式，该表达式具有语法 E:: T E'，所以这就是它现在所做的以及它所做的所有事情。
private ParseTree ParseAdditive()
{
var term = ParseTerm();
var prime = ParseAdditivePrime();
return new Additive(term, prime);
}
如果您的解析器方法看起来不是非常简单，那么您做错了什么。递归下降解析器的全部要点是易于理解和易于实现。
现在我们可以看看如何实现ParseTerm()；它只消耗一个令牌：
private string Consume()
{
var t = this.tokens[this.current];
this.current += 1;
return t;
}
private ParseTree ParseTerm() {
return new Term(Consume());
}
同样，我们假设令牌流格式正确。当然，如果它是 ill-formed，这会崩溃，但这是另一天的问题。
最后，最后一个有点难，因为有两种情况。
private bool OutOfTokens()
{
return this.current >= this.tokens.Count;
}
private ParseTree ParseAdditivePrime()
{
if (OutOfTokens())
return new Nil();
var op = Consume();
var term = ParseTerm();
var prime = ParseAdditivePrime();
return new AdditivePrime(op, term, prime);
}
这么简单。同样，您的所有方法都应该与它们所做的完全一样。
注意我没有写
private ParseTree ParseAdditivePrime()
{
if (this.current >= this.tokens.Count)
return new Nil();
让程序的文本像它正在执行的操作一样阅读。我们想知道什么？ 我们的代币用完了吗？所以说。不要让 reader -- 你自己 -- 必须考虑哦，我的意思是 > 或 < 或 <= 还是...只是不要。解决问题一次，将解决方案放在名字好听的方法中，然后调用te 方法。您未来的自己会感谢过去的自己的照顾。
另请注意，我没有编写 C# 7 super slick：
private ParseTree ParseAdditivePrime() =>
OutOfTokens() ? new Nil() : new AdditivePrime(Consume(), ParseTerm(), ParseAdditivePrime());
您 可以 将您的解析器方法编写为 one-liners 这表明您已经设计了一个好的解析器，但这并不意味着您 应该。如果将解析器保持在顺序语句形式而不是华而不实的小 one-liners，通常更容易理解和调试解析器。运用良好的判断力。
好的，我们已经解决了更简单的问题！现在让我们解决一个稍微更难的问题。我们已经解决了解析语法E ::= T E', E' ::= + T E' | nil，但是我们想要解析的语法是B :: T | B + T.
请注意，我没有混淆 E，它是 term-and-suffix，而 B 是 T 或 B、一个 + 和一个 T。由于B和E不同，所以用不同的类型来表示。
让我们为 B 创建一个类型：
sealed class Binary : ParseTree
{
public ParseTree Left { get; private set; }
public string Operator { get; private set; }
public ParseTree Right { get; private set; }
public Binary(ParseTree left, string op, ParseTree right)
{
this.Left = left;
this.Operator = op;
this.Right = right;
}
public override string ToString()
{
return "(" + Left + Operator + Right + ")";
}
}
请注意，我在输出中添加了括号作为视觉辅助，以帮助我们看到它是左关联的。
现在，假设我们手头有一个 Additive，我们需要一个 Binary。 我们要怎么做？
加法总是一个项和一个素数。所以有两种情况。素数要么为零，要么不是。
如果质数为零，那么我们就完成了：在需要 Binary 的地方，Term 是可以接受的，因此我们可以将项传回。
如果素数不为零则素数为op, term, prime。 我们必须以某种方式从中得到一个 Binary。二进制文件需要三样东西。 记住，我们将每个令牌都归于一个节点，所以这将帮助我们弄清楚。
- 我们从加法中得到了左项。
- 我们有来自素数的 op。
- 我们从质数中得到了正确的任期。
但这就把质数的质数抛在脑后了！我们需要为此做点什么。让我们推理一下。同样，有两种情况：
- 如果质数的质数为零，则结果为二进制。
- 如果素数的素数不为零，那么结果是一个新的二进制，左边是旧的二进制，并且... 等一下，这与我们刚才描述的算法相同用于将加法转换为二进制.
我们刚刚发现这个算法是递归的，一旦你意识到写起来很简单：
private static ParseTree AdditiveToBinary(ParseTree left, ParseTree prime)
{
if (prime is Nil) return left;
var reallyprime = (AdditivePrime) prime;
var binary = new Binary(left, reallyprime.Operator, reallyprime.Term);
return AdditiveToBinary(binary, reallyprime.Prime);
}
现在我们修改 ParseAdditive:
private ParseTree ParseAdditive()
{
var term = ParseTerm();
var prime = ParseAdditivePrime();
return AdditiveToBinary(term, prime);
}
和运行它：
(((1+2)+3)+4)
我们完成了。
嗯，不完全是。 ParseAdditive 不再像罐头上所说的那样做！它说 ParseAdditive 但它 returns 一个 Binary.
事实上...我们真的需要Additive吗？我们可以从解析器中完全消除它吗？事实上我们可以；我们现在 从不创建 Additive 的实例，因此可以将其删除，并且 ParseAdditive 可以重命名 ParseBinary.
在使用“解决一个更简单的问题”的技术构建程序时，经常会发生这种情况。您最终能够扔掉您之前的工作，这是 很棒 。删除的代码没有错误。
- 练习：将运算符表示为字符串很恶心。制作一个类似于
Term的Operatorclass，以及一个解析运算符的方法。 不断提高解析器的抽象级别，使其远离具体字符串并进入解析器的业务领域。与代币类似；它们不应该是字符串。 - 练习：我们已经解决了一个稍微难一点的问题，所以请继续。你现在可以加乘法了吗？
- 练习：你能解析一种混合了左右结合运算符的语言吗？
一些额外的想法：
我猜你这样做是为了自己的乐趣，还是为了学校作业。 不要将我的作品复制粘贴到您的作业中。那是学术造假。 如果作品不完全属于您自己，请记住在提交时正确注明所有作品的属性。
如果您只是为了好玩，那就尽情享受设计语言的乐趣吧！这是一个很好的爱好，如果你真的很幸运，总有一天会有人付钱让你去做。
你在设计自己的语言，所以你不必重蹈过去的覆辙。例如，我注意到您的评论表明您将添加强制转换表达式。如果您喜欢 C、C++、C#、Java 等，欢迎来到痛苦的世界。所有这些语言都必须让它们的解析器消除
(x)+y之间的歧义，意思是“对 y 应用一元加号并将其转换为x”，以及“将数量(x)添加到y”。这是一个很大的痛苦。考虑一种更好的强制转换语法，例如as运算符。另外，检查演员表的含义；在 C# 中，强制转换意味着两者都“生成表示相同值的不同类型的实例”和“我断言这个东西的 运行time 类型与其编译时类型不同；如果我错了就抛出”。这些操作完全不同，但它们具有相同的语法。所有的语言都是对以前语言的回应，好好想想自己喜欢什么因为熟悉 vs 因为好.