这个语法是模棱两可的吗？

Question

我不知道上下文无关文法是否模棱两可：

EXP -> EXP_1
EXP_1 -> EXP_2
EXP_1 -> EXP_1 ( EXP_2 )
EXP_2 -> EXP_2 j
EXP_2 -> \epsilon

其中\ epsilon，'（'，'）'和'j'是终端。你能帮我吗？我曾尝试为同一字符串构造不同的语法树，但找不到任何语法树（可能遗漏了一些），但我不知道如何将其分类为模棱两可。

Answer 1

语法是明确的，我们可以使用数学归纳法对派生字符串中括号的数量进行证明。

基本情况：空字符串使用的是这种语法，并且具有唯一的派生EXP-> EXP_1-> EXP_2-> epsilon。因此，对于n = 0，语法不会以歧义的方式派生任何字符串。

归纳假设：对于包含不超过k个左括号的字符串，语法不会模糊地得出任何字符串。

归纳步骤：我们必须证明语法不会派生任何含k + 1个左括号的字符串。请注意，此语法派生的任何带有k +1个左括号的字符串都必须使用了产生EXP_1-> EXP_1（EXP_2）等于k + 1的次数，因为每个应用程序都引入了一个左括号，而没有其他产生。因此，我们的具有k +1个括号的字符串是通过对该应用的k个应用程序的某些字符串进行部分推导而获得的，然后是另一个应用程序。因为带有k个应用程序的字符串是明确地派生的，所以我们需要显示的是，通过再施加一次EXP_1-> EXP_1（EXP_2），然后再使用其他所有产生方式来消除所有非终结符，就不会产生歧义。看到这个：

1. EXP_1-> EXP_1（EXP_2）完全明确]]
2. 我们现在被迫使用EXP_1-> EXP_2消除EXP_1，因为我们不能再使用EXP_1-> EXP_1（EXP_2）（回想一下，我们只想使用EXP_1-> EXP_1（EXP_2））
3. 为了消除EXP_2，我们必须使用EXP_2-> EXP_2 j和/或EXP_2-> \ epsilon，这两者都不会引起任何歧义，因为一个人添加了j的实例而一个人删除了EXP_2。

由于剩余的产生式都不能引入歧义，因此我们得出结论，根据语法可派生的，带有k +1个左括号的字符串必须在语法中明确可推导。但是，语法语言中的每个字符串都有一定数量的左括号，因此该语法不会产生任何歧义的字符串：这是明确的语法。

注意：要明确，一个字符串根据语法有两个派生是不够的；字符串必须具有不同的解析树。考虑简单的语法

S -> AB
A -> a
B -> b
此语法显然是明确的，但是语法中的字符串ab有两个派生：

S -> AB -> Ab -> ab
S -> AB -> aB -> ab
但是，只有一棵解析树：

  A---a
 /
S
 \
  B---b