为什么我的递归下降分析器是右关联的

正如我在评论中指出的,问题是你 二元运算符的最右边的子项 具有 加法时间中最右边的子项 . 二进制运算符的最右边的子项是 表达 。加法时间的最右边是 加法时间 ,因此仅就“树节点类型”而言,我们必须断定您构建了错误的解析树。

跟踪每个解析工件的“逻辑类型”是在解析器中查找错误的强大技术。另一个我喜欢的,可悲的是没有被充分利用 将程序中的每个标记都精确地赋给一个解析树节点 。如果你这样做了,你会很快意识到操作符的标记在逻辑上是 二 位置:在二进制运算符及其最右边的子运算符中。这也告诉我们出了问题。

不起作用的是,用于解析的基础结构是一个传递数字和参数的糟糕的混乱。 您的解析器缺乏纪律性 . 您的解析器代码看起来像 计数令牌 是解析器所做的最重要的事情,其他的事情都是附带的。

解析是 非常清晰的问题 ,解析器方法应该做一件事,只做一件事,并且做得完美。解析器的结构和每个方法的结构应该 直接地 反映正在分析的语法。应该有 几乎没有整数运算 在解析器中,因为解析是关于构建一个解析树,而不是关于计算令牌。

我以构建递归下降分析器为生。让我向您展示如何构建这个解析器,如果我为了自己的目的快速构建它的话。(如果我为生产应用程序构建它,它在许多方面都会有所不同,但我们在这里会更容易理解。)

好吧,我们开始吧。首先是: 当你困在一个问题上,解决一个更简单的问题 . 让我们用以下方式简化这个问题:

• 假设令牌流是格式良好的程序。没有错误检测。
• 标记是字符串。
• 语法是: 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 ""; }
}

注意以下几点:

• 抽象类是抽象的。
• 混凝土类是密封的。
• 一切都是不变的。
• 一切都知道如何打印。
• 没有空! 无空值 . 空值导致崩溃。你有一个名为nil的产品,所以创建一个名为 Nil 代表它。

下一步:我们希望解析器从用户的角度看是什么样的?我们想要一个令牌序列进入,我们想要一个解析树出来。伟大的。因此,公众面应该是:

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

同样,我们假设令牌流是格式良好的。当然,如果这是一个错误的形式,这将崩溃,但这是一个问题的另一天。

最后,最后一个有点难,因为有两个案例。

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

使程序的文本读起来像它正在执行的操作一样 。我们想知道什么? 我们的代币用完了吗? 所以 说 . 别让读者——你自己——不得不考虑哦,我是说 > 或 < 或 <= 或者…别这样。解决问题 一旦 ,将解决方案放入一个名称正确的方法中,然后调用该方法。你未来的自我会感谢你过去的自我对你的照顾。

还请注意,我没有写C 7超级光滑:

private ParseTree ParseAdditivePrime() => 
  OutOfTokens() ? new Nil() : new AdditivePrime(Consume(), ParseTerm(), ParseAdditivePrime());

那就是你 可以 将解析器方法编写为一行是设计了一个好的解析器的标志,但这并不意味着 应该 . 如果保持解析器的顺序语句形式,而不是简单的一行代码,那么它通常更容易理解和调试。做出正确的判断。

好的,我们已经解决了更简单的问题!现在我们来解决一个 轻微地 更难的问题。我们已经解决了语法分析问题 E::=T E',E':=+T E'零 ,但是语法我们 希望 解析是 B :: T | B + T .

注意,我并不困惑 E ,这是一个带有 B ,或者是 T 或A 乙 A + 和A T . 自从 乙 和 e 是不同的,用不同的类型来表示。

让我们为 乙 :

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 . 我们要怎么做 ?

加法总是一个项和一个素数。所以有两个案子。要么素数是零,要么不是。

如果素数为零,我们就结束了:a Term 在以下情况下是可以接受的 二元的 是必需的,这样我们就可以把这个词传回去了。

如果素数不是零,那么素数就是op,term,prime。 我们总得找个 二元的 从那 。一个二进制需要三样东西。 记住,我们将每个令牌都赋给一个节点 ,所以这将帮助我们找到答案。

• 我们有加法中的左项。
• 我们的手术是从黄金时期开始的。
• 我们从黄金时期就有了合适的任期。

但这就把素数的素数抛在后面了!我们需要做点什么。我们来解释一下。同样,有两种情况:

• 如果素数的素数是零,那么结果就是二进制数。
• 如果素数的素数不是零,则结果是一个新的二进制数,旧的二进制数在左边,并且… 等等,这和我们刚才描述的把加法转换成二进制的算法是一样的 .

我们刚刚发现,这个算法是递归的,一旦你意识到写这个算法很简单:

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

现在我们修改了 分析添加剂 :

private ParseTree ParseAdditive()
{
    var term = ParseTerm();
    var prime = ParseAdditivePrime();
    return AdditiveToBinary(term, prime);       
}     

运行它:

(((1+2)+3)+4)

我们结束了。

嗯,不完全是。 分析添加剂 别再做罐头上写的事了!它说 分析添加剂 但它返回一个 二元的 .

事实上… 我们需要 添加剂 完全 ?我们可以从解析器中完全消除它吗?事实上我们可以;我们现在 从不创建的实例 添加剂 ,所以它可以被删除,并且 分析添加剂 可以重命名 ParseBinary .

当使用“解决更简单的问题”的技术构造程序时,经常会发生这种情况。你最终可以丢掉你以前的工作 伟大的 . 删除的代码没有错误。

• 运动 :将运算符表示为字符串是粗糙的。做一个 Operator 类类似于 术语 ,以及分析运算符的方法。 不断提高解析器的抽象级别,使之远离具体的字符串并进入解析器的业务领域 . 与记号类似;它们不应该是字符串。
• 运动 :我们解决了一个稍微困难的问题,所以继续前进。你现在能加乘法了吗?
• 运动 :您能解析一种左右结合运算符的语言吗?

一些额外的想法:

• 我想你这样做不是为了自己的乐趣,就是为了学校的作业。 不要把我的工作复制粘贴到你的作业中 . 那是学术欺诈。 如果你提交的作品不完全是你自己的,记得在提交时正确地将所有的作品归类。

• 如果你做这件事是为了好玩,那么设计一门语言就很有趣了!这是个不错的爱好,如果你真的很幸运,总有一天会有人付钱给你。

• 你在设计你自己的语言,所以你不必重复过去的错误。例如,我注意到您的评论建议您添加cast表达式。欢迎来到一个痛苦的世界,如果你像C,C++,C语言,Java等等。所有这些语言的解析器必须在 (x)+y 意思是“把一元加在y上,然后把它转换成 x ,和“添加数量” (x) 到 y “。这是一个很大的痛苦。考虑一个更好的强制转换语法,比如 as 操作员。此外,还要检查强制转换的含义;在c强制转换意味着“生成一个表示相同值的不同类型的实例”和“我断言此对象的运行时类型与其编译时类型不同;如果我错了就抛出”。这些操作完全不同,但语法相同。所有的语言都是对以前语言的回应,所以仔细想想你喜欢什么 因为它很熟悉 VS 因为它很好 .