1、编译原理编译原理高级语言及其语法描述2023-8-19SEI2Contents程序语言的定义1高级语言的一般特性2上下文无关文法3形式语言42023-8-19SEI32.1 程序语言的定义v一个程序语言是一个记号系统v如同自然语言一样，程序主要由语法和语义两个方面定义 语法描述程序中单词的排列方式或结构 语义描述程序的含义v有时候语言定义也包含语用信息 语用主要是有关程序设计技术和语言成分的使用方法，它使语言的基本概念与语言的外界（如数学或计算机的对象和操作）联系起来2023-8-19SEI4语法v任何语言程序都可以看作是一定字符集（字母表）上的字符串v合式的程序 形式上正确的程序v所谓一个语
2、言的语法是指这样一组规则，用它可以形成和产生一个合式的程序 这些规则的一部分称为词法规则 另一部分称为语法规则（产生规则）v词法规则和语法规则规定了程序的形式结构，是判断输入字符串是否构成一个合式程序的依据。2023-8-19SEI5词法规则v单词符号 单词符号是语言中具有独立意义的最基本结构 常数、标识符、基本字、算符、界符v词法规则是指单词符号的形成规则v描述和分析的工具 有限自动机（Finite Automata）正规表达式 正规文法2023-8-19SEI6语法规则v语法范畴（语法单位）表达式、语句、过程、程序v语法规则是语法单位的形成规则，它规定了如何从单词符号形成更大的结构，即语法
3、单位。v描述工具 上下文无关文法（Context-Free Grammar，CFG）2023-8-19SEI7语义v所谓一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义规则v语义规则的描述 没有公认的形式系统 现常用属性文法2023-8-19SEI8程序语言和程序v程序语言的基本功能 描述数据和对数据的运算v程序 所谓一个程序，从本质上说是描述一定数据的处理过程2023-8-19SEI9程序的层次结构程序子程序或分程序语句数据引用表达式算符函数调用2023-8-19SEI102.2 高级语言的一般特性高级语言的分类1程序结构2数据类型和数据结构3语句与控制结构4
4、2023-8-19SEI11高级语言的分类v强制式语言 命令驱动，面向语句v应用式语言 函数式语言，LISPv基于规则的语言 检查条件，执行动作，Prologv面向对象语言 封装，继承，多态2023-8-19SEI12程序结构示例v过程式程序 FORTRAN Pascalv基于对象/面向对象程序 Ada Java2023-8-19SEI13数据类型与操作v数据类型的三要素 用于区别这种类型数据的属性 这种类型的数据对象可以具有的值 可以作用于这种类型的数据对象的操作v数据类型 初等数据类型 数据结构 抽象数据类型2023-8-19SEI14初等数据类型v数值数据 整数，实数；可以进行算术运算v
5、逻辑数据 逻辑型数据，位串；v字符数据 字符和字符串v指针类型2023-8-19SEI15标识符和名字v标识符 程序中的各种名字都用标识符表示 标识符的构成规则v名字 具有明确的意义和属性 存储单元、值 类型、作用域2023-8-19SEI16数据结构v数组 下标、下标变量 数组的存放方式与元素地址v记录 字段，域 存放方式与边界对齐v其它 字符串、表、栈2023-8-19SEI17抽象数据类型v抽象数据类型包括 数据对象的一个集合 作用于这些数据对象的抽象运算的集合 这种类型对象的封装2023-8-19SEI18语句与控制结构v表达式 变量、常数是表达式；若E1、E2为表达式，是一个二元算符
6、，则E1 E2是表达式；若E是表达式，是一元算符，则E（或E）是表达式；若E是表达式，则（E）是表达式。v算符 操作数个数、优先级、结合性例C语言运算符2023-8-19SEI20语句v按功能分类 说明性语句 执行性语句 赋值、控制、输入输出v按形式分类 简单语句 复合语句2023-8-19SEI212.3 程序语言的语法描述上下文无关文法1文法和语言2推导、语法分析树3二义文法4语法v语言的语法是程序或句子中单词的排列方式 自然语言 形式语言v我们使用产生规则来描述语言的语法 上面的产生规则说明一个C语言的if语句的结构 一个if 然后一个(，某种表达式，再一个)最后是某种语句2023-8-
7、19SEI222023-8-19SEI23基本术语和概念v有穷字母表 一个符号的集合 如ASCII、unicode、简体中文GBv符号 字母表中的元素 如a王v符号串 由中的符号构成的一个有穷序列 如”a”、”while”、”a=b+2”、”王者之风”2023-8-19SEI24基本术语和概念v空字 不包含任何符号的序列 不是空格 如C语言中的v*上所有符号串的全体，也包含在其中 如a,b，则*,a,b,aa,bb,ab,ba,aaa,v空集 不包含任何元素的集合基本术语和概念v*的子集U和V的（连接）积定义为 即集合UV中的符号串是由U和V的符号串连接而成的 不满足交换律 UVVU 满足结合
8、律(UV)W=U(VW)2023-8-19SEI25基本术语和概念vV自身的n次（连接）积记为vV*称为V的闭包 其中的每个符号串都是由V中的符号串经有限次连接而成的vV+称为V的正则闭包2023-8-19SEI262023-8-19SEI27上下文无关文法v文法 描述语言的语法结构的形式规则（即语法规则）v文法的作用 句子生成：这个文法产生哪些句子？分析：一个句子S是否是这个文法产生的？v上下文无关文法 所谓上下文无关文法是这样一种文法，它所定义的语法范畴是完全独立于这种范畴可能出现的环境的例：一个英语文法v语法范畴2023-8-19SEI28例：一个英语文法 S,NP,VP,N,Det,V
9、 非终结符 John,Lisa,house,died,.终结符 S 开始符号例：句子产生1.从开始符号开始2.从右边选择一个非终结符X3.选择一条语法规则4.用代替X5.重复直到得到一个单词（字符）串上下文无关文法v一个CFG包括四个组成部分 一组终结符号 组成语言的基本符号，就是前面提到的单词符号 终结符号从语法分析的角度看来是语言不可再分的基本符号 一组非终结符号 也称语法变量，用来代表语法范畴 一个非终结符是一个类或集合记号，而不是一个个体记号 一个开始符号 特殊的非终结符，代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为句子 一组产生式 定义语法范畴的一种书写规则202
10、3-8-19SEI31例：算术表达式文法2023-8-19SEI32v自然语言描述 变量是一个算术表达式 若E1和E2是算术表达式，则E1+E2、E1*E2和(E1)也是算术表达式2023-8-19SEI33上下文无关文法的形式定义v 形式上说，一个上下文无关文法G是一个四元式,SVVNT VT是一个非空有限集合，其中每个元素称为终结符号 VN是一个非空有限集合，它的每个元素称为非终结符号，VTVN S是一个非终结符号，称为开始符号 P是一个产生式集合，每个产生式的形式是2023-8-19SEI34上下文无关文法v 例：简单算术表达式的上下文无关文法可表示如下：VN=E VT=+，*，(，)，
11、iS=EP:E E+E(1)E E*E(2)E（E）(3)E E (4)E i (5)（G2.1）该文法可以重写为：E E+E （1）|E*E （2）|（E）（3）|E （4）|i （5）（G2.2）2023-8-19SEI35文法和语言v文法如何定义语言呢？从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。1.产生式E(E)2.产生式E E+E3.产生式E i4.产生式E i2023-8-19SEI36文法和语言v直接推出v推导v最左推导、最右推导2023-8-19SEI37文法和语言v句型、句子、语言文法、句子和句型示例v 例1：证明(i i+i i)是文法（G2.1）的
12、句子证明：因为存在着如下推导 E E (E)(E+E)(i+E)(i+i)所以(i i+i i)是文法的句子。（证毕）出现在这个推导中的E,E,(E),(i i+i i)都叫做这个文法的句型。2023-8-19SEI38文法、句子和句型示例v 例2：文法G1定义的语言SbA A aA|a解答：可以分析得出 L(G1)=ban|n1v 例3：文法G2定义的语言SAB AaA|a BbB|b解答：可以分析得出 L(G2)=ambn|m,n12023-8-19SEI39文法、句子和句型示例v 例4：构造文法G3使得L(G3)=anbn|n1解答：构造文法G3如下SaSb|ab v 例5：构造文法G5
13、使得L(G5)=anbm|n1,m 0解答：构造文法G5如下SAB AaA|a BbB|2023-8-19SEI40简单程序语言文法1是该文法的一个句子因为存在下面的推导简单程序语言文法22023-8-19SEI43文法和语言v文法与语言之间并不存在一一对应的关系 某一给定的文法可唯一确定它所产生的语言 对于一个给定的语言来说，却往往可以用若干个不同的文法来产生 v文法的等价性 设G1和G2是两个文法，若这两个文法产生同样的语言，即L(G1)=L(G2)，则称G1和G2等价。2023-8-19SEI44语法分析树v 可以用图表示一个句型的推导，这种表示法称为语法分析树，简称语法树或分析树1.根
14、节点的标记为文法开始符号；2.每个叶子节点由一个终结符标记；3.每个中间节点由一个非终结符标记4.如果有一步推导为 即我们使用了产生式 则语法分析（子）树的表示为 2023-8-19SEI45语法分析树v 一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程，包括最左（最右）推导。v 如果坚持使用最左（最右）推导，得到的语法树就完全等价于一个最左（最右）推导。由E最左推导(i+i)建立的语法树 EEE EE()EEE()EEE+EE()EEE+iEE()EEE+ii语法分析树示例2023-8-19SEI47二义性v 如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的
15、。v 二义性问题是不可判定的。不存在一个算法，能够在有限步内确切地判定一个文法是否为二义的。v 可以证明一个文法是有二义性的 为文法的一个句子找到两个不同的最左推导（或最右推导，或语法树）v 文法的二义性不同于语言的二义性。可以对二义文法进行改写二义性、优先级、结合性2023-8-19SEI48构造无二义文法示例v文法G2.1是二义的 改写为无二义文法G2.32023-8-19SEI49 E E+E(1)E E*E(2)E（E）(3)E E (4)E i (5)（G2.1）E E+T E T T T*F T F F（E）F F F i （G2.3）二义性、优先级、结合性v构造无二义的表达式文法
16、1.为每个优先级创建一个非终结符，如P1,P2,Pn，其中Pn的优先级最高2.对优先级为i的运算符op如下构造产生式如果op是左结合的，则产生式为 Pi Pi op Pi+1|Pi+1如果op是右结合的，则产生式为 Pi Pi+1 op Pi|Pi+13.对于初等表达式如数字、标识符、括号等，创建非终结符Pn+1，构造产生式为 Pn+1 num|id|(P1)2023-8-19SEI502023-8-19SEI51化简了的文法v文法中不含任何下面形式的产生式：PPv每个非终结符P必须都有用2023-8-19SEI522.4 形式语言鸟瞰v 乔姆斯基（Chomsky）给出了文法的定义：G（VN,
17、VT,P,S）（VN VT=，VN VT=V）v 对产生式的形式给以不同的限制可定义四类基本文法，分别称为0型文法，1型文法，2型文法，3型文法。2023-8-19SEI532.4 形式语言鸟瞰v四类文法描述语法的能力从0型文法开始依次减弱k型语言类Lk必然是k-1型语言类Lk-1的子类(其中,k=1,2,3)存在这样的k型语言，它不能由任何k+1型文法来描述(其中，k=0,1,2)编译原理编译原理本章小结本章小结55p 经常不断地学习,你就什么都知道。你知道得越多,你就越有力量p Study Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will Be写在最后Thank You在别人的演说中思考，在自己的故事里成长Thinking In Other PeopleS Speeches，Growing Up In Your Own Story讲师：XXXXXX XX年XX月XX日
