语言与文法

• 语言与文法
  • 语言的定义与运算
  • 文法
  • 推导和句型
  • 文法的分类

语言的定义与运算

• 字母表：字符的有限集合
  • 字符不一定是单个字符，如 aa 也可以是一个字符
  • 字符不允许重复，具有唯一性
  • 常用 T 、\(\sum\) 表示
• 字符串：由字母表中的字符构成的有限序列
  • 空串用 \(\epsilon\) 表示
  • 字符串 w 的长度记为 |w|

字符串的运算

• 连接：把两个字符串相连
  • 结合律：\((xy)z=x(yz)\)
  • \(\epsilon x=x \epsilon=x\)
  • \(|xy|=|x|+|y|\)
• 前缀、后缀、子串
  • 空串是任何字符串的前缀、后缀和子串
• 逆：w 的逆记为 \(\overline{w}\)
  • 空串的逆还是空串
• 幂运算
  • \(T^0={\epsilon}\)
  • \(x \in T^{n-1},a\in T,ax\in T^n\)
  • • 闭包 \(T^* = T^0\cup T^1...\)，字母表 T 上的所有字符串和空串的集合
  • • 闭包 \(T^+=T^1\cup T^2...\)，字母表 T 上的所有字符串的集合
  • • 闭包不包含空串

语言

• 定义：设 T 为字母表，则任何 T* 的子集 L 就是字母表 T 上的一个语言，可能有限可能无限
• 空语言：不包含任何字符串的语言，不是只包含空串的语言，记为 \(\Phi\)

语言的基本运算

• 积：两个语言的积就是两个语言中的字符串连接构成的集合，注意先后顺序
  • 积不满足交换律
  • 语言的幂：\(L^n=L^{n-1}\cdot L=L\cdot L^{n-1}\)

文法

定义：定义语言的数学模型

表示语言的方法

• 有限：穷举法
• 无限
  • 文法产生系统，由定义的文法规则产生语言
  • 机器识别系统（自动机）：当一个字符串能被一个语言的识别系统接收，就属于语言；否则不属于

元语言：用来描述语言的语言

BNF 范式：通常作为讨论程序设计语言的元语言

文法是一种元语言，一种方法，根据文法产生语言的句子

Chomsky 文法体系

• 文法的生成式：\(\rightarrow\) 表示可替代，如 \(L\rightarrow a|b|c...|z\) 表示小写字母
• 生成式集合：一个文法的所有生成式
• 任何一种文法必须包含两个不同的有限符号的集合，即非终结符集合 N 和终结符集合 T，一个形式规则的有限集合 P ，一个起始符 S
• P 中的生成式是产生语言句子的规则，句子是仅由终结符构成的字符串，这些字符串必须从起始符 S 开始，不断使用 P 中的生成式导出
• 文法的核心是生成式的集合

文法的形式定义

• 文法 G 是一个四元组 G = ( N,T,P,S )
• P 的形式为 \(\alpha\rightarrow\beta\)
  • \(\alpha\in(N\cup T)^*N^+(N\cup T)^*\)，即 N 和 T 中字符的任意组合，不包含空串
  • \(\beta\in(N\cup T)^*\)，即 N 和 T 中字符的任意组合
  • S 为起始符，\(S\in N\)

推导和句型

• 直接推导
  • 对于文法 G，若有生成式 \(A\rightarrow\beta;\alpha,r \in(N\cup T)^*\)，则称 $\alpha A r => \alpha\beta r $为直接推导
• 推导序列
  • 对于文法 G，若 \(a_i\rightarrow a_{i+1}\)，则称 \(a_0=>a_1=>a_2...=>a_n\) 为长度为 n 的推导序列
  • 对 \(a_0\) 推导出 \(a_n\) 可以记为 \(a_0 \rightarrow^*_G a_n\)，若推导序列长度大于 0，可以把 * 改成 +
  • 推导序列的每一步都产生一个字符串，这些字符串称为句型

句型：字符串 a 是文法 G 的句型当且仅当 \(S\rightarrow^*_G a\)

句子：w 是 G 的句子当且仅当 \(S\rightarrow ^*_G w\)，且 $w\in T^* $，即 w 是由终结符组成的字符串

句型包含句子

文法产生语言的定义

由文法 G 产生的语言记为 L(G)，\(L(G)=\{w|w\in T^*且S\rightarrow _G^* w\}\)

文法的分类

文法根据生成式的形式分为四类：0 型，1 型，2 型，3 型

• 0 型：无限制，对应递归可枚举语言，与图灵机等价
• 1 型：上下文有关文法，生成式形式为 \(\alpha\rightarrow\beta,|\alpha|\leq|\beta|,\beta\in(N\cup T)^+\)，对应上下文有关语言，与线性有界自动机等价
• 2 型：上下文无关文法，生成式形式为 \(A\rightarrow\beta,A\in N,\beta\in(N\cup T)^*\)，对应上下文无关语言，与下推自动机等价
• 3 型：正则文法
  • 右线性文法，生成式形式为 \(A\rightarrow wB或A\rightarrow w,A,B\in N,w\in T^*\)
  • 左线性文法，生成式形式为 \(A\rightarrow Bw或A\rightarrow w,A,B\in N,w\in T^*\)
  • 对应正则语言，与有限自动机等价

文法唯一表示一种语言，一种语言可以用多个文法表示

2 型包含 3 型，不包含 \(A\rightarrow\epsilon\) 的 2 型和 3 型属于 1 型