第二章 语言及其文法

---

文章目录

第二章 语言及其文法@[toc]1. 基本概念(1). 字母表(2). 符号表上的运算1). 字母表的乘积2). 字母表上的幂运算3). 字母表的正闭包4). 字母表的闭包 (3). 串(4). 符号串上的运算1). 符号串的长度2). 符号串的连接3). 符号串的幂运算 (5). 符号串集合上的运算1). 符号串集合的乘积运算2). 符号串集合的幂运算3). 符号串集合的闭包 2. 文法定义(1). 文法(2). 文法的形式化定义(3).产生式(4). 符号约定1). 终结符2). 非终结符 3. 语言定义(1). 推导和规约(2). 句型和句子(3). 语言的形式化定义(4). 语言上的运算 4. 文法的分类(1). 0型文法(2). 1型文法(CSG)(3). 2型文法(CFG)(4). 3型文法(RG) 5. CFG的分析树(1). 概念(2). 短语(3). 二义性文法

1. 基本概念

(1). 字母表

​ 字母表:字母表Σ是符号元素的非空集合.

​ 符号:字母表中的元素.

​ 符号串:字母表中符号组成的任意有穷序列.

例:有一个字母表Σ={a,b} 则:a,b是字母表中的符号 a,aa,aaa,ab,bb,bbb,abab,abaabb.....这些都是符号串

​ 空符号串:不含任何符号的符号串,用ε(epsilon)表示.

(2). 符号表上的运算

1). 字母表的乘积

​ Σ1Σ2 = {ab| a∈ Σ1, b ∈ Σ2}

{0, 1}{a, b} = {0a, 0b, 1a, 1b}

2). 字母表上的幂运算

​ 字母表的n次幂相当于n个字母表相乘.也就是长度为n的符号串构成的集合

3). 字母表的正闭包

​ Σ⁺ = Σ¹ ∪ Σ² ∪ Σ³ ∪ …

​ 相当于由字母表中字母构成的除空串以外的所有串.

4). 字母表的闭包

​ Σ^* = Σ⁰ ∪ Σ¹ ∪ Σ² ∪ Σ³ ∪ …

​ 现在包含空串了…

(3). 串

​ 字母表Σ上的闭包称之为Σ上的串,是表中符号的一个有穷序列.

(4). 符号串上的运算

1). 符号串的长度

​ 指符号串中符号的个数,用|X|表示.

例:|aabbb| = 5

2). 符号串的连接

​ 符号串x和y的链接用xy表示.

例:符号串x = ab, y = bc, 则xy = abbc, yx = bcab

3). 符号串的幂运算

​ 符号串x的幂运算就是指数个x的连接.

​ 任何符号串的零次幂都是空串ε.

例:符号串x = ab, 则x^2 = xx = abab

(5). 符号串集合上的运算

1). 符号串集合的乘积运算

​ 很像笛卡尔积,就是两个集合中的符号串两两进行连接操作.

例:符号串集合A={aa,b,ccc}, B={ce,abc} 则:AB = {aace, aaabc, bce, babc, cccce, cccabc} BA = {ceaa, ceb, ceccc, abcaa, abcb, abcccc}

2). 符号串集合的幂运算

​ 就是把符号串的幂运算中符号串的连接换成符号串集合的乘积运算.

例:符号串集合A={a,b,c} 则:A^2 = AA = {aa,ab,ab,ba,bb,bc,ca,cb,cc} 这里A的n次幂就是由A中的符号构成长度为n的所有符号串组成的集合.

3). 符号串集合的闭包

​ 正闭包:A+ = A^1 ∪ A^2 ∪ A^3 ∪…

​ 闭包:A+ = A^0 ∪ A^1 ∪ A^2 ∪ A^3 ∪…(多了一个A^0, 也就是空串ε)

2. 文法定义

(1). 文法

​ 任何程序都可以认为是一定字符集上的一个字符串,而判断一个字符串是否是一个结构上合法的程序就是依据语言的文法.

​ 语言的文法是一组规则,包含词法规则和语法规则.

​ 词法规则:描述语言**单词**构成的规则.语言的单词符号包括表示服,常数,运算符等.词法规则的描述工具通常为正规文法(正规式,有限自动机).

