资源描述
形式语言基本知识 第二章 本章要求 主要内容 ：符号串，文法的概念及分 类，语言的定义过程 重点掌握 ：上下文无关文法、推导、 句型、句子、语言，语法树、二义性 文法、文法的语言生成过程 以 C和 PASCAL为例复习高级语言 1 语言的基本字符集的定义 (字母 , 数字 , 界符 ) 2 单词集的定义 3 数据类型的定义 4 表达式的定义 5 语句的定义 6 程序定义 PASCAL和 C的主要区别 2.1 符号和符号串 1. 字母表 ：是元素的有穷非空集合 2. 符号 ：字母表中的每个元素，因此字母表也称 为符号集。 不同的语言可以有不同的字母表，例如英文的字 母表中 26个字母、数字及标点符号等。 PASCAL语言的字母表是由字母、数字、若干专 用符号组成。 符号是该语言能识别的符号，字母表是该语言能 识别的所有符号的全体（字符集）。 基本概念 (续 ) 3. 符号串 : 由字母表中的符号组成的任何有穷 序列称为符号串，例如 00 11 10 是字母表 = 0， 1 上的符号串 . 字母表 A= a,b,c上的一些符号串有： a,b,c,ab,aaca等。 在符号串中，符号的顺序是很重要的，符号串 ab就不同于 ba,abca和 aabc也不同。 符号串 STR表示 “ 由符号 S、 T和 R，并按此顺序组成 . 基本概念 (续 ) 4. 符号串的运算 a. 字符串的 连接 ： 字符串 称为字符串 和 的连接 符号串的长度 :符号串中符号的个数，例如 : 某符号串中有 m个符号 ,则称其长度为 m，表示 为 x =m，如 001110的长度是 6。 空符号串 : 即不包含任何符号的符号串，用 表 示，其长度为 0， 即 =0。 用 *表示 上所有的符号串的全体 (长度为 0， 1， 2， ) 。 集合的运算 b. *的子集 U、 V的 积 ： UV = | U & V 长度相加 即 : 集合 UV中的符号串是由 U和 V的符号串连接而成。 U = aa,bb V=00,11 则 UV=? c. 集合的 方幂 ： n个相同符号连接 Vn =VVVV . V 规定 V0 = d. 闭包、正闭包 的运算 例： =a,b *= ,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab, 使用 * 表示 上的一切符号串（包括 ）组成 的集合。 称为 的闭包 。 上的 除 外 的所有符号串组成的集合记为 + 。 称为 的正闭包 。 . 3 2 = + V=0,1 V* = ? V+ = ? . 3 2 = * 2.2 上下文无关文法及其语言 文法 是描述语言的语法结构的形式规则。 是一种工具，它可用于严格定义句子的结 构；用有穷的规则刻划无穷的集合 文法是被用来精确而无歧义地描述语言的 句子的构成方式 . 文法描述语言的时候不考虑语言的含义。 引 例 例 1： 有如下 规则 (表示由 组成 ) | 我 大学生 是 | 现要求根据如上规则得出句子：我是大学生 = = = =我是大学生 句子 “ 我是大学生 ” 也可以如下图示分 析 在有规则的情况下，每一次用上述规则的右边去替 换左边，得到“我是大学生”是符合上述规则的句 子 大学生 我 是 上下文无关文法的形式定义 由四部分组成： 终结符号 ：是组成该语言的最基本的符号， 是不可再分的基本符号 ,如保留字、标识符等。 非终结符号 ：规则中用尖括号括起来的符号， 表示一些语法成分，可以推导出其他的语法成 分 ,表示一定符号串的集合，是一个类，如表 达式。 开始符号 ：规则中的一个特殊的非终结符号， 语言中的句子都从它开始推导 ,如程序、句子 产生式 ：定义语法成分的规则，其中： 文法的形式定义 (续 ) 一个 文法 G抽象地表示为四元组 G=（ Vn,Vt,P,S） 其中 Vn表示非终结符号 Vt表示终结符号， VnVt= (字母表 )， VnVt= S是开始符号， P是产生式，形如： ( V +且至少含有 一个非终结符号， V *) 上例中： G=（ Vn,Vt,P,） Vn=（ ， ， ， ， ， ， ） Vt= (我，是，大学生 ) P = | 我 大学生 是 | 产生式的形式为： A 左部符号， 非终结符 右部，可以含有非 终结符和终结符 又称为一条规则 有时一个产生式不足以描述该语法范畴，就用多个产生式， 如算术表达式的描述为： (递归定义 ) E E + E E E * E E i 相同左部的一个右部又称一个 候选式 上下文无关 文法所定义的语法成分独立于它可 能出现的环境，即不考虑上下文。 算术表达式的文法定义 变量是表达式 表达式 + 表达式是表达式 表达式 * 表达式是表达式 (表达式 ) 是 表达式 E E + E E E * E E ( E ) E i E E+E | E*E | (E) | i 从上下文无关文法得到某个符号串的方法 :从文 法的开始符号出发 ,反复连续使用产生式 ,对左 边的非终结符进行替换和展开，直到全部为终 结符为止。 例：表达式定义规则 E E + E E E * E E ( E ) E i ( i+i ) E=( E ) =( E+E ) =( i+E ) =( i + i ) 推导 : 连续使用产生式右部去替换左部某 个非终结符的过程 ,得到的连续序列称为一 个推导。 直接推导 ：又称一步推导 (用 符号 =表示 ), 就是用某条规则的右部去替换该规则的左 部 几个概念的形式定义 直接推导 : 如果 是文法 G=（ Vn,Vt,P,S） 的产生式， 和 是 *中的任意符号，若有符号 串 v,w满足： v= ,w= ,则说 v直接产生 w， (w是 v的 直接推导 )记作： v=w * + 例： S01, 0S0=0010(直接推导 , ) 如果存在 v=w0=w1=w2.=Wn=w(n0)，则 称 v推导 出 w（长度为 n），记作 v=w(至少一步 ) 若有 =w或 v=w，则记作 v=w(0步或若干步 ) 例 3 : G = (E, i, +, *, (, ) , P , E) P： E E+E | E*E | (E) | i 表达式 (i)和 (i+i)*i的推导： E (E) (i) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i E E 0步推导 E (i + i)*i 6步推导 E (i + i)*i 6步推导 E (E) 直接推导 句型 ： 设 (s)是一文法，如果符号串 x是从开始符 号推导出来的，即有 s=x,则称 x是文法 G(s)的一个 句型 。 即 : 任何由开始符推导出来的符号串都是句型。 句子 ： 若 x仅由终结符号组成，则称 x为 G(S)的 句子 * 练习 文法 G： SaAcB | Bd AAaB | c BbScA | b 写出句型 aAcbBdcc和句子 acabcbbdcc的 推导 过程。 文法 G所产生的语言 定义为： L(G)=x|S=x,其中 S为文法的开始符号， x Vt* 。 即 : 一个文法 G可以推导出的所有句子构成的一个集 合 , 就确定了一个语言。 * 例：考虑文法 G: 它定义了什么语言。 S bA A aA|a 推导过程 ： S=bA =ba S=bA =baA=baa . S=bA =baA= =baa 归纳得： L(G1) = ban | n1 练习：文法 (A,B,S,a,b,c,P,S) S Ac|aB A ab B bc 写出 (G)的全部元素 L(G) = abc 例：考虑文法 G2: 它定义的语言是： S AB A aA|a B bB|b L(G2) = ambn |m,n1 思考：构造一个文法 G3使得： L(G3) = anbn |n1 S aSb S ab a,b的个数相同 ,则文法 G3为： 文法等价： 若文法 G1和文法 G2所产生的语言相同，即 L(G1) = L(G2)，则称文法 G1和文法 G2等价 。 例：有如下两个文法，判断它们是否等价？ G1=（ S， 0， S， S0S， S0） G2=（ S， 0， S， SS0， S0） S0 S0S00 S0S 00S 0000 L(G1) = 0n | n1 对于 G2： 对于 G1 ： SS0 S00 0000 L(G2) = 0n | n1 G1G2，但 L(G1) = L(G2)，文法 G1和 G2等价 例 3 : G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 表达式 (i+i)*i的推导 过程 ： (1) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i (2) E E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*i 对给定的文法，利用所有的产生式推导出所有 可能的句子构成的一个集合，称为该文法定义 的语言。 但是一个句型到另一个句型 (句子 )的推导过程 不是唯一的。 最左推导 : 在整个推导过程中 ,任何一步推导 = 都是对 中最左边的非终结符进行替换。 最右推导 : 在推导之前确定推导的顺序，是对句子进行 确 定性分析 所必须的 例 3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i (i+i)*i的最左推导过程： E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i 最右推导过程： E E*E E*i (E + E)*i (E+ i)*i (i + i)*i 2.3 语法树和文法的二义性 语法树 ： 推导的形式化表示 ，有助于理解句子 语法结构的层次 每个结点都有一个标记，该标记属字母集中的 一个符号 ， 根由开始符号标记。 当某个非终结符被它的某个候选式所替换时， 就产生相应的下一层的结点，候选式中自左至 右的每个符号对应一个新的结点，并标记它， 画出其与父结点之间的连线。 例：对文法 G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子 (i+i)*i 的语法树： 在语法树的推导过程中 的任何时刻，没有后代 的端末结点自左至右排 列起来就是一个 句型 一棵语法树表示了一个 句型很多可能的不同推 导过程。 (包括最左推导 和最右推导 ) 例 3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子 ( i * i + i)的语法树： (1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i) (2) E (E) (E * E) (i*E) (i * E + E) (i * i + E) (i *i + i) 并不是任何情况下一个句型就唯一地对应一棵语法树。 2.3 文法的二义性 定义 ：如果一个文法存在某个句子对应 两棵不同的语法树，则说这个文法是 二 义 的 对二义文法中的某个句子的分析不是唯 一的，因此总是希望文法是无二义的。 但是二义文法有时也是有用的。 2.4 文法的分类 文法有四种 :设有 G=(Vn,Vt,P,S),不同类型的文 法只是对产生式的要求不同： 型文法 (短文文法 )： G的每个产生式 满足： V +且 中至少含有一个非终结符 , V * 型文法 (上下文有关文法 )：如果 G的每个产生式 均满足 | |=| |,仅当 除外，但 S不 得出现在任何产生式的右部 型文法 (上下文无关文法 )： G的每个产生式为 A , A是一非终结符， V * 型文法 (正规文法 )： G的每个产生式的形式都是： A B或 A ，其中 A,B是非终结符， 是终结符 串。 (右线性文法 ) 语言的层次 这四种语言可被 4种自动机识别： 0型 图灵机 1型 线性界限自动机 2型 下推自动机 3型 有穷自动机 从外到内，四种文法对产生式的限制越来越 多，语言的描述能力越来越弱 正规文法的描述能力比上下文无关文法的描述 能力弱 正规文法只能用于描述单词的构成 上下文无关文法有足够的能力描述现今大多数 程序设计语言的语法结构 例 .3: L(G3) = anbn |n1 a,b的个数相同 , 不能由任何正规文法产生，可 以由下述上下文无关文法产生。 S aSb S ab 同样，上下文无关语言的描述能力比上下文有关 语言的描述能力弱。 思考题 2 写出 PASCAL语言中 IF语句的上下文无 关文法的完整定义
展开阅读全文