语法树

Question

我在大学里有个实验室。但我不明白我怎么能做到。我有一些语言的语法(例如，算术表达式语法)。我必须建立这种语法树(我不知道怎么做)。那么我必须确定，输入句是否是这种语言的句子？我该怎么做呢？我读过“龙书”的几章，但我没有找到任何需要的东西。我不能用lex/flex和yacc/bison。

编辑对不起！我会更专心的。实际上，我有一个语法，我必须使用这个语法和输入句子来构建树(如果可能的话，我知道怎么做)(在另一种情况下，我必须显示有关它的信息)。有什么简单的理解算法吗？我可以使用任何简单语言的语法，比如算术表达式。

Answer 1

我已经很久没有这样做了，所以我要给你们一个简短的理论答案。我相信其他人会有更深入的解释。

由于您还没有说出您已经做了什么(并且您应该在将来作为您的问题的一部分)，第一步是标记输入。

一旦您拥有了令牌，您就可以构建一个状态机来遍历这些令牌并将它们推入所需的树结构。这应该在你的书中讨论(我还没读过)，但是你可能想从纸(或电子)上构建一个模型开始，并考虑每个步骤的有效输入。等式语句的有效左手值是多少？如果你的树上有标记x，你能从这里去哪里？

如果无法从当前的状态确定下一步的位置，则可能需要在状态机中实现前瞻性(这是否需要取决于语言的复杂性)。

再说一次，我已经十年没有做过这件事了，所以我的记忆是模糊的。希望我已经给出了足够的框架，让你完善你的答案，或者给其他在这个问题上更有知识的人，因为我错了或者过时了(这样你就可以作为一个群体得到你想要的答案)。

Answer 2

我想回答这个问题，但实际上没有足够的材料供我使用--我只剩下这些问题：

• ，这是一个大学实验室，没有伴随的学习材料或课程吗？另外，您还有多少时间？
• ，您到目前为止尝试了什么？
• 您可以将给定的语法硬编码到您的程序中吗?还是您的程序需要能够从文件中读取任何语法并从中构建解析树？
• 语法有多复杂；具体而言:它们是递归的吗？
• 是单一字符的语法标记还是
• ？

编辑:考虑到注释和更新的问题:我认为最直接的方法是递归下降解析器，它在输入匹配时构建树。查找Niklaus的“编译器构建”一书，这本书已经作为PDF在网上提供，它描述了一种简单语言的RDP。

递归下降解析器的基本思想是语法中的每条规则对应于一个函数，每个函数检查下一个令牌并调用相应的下一个下一个解析函数。例如，如果语法有规则

expression : constant '+' constant

关联的解析方法如下所示：

void parseExpression() {
    parseConstant();
    Token token = peek_at_next_token();
    if (token == '+') {
        parseConstant();
        ... tree building code here ...
    }
    else
        throw ParseException("Expected '+', found "+token);
}

但也请看这个问题的其他答案。