语法：自顶向下和自底向上的区别是什么？（示例）

Question

这是一个关于语法：自顶向下和自底向上的区别？的后续问题。

我从那个问题中了解到：

• 语法本身并不是自顶向下或自底向上的，而是解析器。
• 有些语法可以由其中一个解析，但不能由另一个解析。
• （感谢Jerry Coffin）

因此，对于这个语法（所有可能的数学公式）：

    E -> E T E
    E -> (E)
    E -> D

    T -> + | - | * | /

    D -> 0
    D -> L G

    G -> G G    
    G -> 0 | L

    L -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 

这个文本能被自顶向下和自底向上的解析器读取吗？

你能说这是自顶向下语法还是自底向上语法（或者两者都不是）？

---

我之所以问是因为我有一个作业问题，它要求：

“为由所有...”（不同的问题）编写自顶向下和自底向上的语法。

我不确定这是否正确，因为似乎没有自顶向下和自底向上的语法。 有人能澄清吗？

- sixtyfootersdude

---

你能提供完整的问题吗？或许会更加清晰明了。 - Marius Gedminas

也许查阅一下教科书对“自顶向下”语法的定义会有所帮助？我认为自顶向下的解析器只有在执行递归下降而不是类似广度优先搜索的技术（例如将边缘排队尝试）时才会失败。 - gatoatigrado

Answer 1

那个语法很愚蠢，因为它将词法分析和语法分析合并为一个。但是好吧，这只是一个学术例子。

自底向上和自顶向下的问题在于它们有特殊的边角情况，很难用普通的1个展望实现。我认为你应该检查一下是否有任何问题，并更改语法。

为了理解你的语法，我编写了一个适当的EBNF。

expr:
    expr op expr |
    '(' expr ')' |
    number;

op:
    '+' |
    '-' |
    '*' |
    '/';

number:
    '0' |
    digit digits;

digits:
    '0' |
    digit |
    digits digits;

digit:
    '1' | 
    '2' | 
    '3' | 
    '4' | 
    '5' | 
    '6' | 
    '7' | 
    '8' | 
    '9'; 

我特别不喜欢规则digits: digits digits。不清楚第一个数字从哪里开始，第二个数字在哪里结束。我会将规则实现为

digits:
    '0' |
    digit |
    digits digit;

另一个问题是number: '0' | digit digits;这与digits: '0'和digits: digit;冲突。实际上这是重复的。我会更改规则（删除digits）：

number:
    '0' |
    digit |
    digit zero_digits;

zero_digits:
    zero_digit |
    zero_digits zero_digit;

zero_digit:
    '0' |
    digit;

这使得文法是LR1(具有一个向前看的左递归)和上下文无关。这通常是像bison这样的解析器生成器所需要的。而且由于bison是自底向上的，这对于自底向上的解析器来说是一个有效的输入。

对于自顶向下的方法，至少对于递归下降，左递归是一个问题。您可以使用回溯，但对于这些情况，您想要RR1(具有一个向前看的右递归)语法。为此，请交换递归：

zero_digits:
    zero_digit |
    zero_digit zero_digits;

我不确定这是否回答了你的问题。我认为这个问题表述不清且具有误导性；而我从事的工作是编写解析器...

- rioki