logo标签列表

什么是无上下文文法和Backus Naur形式？

syntaxcontext-free-grammarbnf
3

请用通俗易懂的语言解释以下问题：

  1. 什么是无上下文文法？

  2. 什么是Backus Naur形式？

  3. 如何使用这种符号表示方法？

  4. 如何进行字符串派生？

  5. 如何描述语言的句法结构？

2个回答
8
一个上下文无关文法（CFG）G是一个四元组（V，Σ，R，S），其中：
- V：非终止符号的集合 - Σ：终止符号的集合（V ∩ Σ = Ǿ） - R：规则的集合（R：V →（V U Σ）*） - S：起始符号
CFG的示例：
- V = {q，f} - Σ = {0，1} - R = {q → 11q，q → 00f，f → 11f，f → ε} - S = q - R= {q → 11q | 00f，f → 11f | ε}
据我所知，BNF是表示上下文无关文法中显示的内容的另一种方法。
BNF的示例：
[number] ::= [digit] | [number] [digit]
[digit] ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
这可以解读为：
“一个数字是一个数字，或者是任何一个数字后跟另一个数字”
“一个数字是0、1、2、……9中的任意一个字符”
这两种表示方法的符号有一些差别，即：
- -->等于::= - |等于or 除此之外，可能还存在其他差异，但说实话我不知道其他差异。
字符串派生：
设S为“起始”符号
- S --> A，初始状态 - A --> 0A - A --> 1B - A --> ? - B --> 1B - B --> ?
字符串派生的示例：
这个文法是否生成字符串000111？
是的，它生成了。
- S --> A - A --> 0A - 0A --> 00A - 00A --> 000A - 000A --> 0001B - 0001B --> 00011B - 00011B --> 000111

我就说这些了，我也在努力学习，并且如果我了解更多有关定义语言语法的细节，一定会分享给大家。

干杯!

在你的推导中，A和B分别代表什么？我之前从未见过这种方法。 - Andrew S
据我所知，A和B是非终端符号，而0和1是终端符号。 - Hugh Perkins
4
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接