什么是无上下文语法和巴克斯Naur形式？

Question

有人可以用外行的话来解释:

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

2. Backus Naur表格是什么？

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 |ε})

据我所知,Backus Naur Form(BNF)是另一种表示Context Free Grammar(CFG)中显示的内容的方式

BNF的例子:

[编号] :: = [数字] | [编号] [数字]

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

它可以被解读为:"数字是一个数字,或任何数字后跟一个额外的数字"(这是一种扭曲但精确的方式,表示一个数字由一个或多个数字组成)"一个数字是任何一个字符0,1,2,... 9"

区别:

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

- > equals :: =

| 等于或

必须有一些其他的差异,但说实话,我不知道任何其他:)

字符串派生:

让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

这一切都在我身边,我也正在努力,如果我再了解有关定义语言语法的细节,我肯定会分享.

干杯!