编译原理第二章课件.ppt

1 第二章形式语言与自动机理论基础 主要内容 语言文法有限自动机正则表达式 2 自然语言 NaturalLanguage 是人类在社会生活中发展起来的 用于日常相互交流的符号系统 形式语言 FormalLanguage 是为了特定应用而设计的人工语言 形式语言是用精确的数学或机器可处理的公式定义的语言 公式由人们公认的数学和逻辑符号组成 2 1语言和文法 3 语法和语义一个程序设计语言是一个记号系统 它的完整定义包括语法和语义两个方面 语法 Grammar 是一组规则 用它可以产生一个与其所包含的符号含义无关的合法程序 语法是语言的形式 语义 Semantic 是语言的内容 以语法为媒介来说明语义是语言的实质 本章目的形式语言的基础知识 2 1语言和文法 2 1 4 2 1基本概念1 字母表 alphabet 字母表是元素的非空有穷集合 字母表中的一个元素称为该字母表的一个字母 letter 也可叫做符号 symbol 或者字符 character 注意 字母表具有非空性和有穷性 字母表有时也称为符号表 通常用 表示 2 1语言和文法 5 2 符号串由字母表中的符号组成的任何有穷序列称为字母表上的符号串 符号串还可以称为 字符串 字 或 句子 一般用 x y z 表示 或 表示空串 对任一字母表 都有 或 是 上的符号串 空串集 不同于空集 a b c d 符号串又可定义如下 1 空符号串 是 上的符号串 2 若x是 上的符号串 a是 的元素 则xa是 上的符号串 3 y是 上的符号串 当且仅当它可以由1和2导出 2 1语言和文法 8 6 3 符号串长度符号串中字符的个数 用 表示符号串 的长度 0 只有当两个符号串长度相等且相应位置的符号均相同时 这两个符号串才是相等的 2 1语言和文法 7 4 符号串连接设 和 均是字母表 上的符号串 和 的连接是把 的所有符号顺次地接在 的所有符号之后所得到的符号串 记为 例如 设 abc de 则 和 的连接 abcde 由于 是不包含任何符号的字符串 特别有 连接运算不满足交换律 2 1语言和文法 8 5 符号串的方幂设x是字母表 上的符号串 把x自身连接n次得到的符号串z 即z xx xx n个x 称作符号串x的n次幂 记作z xn 根据定义有 x0 x1 xx2 xxx3 x2x xx2 xxx xn xn 1x xxn 1 xx xx n个x 例2 1设x 001 则有 x0 x1 001x2 001001x3 001001001 9 6 符号串前缀和后缀设x是某一字母表上的符号串 x yz 则y是x的前缀 z是x的后缀 特别是当z 时 y是x的真前缀 y 时 z是x的真后缀 例 设x abc 则 前缀真前缀后缀真后缀 x abc abc x abc ab c x abc a bc x abc abc 2 1语言和文法 10 7 子字符串一个非空字符串x 同时删去它的一个前缀和一个后缀后所得到的字符串称为x的子字符串 简称子串 如果删去的前缀和后缀不同时为 则称该子串为真子串 例如 设x abc 其子串为 abc ab a bc c b 真子串为 ab a bc b c 注意 ac并不是x的子串 2 1语言和文法 11 当对符号串z xy的头感兴趣而对其余部分不感兴趣时 采用省略写法 z x 如果只是为了强调x在符号串z中的某处出现 则可表示为 z x 2 1语言和文法 12 8 符号串集的乘积设A B是两个符号串集合 AB表示A与B的乘积 具体定义为 AB xy x A y B 运算结果仍然表示符号串的集合 例2 3设A a bc B de f 则 AB ade af bcde bcf 特别有 1 A A 其中 表示空集 2 A A A 2 1基本概念 13 9 符号串集合的方幂设A为符号串的集合 则称 i为符号串集 的方幂 具体定义如下 1 A 2 AA n n 1A AAA A n个 例 a b 则 0 1 a b 2 AA aa ab ba bb 3 A2A aaa aab aba abb baa bab bba bbb n n 1A AAA A 2 1基本概念 14 10 符号串集合的正闭包设A为符号串的集合 则称 为符号串集 的正闭包 具体定义如下 1 A2 A3 AN 2 1基本概念 15 11 符号串集合的星闭包设A为符号串的集合 则称 为符号串集 的星闭包 具体定义如下 A0 1 A2 A3 AN注意 A 2 1基本概念 16 例 设A ab cd 则 A ab cd abab abcd cdab cdcd ababab ababcd A ab cd abab abcd cdab cdcd ababab ababcd 17 2 2文法 1956乔姆斯基从产生语言的角度出发 给出了形式语言的一种描述形式 创建了文法体系 也就是乔姆斯基体系 文法 表示无穷字符串集合的方法 文法字符串集合 2 2文法 18 2 2 1文法 Grammar 的定义文法的定义一个文法G是一个四元组 G VN VT S P 其中 VT TerminalVocabulary 是一个非空的有限集合 它的每个元素称为终极符号或终极符 一般用小写字母表示 从语法分析的角度看 终极符号是一个语言不可再分的基本符号 2 2 1文法的定义 19 VN NonterminalVocabulary 是一个非空的有限集合 它的每个元素称为非终极符号 非终极符或中间符 一般用大写字母表示 非终极符是一个语法范畴 表示一类具有某种性质的符号 它不出现在句子中 注 设V是文法G的符号集 则有 V VN VT VN VT 2 2 1文法的定义 20 S Start 是一个特殊的非终极符号 称为文法的开始符号 S VN 2 2 1文法的定义 21 P production 是产生式的有限集合 所谓的产生式 也称为产生规则 简称为规则 是按照一定格式书写的定义语法范畴的文法规则 产生式的形式为 或 其中 称为产生式的左部 头 V 并且至少含有一个非终极符 称为产生式的右部 体 V 或 读作 定义为 或 由 组成 开始符号S必须至少在某个产生式的左部出现一次 2 2 1文法的定义 22 为了书写方便 若干个左部相同的产生式 如 P 1P 2 P n可合并为一个 缩写为 P 1 2 n其中 每个 i称为P的一个候选式 符号 读作 或 2 2 1文法的定义 23 一个文法的核心是产生式 一般约定 用括起来或大写字母 非终结符不用括起来或小写字母 终结符 24 例1 G VN VT S P 其中 VN S A VT a b c P S aA S b A Ac A c G S S aA bA Ac c G S S aAS bA AcA c 2 2 1文法的定义 G S S aA bA Ac c G S aA bA Ac c 25 例2 字母表 a 上的符串集 S a2n n 1 A的文法表示如下 G VN VT S P 其中 VN S VT a P S aa S Saa G S S aaS Saa G S S aa Saa 2 2 1文法定义 26 例3 考虑字母表 a b 上的符串集 A abna n 1 A的文法表示如下 G VN VT A P 其中 VN A B VT a b P A aBa B b B Bb G A A aBaB bB Bb G A A aBaB b Bb 2 2 1文法的定义 27 1956年 著名的语言学家乔姆斯基 Noam Chomsky 将文法分为四类 四类文法对应四种类型的语言 0型文法 短语型文法 如果对文法G中的任一产生式 不加任何限制 则称G为0型文法或短语型文法 其中 是符号串 2 2 2文法的分类 2 2 2文法的分类 28 1型文法 上下文相关文法 如果对文法G中的任一产生式均限制为形如 A 其中A VN VT VN VT VN 则称文法G为1型文法或上下文相关文法 2 2 2文法的分类 A 29 2型文法 又称上下文无关文法context freeGrammerCFG 如果对文法G中的任一产生式均限制为形如 A 其中A VN VT VN 则称G为2型文法或上下文无关文法 例1 文法G S aSb abL G anbn n 1 2 2 2文法的分类 30 3型文法 又称线性文法 正则文法 正规文法 如果对文法G中的任一产生式均限制为形如 A B或A 其中 A B VN VT则称文法G为3型文法 上述形式的3型文法也称为右线性文法 如果对文法G中的任一产生式均限制为形如 A B 或A 其中 A B VN VT这样的3型文法称为左线性文法 2 2 2文法的分类 31 四类文法之间的关系 从0型到3型 对产生式的限制是逐步增强 而描述语言的能力是逐步减弱 其后一类都是前一类的子集 四类文法之间的关系可以表示为 0型 1型 2型 3型 2 2 2文法的分类 32 2 2 2文法的分类 33 在编译技术中通常用3型文法来描述高级程序设计语言的词法部分 2型文法 或上下文无关文法描述的程序设计语言的语法结构 比如描述算术表达式 描述各种语句等等 今后对 文法 一词如无特殊说明则均指上下文无关文法 2 2 2文法的分类 34 2 2 3推导和归约 1 直接推导若 是文法G VN VT S P 中的一条产生式 VT VN 若有符号串v w满足 v w 则称v 应用规则 直接推导出w 或者说w是v的直接推导 记作 v w 又称w直接归约到v 2 2 3推导和归约 35 2 2 3推导和归约 例 对于表达式文法G E E E E E E i i E E i E E E 36 2 直接推导序列如果存在 v 0 1 1 2 n 1 n w n 1 则说 v经过n n 0 步推导出w 记作 v w 若有v w 或v w 则说v经过n n 0 步推导出w 记作 v w 即 表示0步或多步直接推导 推导的逆过程称为归约 2 2 3推导和归约 37 例 对于表达式文法G E E E 1 E E 2 E 3 i 4 符号串i i i的直接推导序列是 1 即 E i i i E E E i E i E E i i E i i i 4 2 4 4 2 2 3推导和归约 38 3 最右推导在推导过程中 总是对当前符号串中最右边的非终极符进行替换 称为最右推导 又称之为规范推导 并用符号 rm表示 规范推导的逆过程称为规范归约 例 上述符号串i i i的最右推导过程是 E E E E E E E E i E i i i i i 最右非终极符 最右非终极符 最右非终极符 最右非终极符 最右非终极符 即 E rmi i I 2 2 3推导和归约 39 4 最左推导在推导过程中 总是对当前符号串中最左边的非终极符进行替换 称为最左推导 并用符号 lm表示 例 对于表达式文法G E E E E E E i符号串i i i的最左推导过程是 E E E i E i E E i i E i i i 最左非终极符 最左非终极符 最左非终极符 最左非终极符 最左非终极符 即 E lmi i i 2 2 3推导和归约 40 5 句型设有文法G VN VT S P S是文法G的开始符号 如果有 S VT VN 则称 为G的句型 最右推导得到的句型称为最右句型或规范句型 最左推导得到的句型称为最左句型 2 2 3推导和归约 41 E E E i E i E E i i E i i i 例 对于表达式文法G E E E E E E iE E E i E i E E i i E i i i为G的句型 句型 E 句型 E E 句型 i E 句型 i E E 句型 i i E 句型 i i i 2 2 3推导和归约 42 6 句子设有文法G S是文法G的开始符号 如果有 S VT 则称 为G的句子 例 上例中i i i为G的句子 7 语言所有句子的集合称为文法的语言 记作 L G S VT 2 2 3推导和归约 43 例1 文法G S S aPdP bPc bc S aPd abPcd abbPccd abb bPcc cd L G abmcmd m 1 2 2 3推导和归约 abcd abbccd abbbcccd 44 例2 文法G S S aSd PP bPc bcS aSd aaSdd aaaSddd a aSd d a aPd d a abPcd d a ab bPc cd dL G anbmcmdn m 1 n 1 2 2 3推导和归约 45 8 短语设S是文法的开始符 是句型 即有 S 如果满足条件 S A A 则称 是句型 的一个短语 2 2 3推导和归约 46 例 对于表达式文法G E E E E E E ii i为句型i i i的一个短语 因为 2 2 3推导和归约 思考题 i i i亦为句型i i i的一个短语 47 9 直接短语 简单短语 如果满足条件 S A A 则称 是句型 的一个简单短语 2 2 3推导和归约 48 例 对于表达式文法G E E E E E E ii i不是句型i i i的简单短语 因为 2