2

在 Stackoverflow 上读了无数次关于“如何使用 Regex 解析 HTML”的问题后，我再次对语法感兴趣，拿起我的大学脚本，几分钟后我想知道我是如何通过考试的。

作为一个简单（嗯，“简单”，我期望它是）练习，我尝试编写一个 CFG 来生成有效的 python 元组（为简单起见，仅使用标识符a,b和c）。经过一段美好的时光后，我现在想出了这个：

G = ( {Tuple, TupleItem, Id}, {“a”, “b”, “c”, “,”, “(“, “)”}, P, Tuple)

作为P：

Tuple → “(“ TupleItem “)”
Tuple → “(“ TupleItem Id “)”
Tuple → “(“ TupleItem Tuple “)”
TupleItem → TupleItem TupleItem
TupleItem → Id “,”
TupleItem → Tuple “,”
Id → “a”
Id → “b”
Id → “c”

这个语法应该产生例如(a,), (a,b), (a,b,), ((a,),), ((a,b,),(a,),), 但不是(,a), (),,等(a,b c)。我不想产生多余的括号，比如((a),)or ((a,b))。实际上，有时可选的（当不止一项时）有时是强制性的（当只有一项时）尾随逗号几乎要了我的命。

  1. 此语法是否生成所有有效的 python 元组（仅使用a,b和c）？
  2. 这个语法会产生不是有效 python 元组的字符串吗？
  3. 这个语法正确吗？（我不确定循环标准）
  4. 为什么我的语法这么长？如何减少生产规则的数量？（不是通过使用像管道这样的语法糖，因为它们只将几条规则放在一行上。）

提前感谢您的评论和回答。

4

1 回答 1

2

在没有实际提及 Python 语法的情况下，我很确定您的语法会生成所有有效的 Python 元组，除了一个 ( ()，空元组)，并且它不会产生任何不是 Python 元组的东西。所以到这个程度，还好。

但是，它对解析没有多大用处，因为

TupleItem → TupleItem TupleItem

是指数模棱两可的。（Dicho sea de paso，TupleItem 不是这个非终结符的一个描述性很强的名称，它实际上是一个列表。）歧义文法是“正确的”，因为它们遵守上下文无关文法的所有规则，但没有二义性文法通常会更好。

很容易修复：

Tuple → “(“ “)”
Tuple → “(“ ItemList “,” “)”
Tuple → “(“ ItemList “,” Item “)”
ItemList → Item
ItemList → ItemList “,” Item
Item → Id
Item → Tuple

（我省略了Id产生式；在实际语法中，Id这将是一个终端，但几乎没有什么区别。）

最后，为什么这个语法“这么长”？（七部作品真的“这么长吗？”？取决于你的标准，我猜。）

简单的答案是 CFG 就是这样。您可以添加语法糖来制作右侧的正则表达式（不仅是交替，还有 Kleene 星及其同伴）：

Tuple → “(“ [ ItemList “,” Item? ]? “)”
ItemList → Item // “,”
Item → Id | Tuple

在这里，我使用了有用的插值运算符//，它很少在学术课程中教授，因此实现起来令人惊讶地少：

a // b =def a(ba)*

以上内容是否更容易阅读，我留给读者。它类似于语法说明中常用的 EBNF（扩展巴科斯-瑙尔形式），特别是在 RFC 中。（EBNF 是为数不多的带有插值运算符的形式之一，尽管它的写法不像我的那样明确。）

无论如何，除此之外，我不相信你的语法可以修剪。

于 2013-09-14T15:44:45.373 回答