语言及文法

#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_my=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_3TT 上的字符串,则 w1w_1w1w2w_1w_2 的前缀,w2w_2w1w2w_1w_2 的后缀,w2w_2w1w2w3w_1w_2w_3 的子串。

w=b1b2...bnw = b_1b_2...b_nw=bnbn1...b1\overline w = b_nb_{n-1}...b_1

字母表的运算

幂运算

  1. T0={ϵ}T^0 = \{\epsilon \}
  2. xTn1,aTaxTnx \in T^{n-1}, a \in T \Rightarrow ax \in T^n​

闭包

* 闭包T=T0T1T2...T^* = T^0 \cup T^1 \cup T^2 \cup ...

++ 闭包T+=T1T2...T^+ = T^1 \cup T^2 \cup ...

T=T+{ϵ}T^* = T^+ \cup \{\epsilon\}T+=T{ϵ}T^+ = T^* - \{\epsilon\}

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

语言

TT 为字母表,则集合 LTL \sub T^*TT 上的一个语言

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

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

语言的运算

积/幂

字符串的连接。

文法

元语言:描述语言的语言

BNF 范式

digit::=0123456789\langle\text{digit}\rangle::=\texttt0|\texttt1|\texttt2|\texttt3|\texttt4|\texttt5|\texttt6|\texttt7|\texttt8|\texttt9 letter::=ABC...zabc...z\langle\text{letter}\rangle::=\texttt A|\texttt B|\texttt C|...|\texttt z|\texttt a|\texttt b|\texttt c|...|\texttt z identifier::=letteridentifierdigitidentifierletter\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 为终结符的有限集合,NT=N\cap T = \emptyset
  • PP 为形式为 αβ\alpha \to \beta 的生成式的有限集合,其中 α(NT)N+(NT)\alpha \in (N\cup T)^*N^+ (N\cup T)^*β(NT)\beta \in (N\cup T)^*
  • SS​ 为推导起始符,且 SNS \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 的句型,当且仅当 SGαS\xrightarrow[G]*\alpha,且 α(NT)\alpha \in (N\cup T)^*

句子:字符串 ω\omega​ 是文法 GG​ 的句子,当且仅当 SGωS \xrightarrow[G]*\omega​,且 ωT\omega \in T^*​

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

文法产生的语言:由文法 GG 产生的语言记作 L(G)L(G)L(G)={ωωTSGω} L(G) = \{\omega|\omega \in T^*\wedge S \xrightarrow[G]*\omega\}

Chomsky 文法的分类

### 0 型文法

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

定义:生成式具有形式 αβ\alpha \to \betaα,β(NT)+\alpha, \beta \in (N\cup T)^+,且满足 αβ\lvert\alpha\rvert \leq \lvert\beta\rvert

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

定义:生成式具有形式 AβA \to \betaANA \in Nβ(NT)\beta \in (N\cup T)^*

3 型文法/正则文法

定义:生成式具有形式

  • 右线性文法:AωBωA \to \omega B | \omegaA,BN,ωTA, B \in N, \omega \in T^*
  • 左线性文法:ABωωA \to B\omega | \omegaA,BN,ωTA, 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 型。