​ 语法规则:描述语言**语法单位**构成的规则.语法单位包括表达式,语句,函数,过程等.语法规则的描述工具通常为:上下文无关文法.

(2). 文法的形式化定义

​ 文法是一个四元组:G[S] = (Vn, Vt, P, S)

​ 其中:Vn是非终结符,就是所有出现在产生式左边的符号,有穷,用大写字母表示

​ Vt是终结符,是所有符号减去非终结符,有穷,用小写字母,运算符,数字,符号串表示

​ Vn ∩ Vt = ∅ (不会有一个符号既是非终结符也是终结符)

​ Vn ∪ Vt = V* (所有符号)

​ P为产生式的集合,有穷

​ S为文法的开始符号,是Vn(非终结符)的一部分

(3).产生式

​ 产生式: A → α, |A| = 1, |α| ≥ 0 (A的长度为1, α的长度任意)

​ 其中:A被称为产生式的左部符号,α为产生式的右部有穷符号串.

​ 产生式的简写:用 | 代表或者

(4). 符号约定

1). 终结符

​ 前面的小写字母,运算符,标点符号,数组,粗体字母

2). 非终结符

​ 前面的大写字母,S(开始符号),小写斜体的名字

3. 语言定义

(1). 推导和规约

​ **推导**就是用产生式的右边反复的替换产生式的左边.

设G=(Vn, Vt, P, S)是给定的文法, x,y,A,B ∈ V*,且A→B属于P

此时符号串 xAy 可以直接产生出符号串 xBy,我们称:

​ 符号串 xBy 是 符号串 xAy 的直接推导

​ 符号串 xAy 是 符号串 xBy 的直接规约

推导和规约是逆过程

​ 直接推导使用=>表示, =>⁺表示正数步推导, =>^*表示若干步推导(可以为0步,也就是不推导)

(2). 句型和句子

​ 如果由一个文法的开始符号可以**推导出符号串a**,那么a是这个文法的句型,(a包含终结符,非终结符或者空串)

​ 如果这个符号串a**只包含终结符**,那么称a是这个文法的句子.通俗一点:在文法的推导过程中,所有出现的式子都是句型,最后一步的结果是句子.

(3). 语言的形式化定义

​ 一个文法G中,由开始符号**推导出的所有句子**构成的集合成为文法G生成的语言,记为L(G).

(4). 语言上的运算

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dOTLXNpO-1573983847355)(/home/benjamin/.config/Typora/typora-user-images/1573657365196.png)]

4. 文法的分类

​ 乔姆斯基将文法分为0型文法,1型文法,2型文法,3型文法.它们之间的关系是拓展,类似数据库概论中的范式

(1). 0型文法

​ 无限制文法

​ ∀a -> b ∈ P, a中至少包含一个非终结符

(2). 1型文法(CSG)

​ 上下文有关文法

​ ∀a -> b ∈ P, |a| ≤ |b|

​ 产生式的一般形式: a1 A b1 -> a1 B b1 (所以上下文有关了)

(3). 2型文法(CFG)

​ 上下文无关文法

​ ∀a -> b ∈ P, a ∈ Vn(推导中只能对单个的非终结符进行替换)

​ 产生式的一般形式:A -> B

(4). 3型文法(RG)

​ 正则文法,又分为右线性文法和左线性文法.

​ 右线性文法: A -> wB | w

​ 左线性文法: A -> Bw | w

5. CFG的分析树

(1). 概念

​ 根节点的标号是文法的开始符号

​ 内部结点表示一个产生式的应用

​ 分析树不唯一

​ 叶节点可以使非终结符也可以是终结符.从左到右排列的所有叶节点成为这棵树的边缘.

​ 如果一个文法可以为某个句子生成多颗分析树,那么这个文法是二义性的.

(2). 短语

​ 对于一个给定的句型,其分析树中的每一颗子树的边缘都成为该句型的一个短语.(当前推导中某个产生式的右部)

​ 如果这个子树的高度仅为2,那么这颗子树的边缘成为该句型的直接短语.

(3). 二义性文法

​ 如果一个文法可以为某个句子生成多颗分析数,则称这个文法是二义性的.