context-free-grammar - 上下文自由语法歧义

Question

给定一个 CFG： S--> aS | Sa | b 我找不到任何可以由两个不同的 pars 树组成的字符串。

中间状态已经离开递归但没有消除是否有任何字符串显示 CFG 歧义？任何人都可以帮助PLZ。

Answer 1

如果您应用规则 1、2 和 3，您将获得：

S -> aS -> aSa -> aba

如果你应用规则 2、3 和 1，你会得到相同的字符串：

S -> Sa -> aSa -> aba

有歧义。

找到了一个检查歧义的工具：http ://services.brics.dk/java/grammar/demo.html

输入语法并检查analyze the grammar for potential ambiguity：

S : "a" S
  | S "a"
  | "b"

结果：

*** vertical ambiguity: S[#1] <--> S[#2]
    ambiguous string: "aba"
the grammar is ambiguous!