语法如下。
S -> SS' | a | b
S' -> a | b
根据我的理解,从该语法派生的就像SS'S'S'S'... (0 or more S')
,其中每个S
或S'
都将生成a
或b
。
有人可以提供示例说明此语法不明确吗? (解决方案说是。)
这并不含糊。您的分析是正确的。
这是对您的语法的机械检查(为我们的工具重新设计):
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个非终结符时,手工操作就困难得多。
((对于理论家:此工具显然无法为所有语法都决定这一点。它在非末尾扩展空间中使用递归迭代加深搜索,以查找重复/模糊扩展。在实践中,效果很好。