语法:自上而下和自下而上的区别? (例子) [英] Grammar: difference between a top down and bottom up? (Example)

问题描述

这是>语法:自上而下和自底向上?

我从这个问题中了解到:

I understand from that question that:

• 语法本身不是自上而下或自下而上的，解析器是
• 有些语法可以被一个人解析，而另一个不能解析
• (感谢 Jerry Coffin

因此对于此语法(所有可能的数学公式):

So for this grammar (all possible mathematical formulas):

    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 

自上而下和自下而上的解析器会可读吗?

Would this be readable by a top down and bottom up parser?

您能说这是自上而下的语法还是自下而上的语法(或都不是)?

Could you say that this is a top down grammar or a bottom up grammar (or neither)?

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

I am asking because I have a homework question that asks:

编写由所有...组成的语言的自上而下和自下而上的语法"(不同的问题)

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

我不确定这是否正确，因为似乎没有自上而下和自下而上的语法.有人可以澄清吗?

I am not sure if this can be correct since it appears that there is no such thing as a top-down and bottom-up grammar. Could anyone clarify?

推荐答案

该语法很愚蠢，因为它将词法分析和语法分析统一为一个语法.好的，这是一个学术例子.

That grammar is stupid, since it unites lexing and parsing as one. But ok, it's an academic example.

自下而上和自上而下的事情是，具有特殊的特殊情况，通常情况下您很难实现1向前看.我可能认为您应该检查它是否有问题并更改语法.

The thing with bottoms-up and top-down is that is has special corner cases that are difficult to implement with you normal 1 look ahead. I probably think that you should check if it has any problems and change the grammar.

为了理解您的语法，我写了适当的EBNF

To understand you grammar I wrote a proper 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.目前尚不清楚第一个数字和第二个数字在哪里开始.我将规则实施为

I especially don't like the rule digits: digits digits. It is unclear where the first digits starts and the second ends. I would implement the rule as

digits:
    '0' |
    digit |
    digits digit;

另一个问题是number: '0' | digit digits;.这与digits: '0'和digits: digit;冲突.事实上，这是重复的.我将规则更改为(删除数字):

An other problem is number: '0' | digit digits; This conflicts with digits: '0' and digits: digit;. As a matter of fact that is duplicated. I would change the rules to (removing digits):

number:
    '0' |
    digit |
    digit zero_digits;

zero_digits:
    zero_digit |
    zero_digits zero_digit;

zero_digit:
    '0' |
    digit;

这使语法LR1(左递归，向前看)和上下文无关.这通常是您给诸如bison之类的解析器生成器提供的.而且由于野牛是自下而上的，因此这对于自下而上的解析器来说是有效的输入.

This makes the grammar LR1 (left recursive with one look ahead) and context free. This is what you would normally give to a parser generator such as bison. And since bison is bottoms up, this is a valid input for a bottoms-up parser.

对于自顶向下方法，至少对于递归体面的方法，左递归有点问题.如果愿意，可以使用回滚，但对于这些，您需要RR1(一个正确的递归视图)语法.为此，请交换递归:

For a top-down approach, at least for recursive decent, left recursive is a bit of a problem. You can use roll back, if you like but for these you want a RR1 (right recursive one look ahead) grammar. To do that swap the recursions:

zero_digits:
    zero_digit |
    zero_digit zero_digits;

我不确定是否能回答您的问题.我认为这个问题的措词不当且具有误导性.然后我以解析器为生...

I am not sure if that answers you question. I think the question is badly formulated and misleading; and I write parsers for a living...

这篇关于语法:自上而下和自下而上的区别? (例子)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！