-程序语言的语法描述课件

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