这个语法(对于 Lua 的一小部分)有歧义吗?
Is this grammar (for a small subset of Lua) ambiguous?
我有以下语法,它是 "The Complete Syntax of Lua" 的一小部分:
chunk -> | chunk stat.
stat -> var `=´ exp.
var -> Name | exp `[´ exp `]´.
exp -> var | exp `(´ exp `)´ | `(´ exp `)´.
根据 a context-free grammar tool,此语法不是 LR(1)
并且(因此?)不是 LALR(1)
、SLR(1)
、LR(0)
或 LL(1)
.
这个语法有歧义吗?如果是这样,你能举一个歧义句的例子吗?如果不是,是否有充分的理由说明它不是 LR(1)
?
编辑: 表现出相同问题的稍微简化的语法:
stat -> exp | exp var.
var -> Name | exp `[´ exp `]´.
exp -> var | exp `(´ exp `)´ | `(´ exp `)´.
编辑 2: 感谢 Michal Bohuslávek 提供了一个句子示例,该句子相对于第二个语法有歧义。不幸的是,该句子并没有直接导致与第一个语法的歧义。
但是,如果将第二个语法的第一条规则更改为 stat -> exp var.
,则歧义句子 将 导致与第一个语法的歧义。 Michal的思路可以扩展生成这样一句话:exp '(' exp ')' '(' exp ')' '[' exp ']'
.
例如,这个序列在 IMO 中是不明确的:
exp '(' exp ')' '[' exp ']'
可以是:
exp '[' exp ']'
/ \
exp '(' exp ')'
或者:
exp var
/ \
exp '[' exp ']'
|
'(' exp ')'
我有以下语法,它是 "The Complete Syntax of Lua" 的一小部分:
chunk -> | chunk stat.
stat -> var `=´ exp.
var -> Name | exp `[´ exp `]´.
exp -> var | exp `(´ exp `)´ | `(´ exp `)´.
根据 a context-free grammar tool,此语法不是 LR(1)
并且(因此?)不是 LALR(1)
、SLR(1)
、LR(0)
或 LL(1)
.
这个语法有歧义吗?如果是这样,你能举一个歧义句的例子吗?如果不是,是否有充分的理由说明它不是 LR(1)
?
编辑: 表现出相同问题的稍微简化的语法:
stat -> exp | exp var.
var -> Name | exp `[´ exp `]´.
exp -> var | exp `(´ exp `)´ | `(´ exp `)´.
编辑 2: 感谢 Michal Bohuslávek 提供了一个句子示例,该句子相对于第二个语法有歧义。不幸的是,该句子并没有直接导致与第一个语法的歧义。
但是,如果将第二个语法的第一条规则更改为 stat -> exp var.
,则歧义句子 将 导致与第一个语法的歧义。 Michal的思路可以扩展生成这样一句话:exp '(' exp ')' '(' exp ')' '[' exp ']'
.
例如,这个序列在 IMO 中是不明确的:
exp '(' exp ')' '[' exp ']'
可以是:
exp '[' exp ']'
/ \
exp '(' exp ')'
或者:
exp var
/ \
exp '[' exp ']'
|
'(' exp ')'