java - 创建解析树以确定给定的 LL 语法的正确性

Question

我有一个程序，当前将生成 token 输出，用于下一个程序的输入。它将检查代码语法的正确性。

我遇到了如何开始将此语法转换为可用程序的问题。

下面是语法使用，我将如何着手制作它。或者哪里有好的资源可以帮助我学习创建自己的解析器的基础知识。

这个实现将使用 Java，所以如果你能得到与 Java 实现相对应的答案，那就太棒了

program → stmt_list $$$

stmt_list → stmt stmt_list | ε

stmt → id = expr | input id | print expr

expr → term term_tail

term_tail → add op term term_tail | ε

term → factor fact_tail

fact_tail → mult_op fact fact_tail | ε

factor → ( expr ) | number | id

add_op → + | -

mult_op → * | / | // | %

Answer 1

您应该首先阅读编译器 - 原理、技术和工具(也称为龙书)的语法分析章节。
检查输出标记的步骤是:

构建First和Follow集合。

构造预测解析表。

检查同一表格单元格中的多个产生式(冲突)

所有这些步骤都可以在龙书上找到，并用各自的算法进行了完美的解释。
我希望这有帮助。 这实际上只是解析之前的一个步骤，所以如果你到了能够检查语法是否为 LL(1) 的地步，我建议实现解析算法，它只是有一个将非终端压入的堆栈并引用该表以生成 AST。