第二章 形式语言基础(3).ppt

1 南京邮电大学计算机学院蒋凌云Jianglingyun 教材 编译技术原理及其实现方法 王汝传编著 编译原理CompilerPrinciples 2 第二章形式语言基础知识 2 4语法分析初步一 自顶向下语法分析1 分析基本思想2 分析方法二 自底向上语法分析1 分析基本思想2 分析方法 3 第二章形式语言基础知识 2 4语法分析初步一 自顶向下语法分析1 分析基本思想2 分析方法二 自底向上语法分析1 分析基本思想2 分析方法 4 2 4语法分析初步一 自顶向下语法分析 导出法 1 分析基本思想自顶向下分析就是从文法的开始符号出发 利用其中产生式 逐步推导出要分析的符号串 换言之 对于任何给定的输入串 试图用一切可能的办法 从文法开始符号出发 自上而下 从左到右地为输入串建立语法树 这种分析过程本质上是一个试探过程 是反复使用不同规则谋求匹配输入串的过程 5 第二章形式语言基础知识 2 4语法分析初步一 自顶向下语法分析1 分析基本思想2 分析方法二 自底向上语法分析1 分析基本思想2 分析方法 6 2 4语法分析初步一 自顶向下语法分析 导出法 2 分析方法例如 设有文法G VN VT P S 其中 VN S A VT a b c d P S cAdA ab a 试分析符号串x cad是否是文法G的句子 根据推导S cAd cad容易判断出x cad是该文法的句子 若用画语法树的方法我们同样可以判断出cad是文法的句子 S A d c a 7 1 为了自上而下为符号串x建立语法树 首先将文法的开始符号S作为树的根结点 并设输入串指针i指向其第一个符号c 然后用S为左部的产生式来扩展这棵树 若按自上而下语法分析程序的步骤进行分析判断 其过程如下 P S cAdA ab a S A d c S cAd cad i 8 2 此时该树最左边末结点c与x的第一个符号c相匹配 于是调整指针i使其指向输入串下一符号a 我们再试图让树的中间端末结点A去匹配a 显然 由于A是非终结符 它不可能直接与终结符a匹配 我们只得在文法中选择以A为左部的产生式 这里以A为左部的产生式有两个 我们试着用第一个选择来匹配输入串 并扩展语法树 若按自上而下语法分析程序的步骤进行分析判断 其过程如下 P S cAdA ab a S A d c S cAd cabd cad 9 3 此时子树A最左端末结点a与i所指的符号a匹配 于是再调整i使其指向下一输入符号d 并试图用A的最右端末结点b与之匹配 但它们不匹配 因此 子树A的匹配失败 这意味着选用A的第一个候选式对此时的情况不适合 不能构造出输入串x的语法树 在这种情况下 我们应该回头看看 回溯 是否还有其它的候选式可供利用 若按自上而下语法分析程序的步骤进行分析判断 其过程如下 P S cAdA ab a S A d c S cAd cabd cad a b ERROR 10 4 我们应把A的第一个候选式所扩展的子树剪掉 还应把指针i恢复到进入A时所指的输入符号a 再选用A第二个候选式来构造语法树 若按自上而下语法分析程序的步骤进行分析判断 其过程如下 P S cAdA ab a S A d c S cAd cad i 11 5 此时子树A的唯一端末结点a与i所指的输入符号a匹配 因此A匹配成功 调整指针i 使其指向下一个输入符号d 若按自上而下语法分析程序的步骤进行分析判断 其过程如下 P S cAdA ab a S A d c S cAd cad cad i a 12 6 最后考虑S的第三个端末结点d 它与i所指的最后一个输入符号匹配 因此完成了构造输入串x的语法树的任务 从而证明了x是所给文法推导出一个句子 若按自上而下语法分析程序的步骤进行分析判断 其过程如下 P S cAdA ab a S A d c S cAd cad cad i a SUCCESS 13 下面我们将上述分析过程总结一下 1 自根开始建树试图生成一个和所给的符号串相一致的终结符号串 2 选择不同的规则反复试探在建树过程中 反复选择不同的规则 每一步试图将语法树最左的叶子与所给的符号串进行匹配 3 匹配失败退回出错点当匹配失败时 必须回到出错点 然后再选择其他规则进行试探这种方法称为回溯 采用自顶向下分析时 不仅可能遇到回溯问题 而且还可能由于文法中有左递归规则而陷入无限循环 我们将在第四章中要介绍这两方面问题及其解决办法 14 第二章形式语言基础知识 2 4语法分析初步一 自顶向下语法分析1 分析基本思想2 分析方法二 自底向上语法分析1 分析基本思想2 分析方法 15 第二章形式语言基础知识 2 4语法分析初步一 自顶向下语法分析1 分析基本思想2 分析方法二 自底向上语法分析1 分析基本思想2 分析方法 16 2 4语法分析初步二 自底向上语法分析1 分析基本思想自底向上分析是从所给的符号串w开始 在其中寻找与文法规则右部相匹配的子串 并用该规则的左部取代此子串 即归约 重复此过程 步步向上归约 最后试图将符号串w归约到文法识别符号 如归约成功 则符号串w是文法的句子 17 第二章形式语言基础知识 2 4语法分析初步一 自顶向下语法分析1 分析基本思想2 分析方法二 自底向上语法分析1 分析基本思想2 分析方法 18 2 4语法分析初步二 自底向上语法分析2 分析方法 例2 24设有文法G VN VT P S 其中VN A B S VT a b c d e P S aAcBeA Ab bB d试分析w abbcde是否为此文法的句子 19 为了描述分析归约过程 先设立一个符号栈 即将输入串中符号逐个移进栈 当栈顶符号串形成一个句柄时 就进行一次归约 把栈顶句柄那个符号串用相应规则左部的非终结符号来代替 接着再检查在栈顶是否形成新的句柄 若出现新的句柄 那么再进行归约 若没有形成新句柄 则再从输入符号串中移进新符号 如此继续到整个输入符号串处理完毕 最终 如栈底为开始符号 则输入符号串是该文法的句子 报告成功 否则 是不合法的符号串 报告错误 20 为了具体实现方便 我们统一以符号 作为待分析符号串左右分界符 作为初始状态 先将符号串的左分界符压入符号栈 作为栈底符号 对符号串abbcde分析过程如下所示 由上述可知 自底向上分析中 每次归约时 应当归约当前句型的句柄 寻找或确定一个句型的句柄是一个关键问题 在第 3 步是b归约为A 但在第 5 步 为什么不用b归约为A 而用Ab归约为A呢 在第四章将作进一步讨论这个问题 步骤符号栈输入符号串动作 abbcde 左界符进栈 abbcde a进栈 abbcde b进栈 aAbcde 用A b归约 aAbcde b进栈 aAcde 用A Ab归约 aAcde c进栈 aAcde d进栈 aAcBe 用B d归约 aAcBe e进栈 S 用S aAcBe归约 S 接受 21 第二章形式语言基础知识 2 1引言一 形式语言提出二 语言描述方法 2 2用文法生成法对语言进行描述一 巴科斯范式二 语法和语义三 语法树 2 3形式语言基本概念和术语一 元语言二 符号和符号串三 产生式 规则 四 文法五 推导和归约六 句型和句子七 语言 八 递归文法九 短语和简单短语十 最左推导和最右推导十一 文法二义性 2 4语法分析初步一 自顶向下语法分析二 自底向上语法分析 2 5文法和语言分类一 文法分类二 文法和自动机三 压缩过文法 2 6文法其他表示法一 扩充巴科斯范式二 语法图 22 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 23 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 24 如前所述 文法G形式定义为G VN VT P Z 其规则P呈如下形式 U w其中 U VN w V 但仅有这种文法 还不足以描述许多语言 例如语言L G anbncn n 1 便不能完全用上述形式规则来描述 因此还得定义其它类型的文法 根据对P中规则施加不同限制 Chomsky将文法和语言分为四类 2 5文法和语言分类一 文法分类 25 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 26 2 5文法和语言分类一 文法分类1 0型文法若在文法G中 P中规则具有如下形式 其中 V 且至少含一个非终结符 则文法G称为0型文法或称短语结构文法 简记为PSG PhraseStructureGrammar 由0型文法所描述和定义的语言称为0型语言 记PSL 即L0 27 例2 25设文法G VN VT P S 其中 VN S A B C D E VT a P S ACaB Ca aaC CB DB CB E aD DaAD AC aE EaAE 这是一个0型文法 它所产生语言为 L G ai i是2的正整次方 即 L G aa aaaa aaaaaaaa 28 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 29 2 5文法和语言分类一 文法分类2 1型文法若在文法G中 P中规则具有如下形式 A w 其中 V A w 则称文法G为1型文法或上下文有关文法 也称上下文敏感文法 简记为CSG ContextSensitiveGrammar 之所以如此命名 是因为在一个句型中 只有当非终结符A的上下文为 和 时 方可用w去替换A 同时产生式右部不得为空 仅仅S 例外 但S不得出现在产生式右部 1型文法相应的语言称1型语言 记CSL 即L1 例2 26设文法G VN P S 其中 VN S B C VT a b c P S aSBC S aBC CB BC aB ab bB bb bC bc cC cc 这也是一个1型文法 它所产生的语言为 L G anbncn n 1 30 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 31 2 5文法和语言分类一 文法分类3 2型文法若在文法G中 P中规则具有如下形式 A w 其中A VN w V 则称文法G为2型文法或称上下文无关文法 简记为CFG ContextFreeGrammar 之所以称上下文无关文法 是由于利用规则将A替换成w时 无需考虑A的上下文出现情况 由2型文法所确定的语言称2型语言 记CFL 即L2 大部分程序设计语言的文法近似于2型文法 通常使用BNF表示法等价于前后文无关文法 凡是用BNF定义的语言都是前后文无关语言 例2 27设文法G VN 其中 VN S VT a b P S aSb S ab 这是一个前后文无关文法 它所定义的语言是 L G aibi i 1 32 思考题 请给出描述语言L a2m 1bm 1 m 0 U a2mbm 2 m 0 的上下文无关文法 33 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 34 2 5文法和语言分类一 文法分类4 3型文法若在文法G中 P中规则具有如下形式 A aB或A a 其中A B VN a VT则称文法G为右线性文法 类似地 如P中规则有如下形式 A Ba或A a 则称文法G为左线性文法 通常 我们把左线性文法和右线性文法称3型文法或正规文法 简记为RG RegularGrammar 由3型文法所产生的语言称3型语言 记RL 即L33型文法与词法分析密切相关 35 例2 28设文法G VN VT P S 其中 P S A0 B1 A 0 1 B 0 1 这是一个 左线性 3型文法 它所定义的语言为 L G 00 01 10 11 36 思考题 语言L G S b2i 1 i 0 对应的3型文法 37 由于将文法分为0型 1型 2型 3型四类 是逐渐增加对规则限制条件而得到的 因此 由它们所定义的语言是依次缩小 如果分别用L0 L1 L2和L3表示0型 1型 2型和3型语言 则有 L0 L1 L2 L3 编译中分别借助于2型 上下文无关 文法和3型 正规 文法来研究语法分析和词法分析 38 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 39 2 5文法和语言分类二 文法和自动机能识别或生成语言的识别器 某种算法或过程 称为自动机 自动机给出了有穷的方式来描述无穷的语言的另一种手段 对于L0 L1 L2和L3四种语言 正好有一类自动机与它相对应 40 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 41 2 5文法和语言分类二 文法和自动机1 3型语言与有穷状态自动机3型语言所对应的自动机称为有穷状态自动机 简称有穷自动机 简写FA 这种自动机仅由一个有穷状态集和一个状态对偶之间转换集所组成 一般每个状态与某个非终结符相关 而每个转换规则与某个终结符号相关 42 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 43 2 5文法和语言分类二 文法和自动机2 2型语言与下推动自动机2型语言或上下文无关语言所对应的自动机称为下推自动机 简写为PDA 下推自动机与有穷自动机区别在于 它还有一个下推存贮器 下推存贮器实际上是一种先进后出栈 在这种自动有穷描述中 只有位于栈顶部有穷个元素是经常使用的 44 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 45 2 5文法和语言分类二 文法和自动机3 1型语言与线性界限自动机1型语言或称上下文有关语言所对应的自动机是线性界限自动机 简称LBA 46 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 47 2 5文法和语言分类二 文法和自动机4 0型语言与图灵机 0型语言所对应的自动机是图灵机 简称TM 任何能用图灵机描述的计算都能机械实现 而任何能在现代计算机上实现的计算都能用图灵机描述 因而图灵机理论颇引起人们重视 本书主要讨论前两类语言及其相应自动机 将在第三章 第四章叙述 48 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 49 2 5文法和语言分类三 压缩过文法压缩过文法对有关文法的实用限制 限制文法中不得含有有害规则和多余规则 满足下列条件文法G VN VT P Z 称为压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 50 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 51 2 5文法和语言分类三 压缩过文法1 在文法中不含有形如A A的规则 这样规则显然是没有必要 并且还会引起文法的二义性 由于这样的规则是有害的 所以应删除 如 文法G 其产生式P为 S 0S1 01 显然它是一个无二义文法 其描述的语言L G 0n1n n 1 若将规则P改为 S S 0S1 01 对于句子0011可以画出多棵语法树 引起二义性 所以应将S S这样的有害规则删除掉 52 第二章形式语言基础知识 2 5文法和语言分类一 文法分类1 0型文法2 1型文法3 2型文法4 3型文法二 文法和自动机1 3型文法和有穷自动机2 2型文法和下推动自动机3 1型文法和与线性界限自动机4 0型文法和图灵机三 压缩过文法1 在文法中不含有形如A A的规则 2 在文法中不包含多余规则 53 2 5文法和语言分类三 压缩过文法2 在文法中不包含多余规则 1 每一个非终结符号A Z除外 必须在某句型中出现 否则为不可到达的 即Z A 其中 V 2 非终结符A必须推出终结符串t来 否则为不可终止的 即 A tt VT 54 例如 已知文法G 其产生规则P为 Z BeA Ae eB Ce AfC CfD f求其压缩过文法G 由该文法可知 因为规则D f中非终结符D不在其它任何规则右部出现 所以规则D f在推导中不起作用 为多余规则 应将其删除 另外 规则C Cf也是多余规则 因为一旦使用了这条规则 便会使推导无限制进行下去 最终无法推出终结符号串 所以也是该删除的多余规则 同理 B Ce也是多余规则 因为它含有非终结符C 所以 将该文法多余文法删除得到压缩过文法为G 其规则为 Z BeA Ae eB Af 55 第二章形式语言基础知识 2 1引言一 形式语言提出二 语言描述方法 2 2用文法生成法对语言进行描述一 巴科斯范式二 语法和语义三 语法树 2 3形式语言基本概念和术语一 元语言二 符号和符号串三 产生式 规则 四 文法五 推导和归约六 句型和句子七 语言 八 递归文法九 短语和简单短语十 最左推导和最右推导十一 文法二义性 2 4语法分析初步一 自顶向下语法分析二 自底向上语法分析 2 5文法和语言分类一 文法分类二 文法和自动机三 压缩过文法 2 6文法其他表示法一 扩充巴科斯范式二 语法图 56 第二章形式语言基础知识 2 6文法其他表示法一 扩充巴科斯范式1 花括号 2 方括号 3 圆括号 二 语法图1 定义2 语法图表示法 57 第二章形式语言基础知识 2 6文法其他表示法一 扩充巴科斯范式1 花括号 2 方括号 3 圆括号 二 语法图1 定义2 语法图表示法 58 2 6文法其他表示法一 扩充巴科斯范式 BNF 在前面我们介绍了文法的形式定义 对于形式定义中的规则我们用巴科斯范式 BNF 来表示 但是除了用BNF表示来定义文法以外 还可以用其它一些表示方法 在文法BNF表示中 使用下列4个元语言符号 在扩充的BNF中 除了使用上述4个元符号外 还引入以下6个元语言符号使用 这6个符号是 和普通括号一样 这6个符号在文法中是两两成对出现 下面简单介绍这些符号的使用 59 第二章形式语言基础知识 2 6文法其他表示法一 扩充巴科斯范式1 花括号 2 方括号 3 圆括号 二 语法图1 定义2 语法图表示法 60 2 6文法其他表示法一 扩充巴科斯范式1 花括号 1 t nm表示符号串t可重复出现m次 m 1次 m 2次 直到n次 2 t n表示符号串t不出现或至多出现n次 3 t m表示符号串t至少重复m次 4 t 表示符号串t不出现或出现任意多次 61 例如用BNF表示下列文法规则 标识符 字母 标识符 字母 标识符 数字 E T E TT F T F 引入花括号 用扩展BNF表示上面同样文法规则为 标识符 字母 字母 数字 E T T T F F 采用花括号表示文法 除能方便表示重复次数外 还能消除文法中左递归 这在采用自顶向下语法分析时将是十分有用的 62 第二章形式语言基础知识 2 6文法其他表示法一 扩充巴科斯范式1 花括号 2 方括号 3 圆括号 二 语法图1 定义2 语法图表示法 63 2 6文法其他表示法一 扩充巴科斯范式2 方括号 方括号用来表示可供选择的符号串 即 t 或t 例如 关于 语句 的BNF表示为 语句 变量 表达式 IF 布尔表达式 THEN 语句 IF 布尔表达式 THEN 语句 ELSE 语句 变量 i i 表达式 引入方括号以后 可表示为 语句