1

所以我一直在阅读一些关于词法分析器、解析器、解释器甚至编译的内容。

对于我正在尝试实现的一种语言，我选择了递归下降解析器。由于该语言的原始语法具有左递归，我不得不稍微重写它。

这是我所拥有的语法的简化版本（请注意，它不是任何标准格式语法，但有点伪，我猜，这就是我在文档中找到它的方式）：

expr:
-----
expr + expr
expr - expr
expr * expr
expr / expr
( expr )
integer
identifier

为了摆脱左递归，我把它变成了这个（注意添加了 NOT 运算符）：

expr:
-----
expr_term {+ expr}
expr_term {- expr}
expr_term {* expr}
expr_term {/ expr}

expr_term:
----------
! expr_term
( expr )
integer
identifier

然后使用以下子例程（简化的伪代码）检查我的令牌：

public string Expression()
{
    string term = ExpressionTerm();

    if (term != null)
    {
        while (PeekToken() == OperatorToken)
        {
            term += ReadToken() + Expression();
        }
    }

    return term;
}

public string ExpressionTerm()
{
    //PeekToken and ReadToken accordingly, otherwise return null
}

这行得通！调用后的结果Expression总是等于给出的输入。

这让我想知道：如果我在这些子例程中创建 AST 节点而不是字符串，并使用中缀评估器评估 AST（它还牢记运算符的关联性和优先级等），我不会得到相同的结果?

如果我这样做了，那么为什么有这么多主题涵盖“修复左递归，牢记关联性等等”，而实际上解决起来“非常简单”，甚至看起来似乎不是问题？或者它真的是人们关心的结果 AST 的结构（而不​​是它的评估结果）？谁能解释一下，我可能也搞错了，哈哈！

4

2 回答 2

2

AST 的形状很重要，因为a+(b*3)它通常不一样，(a+b)*3并且人们可能会合理地期望解析器指出这些a+b*3方法中的哪一个。

通常，AST 实际上会删除括号。（解析树不会，但 AST 预计会抽象出句法噪声。）所以 ASTa+(b*3)应该看起来像：

          Sum
           |
       +---+---+
       |       |
      Var     Prod
       |       |
       a   +---+---+
           |       |
          Var    Const
           |       |
           b       3

如果您的语言遵循通常的数学符号约定，那么a+b*3.

“中缀评估器”——或者我想你所指的——只是另一个解析器。所以，是的，如果您愿意稍后解析，那么您现在不必解析。

顺便说一句，表明您可以按照阅读它们的顺序将标记重新组合在一起，实际上并不能说明解析器的功能。只需回显标记器的输出，您就可以更简单地做到这一点。

于 2013-10-19T01:16:05.650 回答
0

处理数学表达式或其他表达式的标准且最简单的方法是使用反映预期关联和运算符优先级的规则层次结构：

expre = sum

sum = addend '+' sum | addend

addend = term '*' addend | term

term = '(' expre ')' | '-' integer | '+' integer | integer

这样的语法让解析或抽象树可以直接评估。您可以扩展规则层次结构以包括幂运算符和位运算符，或使其成为具有and or和比较的逻辑表达式层次结构的一部分。

于 2013-10-19T15:54:30.330 回答