语法:自上而下和自下而上的区别？ (例子)

Question

这是 Grammar: difference between a top down and bottom up? 的后续问题

我从这个问题中了解到:

• 语法本身不是自上而下或自下而上的，而是解析器
• 有些语法可以被一种语法解析，但不能被另一种语法解析
• (感谢 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 

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

你能说这是自上而下的语法还是自下而上的语法(或两者都不是)？

<小时/>

我问这个问题是因为我有一个作业问题要问:

"Write top-down and bottom-up grammars for the language consisting of all ..." (different question)

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

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:
    '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;

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