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

Question

这是Grammar的后续问题:自上而下和自下而上的区别？

我从这个问题中了解到:

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

那个语法是愚蠢的,因为它将lexing和解析结合为一个.但好吧,这是一个学术的例子.

自下而上和自上而下的东西是有特殊的角落情况,很难实现正常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;.事实上,这是重复的.我会将规则更改为(删除数字):

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;

我不确定这回答你的问题.我认为这个问题制定得很糟糕,误导人; 我写解析器以谋生......