编译原理第2章.ppt

第2章高级语言及其语法描述 2 1程序语言的定义2 2高级语言的一般特性2 3程序语言的语法描述 常用的高级语言FORTRAN数值计算COBOL事务处理PASCAL结构程序设计ADA大型程序 嵌入式实时系统PROLOG逻辑程序设计ALGOL算法语言C C 系统程序设计JavaInternet程序设计 与机器语言或汇编语言比较 高级语言的优点 较接近于数学语言和工程语言 比较直观 自然和易于理解 便于验证其正确性 易于改错 编写效率高 易于移植 2 1程序语言的定义 自然语言与计算机语言的区别与联系 计算机程序语言 一个记号系统 类似于自然语言 由语法 语义定义 2 1程序语言的定义 一 语法 一组规则 使用它可以形成和产生一个合式的程序 则这组规则称为语法 定义了程序的形式结构 是判断输入字符串是否构成一个形式上 即合式 正确程序的依据 2 1程序语言的定义 二 语义 1 语义规则 一组规则 使用它可以定义一个程序的意义 离开语义 语言只不过是一堆符号的集合 在许多语言中有着形式上完全相同的语法单位 但含义却不尽相同 注意 阐明语义要比阐明语法难得多 现在还没有一种公认的形式系统 借助于它可以自动地构造出实用的编译程序 本书 基于属性文法的语法制导翻译方法 较接近形式化 程序语言的基本功能和层次结构 程序语言的基本功能 描述数据和对数据的运算 所谓程序 本质上说是描述一定数据的处理过程 程序的层次结构 程序 子程序或分程序 过程 函数 语句 表达式 数据引用算符函数调用 2 程序语言的语法描述 基本概念 1 有穷字母表 中的每个元素 由 中的符号所构成的一个有穷序列 空字 不包含任何符号的序列 上的所有符号串的全体 包括 注 区分 空集 不含任何元素的集合 符号 上的符号串 2 程序语言的语法描述 连接 积 UV U V U V V的闭包 V的正则闭包 注 V 中的每个符号串都是由V中的符号串经有限次连接而成的 例 a b U ab b V aa bb a b a b 0 a b 1 a b 2 a b ab aa bb ba a b a b a b a b a b ab aa bb ba a b ab aa bb ba ab b aa bb abaa abbb baa bbb UV 设 V a aa 那么 V a aa aaa aaaa V a aa aaa aaaa 2 程序语言的语法描述 一 上下文无关文法 1 定义 文法 描述语言的语法结构的形式规则 即语法规则 上下文无关文法 所定义的语法范畴 或语法单位 是完全独立于这种范畴可能出现的环境的一种文法 描述语法规则的且独立于环境 描述语法规则 例 英语中 一般句子是由主 谓二部分构成 2 程序语言的语法描述 2 文法 语法的类比 分析 Thegreywolfwilleatthegoat Thegreywolfwilleatthegoat 直接宾语 名词 动词 谓语 名词 形容词 冠词 主语 句子 助动词 动词原形 冠词 2 程序语言的语法描述 产生句子的规则 从产生语言的角度 1 2 the grey 5 6 9 will eat wolf goat 2 程序语言的语法描述 B 句子的语法组成 终结符号集 非终结符号集 语法规则 开始符号 终结符号集VT the grey wolf will eat goat 非终结符号集VN 语法规则集P 开始符号S 2 程序语言的语法描述 C 句子的派生 推导 根据规则 the thegrey thegreywolf thegreywolf thegreywolfwilleatthegoat 2 程序语言的语法描述 D 句子的语义要求 thegreywolfwilleatthegoatthegreywolfwilleatthewolfthegreygoatwilleatthewolfthegreygoatwilleatthegoat 符合语法且符合语义的句子仅是 thegreywolfwilleatthegoat 2 程序语言的语法描述 3 上下文无关文法 的形式定义 是一个四元组 终结符号集 非空有限集 非终结符号集 非空有限集 终结符号 描述单词符号 组成语言的基本符号 是一个语言的不可再分的基本符号 例如 基本字 标识符 常数 算符 界符等 非终结符 代表语法范畴 一个非终结符代表一个一定的语法概念 每个非终结符表示一定符号串的集合 例如 算术表达式 布尔表达式 赋值句 分程序 过程等 2 程序语言的语法描述 开始符号 一个特殊的非终结符号 产生式集合 有限集 产生式 定义语法范畴的一种书写规则 形式 A A VN VT VN 注 定义为 或 非终结符号 用大写字母 或汉语组代表终结符 用小写字母 代表 至少必须在某个产生式的左部出现一次 巴科斯范式 BNF Backus NaurForm的缩写 描述计算机语言语法的符号集 由JohnBackus和PeterNaur首次引入一种形式化符号来描述给定语言的语法 最早用于描述ALGOL60编程语言 JohnBackus PeterNaur BNF现在是定义一种计算机语言的标准方式 2 程序语言的语法描述 例1 上下文无关文法 E i EAEA 非终结符号 开始符号 终结符号 E A E i G E 2 程序语言的语法描述 例2 算术表达式的文法 标识符 id 常量 变量 是表达式 E 表达式加一个表达式是表达式 表达式减一个表达式是表达式 表达式乘一个表达式是表达式 表达式除一个表达式是表达式 表达式加上括号是表达式 E idE E EE E EE E EE E EE E P E id E E E E E E E E E 2 程序语言的语法描述 文法与语言的关系 中心思想 从文法的开始符号出发 反复连续使用产生式 对非终结符施行替换和展开 一个上下文无关文法如何定义一个语言呢 2 程序语言的语法描述 例 E id E E E E E E E E E i i 注 我们可以从 出发 进行一系列的推导 推出种种不同的算术表达式出来 该推导过程证明了 是文法 所定义的一个算术表达式 2 程序语言的语法描述 若 则称该序列是从 至 的一个推导 可推导出 表示 直接推出 即仅推出一步 A 仅当 是一个产生式 且 推导 从 出发 经过 步或若干步 可推导出 从 出发 经一步或若干步 可推导出 注 符号的含义 已知文法G T T F FF F P PP T aT P T F 2 程序语言的语法描述 句型 设 是一个文法 是其开始符号 VN 5 语言 句子 仅含终结符号的句型是一个句子 已知文法G S aAbA BcA BB idt 1 aidtcBcAb 2 aidtccb 3 ab 4 abidt句型句子 2 程序语言的语法描述 6 最左 右推导定义 任何一步 都是对 中的最左 最右非终结符进行替换的 最左推导 最右推导 练习 G S S a T T T S S分别给出下列句子的最左和最右推导过程 1 a a a 2 a a 1 最左推导 S T T S S S a S a T a T S a S S a a S a a a 2 最左推导 S T T S S S a S a T a T S a S S a a S a a 2 程序语言的语法描述 2 程序语言的语法描述 分析 与 类似 由 可知 其必产生 且以此终结 2 程序语言的语法描述 例 构造一个文法 使 分析 与 的区别在于 必须使 出现的次数相等 故而 必须同时出现 G 2 程序语言的语法描述 思考 考虑文法D D D TLT int charL L id id定义了一个什么样的语言 2 程序语言的语法描述 二 语法分析树与二义性 语法分析树用树的形式表示一个句型的推导生成 有助于理解一个句子语法结构的层次 2 程序语言的语法描述 例 的最左推导 次 层 结论 一个句型不一定有唯一的一棵语法树 即一个句型的最左 右推导可能不唯一 2 程序语言的语法描述 例 关于文法 的另一个最左推导 2 程序语言的语法描述 2 二义文法用若一个文法中存在某个句子 它有两个不同的最左 右推导 则该文法为二义文法 例 上述文法 实质 同一个句子存在两棵语法分析树 2 程序语言的语法描述 例 句子 的最左推导过程 最左推导 2 程序语言的语法描述 最右推导 已知文法G E E EOE E v dO 请证明该文法是二义的 提示 v v d的语法树不只一棵 2 程序语言的语法描述 注意 区分 文法的二义性 语言的二义性二义文法 无二义文法 但 B 二义问题是不可判定的 即不存在一个算法 它能在有限步骤内 确切的判定一个文法是否为二义的 所能做的只是为无二义性寻找一组充分条件 2 程序语言的语法描述 形式语言鸟瞰 Chomsky于1956年建立形式语言体系 他把文法分成四种类型 0 1 2 3型 与上下文无关文法一样 它们都由四部分组成 但对产生式的限制有所不同 乔姆斯基 NoamChomsky 1928 美国语言学家 转换 生成语法的创始人 从上世纪60年代起 他一直在骂美国外交政策 从越战骂到伊战 骂成著作等身的 老愤青 他被美主流媒体封杀 邮箱曾一度需要特工检查后才能打开 他的海报贴在北京大学校园 继上个世纪罗素与杜威之后 最有名的西方学者的东方之行 他来华演讲的诱惑无人能抵挡 在他演讲前的几个小时 满广场的学生和老师在等侯着多余的门票 在北大 这是某国总统演讲时才会出现的场面 82岁的他首次访华 作为一名美国异见分子 不用指望受到当权者的欢迎 他在演讲中说 2 程序语言的语法描述 三 形式语言 G VT VN S 0型