程序设计语言的语法描述.ppt

2020 3 26 第3章程序设计语言的语法描述 3 1文法的引入3 2上下文无关文法3 3文法举例 略 使用文法对程序设计语言的结构进行定义和描述 2020 3 26 3 1文法的引入 先讨论自然语言的文法 例 thebigelephentateabanana 语法树根据英语的语法 上述句子的语法结构可用图 语法树 表示如下 非叶结点称为语法单位 在形式语言中称为非终结符 处于根结点位置的结点又称为开始符号 叶结点称为单词符号 在形式语言中称为终结符 2020 3 26 规则可以通过建立一组规则 来描述上述句子的语法结构 规则在形式语言中称为产生式 the a big elephant banana ate 由规则推导句子可用规则来推导出句子 从开始符号出发 若能从规则推导出某符号串 则该符号串就是该文法的合法的句子 反之语法错误 上述英文句子可用下述规则来描述 2020 3 26 the thebig thebigelephant thebigelephant thebigelephantate thebigelephantate thebigelephantatea thebigelephantateabanana上述推导可简单表示为 thebigelephantateabanana 值得注意的是用上述规则可推导出多个句子 因存在推导 abigbananaatetheelephant所以 abigbananaatetheelephant也是文法的一个合法的句子 但意义是荒谬的 也就是说句子的语义是错误的 一个语法正确的句子不能保证其语义是正确的 故一个句子是否正确 需要进行语法和语义两方面检查 综上所述 语言结构通常是用文法来定义和描述 文法是由终结符 非终结符 开始符号 特殊非终结符 及产生式四个要素构成 从开始符号出发 根据产生式能推导出的句子全体称为文法所规定的语言 2020 3 26 递归规则和递归文法递归是编译技术中的一个重要概念 递归定义 定义某事物 又用到该事物本身 递归规则 直接递归 在规则的左部和右部有相同的非终结符 例 U xUy 通常用大写字母表示非终结符 用小写字母表示终结符 左递归规则 x U Uy 表示空串 右递归规则 y U xU 间接递归 由规则推导产生 例 V Uy Z U xV因存在推导V Uy xVy 故存在间接递归 间接左递归 若x 则V Vy 间接右递归 若y 则V xU 递归文法 含有递归规则和间接递归的文法 称为递归文法 利用递归文法 可以用有穷的规则来描述无穷的语言 这不但解决了语言的定义问题 而且使得对语言的语法检查成为可能 2020 3 26 3 2上下文无关文法 形式语言的奠基人乔姆斯基 Chomsky 将文法分为4种类型 它们是 短语文法 0型文法 上下文有关文法 1型文法 上下文无关文法 2型文法 正规文法 3型文法 这四种文法在形式语言中都有严格的定义 但对于程序设计语言来说 上下文无关文法已经够用了 上下文无关文法有足够的能力描述大多数现今使用的程序设计语言的语法结构 以后 文法 一词若无特别说明 则指 上下文无关文法 2020 3 26 文法和语言一个文法G是一个四元式 VT VN S P 其中VT是一个终结符的非空有限集 终结符通常用小写字母表示 VN是一个非终结符的非空有限集 非终结符通常用大写字母表示 S是一个特殊的非终结符 S VN 称为开始符号 P是一个产生式 规则 的有限集合 每个产生式的形式是A 其中A VN VT VN 终结符是语言的基本符号 即程序设计语言的单词 语法分析时 终结符用单词的种别表示 根据前面约定 标识符 简单变量 i无符号整常数 x无符号实常数 y单字符单词 用单词本身表示 例单词 的种别用 表示 多字符单词 需特别指定 例 用 表示 2020 3 26 非终结符表示抽象的语法单位 例 算术表达式 布尔表达式 赋值语句 说明语句 和 程序 等 非终结符通常用大写字母表示 也可以用带尖括号的汉字表示 开始符号是一个特殊的非终结符 它代表我们最感兴趣的语法单位 例如讨论算术表达式 那么描述算术表达式文法的开始符号就是 在程序设计语言中 我们最感兴趣的语法单位是 程序 产生式是定义语法单位的一种书写规则 上下文无关文法产生式的左部必定是一个非终结符 该非终结符称为左部符号 产生式的右部是终结符和非终结符经有限次连接构成的文法符号串 可以是空字 四种文法的区别主要是对产生式的左部和右部的限制不同 若干个左部符号相同的产生式 可合并为一个 例 A 1 2 n 其中 i称为A的候选式 1 i n 2020 3 26 例1 描述算术表达式文法G VT VN S P 其中VT i x y VN S P i 标识符 x 无符号整常数 y 无符号实常数 根据上述文法 可推导出任何仅包含加减乘除的算术表达式 2020 3 26 因已约定非终结符和终结符的书写方式 非终结符和终结符在产生式中一目了然 故终结符集VT和非终结符集VN无需再显式列出 若规定左部符号为开始符号的产生式写在所定义文法的第一行 上述文法G又可简单表示为如下形式 i x y若用E表示 T表示 F表示 借助符号 算术表达式文法G可表示成如下最简形式 E E T E T TT T F T F FF E i x y 2020 3 26 例2 描述算术表达式文法G VT VN S P 其中VT i x y VN P i 标识符 x 无符号整常数 y 无符号实常数 根据上述文法 同样可推导出任何仅包含加减乘除的算术表达式 用E表示 上述文法可简记为 E E E E E E E E E E i x y 2020 3 26 基本术语以文法G E E E E E E i为例 进行下述讨论 直接推出和直接归约 推导和归约若 1 2 n 则称该直接推出序列是从 1到 n的一个推导 记作 1 n或 n 1 n 从 1始 经一步或一步以上可推导出 n 1 n 从 1始 经 步或 步以上可推导出 n 即 1 n或 1 n 也可称直接归约序列 n n 1 1为 n到 1的一个归约 句型若存在推导S S为文法的开始符号 则称 是文法的一个句型 句子仅包含终结符的句型称为句子 2020 3 26 语言文法 所能推导出的句子全体称为该文法的语言 记为 L G S VT 等价文法 1和 2是二个不同的文法 若L G1 L G2 则称G1和G2是等价文法 等价文法的存在 使我们能够在不改变文法所规定的语言的前提下 为了某种目的改造文法 最左推导和最右推导在各种推导中 考虑今后语法分析的需要 我们仅对两种推导感兴趣 1 最左推导在推导过程中始终对最左面的非终结符进行替换 记为 2 最右推导在推导过程中始终对最右面的非终结符进行替换 记为 2020 3 26 文法的二义性 语法树我们可以用一个有向图表示一个句型的推导 这种表示称为语法树 语法树有助于理解一个句子语法结构的层次 在一般情况下 某一句型不论其推导过程如何 其最终形成的语法树是相同的 故语法树是不同推导过程的共性抽象 若仅进行最左 右 推导 则语法树和最左 右 推导等价 二义文法若一个文法所产生的语言中 只要存在一个句子 它有二个最左推导 或有二个最右推导 或句子的推导对应两棵语法树 则称该文法为二义文法 二义文法的利用和处理1 根据条件修改文法 语言不变 算符优先性 规定 优先于 i i i等价于i i i 算符结合性 规定同级运算服从左结合 i i i等价于 i i i 2 根据条件修改编译程序的语法分析表 文法保持不变 详见第四 五章 2020 3 26 1 根据条件修改文法 语言不变 算符优先性 规定 优先于 i i i等价于i i i 算符结合性 规定同级运算服从左结合 i i i等价于 i i i 例文法GG E E E E E E i是一个二义文法 根据上述条件将文法G修改成G 如下所示G E E T TT T F FF E i显然G 不是二义文法 但L G L G 故G和G 等价 例句子i i i的最右推导 E E T E T F E T i E F i E i i T i i F i i i i iE T T F 先形成 才有可能形成 若先形成 只有带括号才可能形成 2020 3 26 2 根据条件修改编译程序的语法分析表 文法保持不变 例文法G if标识符thenelseS fitSeS if标识符thenS fitS 标识符 S i E 无符号整常数E x程序段a 2ifxthenifythena 4elsea 6相应的语法结构表示为i xfitfiti xei x句子fitfiti xei x的最左推导序列有二个 如下所示 S fitSeS fitfitSeS fitfiti EeS fitfiti xeS fitfiti xei E fitfiti xei xS fitS fitfitSeS fitfiti EeS fitfiti xeS fitfiti xei E fifii xei x因句子fitfiti xei x存在二个最左推导 故文法G为二义文法 2020 3 2