程序设计语言编译原理(第三版)第2章.pptVIP

2.３程序语言的语法描述 例：句子　ｉ+ｉ＊ｉ的最左推导过程 Ｅ Ｅ Ｅ Ｅ * Ｅ + ｉ ｉ ｉ Ｅ Ｅ Ｅ Ｅ + Ｅ * ｉ ｉ ｉ 最左推导 Ｅ?Ｅ+Ｅ?ｉ＋Ｅ 　?ｉ＋Ｅ*Ｅ?ｉ＋ｉ＊Ｅ 　?ｉ＋ｉ＊ｉ Ｅ?Ｅ*Ｅ?Ｅ＋Ｅ*Ｅ 　?ｉ＋Ｅ*Ｅ?ｉ＋ｉ＊Ｅ 　?ｉ＋ｉ＊ｉ * 2.３程序语言的语法描述 最右推导 Ｅ Ｅ Ｅ Ｅ * Ｅ + ｉ ｉ ｉ Ｅ Ｅ Ｅ Ｅ + Ｅ * ｉ ｉ ｉ Ｅ?Ｅ+Ｅ?Ｅ＋Ｅ*Ｅ 　?Ｅ＋Ｅ*ｉ?Ｅ+ｉ＊ｉ 　?ｉ＋ｉ＊ｉ Ｅ?Ｅ*Ｅ?Ｅ*ｉ 　?Ｅ＋Ｅ＊ｉ?Ｅ+ｉ＊ｉ 　?ｉ＋ｉ＊ｉ * 2.３程序语言的语法描述 注意： Ａ、区分：文法的二义性——语言的二义性 　　二义文法Ｇ≠无二义文法Ｇ’　　但Ｌ（Ｇ）＝Ｌ（Ｇ’） 例如：Ｇ　：Ｅ?Ｅ+Ｅ｜Ｅ*Ｅ｜（Ｅ）｜ｉ Ｇ’：Ｅ?Ｔ｜Ｅ+Ｔ Ｔ?Ｆ｜Ｔ*Ｆ Ｆ?（Ｅ）｜ｉ ?Ｌ（Ｇ）＝Ｌ（Ｇ’） * B、二义问题是不可判定的： 即不存在一个算法，它能在有限步骤内，确切 的判定一个文法是否为二义的． 所能做的只是为无二义性寻找一组充分条件 2.３程序语言的语法描述 * 2.３程序语言的语法描述 三、形式语言 G=(VT ,VN ,S ,Ρ) 0型文法： ??? ?? (VN?VT)* ，至少有一个非终结符 任何产生式 ??? 均满足|?|≤ |?|； 仅S??例外，但S不得出现在任何产生式的右部。 1型文法： 短语文法 上下文有关文法 * 2.３程序语言的语法描述 2型文法： A??, A?VN , ??(VN? VT)* G的任何产生式为A??B或 A?? 其中??VT*，A、B ? VN 。 3型文法： G的任何产生式为A ?B ?或 A??， 其中??VT*，A、B ? VN 。 上下文无关文法 正规文法 右线性正规文法 左线性正规文法 * 第2章　高级语言及其语法描述 2.1 程序语言的定义 2.2 高级语言的一般特性（略） 2.3 程序语言的语法描述 * 2.1 程序语言的定义 自然语言与计算机语言的区别与联系： 计算机程序语言——一个记号系统， 类似于自然语言，由语法+语义定义 自然语言（1）人与人的通讯工具 （2）语义：由环境、背景知识、语气等决定 二义性（常有）——难以形式化 计算机语言 （1）计算机系统间、人机间通讯工具 （2）具有严格的语法、语义 ——易于形式化（严格） * 2.1 程序语言的定义 一、语法 一组规则，使用它可以形成和产生一个合式的程序，则这组规则称为语法。 定义了程序的形式结构，是判断输入字符串是否构成一个形式上（即合式）正确程序的依据。 词法规则——单词符号的形成规则，即规定了字母表中 哪样的字符串是一个单词符号。 单词符号——语言中具有独立意义的最基本结构。 语法规则——语法单位的形成规则，即规定了如何从单 词符号形成更大的结构（即语法单位）。 * 2.1 程序语言的定义 二、语义 1. 语义规则：一组规则，使用它可以定义一个程序的意义 。 离开语义，语言只不过是一堆符号的集合；在许多语言中有着形式上完全相同的语法单位，但含义却不尽相同。 ２. 注意：阐明语义要比阐明语法难得多，现在还没有一 　　种公认的形式系统，借助于它可以自动地构造 　　出实用的编译程序。 本书?基于属性文法的语法制导翻译方法?较接近形式化 * 2.３程序语言的语法描述 基本概念 1. 有穷字母表。 ∑中的每个元素。 由∑中的符号所构成的一个有穷序列。 空字，不包含任何符号的序列。 ∑上的所有符号串的全体，包括ε。 注：区分： ε 、｛ε｝、Ф 空集Ф ＝｛｝：不含任何元素的集合 ∑： 符号： ∑上的符号串： ε： ∑*： * 2.３程序语言的语法描述 ２.（连接）积：UV={αβ|α∈ U＆β∈ V } U、V? ∑* UV不一定等于 VU,　但(UV)W=U(VW) Vn=VV…V V0 = {ε} V*=V0 ∪ V1 ∪ V2 ∪ V3 ∪ … V+=VV* n个 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,