编译原理第三章文法和语言.ppt

引言和预备知识 高级语言 程序语言是一个记号系统 语法 语义 语法 任何语言程序都可以看成是一定字符集（字母表）上的字符串 语法使得这串字符形成一个形式上正确的程序 语法=词法规则+语法规则 例如：0.5*x1+c 0.5、x1、c、*、+是语言的单词符号 0.5*x1+c是语言的语法单位 词法 单词符号 语言中具有独立意义的最基本结构 词法规则 词法规则规定了字母表中哪些字符串是单词符号 单词符号一般包括：常数、标识符、基本字、算符、界限符等 我们用正规式和有限自动机理论来描述词法结构和进行词法分析 语法 单词符号 语法单位 表达式、子句、语句、函数、过程、程序 语法规则 规定了如何从单词符号来形成语法单位 现在多数程序语言使用上下文无关文法来描述语法规则 语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据 例，对于一个PASCAL程序来说，一个上下文无关文法可以定义 A:=B+C 是合乎语法的， 而A:=B+ 是不合乎语法的。 语义 对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义 离开语义，语言只是一堆符号的集合 各种语言中有形式上完全相同的语法单位，含义却不尽相同 对某种语言，可以定义一个程序的意义的一组规则称为语义规则 目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义 对于高级程序设计语言及其编译程序来说，语言的语法定义是很重要的。本章主要介绍语法结构的形式描述问题，编译原理的主要内容也可以归纳为应用形式语言理论，并将它贯穿于词法分析和语法分析两个阶段 句子：字母表上符合某种规则构成的串 语言：字母表上句子的集合 注：约定用a, b, c…表示符号；用?, ?, ?…表示符号串；用A, B, C表示其集合 文法简化的步骤 查找有无形如P→P的产生式，若有则删除 若某个产生式在推导过程中永远不会被用到，删除它 若某个产生式在推导过程中不能从中导出终结符，删除它 最后，整理所有剩余产生式，就得到简化的文法 * * 二义性 问题：一个句型是否对应唯一的一棵语法树？ 例：G[E]: E → i E → E+E E → E*E E → (E) E E + E E * E i i i E E * E i E + E i i 句型 i*i+i 的两个不同的最左推导： 推导1：E ? E+E ? E*E+E ? i*E+E ? i*i+E ? i*i+i 推导2：E ? E*E ? i*E ? i*E+E ? i*i+E ?i*i+i * * 若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。 文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。 产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。 * * 注： 二义性会给语法分析带来不确定性 文法的二义性是不可判定的，即不存在算法，能够在有限步数内确切判定一个文法是否为二义文法 若要证明是二义性，只要举出一例 * * 若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事 二义文法改造为无二义文法 G[E]: E → i G[E]：E → T|E+T E → E+E T → F|T*F E → E*E F → (E)|i E → (E) 规定优先顺序和结合律 * * 3.6 句型的分析 句型分析 就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法 ，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。 * * 分析算法可分为： 自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。 自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 两种方法反映了两种不同的语法树的构造过程 * * 自上而下的语法分析 例：文法G：S → cAd A → ab