时间戳

首页 > 解决方案 > 使用 Epsilon 或 Lambda 的语法

parsing - 使用 Epsilon 或 Lambda 的语法

问题描述

所以我有一套语法

S -> X Y
X -> a X
X -> 
Y -> b
Z -> a Z
Z -> a

我唯一对这个语法感到困惑的是 X 的第二个生产

那里什么都没有。这是否相当于使用 Epsilon ε 或 Lamda λ

我假设这只是语法符号的不同，但我想确定，因为我正在尝试构建第一个和后续集合

标签： parsinggrammarcontext-free-grammarparse-tree

解决方案

ε 和 λ（有时是 Λ）都被不同的作者用来表示空字符串。在现代写作中，ε 更为常见，但您经常会在较旧的教科书中找到 λ，在更旧的教科书中找到 Λ。

使用这些符号的目的是使空序列可见。不管它是怎么写的，它是一个空序列，应该像在你的生产中一样阅读它，就像它什么都没有一样X ⇒ 。

如果您很难理解符号没有任何意义的想法，那么您可能会喜欢阅读 Charles Seife 的《零：一个危险想法的传记》或罗伯特·卡普兰的《虚无：零的自然历史》，均发表在象征性的 2K 年，两者都探索了理解虚无概念的漫长而艰难的斗争。（“没有人出去买零鱼”——阿尔弗雷德·诺斯·怀特黑德）。

有人认为 Λ/λ 来自德语单词“leer”，意思是空的，而 ε 来自英语“empty”。曾经有一段时间德语在数理逻辑的学术讨论中比较普遍，所以这个理论似乎是合理的。

推荐阅读