0

问题

通过给出字符串 abaca 的两个解析树，证明上下文无关文法“S->SbS|ScS|a”是不明确的。

我不明白字符串是如何模棱两可的？我正在读一本关于编译器和自学的书，所以我在书中做这个问题，我被难住了。

可能的解决方案

abaca         abaca
a(aba)aca     aba(aca)a

谁能确认我的解决方案是否正确，如果不是，请指导我。

4

1 回答 1

2

用笔和纸更容易做到这一点。在所有可能性中，我列出了通过推导初始符号找到的三种可能性S。

S -> SbS -> abS -> abScS -> abacS -> abaca
S -> ScS -> Sca -> SbSca -> abSca -> abaca
S -> SbS -> SbScS -> abScS -> abSca -> abaca

还有其他的，这不难看出。但是，通常将字符串 ( abaca) 简化为原始符号 ( S) 会更容易。许多编译器这样做是为了避免无限递归：

abaca <- Sbaca <- SbSca <- Sca <- ScS <- S
abaca <- abacS <- abScs <- abS <- SbS <- S

这样做的方法是手动选择一种方法（推导或归约），然后通过反复试验，根据语法进行可能的替换，这将引导您找到一棵树。树中通向目标的节点（原始符号或最终字符串）是正确的节点。如果路径不止一条，那么它就是模棱两可的。

现在，这些推导中的每一个以及其他推导都将产生一个所谓的Parse Tree. 解析树表示能够从初始符号生成终端字符串的派生集。为了更好地可视化解析树，我在网上找到了一个工具来绘制这些树，你可以在这里找到它。

它使用的格式是[NonTerminal terminal [NonTerminal terminal] terminal]，几乎是一个类似 Lisp 的列表，带有方括号而不是括号。比如我构建的第一个推导，可以S -> SbS -> abS -> abScs -> ...写为 希望这个工具可以帮助您学习正式的语法！[S [S a] b [S [S a] c [S a]]][S [S ...] b [S ...]][S ...][S a]

于 2014-10-19T01:42:07.577 回答