第二章形式语言与文法1报告.ppt

编 译 原 理 第二章 形式语言与文法 主要内容: 1 语言的形式描述. 2 语言与文法的形式定义. 3 文法的分类. 4 语法树及句型分析. § 1.符号串 符号串是形式语言中最基本的名词. 一, 字母表与符号串 1,字母表∑ 定义:元素的非空有穷集合 例:∑={a, b, c} (a, b, c字母表) ∑={0, 1} (二进制数字字母表) ∑={汉字,数字,标点符号, …} (汉字组成的字母表) 注:元素可是字母、数字或其他符号. 字母表中至少有一个元素. 2. 符号(字符) 定义：字母表中的元素. 注:符号是字母表中不可再分解的最小单位. 3. 符号串 　　定义：字母表中的符号组成的有穷序列. 例:∑={a, b, c} 符 号:a, b, c 符号串:a, b, c, ab, ac, aa, ba, ca, abc, … 例;设字母表A={0, 1} A中的符号:0, 1 A中的符串:0,1,01,10,00,11,001,010, …,01000, … 显然:字母表上的符号串可形成一个集合(可数无穷) 注: 1.符号串的组成是有序的.如:01≠10,ab≠ba 2.空符号串为不包含任何符号的符号串,记为: ε 3.符号串的长度:符号串所含符号的个数.设符号串为x,则x的 长度为∣x∣。 例:∣a∣=1 ∣abc∣=3 特别：|ε |＝0　即空符号串的长度为零． 二．符号串的运算 １．连接运算 　定义：设x和y为符号串，则xy被称为x与y的连接． 　　设x＝abc，y＝10a 　　则xy＝abc10a；yx＝10aabc ２．符号串的方幂 设有符号串x，则x的n次连接称为x的n次方幂，记为:x 　　例：x ＝ ε 　（注:x ≠１） 　　　　x＝x 　　　　x ＝xx 　　　　x ＝x x＝xx ＝xxx 　　　　…… 　　　　x＝x　x＝xx　＝xx…x 　　　　　　　　　　　　n次连接 　　例:x＝abc　则x＝ ε ，x ＝abc，x ＝abcabc 　　　即︱x︱＝０，︱x︱＝３，︱x︱＝６ ３．符号串集合的乘积 　设AB＝｛xy︱x∈Ａ，y∈Ｂ｝ 　即:AB是x∈Ａ,且y∈Ｂ的所有符号串xy构成的集合． 　 例:设A＝｛a，b｝，B＝｛c，d｝ 　　　则AB＝｛ac，ad，bc，bd｝ 　　　注：{ε }A=A{ε}=A A=A =A (其中 为空集) ={ } 注: ε 不属于 ， 即空符号串并不属于空集 4.符号串集合的方幂 设A为符号串集合,则定义 A={ε} A=A A=AA A=AA=AA=AAA …… A=A A=AA =AA……A (n个) 例:设A={a,b} A={ε} A={a,b} A={aa,ab,ba,bb} (A共有2 =4个长度为2的元素) A=AA={aa,ab,ba,bb}{a,b} ={aaa,aba,baa,bba,aab,abb,bab,bbb} (A共有2 =8个长度为3的元素) 5.符号串集合的正闭包A和闭包A ⑴.符号串集合的正闭包A 设A为符号串集合,则A定义为: A=A UA UA U……UA U…… 例 设A={a,b}则 A = {a,b} ={a,b} U {aa,ab,ba,bb} U…… ={a,b,aa,ab,ba,bb,aaa,…,bbb,……} 即:A包括了由A上的元素a,b构成的所有符号串. ⑵.符号串集合A的闭包A. A =A U A U A U…U A U…… (A =A U A ) 即A ={ε} U A = A U {ε} (A = A－{ε