编译原理语法1(文法和语言).ppt

第4讲 编译原理 西北农林科技大学本科教程 主讲教师 赵建邦 第三章语法分析 3 1文法和语言3 2推导与语法树3 3自顶向下的语法分析3 4自底向上的语法分析3 5规范规约的自底向上语法分析方法 第三章 语法分析 3 1文法和语言文法和语言的基本概念形式语言分类 4类 正规表达式与上下文无关文法重点掌握正规表达式与上下文无关文法 本讲目标 定位语法分析是编译过程的第二个阶段 也是核心部分任务根据语言的语法规则对单词序列进行语法分析 识别合法的语法单位 如表达式 语句 程序段等 若不存在语法错误则给出正确的语法结构理论依据 上下文无关文法方法自顶向下分析 推导 开始符号句子 自底向上分析 规约 句子开始符号 语法分析 3 1文法和语言 文法 Grammar 是程序语言的生成系统 用文法可以精确定义一个语言 并依据该文法构造出识别这个语言的自动机文法对程序语言和编译程序的构造具有重要意义 如程序语言的词法可用正规文法描述 语法可用上下文无关文法描述 而语义则要借助于上下文有关文法描述 3 1文法和语言 3 1 1文法和语言的基本概念1 语言通常我们用 表示字母表 字母表中的每个元素称为字符或符号 不同语言的字母表可能是不同的 程序语言的字母表通常是ASCII字符集 由字母表 中的字符所组成的有穷系列称为 上的字符串或字 字母表 上的所有字符串 包括空串 组成的集合用 表示 那么 对字母表 来说 上的任意一个子集都称为 上的一个语言 记为L 该语言的每一个字符串称为语言L的一个语句或句子 3 1文法和语言 3 1 1文法和语言的基本概念1 语言 例如 设 a b c 则 L a aa ab aaa aab aba abb 为 上的一个语言 如果a表示字母 b表示数字 c看做其它符号 则L即是程序语言中的标识符集 其中的每个标识符就是标识符集中的一个句子 3 1文法和语言 3 1 1文法和语言的基本概念2 文法 定义 文法通常表示成四元组G S VT VN S 1 VT为终结符号集 这是一个非空有限集 它的每个元素称为终结符号 2 VN为非终结符号集 它也是一个非空有限集 其每个元素称为非终结符号 且有VT VN 3 S为文法开始符 是一个特殊的非终结符号 即S VN 3 1文法和语言 3 1 1文法和语言的基本概念2 文法 文法中的基本概念 终结符号 是指语言不可再分的基本符号 通常是一个语言的字母表 终结符代表了语法的最小元素 是一种个体记号 非终结符号 也称语法变量 它代表语法实体或语法范畴 非终结符代表一个一定的语法概念 因此 一个非终结符是一个类 一个集合 注意 1 字母表可以称为文法中的终结符集2 非终结符不能是字母表中的字符 3 1文法和语言 3 1 1文法和语言的基本概念2 文法 定义 文法通常表示成四元组G S VT VN S 4 是产生式的非空有限集 其中每个产生式 或称规则 是一序偶 通常写作 或 读作 产生 是 或 定义为 在此 为产生式的左部 而 为产生式的右部 是由终结符和非终结符组成的符号串 VT VN 且至少有一个非终结符 而 VT VN 3 1文法和语言 3 1 1文法和语言的基本概念2 文法 文法中的基本概念 文法开始符号S 是一个特殊的非终结符 它代表文法所定义的语言中我们最终感兴趣的语法实体 即语言的目标 而其它语法实体只是构造语言目标的中间变量产生式 也称产生规则或规则 是定义语法实体的一种书写规则 一个语法实体的相关规则可能不止一个 P 1P 2 P n 如果 P 1 2 n 其中 每个 i i 1 2 n 称为P的一个候选式 直竖 读为 或 它与 一样是用来描述文法的元语言符号 即不属于 的字符 3 1文法和语言 例如 定义一个仅包含加和乘运算的表达式的文法G E G S VT VN S VT i VN E T F S E 为以下产生式的集合 E E T TT T F FF E i两种文法都可以识别包含加和乘运算的表达式 它们的区别将在后面的课程中讲解 VT i VN E S E E i E E E E E 3 1文法和语言 3 1 1文法和语言的基本概念关于文法表示的约定 在此后的讨论中 用大写字母A B S E等表示非终结符 用小写字母a b i j等表示终结符 并用希腊字母等表示文法符号串 即 等均属于 VT VN 2 3正规表达式与优先自动机简介 例3 1试构造产生标识符的文法 解答 首先 标识符是以字母开头的字母数字串 用L表示 字母 类非终结符 用D表示 数字 类非终结符 T L D 单个的字母或数字字符 S T ST 字母或数字串 其次 如果用S表示 字母数字串 类 则T是一字母或数字 ST也是字母数字串 即有 L a b zD 0 1 9 而用T表示 字母或数字 类非终结符 则有 其中 产生式S T ST是一种左递归形式 由它可以产生一串T 课本例题 最后 作为 标识符 的非终结符I 它或者是一单个字母 或者为一字母后跟字母数字串 即I L LS 因此 产生标识符的文法G I 为 G I VT VN I a b z 0 9 I S T L D I I L LSS T STT L DL a b zD 0 1 9 课本例题 解答 根据题意 我们可以将奇数划分为如图3 1所示的三个部分 即最高位允许出现1 9 用非终结符B表示 中间部分可以出现任意多位数字0 9 每一位用非终结符D表示 最低位只允许出现1 3 5 7 9等奇数 用A表示 例3 2写一文法 使其语言是奇数集合 但不允许出现以0打头的奇数 课本例题 图3 1奇数划分示意 课本例题 G N 0 1 9 N A M B D N N A MA 一位数字 多位数字 M B MD 仅两位数字 无中间位 多于两位数字 A 1 3 5 7 9B 1 2 3 4 5 6 7 8 9D 0 B 由于中间部分可出现任意位 所以另引入了一个非终结符M 它包括最高位和中间位部分 假定开始符为N 则可得到文法G N 为 课本例题 3 1文法和语言 3 1 1文法和语言的基本概念3 文法产生的语言设文法G S VT VN S 且 VT VN 如果存在产生式A VT VN 则称 A 可直接推出 即其中 表示直接推导 是应用产生规则进行推导的记号 这里仅使用一次规则注意 与 不同 是产生式中的定义记号 直接推导是指对文法符号串 A 中的非终结符A用相应的产生式A 的右部 来替换 从而得到 A 3 1文法和语言 推导的说明 1 如果 1可直接推出 2 2可直接推出 3 n 1可直接推出 n 即存在一个自 1至 n的推导序列 1 2 3 n n 0 则称 1可推导出 n 记为 1 n 它表示从 1出发经过一步或若干步可推导出 n 2 如果记 1 1 1 n则表示从 1出发 经过0步或若干步可推导出 n 也即 1 n 意味着或者 1 n 或者 1 n 这个概念叫做 广义推导 显然 直接推导的长度是1 推导的长度 1 广义推导的长度 0 0 3 1文法和语言 推导的举例 例如 对下面的文法G E E E E E E E i 3 1 其中 惟一的非终结符E可以看成是代表一类算术表达式 可以从E出发进行一系列的推导 如表达式i i i的推导如下 E E E E E E E E i E i i i i i 注意 在每一步推导过程中 只能对其中的一个非终结符用其对应的产生式右部的一个候选式来替换 3 1文法和语言 3 1 1文法和语言的基本概念句型 假定G S 是一个文法 S是它的开始符号 如果S VT VN 则称 是文法G S 的一个句型 句子 如果 VT 则称 是文法G S 的一个句子 仅含终结符的句型是一个句子 由定义可知 开始符S本身只能是文法的一个句型而不可能是一个句子 句子是特殊的句型 上面推导出的i i i是文法G E 的一个句子 当然也是一个句型 而E E E E E E E i和E i i都是文法G E 的句型思考 文法G S S aB BbB a b的句型和句子有多少个 3 1文法和语言 3 1 1文法和语言的基本概念文法产生的语言 对于文法G S 它所产生的句子的全体称为由文法G S 产生的语言 记为L G 即有 L G S 且 VT 注意 1 S至少进行一次推导 2 S所推导出的 必须全部由终结符组成 3 当文法给定 语言也就唯一地确定 即G L G 给定一个语言 它所对应的文法不是唯一的 4 L G 是VT 的子集 属于VT 的符号串不一定属于L G 3 1文法和语言 3 1 2形式语言分类语言学家NoamChomsky于1956年首先建立了形式语言的描述 定义了四类文法及相应的形式语言 它对程序语言的设计 编译方法 计算复杂性等方面都产生了重大影响 0型文法与0型语言 对应图灵机 1型文法与1型语言 对应线性界限自动机 自然语言 2型文法与2型语言 对应下推自动机 程序设计语言 3型文法与3型语言 对应有限自动机 3 1文法和语言 3 1 2形式语言分类1 0型文法与0型语言如果文法G S 的每一个产生式具有下列形式 其中 V VNV 注 V VN VT 即至少含有一个非终结符 V 则称文法G S 为0型文法或短语文法 记为PSG PhraseStructureGrammar 0型文法相应的语言称为0型语言或称递归可枚举集 它的识别系统是图灵 Turing 机 例如 S ACaBCa aaCCB DBCB EaD DaAD ACaE EaAE 3 1文法和语言 3 1 2形式语言分类2 1型文法与1型语言文法G S 的每一个产生式 均在0型文法的基础上增加了字符长度满足 的限制 则称文法G S 为1型文法或上下文有关文法 记为CSG 1型文法相应的语言称为1型语言或上下文有关语言 它的识别系统是线性界限自动机 1型文法的等价定义文法G S 的每一个产生式具有下列形式 A 其中 V A VN V 显然 它满足前述定义的长度限制 但它更明确地表达了上下文有关的特性 即A必须在 的上下文环境中才能被 所替换 3 1文法和语言 3 1 2形式语言分类3 2型文法与2型语言文法G S 的每一个产生式具有下列形式 A 其中 A VN V 则称文法G S 为2型文法或上下文无关文法 记为CFG 2型文法相应的语言称为2型语言或上下文无关语言 它的识别系统是下推自动机 例 G S a b S S S aSb S ab 产生的语言为 3 1文法和语言 3 1 2形式语言分类3 2型文法与2型语言上下文无关文法有足够能力描述现今程序设计语言的语法结构 例如 产生条件句的文法片段语句 if条件then语句 if条件then语句else语句 其他语句 3 1文法和语言 3 1 2形式语言分类4 3型文法与3型语言文法G S 的每个产生式具有下列形式 A a或A aB其中 A B VN a VT 则文法G S 称为3型文法 正规文法或右线性文法 记为RG 3型文法相应的语言称为3型语言或正规语言 它的识别系统是有限自动机 3型文法还可以呈现左线性形式 A a或A Ba 3 1文法和语言 3 1 2形式语言分类4 3型文法与3型语言文法G S 的每个产生式具有下列形式 A a或A aB其中 A B VN a VT 则文法G S 称为3型文法 正规文法或右线性文法 记为RG 3型文法相应的语言称为3型语言或正规语言 它的识别系统是有限自动机 3型文法还可以呈现左线性形式 A a或A Ba 3 1文法和语言 3 1 2形式语言分类5 4类文法的关系与区别关系 1 从0型文法到3型文法的限制逐渐增 2 1 3型文法都属于0型文法 3 2 3型文法不一定属于1型文法 因为1型文法不允许存在 A 形式的产生式 则 如果2 3文法不含有类似产生式 则该文法属于1型文法 3 1文法和语言 3 1 2形式语言分类5 4类文法的关系与区别区别 1 1型文法中不允许有形如 A 的产生式存在 而2 3型文法则允许形如 A 的产生式存在 2 0 1型文法的产生式左部存在含有终结符号的符号串或两个以上的非终结符 而2型和3型文法的产生式左部只允许是单个的非终结符号 3 1文法和语言 3 1 3正规表达式与上下文无关文法1 正规表达式到上下文无关文法的转换正规表达式所描述的语言结构均可用上下文无关文法描述 反之则不一定正规表达式构造上下文无关文法 1 构造正规表达式的NFA 2 若0为初始状态 则A0为开始符号 3 如果存在映射关系f i a j 则定义产生式AiaAj 4 如果存在映射关系f i j 则定义产生式AiAj 5 如果i为终态 则定义产生式Ai 例题 用上下文无关文法描述正规表达式1 0 1 1