algorithm - 语法树

Question

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

---

编辑 抱歉!我应该更专心。真的，我有一个语法，如果可能的话，我必须使用这个语法和输入句子(我知道怎么做)来构建树(在另一种情况下，我必须显示关于它的信息)。有什么简单易懂的算法吗？我可以使用任何简单语言的语法，例如算术表达式。

Answer 1

我假设这是理论上的，因为它是家庭作业，而不是您此时实际需要编写代码的东西。 (肯德里克的回答涵盖了代码方法)

基本思想是从您的 BNF 开始变量开始，并尝试弄清楚如何扩展它，一次应用一个规则，看看您是否可以想出您的输入序列。

对于如下规则集:

(1) start: expression

(2) expression: expression '+' term
(3)           | expression '-' term
(4)           | term

(5) term: 'a'
(6)     | 'b'

给定表达式 a + b - a，你会像这样:

一个。 开始(给定的)
b. 表达式 (1)
C。 表达式“-”项 (3)
d. 表达式 '-' 'a' (5)
e. 表达式 '+' term '-' 'a' (2)
F。 术语“+”术语“-”“a” (4)
G。 'a' '+' term '-' 'a' (5)
H。 'a' '+' 'b' '-' 'a' (6)

这就是您一次一步完成的方式……现在的诀窍是，您需要追踪所有规则调用。所以你真正的树看起来像这样:

                          start
                            | (b)
                        expression
                        /   |   \ (c)
               expression  '-'  term
                /  |  \ (e)       | (d)
       expression '+' term       'a'
           | (f)        | (h)
          term         'b'
           | (g)
          'a'

一开始有点复杂，但是一旦您真正了解了它是如何完成的，就不难上手了。

注意:有些人发现逆向工作更容易，从您的输入开始，然后反向应用规则来尝试找到您的起始表达式。当您编写解析器时，您将不可避免地需要在某种程度上遵循这条路线。

编辑: 我在上面列出了所有使用小写字母的表达式步骤，然后显示树中的每组分支实际上对应于一个规则应用程序。可能有帮助也可能没有帮助。