语法：自上而下和自下而上的区别？ （例子）

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 

这可以被自上而下和自下而上的解析器读取吗？

能说这是自上而下的语法还是自下而上的语法（或两者都不是）？

---

你

“为包含所有...的语言编写自上而下和自下而上的语法”（不同的问题）

我不确定这是否正确，因为似乎不存在自上而下和自下而上的语法语法。有人能澄清一下吗？

Answer 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:digitsdigits。目前尚不清楚第一个数字从哪里开始，第二个数字从哪里结束。我会将规则实施为

digits:
    '0' |
    digit |
    digits digit;

另一个问题是 number: '0' | digital digitals; 这与 digits: '0' 和 digits: digital; 冲突。事实上，这是重复的。我会将规则更改为（删除数字）：

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;

我不确定这是否回答了您的问题。我认为这个问题的表述很糟糕并且具有误导性；我以编写解析器为生......