在 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))
。实际上,有时是可选的(当多个项目时)有时是强制性的(当只有一项时)尾随逗号几乎要了我的命。
- 此语法是否会生成所有有效的 Python 元组(仅使用
a
、b
和c
)? - 此语法生成的字符串是否不是有效的 Python 元组?
- 这个语法正确吗? (我不确定循环标准)
- 为什么我的语法这么长?如何减少产生式规则的数量? (不要使用像管道这样的语法糖,因为它们只会将几条规则放在一行上。)
预先感谢您的评论和回答。
最佳答案
在没有实际引用 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
这里我使用了有用的插值运算符 //
,在学术类(class)中很少教授,因此实现也少得出奇:
a // b =<sub>def</sub> a(ba)<sup>*</sup>
以上是否更容易阅读,我留给读者。它类似于语法说明(尤其是 RFC)中常用的 EBNF(扩展巴科斯-诺尔范式)。 (EBNF 是少数带有插值运算符的形式之一,尽管它的写法不像我的那么明确。)
无论如何,除此之外,我不相信你的语法可以被修剪。
关于python - python 风格元组的 CFG,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18797248/