syntax - 什么是上下文无关语法和巴科斯诺尔范式？

Question

有人可以用通俗的语言解释一下吗:

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

2. 什么是巴科斯诺尔范式？

3. 如何使用这个表示法？

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

5. 如何描述语言语法？

Answer 1

上下文无关语法 (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)是表示上下文无关语法(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

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

干杯!