语言及文法笔记
语言的定义与运算
- 字符的有限集合称为字母表，记为T
- 由字母表T中的字符构成的有限序列称为字母表T上的字符串
- 设ω 1 \omega_1ω1和ω 2 \omega_2ω2是字母表T上的字符串，ω 1 = a 1 a 2 . . . a m \omega_1=a_1a_2...a_mω1=a1a2...amω 2 = b 1 b 2 . . . b n \omega_2=b_1b_2...b_nω2=b1b2...bn则ω 1 ω 2 = a 1 a 2 . . . a m b 1 b 2 . . . b n \omega_1\omega_2=a_1a_2...a_mb_1b_2...b_nω1ω2=a1a2...amb1b2...bn
- T ∗ T^*T∗是字母表T上所有字符串和空串的集合，T + T^+T+是字母表T上的所有字符串构成的集合，并有T + = T ∗ − ϵ T^+=T^*-{\epsilon}T+=T∗−ϵ
- 字母表T上的语言L是T ∗ T^*T∗的子集
- 两个语言L 1 L_1L1和L 2 L_2L2的积L 1 L_1L1⋅ \cdot⋅L 2 L_2L2,是由L 1 L_1L1和L 2 L_2L2中字符串的连接所构成的字符串的集合，需要注意L 1 L_1L1⋅ \cdot⋅L 2 L_2L2≠ \neq=L 2 L_2L2⋅ \cdot⋅L 1 L_1L1
- 语言L的幂可归纳定义如下：
L 0 = ϵ L^0={\epsilon}L0=ϵL n = L ⋅ L n − 1 , n ≥ 1 L_n=L\cdot{L^{n-1}},n\ge1Ln=L⋅Ln−1,n≥1 - 语言L的闭包L ∗ L^*L∗定义为
L ∗ = ⋃ n ≥ 0 L n L^*=\bigcup_{n\ge0}L^nL∗=n≥0⋃Ln语言L的正闭包L + L^+L+定义为L + = ⋃ n ≥ 1 L n L^+=\bigcup_{n\ge1}L^nL+=n≥1⋃Ln
文法(Chomsky文法体系)
文法G是一个四元组，G = N , T , P , S G={N,T,P,S}G=N,T,P,S其中
(1)N NN 非终结符的有限集合
(2)T TT 终结符的有限集合，且N NN⋂ \bigcap⋂T TT=ϕ \phiϕ
(3)P PP 形式为α \alphaα→ \rightarrow→β \betaβ的生成式有限集合，且α ∈ ( N ⋃ T ) + \alpha\in(N\bigcup{T})^+α∈(N⋃T)+β ∈ ( N ⋃ T ) ∗ \beta\in(N\bigcup{T})^*β∈(N⋃T)∗且α \alphaα至少含一个非终结符号
(4)S SS 起始符，且S ∈ N S\in{N}S∈N
其中“→ \rightarrow→”含义是可被代替字符串α \alphaα是文法G GG的句型，当且仅当S ⟹ G ∗ α S\Longrightarrow_{G}^{*}\alphaS⟹G∗α且α ∈ ( N ⋃ T ) ∗ \alpha\in(N\bigcup{T})^*α∈(N⋃T)∗ω \omegaω是G GG的句子，当且仅当S ⟹ G ∗ ω S\Longrightarrow_{G}^{*}\omegaS⟹G∗ω且ω ∈ T ∗ \omega\in{T^*}ω∈T∗
文法的分类
0型文法
由定义1定义的不加任何限制的文法
由0型文法产生的语言称为无限制性语言
1型文法(上下文有关文法)
生成式的形式为α \alphaα→ \rightarrow→β \betaβ，其中∣ α ∣ |\alpha|∣α∣≤ \leq≤∣ β ∣ |\beta|∣β∣，且α \alphaα,β \betaβ∈ \in∈( N ⋃ T ) + (N\bigcup{T})^+(N⋃T)+,且α \alphaα至少含有一个非终结符号。
P特点：每个生成式左部字符串长度小于等于右部字符串长度
由1型文法产生的语言称为上下文有关语言
2型文法(上下文无关文法)
生成式的形式为A AA→ \rightarrow→α \alphaα,A AA∈ \in∈N NN且α \alphaα∈ \in∈( N ⋃ T ) + (N\bigcup{T})^+(N⋃T)+
P特点：每个生成式的左部是单个非终结符
由2型文法产生的语言称为上下文无关语言
其常见表示形式有
(1) 巴科斯范式(BNF, Backus Normal Form)
例：用BNF表示法描述十进制数的文法的生成式
<十进制数>::=<无符号整数>|<十进制小数>|<无符号整数><十进制小数>
<十进制小数>::=.<无符号整数>
<无符号整数>::=<数字>|<数字><无符号整数>
<数字>::=0|1|2|3|4|5|6|7|8|9
(2) 语法图
- 每一个语法图表示一个语法规则
- 圆边框或圆形框内书写的是“终结符号”
- 矩形框内所写的则是“非终结符号”
- 用语法图定义语法规则的过程类似于“自顶向下，逐步细化”的过程
- 语法图与流程图不同，语法图只规定了语法的内容和次序，与步骤无关
3型文法(正则文法)
右线性文法：生成式的形式为A AA→ \rightarrow→ω \omegaωB BB或A AA→ \rightarrow→ω \omegaω，A AA，B BB∈ \in∈N NN，ω \omegaω∈ \in∈T ∗ T^*T∗
左线性文法：生成式的形式为A AA→ \rightarrow→B BBω \omegaω或A AA→ \rightarrow→ω \omegaω，A AA，B BB∈ \in∈N NN，ω \omegaω∈ \in∈T ∗ T^*T∗
由3型文法产生的语言称为正则语言
文法之间的关系(若无A AA→ \rightarrow→ω \omegaω，则为包含关系)
1、2、3型文法都是在0型闻法得前提下所加的限制，所以必然属于0型文法
1型文法不允许形式为A AA→ \rightarrow→ω \omegaω的生成式存在，所以具有A AA→ \rightarrow→ω \omegaω生成式的2型文法或3型文法不属于1型文法
如果2型文法或3型文法没有A AA→ \rightarrow→ω \omegaω生成式存在，则其属于1型文法