编译原理 文法和语言讲解

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

指导教师:杨建国 二零零七年十一月1

第三章 文法和语言 第一节 文法的直观概念 第二节 符号和符号串盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

第三节 文法和语言的形式定义 第四节 文法的类型 第五节 上下文无关文法及其语法树 第六节 句型分析 第七节 有关文法实用中的一些说明 第八节 典型例题及解答2

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

知 识 结 构

第三章 文法和语言盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

§3.1 文法的直观概念 所谓一个语言的语法是指一组规则，用它可 以形成和产生一个合适的程序 目前广泛使用的手段是上下文无关文法，即 用上下文无关文法作为程序设计语言语法的描 述工具4

程序设计语言的描述：盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

语法： 程序的结构或形式

语义： 语言所代表的含义

语用： 语言的实际应用

例如，对于赋值语句x : = a + b 述是：

*

c的非形式描

语法：赋值语句=变量+:=+表达式盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

语义：先求右部，然后把结果给左部变量 语用：赋值语句可用来计算和保存表达式的值

形式化方法：用一整套带有严格规定的符号体系 来描述问题的理论和方法

形式语言：一种不考虑含义的符号语言6

程序设计语言的语义分成：盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

静态语义：是一系列限定规则，并确定哪些合乎 语法的程序是合适的

动态语义(运行语义、执行语义):表明程序要 做什么，要计算什么

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

以自然语言为例，人们无法列出全部句子， 但是人们可以给出一些规则，用这些规则来说 明(或者定义)句子的组成结构：

例如, 有一组规则: < 句子 > :: = < 主语 > < 谓语 > < 主语 > :: = < 冠词 > < 形容词 > < 名词 > < 冠词 > :: = the盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

< 冠词 > :: = a< 形容词 > :: = big < 谓语 > :: = < 动词 > < 直接宾语 >

< 动词 > :: = ate< 直接宾语 > :: = < 冠词 > < 名词 > < 名词 > :: = cat

< 名词 > :: = mouse显然, 由这一组规则可以产生句子: The big cat / mouse ate a mouse / cat9

这样的语言描述称为文法盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

使用文法作为工具，不仅为了严格地定义句 子的结构，也是为了适当条数的规则把语言 的全部句子描述出来，可以说文法是以有穷 的集合刻画无穷的集合的一个工具。

§3.2 符号和符号串一.字母表和符号串盛 威 网 ： 专 业

的 计 算 机 学 习 网 站

1.语言可以看成在一个基本符号集上定义的，按一定规 则构成的一切基本符号串组成的集合2.字母表(符号集):是一个非空有穷集合 3.符号(字符):字母表中的元素 4.符号串：符号的有穷序列。注意： 表示空符号串！ 5.符号串集合：字母表 上若干个符号串组成的集合11

重要约定：盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

小写字母 a, b, c,

, r 表示符号

小写字母 s, t, u, , z 表示符号串

大写字母 A, B, C, , Z 表示符号串集合

二.符号串的运算盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

1.符号串相等设x、y是字母表 上的两个符号串，若x与y 的诸符号依次相等，则该两符号串相等，记为 x=y。

2.符号串长度设x是字母表 上的符号串，符号串中包含符号 的个数称为符号串 x 的长度，用 x 表示盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

例:(1) | |= 0 ; (2) |ax|=|xa|=|x| + 1(a∈∑) 【注】对于字母表A={begin,if,real,end} 【1】符号串beginif的长度是多少？ 2 【2】 begini或eginif是不是A上的符号串

3.符号串的连结设x与y是字母表 上的两个符号串，把y的所盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

有符号相继写在x的符号之后所得到的符号串称为

x与y的连结，用xy表示

注意: |xy|=|x|+|y| x = x = x

xy ≠ yx ( 一般说来 )15

4.符号串的逆设x是字母表 上的符号串，其逆为符号串x的 ~ 倒臵，记为 X 。盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

(1)若x=abcd,则 X = dcba

~

(2) =

~