7

这是语法的后续问题：自上而下和自下而上的区别？

我从这个问题中了解到：

  • 语法本身不是自上而下或自下而上的，解析器是
  • 有些语法可以被一个解析，但不能被另一个解析
  • （感谢杰里·科芬

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

    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

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

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

我问是因为我有一个家庭作业问题：

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

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

4

1 回答 1

5

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

自下而上和自上而下的事情是有特殊的极端情况，很难用你的正常 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;This 与digits: '0'and冲突digits: digit;。事实上，这是重复的。我会将规则更改为（删除数字）：

number:
    '0' |
    digit |
    digit zero_digits;

zero_digits:
    zero_digit |
    zero_digits zero_digit;

zero_digit:
    '0' |
    digit;

这使得语法 LR1（左递归，向前看）和上下文无关。这是您通常会提供给解析器生成器（例如野牛）的内容。由于 bison 是自下而上的，这对于自下而上的解析器来说是一个有效的输入。

对于自上而下的方法，至少对于递归体面而言，左递归有点问题。如果愿意，您可以使用回滚，但对于这些，您需要 RR1（右递归前瞻）语法。为此交换递归：

zero_digits:
    zero_digit |
    zero_digit zero_digits;

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

于 2010-07-21T16:15:04.273 回答