什么是上下文无关文法和Backus Naur形式？ [英] What are Context-Free Grammars and Backus Naur Form?
问题描述
有人可以用外行人的术语解释一下吗？
Can someone please explain in layman's terms:
-
什么是无上下文语法？
what a context-free grammar is?
什么是Backus Naur形式？
what Backus Naur Form is?
如何使用此符号？
如何进行字符串派生？
如何描述语言语法？
推荐答案
上下文无关文法（CFG）G是四元组（V，Σ，R，S），其中
A context-free grammar (CFG) G is a quadruple (V, Σ, R, S) where
- V：一组非终端符号
- Σ：一组终端（V∩ Σ=Ǿ）
- R：一组规则（R：V→（VUΣ）*）
- S：起始符号
- V: a set of non-terminal symbols
- Σ: a set of terminals (V ∩ Σ = Ǿ)
- R: a set of rules (R: V → (V U Σ)*)
- S: a start symbol
CFG示例：
Example of CFG:
- V = {q，f，}
- Σ= {0，1}
- R = {q→11q，q→00f，f→11f，f→ε}
- S = q
- （R = {q→11q | 00f，f→11f |ε}）
- V = {q, f,}
- Σ = {0, 1}
- R = {q → 11q, q → 00f, f → 11f, f → ε}
- S=q
- (R= {q → 11q | 00f, f → 11f | ε })
据我了解，巴科斯·诺尔表格（BNF）是表示Ť上下文无关语法（CFG）中显示的铰链
As far as I understand, Backus Naur Form (BNF) is another way of representing the things that are shown in the Context-Free Grammar (CFG)
BNF示例：
Example of BNF:
[数字] :: = [数字] | [数字] [数字]
[number] ::= [digit] | [number] [digit]
[数字] :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
[digit] ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
，其含义如下：
数字是数字，或任何数字后跟一个额外的数字
（其中是一种曲折而精确的说法，即数字由一个或多个数字组成）
数字是字符0、1、2，... 9中的任何一个
which can be read as something like: "a number is a digit, or any number followed by an extra digit" (which is a contorted but precise way of saying that a number consists of one or more digits) "a digit is any one of the characters 0, 1, 2, ... 9"
差异：
Difference:
这两种表示的符号有些不同，即
Notation of these two representations are a bit different, i-e
->等于:: =
|等于或
必须存在一些其他差异，但老实说，我不知道其他任何东西：）
there must be some other differences but to be honest I don't know any other :)
字符串派生：
String Derivation:
以S开头符号
- S-> A，初始状态
- A-> 0A
- A- -> 1B
- A->？
- B-> 1B
- B-> ？
- S --> A, the initial state
- A --> 0A
- A --> 1B
- A --> ?
- B --> 1B
- B --> ?
字符串派生示例：
Example of String Derivation:
此语法是否生成字符串000111？
是的，确实如此！
Does this grammar generate the string 000111?
yes, it does!
- S-> A
- A-> 0A
- 0A-> 00A
- 00A- -> 000A
- 000A-> 0001B
- 0001B-> 00011B
- 00011B-> 000111
- S --> A
- A --> 0A
- 0A --> 00A
- 00A --> 000A
- 000A --> 0001B
- 0001B --> 00011B
- 00011B --> 000111
这全都是我的意思，我也正在为此做准备，如果我能进一步了解定义该主题的细节，我一定会分享。语言语法。
that's all from my side, I too am working on it and will surely share if I come to know anymore details about defining the language syntax.
欢呼！
这篇关于什么是上下文无关文法和Backus Naur形式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
