上下文无关文法

1、文法

2、语言描述的几个基本概念

基本概念1

字母表：一个有穷字符集，记为∑
字母表中的每个元素称为字符
∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列
不包含任何字符的序列称为空字，记为ε
用∑* 表示∑上所有字的全体，包含空字ε
例如：设∑={a, b}, 则
∑*={ε, a, b, aa, ab, ba, bb,…}

基本概念2

• ∑*的子集U和V的连接(积)定义为
• UV = {α,β | α∈U&β∈V}(U和V的前后顺序影响结果)
  示例：设
  U={a, aa}
  V={b, bb}
  UV={ab,abb,aab,aabb}
• V自身的n次积记为
  Vⁿ = VVVVV…(n个)
• V⁰ = {ε}
• V*是V的闭包：V * = V⁰∪V¹∪V²∪V³∪V⁴∪…
• V+是V的正规闭包：V+ = VV*
• 思考一下V*和V+的区别？
  有时是相等，有时不相等。
  如果V中原来没有空字，闭包会有空字，正规闭包不会有空字。
• 设U={a, aa}
  U* = {ε,a, aa, aaa, aaaa, aaaaa,…}
  U+ ={a, aa, aaa, aaaa,…}

3、上下文无关文法

https://blog.csdn.net/panjunbiao/article/details/9268891
https://blog.csdn.net/chenxu6/article/details/46490689

文法描述形式

上下文无关文法G是一个四元组G=(VT, VN, S, P),其中：

• VT：终结符(Terminal)集合(非空)(不可以分解)
• VN: 非终结符集合(非空)，且VT∩VN=Ø(可以分解)
• S：文法的开始符号，S∈VN
• P：产生式集合(有限)，每个产生式形式为
  P→α，P∈VN，α∈(VT∪VN)*
• 开始符S至少必须在某个产生式的左部出现一次，否则就没有意义

巴科斯范式(BNF)

• “→"用”::="表示
• 约定
  P→α1
  P→α2
  …
  P→αn
  可以缩写为
  P→α1|α2|…|αn
  其中，"|“读成"或”，称αi为P的一个候选式
  表示一个文法时，通常只给出开始符号和产生式，就可以了。
  非终结符用大写字母表示，终结符用小写字母表示