第三章 文法和形式语言基础【荐】.pdf

第三章 文法和形式语言基础 周开来 西南林业大学计算机与信息科学系 第三章 文法和形式语言基础 一、程序语言语法描述的基本概念 二、上下文无关文法 三、语法分析树与二义性 四、形式语言概要 一、程序语言语法描述的基本概念 语言是在某一个特定的字母表上的符号串组成的 集合。（自然语言和形式语言） 程序设计语言是一种符号语言，具有一般形式语 言的共同特征。 形式语言的几个基本概念： 字母表 符号串 符号串的运算 符号串集合及运算 1. 字母表 1.字母表： 定义：字母表是有穷非空的符号集合，用∑表示。 把字母表上的一个元素称为一个符号。 例1： 二进制语言的字母表:{0，1} 例2： C语言的字母表:{a,b,c……z,0，1……9,+,-,*……} 2. 符号串 定义：字母表∑上的符号串是指由∑上的符号 构成的一个有穷序列。 符号串也可叫作字。 例如，字母表∑={a,b,c}上的符号串有： a,b,c,aa,ab,ac,bb,bc,cc,abc,aaa,bbb…… 说明： （1）不包含任何字符的序列称为空字，记为 ε （2）符号串中的符号是有序的 如：ab与ba是不同的符号串 2. 符号串 1.符号串相等：若x、y是集合上的两个符号串，则x＝y iff（当且仅当）组成x的每一个符号和 组成y的每一个符号依次相等。 2.符号串的长度：x为符号串，其长度|x|等于组成该符 号串的符号个数。 例： x＝STV ， |x|=3 3.符号串的运算 (1)连接（积） 设α和β是同一字母表上的两个字符串。把β 的各个符 号相继写在 α符号之后得到的符号串称为α和 β 的连 接。记为αβ 。 例：设在∑ {a,b,c}上有符号串α =ab, β =cba,则： αβ =abcba; β α =cbaab 例：A ＝{a,b},B={c,d}, AB= ？ {ac，ad ，bc ，bd} 因为εx ＝x ε＝x ，所以{ ε}A=A{ ε}=A 3.符号串的运算 (2) 方幂（n次连接） 设α是字母表上的一个字符串，把α 自身连接n次，即 γ= α α α …… α(n个α)，称为符号α 的n次方幂。 记为： γ= α n 注意： n=0时， α 0= ε 例：设α=ab，则 0 1 2 3 α = ε, α =ab, α =abab, α =ababab 4.符号串集合及运算 定义：若集合U中的所有元素都是某字母表∑上的符 号串，则称U为该字母表∑上的符号串集合。 例如： 已知 ∑={a,b,c},则U={a,b,c,aa,bb,cc,abc}是∑上 符号串集合，而V={a,b,c,d,aa,bb,cc,abc}则 不是∑上的符号串集合。 不含有任何元素的空集{ }用Φ表示 (1) 符号串集合的连接 定义： 若集合U和集合V都是某字母表∑上的符号串集 合，则U和V 的连接（积）定义为 UV ＝{ αβ | α∈U β∈ V } 例如，设： ∑={a,b,c} U ＝{ a, ab } V ＝ { b, bc } 那么： UV= { ab, abc, abb, abbc} 注意： (1) 对于任意符号串α有, εα=α ε=α (2) { ε}U=U{ ε}=U (3) Φ U=U Φ= Φ (2)符号串集合的方幂: 定义:集合V 的方幂为集合V 中的多次自身连接. n 即