1

我正在从 Aho 的编译器构造中读取有限自动机和语法，并且我被这种语法困扰了很长时间。我对如何描述它没有清晰的认识：

考虑以下语法：

S -> (L) | 一个 L -> L, S | 小号

请注意，括号和逗号实际上是该语言中的终结符，并出现在该语法接受的句子中。试着描述这个语法生成的语言。这个语法有歧义吗？

我在这里关心的是：这种语法生成的语言可以描述为正则表达式吗？我对如何做到这一点感到困惑。有什么帮助吗？

4

2 回答 2

6

为了证明语法是模棱两可的，你需要能够在解析同一个字符串的同时构造两个不同的解析树。您的字符串将由“(”、“)”、“”和“a”组成，因为它们是语法中唯一的终端符号。

尝试以几种方式排列这 4 个终端符号，看看是否可以显示不同的成功解析，本着Wikipedia 上的模棱两可语法示例的精神。

立即左递归往往会给某些解析器带来问题。看看 "a,a,a" 是否对 "L → L , S | S" 做了什么有趣的事情......

我在这里关心的是这个语法生成的语言作为正则表达式可以描述......我对如何做感到困惑

一个正则表达式不能完全描述语法。重写部分语法将使这一点更加明显：

  1. 小号 → ( 大号 )
  2. S → 一个
  3. L → L , S
  4. 大号→小号

注意#1 和#4。L 可以产生 S，S 可以产生 (L)。这意味着 S 可以产生 ( S )，它可以产生 ( ( S ) )、( ( ( S ) ) ) 等等，无穷无尽。关键是这些括号是匹配的；“（”符号与“）”符号的数量相同。

正则表达式无法做到这一点。

正则表达式映射到有限自动机。有限自动机不能数。语言 L ∈ {w: 0 n 1 n } 不是正则。L ∈ {w: ( n ) n }，只是用 "(" 代替 "0" 和 ")" 代替 "1"，也不是。请参阅： Regular Languages - Wikipedia下的第一个示例部分。（注解：s 1是 s，s 2是 ss，...，s n是 s 重复 n 次。）

这意味着您不能使用正则表达式来描述语言的那一部分。这使其属于 CFG、图灵机和下推自动机领域。

于 2012-04-27T03:41:33.940 回答
3

正则表达式（以及解释它们的库）是识别上下文无关语法句子的糟糕工具。相反，您可能希望使用 yacc、bison 或 ANTLR 之类的解析器生成器。

我认为阿霍书中练习的重点是用文字“描述语言”，以便了解它是否有歧义。处理它的一种方法：给定语法的产生，你能设计一个可以用两种不同方式解析的语法句子吗？如果是这样，则语法是模棱两可的。

于 2012-04-26T14:26:50.670 回答