CFG：为什么这个语法有歧义？

Question

语法如下

S -> SS' | a | b
S' -> a | b

按照我的理解，这个语法的推导就像 SS'S'S'S'... (0 or more S')，其中每个 S 或 S' 将生成 a 或 b .

谁能举个例子说明这个语法有歧义？（解决方案说是。）

Answer 1

没有歧义。你的分析是正确的。

这是对您语法的机械检查（针对我们的工具进行了修改）：

S = S Sprime ;
S = a ;
S = b ;
Sprime = a ;
Sprime = b ;

执行工具：

C:\DMS\Domains\DMSStringGrammar\Tools\ParserGenerator>run ParserGenerator.P0B -interactive C:\
DMS GLR Parser Generator 2.4.1
Copyright (C) 1997-2018 Semantic Designs, Inc.
Opening C:\temp\Example.bnf
*** EOF seen
<<<Rule Collection Completed>>>
NTokens = 5 NRules = 5
LR(1) Parser Generator -- Find Follow and SLR Lookahead sets
Computing MemberSets for Nonterminal Tokens...

What next? ambiguities 100
Print results where (<CR> defaults to console)?
Default paper width: 80
How wide should the printout be (<CR> selects default)?
*** Search for ambiguities to depth 100

Nonterminal < Sprime > is not ambiguous
*** Search for ambiguities to depth 1; trying 2 rule pairs...
*** Search for ambiguities to depth 2; trying 2 rule pairs...
*** Search for ambiguities to depth 3; trying 2 rule pairs...
*** Search for ambiguities to depth 4; trying 2 rule pairs...
Nonterminal < S > is not ambiguous [modulo rule derivation loops]

*** 0 ambiguities found ***
*** All ambiguities in grammar detected ***

这个工具对于有两个非终结符的语法来说有点过分了。但是当有人给出一组 200 个非终结符时，手工操作要困难得多。

(对于理论家：这个工具显然不能为所有语法决定这一点。它在 space 非终结符扩展中使用递归迭代加深搜索来查找 duplicate/ambiguous 扩展。这在实践中非常有效）。

CFG：为什么这个语法有歧义？

CFG: Why is this grammar ambiguous?

grammar

context-free-grammar

context-free-language

ambiguous-grammar