Skip to main content
 首页 » 编程设计

python之用于 python 样式元组的 CFG

2024年11月01日10qq号

在 Stackoverflow 上阅读了无数次关于“我如何使用正则表达式解析 HTML”的问题后,我再次对语法产生了兴趣,抓起我的大学脚本,几分钟后我想知道我是如何通过的我的考试。

作为一个简单的(嗯,“简单”我期望它是)练习,我尝试编写一个生成有效 python 元组的 CFG(为简单起见,仅使用标识符 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),) 或 ( (a,b))。实际上,有时是可选的(当有多个项目时)有时是强制性的(当只有一个项目时)尾随逗号几乎要了我的命。

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

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

请您参考如下方法:

在没有实际提及 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 star 及其同伴):

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

这里我使用了有用的插值运算符 // ,它很少在学术类(class)中教授,因此很少有实现:

a // b =<sub>def</sub> a(ba)<sup>*</sup>

以上内容是否更容易阅读,我留给读者。它类似于语法说明中常用的 EBNF(扩展巴科斯-诺尔形式),尤其是在 RFC 中。 (EBNF 是为数不多的带有插值运算符的形式主义之一,尽管它没有像我写得那么明确。)

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