BNF的BNF是什么？即如何定义BNF元语法？

Question

我正在尝试定义BNF的BNF。换句话说，我正在尝试定义BNF的元语法。也就是说，一个BNF语法是它自己的实例，并且可以生成任何其他的BNF语法。

如果有任何提示/提示/片段，将不胜感激！

谢谢！

- skyknight

---

你的问题似乎已经在BNF维基百科文章中得到了回答。 - Greg Hewgill

@EJP：De Remer在解析器生成器和语法方面非常出色，我不相信他会教这个。我怀疑你记错了你所学的东西。 - Ira Baxter

@EJP：所以，想必这个事实是由某些不可能性证明支持的。你还记得吗？ - Ira Baxter

@EJP：所以，你无法描述变量名的词法结构，因为“<”字符用作变量名的引导？好吧，如果你坚持*变量名拼写为“<var>”，而语法不涉及字符，则我可以看到问题所在。如果您确实*涉及字符，引用字符文字，定义一个拼写涉及“<”的变量，则这不是问题。 - Ira Baxter

@EJP：如果您想使用“<...>”作为标识符名称来创建BNF-of-BNF，只需按照明显的方式修改我提供的自我BNF即可。 - Ira Baxter

Answer 1

这里有一个：

bnf = rules ;
rules = rule ;
rules = rules rule ;
rule = lefthandside EQUAL righthandside SEMICOLON  ;
lefthandside = IDENTIFIER ;
righthandside = ;
righthandside = righthandside token ;
token = IDENTIFIER ;
token = QUOTEDLITERAL ;

这意味着在假设BNF定义为语言标记的情况下，IDENTIFIER、QUOTEDLITERAL、EQUAL和SEMICOLON未被定义。

您可以将BNF定义为字符。只需添加：

EQUAL = '=' ;
SEMICOLON = ';' ;
IDENTIFIER = letter ;
IDENTIFIER = IDENTIFIER letterordigit ;
letterordigit = letter ;
letterordigit = digit ;
letter = 'A' ;
...
letter = 'Z' ;
digit = '0' ;
...
digit = '9' ;

作为读者的练习，请添加选择（|），多个规则和Kleene星号，使其成为EBNF的BNF；这个答案显然回避了空格的处理，但是您可以在允许空格的位置插入“空格”非终端（令人不快但有效）。有BNF规范系统，您实际上需要在字符上编写语法，并且为您执行了这种隐式的空白非终端插入（例如，Stratego's "Syntax Definition Formalism"）。

如果您想要关于BNF的惊人课程，您应该阅读1965年真正的“MetaII”BNF处理系统的paper/do the tutorial。本文介绍了如何在BNF中进行BNF以及如何构建两个编译器，所有这些都在10页内完成。

（一个重要教训：阅读60年代和70年代的所有计算机科学材料。它们并不多，您会惊讶于其中有多少好的材料）。

- Ira Baxter

Answer 2

<line> ::= '<' <word> '>' '::=' <definition>
<definition> ::= <word> '|' | '' <definition> | ''

- 13yr old computer nerd

Answer 3

编程语言的自我定义

通过使用元循环解释器，可以给出一种操作性的编程语言自我定义的示例。

Tymoczko, Thomas. “Gödel and the Concept of Meaning in Mathematics.” Synthese, vol. 114, no. 1, 1998, pp. 25–40

王浩(1980)报告说库尔特·哥德尔曾经说过，所有逻辑都可以从概念的概念(CoC)开始进行定义。CoC是自我定义的。CoC是由它本身定义的对象。

从哥德尔到哲学——逻辑之旅 郝旺带我们进入了哥德尔的思想世界。哥德尔将一个概念的概念描述为逻辑的基础。(第8章，第247页) “从1953年到1959年初，他花费了大量的精力在卡纳普的论文上，试图证明数学不是语言的句法，并支持某种形式的柏拉图主义。”

编程语言的语法（编程语言系列）1977年1月1日 第33页包含BNF的BNF。

- Tony Barr