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

Question

我正在编写自己的编程语言,并且我完成了令牌器(词法分析器).但是对于解析,我在编写递归下降解析器时遇到了麻烦.它似乎是正确的联想,应该留下,我不知道为什么.例如,它解析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,正如开头所说,它正在解析错误的关联性.这是完成root之后ParseAdditiveExpression:

正如你所看到的,这组2同3,不是1.它为什么这样做？

Answer 1

正如我在评论所指出的,问题是你混淆了一个二元运算的最右边的孩子有一个additiveprime的最右边的孩子.二元运算符的最右边的子节点是表达式.添加剂的最右边是添加剂,因此仅在"树节点类型"的基础上我们必须得出结论,你已经构建了一个错误的解析树.

跟踪每个解析工件的"逻辑类型"是一种在解析器中查找错误的强大技术.另一个我喜欢的,可悲的是未充分利用,它将程序中的每个标记属于一个解析树节点.如果你这样做,那么你很快就会意识到运算符的标记在逻辑上分为两个位置:二元运算符和最右边的子节点.这也告诉我们出了问题.

没有用的是你的解析基础设施是一个混乱的数字和输出参数混乱.你的解析器缺乏纪律.您的解析器代码看起来像计数令牌是解析器执行的最重要的事情,而其他一切都是偶然的.

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

我建立了递归下降解析器为生.让我告诉你如何构建这个解析器,我是否为了自己的目的快速构建它.(如果我为生产应用程序构建它,它在许多方面会有所不同,但我们在这里很容易理解.)

好的,让我们开始吧.首先是:当你遇到问题时,解决一个更简单的问题.让我们通过以下方式简化问题:

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

请注意以下几点:

• 抽象类是抽象的.
• 具体课程是密封的.
• 一切都是不变的.
• 一切都知道如何打印自己.
• 没有空! 没有NULLS.空无聊会导致崩溃.你有一个名为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' | nil,但我们要解析的语法是B :: T | B + T.

请注意,我并不混淆E,这是一个术语和后缀B,它是a T或a B,a +和a 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.我们该怎么做？

添加剂总是一个术语和一个素数.所以有两种情况.素数是零,或者不是.

如果素数为零,那么我们就完成了:a Term在Binary需要的地方是可以接受的,所以我们可以传回这个术语.

如果素数不是零,那么素数是op,term,prime. 不知怎的,我们必须得到一个Binary出来的是.二进制需要三件事.请记住,我们将每个令牌归结为一个节点,因此这将帮助我们弄清楚它.

• 我们的左项来自添加剂.
• 我们有来自黄金时段的操作.
• 我们有正确的术语.

但这仍然是最重要的巅峰之作!我们需要做点什么.让我们说出来吧.同样,有两种情况:

• 如果素数的素数为零,则结果为二进制.
• 如果素数的素数不是nil,则结果是左边的旧二进制文件的新二进制文件,并且... 等一下,这与我们刚才描述的将添加剂转换为二进制文件的算法相同.

我们刚刚发现这个算法是递归的,一旦你意识到编写它是微不足道的:

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但它返回一个Binary.

其实...... 我们需要Additive在所有？我们可以完全从解析器中消除它吗？事实上我们可以; 我们现在永远不会创建一个实例Additive,因此可以删除它,并且ParseAdditive可以重命名ParseBinary.

当使用"解决更简单的问题"技术构建程序时,通常会发生这种情况.你最终能够扔掉你早先的作品,这很棒.删除的代码没有错误.

• 练习:将运算符表示为字符串是粗略的.创建一个Operator类似于的类Term,以及一个解析运算符的方法.继续将解析器的抽象级别从具体字符串提升到解析器的业务域.与令牌类似; 他们不应该成为弦乐.
• 练习:我们已经解决了一个稍微难点的问题,所以继续前进.你现在可以添加乘法吗？
• 练习:你能解析一个混合了左右关联运算符的语言吗？

一些额外的想法:

• 我认为你这样做是为了你自己的乐趣,或者是为了学校作业.不要将我的工作粘贴到您的作业中.这是学术欺诈. 如果您的工作不完全属于您自己的工作,请记住在提交时正确归因所有工作.

• 如果你是为了好玩,那就设计一门语言吧!这是一个很好的爱好,如果你真的很幸运,有一天会有人付钱给你.

• 你正在设计自己的语言,所以你不必重复过去的错误.我注意到你的评论表明你要添加强制转换表达式.欢迎来到一个痛苦的世界,如果你这样做,如C,C++,C#,Java等.所有这些语言必须让它们的解析器消除歧义(x)+y意义"应用一元加上y并将事物转换为x",以及"将数量添加(x)到y".这是一个重大的痛苦.为as运算符考虑更好的语法,比如运算符.另外,检查一个演员的意思; 在C#中,强制转换意味着"生成表示相同值的不同类型的实例"和"我断言此事物的运行时类型与其编译时类型不同;如果我错了则抛出".这些操作完全不同,但它们具有相同的语法.所有语言都是对以前语言的回应,所以要仔细思考你喜欢什么,因为它很熟悉,因为它很好.