文档详情

编译原理第二章件(续)——张淑艳.ppt

发布:2018-07-09约6.33千字共28页下载文档
文本预览下载声明
温故知新 温故知新 符号串集合的连接 Σ*的子集U和V的连接(积)定义为 UV = {αβ|α∈U β∈V } 指数:Vn= VV…V,V0 = {ε} 闭包:V* = V0 ∪ V1 ∪ V2 ∪ V3 ∪ … 正闭包:V+ = VV* = V1 ∪ V2 ∪ V3 ∪ … 练习 U: { A, B, …, Z, a, b, …, z }, V: { 0, 1, …, 9 } UV, V6, V*, U(V )*, U+ 温故知新 定义1:上下文无关文法是四元组G =(VT , VN , S, P ) VT : 终结符集合 VN : 非终结符集合, VT ∩VN =? S : 开始符号, S∈VN P : 产生式集合, 产生式形式 : P ? ?, P ∈ VN , ? ∈(VN∪ VT)* 例 :变量i是一个算术表达式; 若E1和E2是算术表达式,则E1+E2、E1*E2和(E1)也是算术表达式 温故知新 上下文无关文法如何定义语言?推导 把产生式看成重写规则,把当前符号串中的非终结符用其产生式右部的串来代替。 温故知新 定义2:符号串的推导与归约:已给文法G=(VN,VT, S, P ) 令α,β∈(VN∪VT)*,且A?γ ∈ P ,此时,由符号串αAβ能够直接推出符号串αγβ ,我们称: 符号串αγβ是符号串αAβ的直接推导; 符号串αAβ是符号串αγβ的直接归约 记作: αAβ ? αγβ 若有α1,α2,…,αn∈ (VN∪VT) * 且α1 ?α2 ?… ?αn-1 ?αn 则称αn是α1的推导。 特别约定:若在推导关系α1 αn中允许α1=αn, 则称αn是α1 的广义推导 温故知新 定义3:句型、句子和语言,已给文法G=(VN,VT, S, P ) 2.3.1 上下文无关文法 E ? E + E | E * E | (E ) | ? E | id E ? ?E ? ?(E) ? ?(E + E) 最左推导:任何一步α ? β都是对α的最左非终结符进行替换的。 E ? lm ?E ? lm ?(E) ? lm ?(E + E) ? lm ?(id + E) ?lm ?(id + id) 最右推导(规范推导) E ? rm ?E ? rm ?(E) ? rm ?(E + E) ? rm ?(E + id) ?rm ?(id + id) 2.3.1 上下文无关文法 2.3.1 上下文无关文法 2.3.2 语法分析树与二义性 语法分析树:句型推导的图形表示,简称语法树。 2.3.2 语法分析树与二义性 E ? E * E ? i * E ? i * E + E ? i * i + E ? i * i + i 2.3.2 语法分析树与二义性 消除二义性: 2.3.2 语法分析树与二义性 用一种层次观点看待表达式 i * i + i i * (i + i) i * (i * i + i) i * i * (i + i) + i * i + i 取消二义性的文法 表达式 ? 项 |表达式 + 项 项 ? 因子| 项 * 因子 因子 ? i |(表达式) 2.3.2 语法分析树与二义性 用一种层次观点看待表达式 i * i + i i * (i + i) i * (i * i + i) i * i * (i + i) + i * i + i 取消二义性的文法 E ? T | E + T T ? F | T * F F ? i |(E) 2.3.2 语法分析树与二义性 例:给出文法G,判断是否为二义文法,如果是,取消二义性 语句 ? if 条件 then 语句 | if 条件 then 语句 else 语句 | 其它语句 例 推导句型:if 条件 then if 条件 then 语句 else 语句 最左推导: 语句 ? if 条件 then 语句 ? if 条件 then if 条件 then 语句 else 语句 语句 ? if 条件 then 语句 else 语句 ? if 条件 then if 条件 then 语句 else 语句 2.3.2 语法分析树与二义性 语句 ? if 条件 then 语句 | if 条件 then语句else语句 | 其它语句 取消二义性的文法: 语句? 匹配句| 非匹配句 匹配句? if 条件 then 匹配句 else 匹配句 | 其它语句 非匹配句 ? if 条件 then 语句
显示全部
相似文档