编译原理文法与语言.ppt

内容回顾 什么是编译程序编译的过程词法分析语法分析语义分析及中间代码生成优化目标代码生成编译程序的结构与组织 文法和语言 字母表和符号串的基本概念文法和语言的形式定义递归规则与递归文法语法树与文法的二义性文法的分类 字母表和符号串的基本概念 字母表 元素的非空有穷集合 记为 字母表包含了语言中所允许出现的一切符号 例如 0 1 符号串 字 字母表中的符号所组成的有穷序列 一个语言的句子总是它的字母表的符号串 这个符号串的组成必须是按照文法规则组合而成的 语法分析的一个重要任务就是 判断一个符号串的组成是否满足某个文法的规定 字母表和符号串的基本概念 空串 不包含任何符号的串 记为 表示 上所有符号串的全体 空集 不包含任何元素 在本课程中 语言被认为是句子的集合 所以 一个语言就是对应于它的字母表上的一个符号串集合 关于符号串的运算 符号串的长度 指符号串x中所含符号的个数 记为 x 符号串相等 若x y是字母表 上的两个符号串 那么当且仅当组成x的各符号与组成y的各符号依次相等时 则符号串x与符号串y相等 记作x y 符号串的前缀 指从符号串x的末尾删除0或多个符号后得到的符号串 符号串的后缀 指从符号串x的开头删除0或多个符号后得到的符号串 关于符号串的运算 符号串的子串 指从符号串x的开头和末尾删除0或多个符号后得到的符号串 符号串的前缀 后缀都是它的子串 连接 并置 若x y是两个符号串 则xy表示连接 是将符号串y连接在符号串x的后面 若x y是字母表 上的两个符号串 则xy也是字母表 上的符号串 注意 连接没有交换率 即xy yx而对于空串 有 x x x方幂 x的n次方幂即将n个x连接 x0 x1 x x2 xx xn xx x xxn 1 xn 1x 符号串集合的运算 乘积 令A B为两个符号串集合 A和B的乘积AB定义为 AB xy x A且y B A A A A A 方幂 A的n次方幂就是将n个A相乘 A0 A1 AA2 AA An AA A AAn 1 An 1A 符号串集合的运算 集合的正则闭包和集合的闭包 设A为一个集合 则集合A的正则闭包用A 表示 定义为 A A1 A2 An 表示A上的所有的非空符号串的集合 集合A的闭包用A 表示 定义为 A A0 A 表示A上的所有符号串 包括空字符串 的集合 例如 A a b 则A a b aa ab ba bb aaa aab A a b aa ab ba bb aaa aab 文法和语言的形式定义 形式语言描述的两种方法枚举方法使用文法来描述 文法是一种工具 它可用于严格定义句子的结构 例如 能够描述句子 themonkeyatethebanana 的文法如下 the ate banana monkey 文法的形式定义 产生式 规则 产生式 一个产生式是一个有序对 通常写作 或 其中 为左部 为右部 产生式意味着能将一个符号串用另外一个符号串替换 因而又被称为重写规则 一组规则规定了一个语言的语法结构 规则中的符号分为两类 终结符号 非终结符号 终结符与非终结符 终结符 VT组成语言的基本符号 在程序设计语言中就是以前屡次提到的单词符号 如 基本字 标识符 常数 算符 界符等 从语法分析的角度看 终结符是一个语言的不可再分的基本符号 非终结符 VN也称语法变量 用来代表语法单位 如 算术表达式 布尔表达式 赋值句 子程序 函数 等 一个非终结符代表一个一定的语法概念 是一个类 集合 记号 而不是一个个体记号 VT VN VT VN为该语言的字母表 文法的定义 Chomcky文法的定义 G VN VT P S 其中 VN 非空有限的非终结符号集VT 非空有限的终结符号集P 产生式集S 开始符号 识别符号 S VN文法被用来精确而无歧义地描述语言的句子的构成方式 文法描述语言的时候不考虑语言的含义 例 按文法形式定义表示上例文法 解 根据文法的形式定义 文法G1 VN VT P S VN 句子 主语 谓语 冠词 名词 动词 直接宾语 VT the ate banana monkey 产生式集合P由右面8条规则组成开始符号S the ate banana monkey 1 2 3 4 05 16 27 38 49 510 611 712 813 9 产生式的简写 A B A C可以简化为 A B C 1 2 3 0 1 2 3 4 5 6 7 8 9 文法举例 G1 VN VT P S 其中 VN E VT i P E E E E E E E E E i S E 语言的形式定义 文法的作用是描述某种语言的句子的构成方式 使用文法我们可以产生对应语言的句子 从识别符号开始 不断将当前符号串中的非终结符号替换为该符号的某个规则的右部 直到当前的符号串中所有的符号都是终结符号为止 推导和直接推导 直接推导 v A w 并且A 是文法中的一个产生式 那么我们说v可以直接推导到w 或者w可以直接规约到v 记作v w 其中 VN VT 推导 若v 0 1 2 n w n 0 则符号串w为符号串v的一个推导 记为v wv w含义 v w或v w 例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 EE0步推导E i i i6步推导E i i i6步推导E E 直接推导 句型 句子 对于文法G S 称为G的一个句型 如果 S 开始符号是最简单的句型 G S 的一个句型 被称为句子 如果 VT 也就是说句子是全部由终结符号组成的句型 文法的语言 文法的语言 一个文法G S 的语言 用L G S 表示 定义如下 L G S S 并且 VT 一个文法的语言就是该文法的所有的句子的集合 文法的语言是所有终结符号串所组成的集合的子集 一般是真子集 文法和语言有如下关系 给定一个文法 就能从结构上唯一的确定其语言 即 G L G 给定一种语言 能确定其文法 但不唯一 即 L G1或G2或 若文法G1和文法G2所产生的语言相同 即L G1 L G2 则称文法G1和文法G2等价 文法与语言举例 描述语言L ban n 1 的文法 S bAA aA a文法S ABA aA aB bB b描述的语言是 L anbm m n 1 文法与语言举例 已知文法G Z 为 Z aZb ab求该文法确定的语言 已知语言为 L G abna n 1 构造产生该语言的文法 思考题 a b 设计文法描述语言L a2n b2n n 1 设计一个表示所有标识符的文法 得到一个语言 是通过利用所有的侯选式推导出所有句子 构成一个集合 但是一个句型到另一个句型 句子 的推导过程不是唯一的 G E i P E P E E E E E E i表达式 i i i的推导过程 最左 右 推导 在推导之前确定推导的顺序 是对句子进行确定性分析所必须的 最左 右 推导定义 在一个推导的过程中 如果每一步直接推导所被替换的总是最左 右 的非终结符号 那么这种推导称为最左 右 推导 最右推导又称为规范推导 用规范推导得到的句型称为规范句型 最左推导的例子 标识符文法G S S L SD SL L a b c x y z D 0 1 2 7 8 9最左推导 S SD SDD LDD aDD a6D a69 最右推导的例子 标识符文法G S S L SD SL L a b c x y z D 0 1 2 7 8 9最右推导 S SD S9 SD9 S69 L69 a69 递归规则与递归文法 递归规则是指那些在规则的右部含有与规则左部相同符号的规则 例如 U xUy 右部含有与规则左部相同符号U 那么就是递归规则 如果这个相同的符号出现在右部的最左端 则为左递归规则 如U Uy如果这个相同的符号出现在右部的最右端 则为右递归规则 如U xU 若文法中至少包含一条递归规则 则称文法是直接递归的 若文法中不含递归规则 但有推导过程U xUy 所以该文法为间接递归文法 递归文法使我们能用有穷的文法刻画无穷的语言 语法树 用一张图来表示一个句型的推导 有助于理解句子语法结构的层次 定义 设文法G VN VT P S 对于文法G的任意一个句型都存在一棵相应的语法树 结点由符号组成 根结点对应于开始符号 只有非终结符号对应的结点有子结点 一个结点和它的子结点分别对应于文法中的一个规则的左部和右部 语法树的例子 语法G S S ABA aAb abB cBd cd S AB abB abcBd abccdd 语法树的相关概念 结点 每个树的结点对应于一个符号 结点的名字就是该符号 边 两个结点之间的连线 根结点 没有边进入的结点 分支 某个结点向下射出的边和其结点称为分支 父子结点 兄弟结点 子树 语法树的某个结点和它向下射出的部分 语法树的相关概念 叶子 末端结点 没有向下射出的边的结点称为叶子 末端结点 在相对于句型的语法树中 叶子 末端结点可能是非终结符号 用语法树表示上下文无关文法的推导 步骤1 根结点为开始符号 步骤2 对于每一次推导使用的规则U u 找出U对应的结点 此时应该是末端结点 从该结点向下画分支 子结点从左到右分别是u中从左到右的符号 重复步骤2直到推导的最后一步 在语法树的推导过程中 没有后代的端末结点自左至右排列起来就是一个句型一棵语法树表示了一个句型很多可能的不同推导过程 文法的二义性 定义 如果对于某文法的一个句子存在两棵不同的语法树 则该句子是二义性的 而该文法是二义性文法 这里的二义性是指语法结构上的 如果一个句子具有二义性 那么对这个句子的结构可能有多种 正确 的解释 通常情况下 句子的语义要通过其语法结构来定义 所以 二义性一般是有害的 定理 文法的二义性是不可判定的 文法二义性的例子 文法G E E E E E E E i文法的句子 i i i 其语法树如下 文法二义性的解决方法 对文法加以限制 从语义解释方面加以限制 IF语句文法如下 IFTHEN IFTHENELSE 说明该文法是二义性文法 文法的实用限制 文法中不含形如P P的产生式 文法中每个非终结符都有用 必须存在含P的句型 从S出发 存在推导 S P 对于P不存在永不终结的回路 必须存在终结符串 VT 使得P 文法的化简和改造 无用符号和无用产生式的删除 产生式的消除单产生式的消除 文法和语言的Chomsky分类 Chomsky文法根据对产生式的不同限制 可分为四类 0型 1型 2型 3型 我们主要用2型和3型文法 0型文法 PSG PhraseStructureGrammar 0型文法的产生式 VN VT 且至少含一VN VN VT 相应语言称为0型语言 又称为递归可枚举集合 1型文法 CSG ContextSensitiveGrammar 1型文法的产生式 1A 2 1 2 其中A VN 1 2 VN VT VN VT 1 2为上下文 1型文法也可以如下定义 所有的规则的右部都比左部长 2型文法 CFG ContextFreeGrammar 2型文法的产生式 A 其中A VN VN VT 2型文法又称为上下文无关文法 一般的程序设计语言的语法都使用2型文法描述 2型文法的例子 S ab aSb 3型文法 RG RegularGrammar 文法产生式 1 A a或者A aB 2 A a或者A Ba其中A B VN a VT 3型文法又称为右 左 线性文法 正则文法 其语言也称为正则语言 3型文法的例子 S 0 1 1A 2BA 1A 0BB 0 1 0B 语言的层次 这四种语言可被4种自动机识别 0型 图灵机1型 线性界限自动机2型 下推自动机3型 有穷自动机 从外到内 四种文法对产生式的限制越来越多 语言的描述能力越来越弱 正规文法的描述能力比上下文无关文法的描述能力弱正规文法只能用于描述单词的构成上下文无关文法有足够的能力描述现今大多数程序设计语言的语法结构 例L G3 anbn n 1 a b的个数相同 不能由任何正规文法产生 可以由下述上下文无关文法产生 S aSbS ab 同样 上下文无关语言的描述能力比上下文有关语言的描述能力弱 例 G Vn Vt P S P S aSBES aBEEB BEaB abbE bbbE beeE ee是一个上下文有关文法 小结 文法及语言的形式定义递归规则与递归文法语法树与二义文法文法的分类