《编译原理cha》PPT课件

《《编译原理cha》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章学习本章的目的2.1文法的直观概念2.2符号和符号串2.3文法和语言的形式定义2.4文法的类型2.5上下文无关文法及其语法树2.6句型的分析2.7有关文法实用中的一些说明文法和语言1一个程序设计语言是一个记号系统，包括语法和语义两方面。语法是一组规则，用它可以形成和产生一个合适的程序，它只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系，这些与符号含义有关的用语法分析无法解决的问题属于语义分析的工作。语义分为两种：静态语义和动态语义。静态语义是一系列限定规则，并确定哪些合乎语法的程

2、序是合适的；动态语义表明程序要做什么，要计算什么。阐明语法的一个工具是文法，是形式语言理论的基本概念之一2学习本章的目的构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述（常用的有语法描述图或扩充的巴科斯-瑙尔范式（即EBNF）），根据这种描述，构造出相应的分析加工程序。语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那么好用，但它推动语言理论的发展。3文法的直观概念有无穷句子的语言，无法列出全部句子，可以给出一些规则，用这些规则来说明（或者定义

3、）句子的组成结构，这些规则成为判别句子结构合法与否的依据，可以看成是一种元语言，用来描述语言，仅仅涉及语言句子的结构描述，这样的语言描述称为文法。（例）有了规则，可以用它们去推导或产生句子（例）文法作为工具，严格地定义了句子的结构，也能够用适当条数的规则把语言的全部句子描述出来，是以有穷集合刻划无穷集合的工具。含有无穷句子的语言如何给出它的有穷表示？4字母表符号串一.符号串的定义二.术语三.符号串的运算四.符号串集合的运算符号和符号串5程序设计语言是一切程序所组成的集合，程序是由类似if,be

4、gin,end的符号、字母和数字这样一些基本符号所组成，每个程序都是一个“基本符号”串。设有一基本符号集，那么程序设计语言可看成是在这个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。不同的程序设计语言可以有不同的符号集。6字母表是元素（符号）的非空有穷集合。任何程序语言都有自己的字母表，例如:1.计算机语言：由符号“0”和“1”组成的字母表,∑={0，1}2.ASCII字符集；3.Pascal字母表为：∑={AZ,az,09,+,-,*,/,<,=,>,:,‘,’,;，.，

5、,(,),{,},[,]，各种保留字}字母表（符号集）7一.符号串的定义(1)ε（空符号串）是∑上的一个符号串。(2)若x是∑上的符号串，而a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作"字"。符号串符号串中，符号是有顺序的8设s是符号串头：移走s的尾部的零个或多于零个符号尾：删去s的头部的零个或多于零个符号子串:从s中删去一个头和一个尾固有头（或固有尾）：若x是s的头（或尾）

6、，且x≠s。真子串：x是s的子串，且x≠sx≠长度：是该符号串中的符号的数目。例如

7、aab

8、=3,

9、ε

10、=0。二术语9：符号串s=banana头：,b,ba,ban,bana,banan,banana尾：banana,anana,nana,ana,na,a,子串:banana,anana,banan,anan,…,固有头：,b,ba,ban,bana,banan固有尾：anana,nana,ana,na,a,真子串:anana,banan,anan，ba,ban长度：banan

11、a=6例10当我们对符号串z=xy头感兴趣而对其余部分不感兴趣时，可以采用省略写法：z=x…;如果只是为了强调x在符号串z中的某处出现，则可表示为：z=…x…;符号t是符号串z的第一个符号，则表示为：z=t…约定111.连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.方幂：设x是符号串，把x自身连接n次得到的符号串。x0=;x1=x;x2=xx;……;xn=xn-1x;例如,x=ba,x1=ba,x2=ba

12、ba,x3=bababa,…...三.符号串的运算12符号串集合：若集合L中的一切元素都是某字母表上的符号串，则称L为该字母表上的符号串集合。设L和M是两个符号串集合，则1.合并：L∪M＝｛s

13、sLorsM}2.连接（乘积）：LM＝｛st

14、sLandtM}3.方幂：L0={ε}，L1＝L，L2＝LL,...,Ln＝Ln-1L四.符号串集合(语言）的运算13四.符号串集合(语言）的运算（续）4.语言L的Kleene闭包，记作L*，L*＝∪Li(i>=0)=L0∪L1∪L2∪L3∪…这里，L