语言及文法

PL

语言的定义及运算

字母表

以 T/ΣT/\Sigma 表示，为字符的集合。

英文字母表 {a,b,c,...,A,B,C,...}\{\texttt{a}, \texttt{b},\texttt{c},...,\texttt{A},\texttt{B},\texttt{C},... \}

字符串

字母表 TT 上的字符串，为 TT 中字符构成的有限序列。

空串，用 ϵ\epsilon 表示。

字符串的长度 ∣w∣\lvert w \rvert，为 ww 中字符的个数。如，∣ϵ∣=0\lvert \epsilon \rvert = 0，∣abbaa∣=5\lvert \texttt{abbaa} \rvert = 5。

约定，a,b,c,da,b,c,d 等小写斜体表示单个字符，t,u,v,w,x,y,zt,u,v,w,x,y,z 表示字符串。

aia^i，表示 ii 个 aa 的字符串。

字符串的运算

连接

设 x=a1a2...amx = a_1a_2...a_m，y=b1b2...bny = b_1b_2...b_n，则 xy=a1a2...amb1b2...bnxy = a_1a_2...a_mb_1b_2...b_n。

连接具有以下性质：

  • (xy)z=x(yz)(xy)z=x(yz)

  • ϵx=xϵ=x\epsilon x = x \epsilon = x

  • ∣xy∣=∣x∣+∣y∣\lvert xy \rvert = \lvert x \rvert + \lvert y \rvert

前缀，后缀，子串

设 w1,w2,w3w_1,w_2,w_3 为 TT 上的字符串，则 w1w_1 为 w1w2w_1w_2 的前缀，w2w_2 为 w1w2w_1w_2 的后缀，w2w_2 为 w1w2w3w_1w_2w_3 的子串。

逆

w=b1b2...bnw = b_1b_2...b_n，w‾=bnbn−1...b1\overline w = b_nb_{n-1}...b_1

字母表的运算

幂运算

  1. T0={ϵ}T^0 = \{\epsilon \}
  2. x∈Tn−1,a∈T⇒ax∈Tnx \in T^{n-1}, a \in T \Rightarrow ax \in T^n

闭包

∗* 闭包：T∗=T0∪T1∪T2∪...T^* = T^0 \cup T^1 \cup T^2 \cup ...

++ 闭包：T+=T1∪T2∪...T^+ = T^1 \cup T^2 \cup ...

T∗=T+∪{ϵ}T^* = T^+ \cup \{\epsilon\}，T+=T∗−{ϵ}T^+ = T^* - \{\epsilon\}

闭包为 TT 上所有字符串的集合。

语言

设 TT 为字母表，则集合 L⊂T∗L \sub T^* 为 TT 上的一个语言。

如，设 T={a,b}T = \{\texttt{a},\texttt{b}\}

  • L1={anbn∣n≥1}L_1 = \{\texttt{a}^n\texttt{b}^n|n\geq 1\}
  • L2={ϵ}L_2 = \{\epsilon\} 只有一个空句子的语言
  • L3={}=∅L_3 = \{\} = \emptyset 空语言

语言的运算

积/幂

字符串的连接。

文法

元语言：描述语言的语言

BNF 范式

⟨digit⟩::=0∣1∣2∣3∣4∣5∣6∣7∣8∣9\langle\text{digit}\rangle::=\texttt0|\texttt1|\texttt2|\texttt3|\texttt4|\texttt5|\texttt6|\texttt7|\texttt8|\texttt9 ⟨letter⟩::=A∣B∣C∣...∣z∣a∣b∣c∣...∣z\langle\text{letter}\rangle::=\texttt A|\texttt B|\texttt C|...|\texttt z|\texttt a|\texttt b|\texttt c|...|\texttt z ⟨identifier⟩::=⟨letter⟩∣⟨identifier⟩⟨digit⟩∣⟨identifier⟩⟨letter⟩\langle\text{identifier}\rangle::=\langle\text{letter}\rangle|\langle\text{identifier}\rangle\langle\text{digit}\rangle|\langle\text{identifier}\rangle\langle\text{letter}\rangle

文法定义

文法 GG 是一个四元组 G=(N,T,P,S)G = (N, T, P, S)，其中

  • NN 为非终结符的有限集合；
  • TT 为终结符的有限集合，N∩T=∅N\cap T = \emptyset；
  • PP 为形式为 α→β\alpha \to \beta 的生成式的有限集合，其中 α∈(N∪T)∗N+(N∪T)∗\alpha \in (N\cup T)^*N^+ (N\cup T)^*，β∈(N∪T)∗\beta \in (N\cup T)^*；
  • SS 为推导起始符，且 S∈NS \in N。

推导

直接推导：一步直接产生。

若存在推导序列使得 α⇒α1⇒...⇒α′\alpha \Rightarrow \alpha_1 \Rightarrow ... \Rightarrow \alpha'，则把 α\alpha 推导出 α′\alpha' 记作

α→G∗α′\alpha \xrightarrow[G]*\alpha'

若推导序列长度大于 0，则记作

α→G+α′\alpha \xrightarrow[G]+\alpha'

推导时每一步产生的中间字符串称作句型。

句型：字符串 α\alpha 是文法 GG 的句型，当且仅当 S→G∗αS\xrightarrow[G]*\alpha，且 α∈(N∪T)∗\alpha \in (N\cup T)^*。

句子：字符串 ω\omega 是文法 GG 的句子，当且仅当 S→G∗ωS \xrightarrow[G]*\omega，且 ω∈T∗\omega \in T^*。

句子仅由终结符组成，句型包含句子。

文法产生的语言：由文法 GG 产生的语言记作 L(G)L(G)。

L(G)={ω∣ω∈T∗∧S→G∗ω}L(G) = \{\omega|\omega \in T^*\wedge S \xrightarrow[G]*\omega\}

Chomsky 文法的分类

0 型文法

1 型文法/上下文有关文法

定义：生成式具有形式 α→β\alpha \to \beta，α,β∈(N∪T)+\alpha, \beta \in (N\cup T)^+，且满足 ∣α∣≤∣β∣\lvert\alpha\rvert \leq \lvert\beta\rvert。

2 型文法/上下文无关文法

定义：生成式具有形式 A→βA \to \beta，A∈NA \in N，β∈(N∪T)∗\beta \in (N\cup T)^*。

3 型文法/正则文法

定义：生成式具有形式

  • 右线性文法：A→ωB∣ωA \to \omega B | \omega，A,B∈N,ω∈T∗A, B \in N, \omega \in T^*
  • 左线性文法：A→Bω∣ωA \to B\omega | \omega，A,B∈N,ω∈T∗A, B \in N, \omega \in T^*

四种文法的关系

  • 0 型：无限制；
  • 1 型：不允许 A→ϵA \to \epsilon；
  • 2 型
  • 3 型：属于 2 型；
  • 不含有 A→ϵA \to \epsilon 的 2 型、3 型属于 1 型，1 型、2 型和 3 型均属于 0 型。