这是 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)
我不确定这是否正确,因为似乎不存在自上而下和自下而上的语法。有人能澄清一下吗?
最佳答案
这种语法很愚蠢,因为它将词法分析和解析合而为一。但好吧,这是一个学术例子。
自下而上和自上而下的问题在于,它们具有特殊的极端情况,很难用正常的 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;
我不确定这是否能回答您的问题。我认为这个问题的表述很糟糕并且具有误导性;我以编写解析器为生......
关于语法:自上而下和自下而上的区别? (例子),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3182243/