syntax - 什么是上下文无关语法和巴库斯瑙尔形式？

Question

有人可以用外行的话解释一下：

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

2. 什么是巴克斯瑙尔形式？

3. 如何使用这个符号？

4. 如何进行字符串推导？

5. 如何描述语言语法？

Answer 1

上下文无关文法 (CFG) G 是四元组 (V, Σ, R, S)，其中

• V：一组非终结符号
• Σ：一组终端（V ∩ Σ = Ǿ）
• R：一组规则（R：V→（VU Σ）*）
• S：开始符号

CFG 示例：

• V = {q, f,}
• Σ = {0, 1}
• R = {q → 11q, q → 00f, f → 11f, f → ε}
• S=q
• (R= {q → 11q | 00f, f → 11f | ε })

据我了解，巴科斯瑙尔形式（BNF）是表示上下文无关语法（CFG）中显示的事物的另一种方式

BNF 示例：

[数字] ::= [数字] | [数字] [数字]

[数字] ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

可以理解为：“一个数字是一个数字，或者任何数字后跟一个额外的数字”（这是一种扭曲但精确的说法，一个数字由一个或多个数字组成）“一个数字是任何一个字符 0, 1, 2, ... 9"

不同之处：

这两种表示的符号有点不同，即

--> 等于 ::=

| 等于或

一定还有其他一些差异，但老实说我不知道​​其他的:)

字符串推导：

让 S 成为开始”符号

• S --> A，初始状态
• A --> 0A
• A --> 1B
• 一个 --> ？
• B --> 1B
• B --> ?

字符串派生示例：

这个语法会生成字符串 000111 吗？
是的，它确实！

• S --> A
• A --> 0A
• 0A --> 00A
• 00A --> 000A
• 000A --> 0001B
• 0001B --> 00011B
• 00011B --> 000111

这都是我的观点，我也在努力，如果我知道更多关于定义语言语法的细节，我一定会分享。

干杯！

Answer 2

上下文无关文法是一种形式语言。Backus Naur 形式是此类语法的规范语言。它用于描述语言语法。
您应该阅读： http:
//en.wikipedia.org/wiki/Formal_language_theory
http://en.wikipedia.org/wiki/Context-free_grammar
http://en.wikipedia.org/wiki/Backus%E2%80% 93Naur_Form