编译原理课件.pptxVIP

2023/2/7华东师大计算机科学技术系1第二章 文法与语言的基本知识2.1 概述程序设计语言是一种形式语言，与自然语言既有相似的性质又有本质的不同。最主要的区别是：形式语言的规则简单、严格、无例外、无二义性。编译程序的正确转换建立在对程序设计语言的精确定义和描述基础上。语法——文法是描述语言语法的形式规则语义——语言中各语句的含义语用——从使用者的角度对语言的描述本章将介绍形式语言和形式文法的基本概念，这是整个编译原理的基础。 2023/2/7华东师大计算机科学技术系2基本概念2.2 基本概念2.2.1 符号与符号串用程序语言书写的程序一般由一些基本符号组成。下面是一些常见的基本符号： 字母：a,b,c,…,x,y,z 数字：0,1,…,9 其他符号：+,-,*,/ ,=,:，等 在这些符号的基础上，组成如if,then,else,for等关键字、程序的标识符和常量，并进一步组成用户程序。 定义1 符号的非空有限集合称为字母表。常用V、?表示。 2023/2/7华东师大计算机科学技术系3符号与符号串例1： ?1＝{0,1} ?1是二进制数的字母表 ?2＝{a,b…….z} ?2是英文小写字母 ?3＝{A….Z,0….9,+,-,*,/,.,(,),=,$,’,:} ?3是FORTRAN4语言的字母表注意：符号可能是字符的组合如： ?5＝ {ASCII码} 则=为一个符号再如： pascal语言的:＝ C语言的等等 2023/2/7华东师大计算机科学技术系4符号与符号串 定义2：字母表(符号的非空有限集合)V上的符号 串的递归定义如下： ① 空串（一个不含任何元素的符号串）是字母表 V上的符号串。空串用希腊字母?表示。 ② 字母表V中任何一个元素a，是字母表V上的符 号串。 ③ 若x，y是字母表V上的符号串，则它们的并置（将符号串y的符号依次写在符号串x后面所得的符号串）也是字母表V上的符号串，记以xy。 注意：‘?’与‘ ’的不同！ 2023/2/7华东师大计算机科学技术系52.2.2 符号串的运算符号串x中的元素的个数称为符号串x的长度，记以|x|。设z＝xy是字母表V上的符号串，则x是符号串z的头（或符号串z的前缀），而y是符号串z的尾（或符号串z的后缀）。若|x|＝1，则x是符号串z的头符号。同样，若|y|=1，则y是符号串z的尾符号。注意，空串?是任何一个符号串的头和尾。当y≠ ? 称x是z的真前缀。当x≠ ? 称y是z的真后缀。并置（连接）是一种运算，满足结合律，但不满足交换律。 2023/2/7华东师大计算机科学技术系6例2：字母表?1＝{0,1}?，0，1，00，11，10，01，……是?1上的符号串如x=1001 y=010 则连接xy=1001010 yx=0101001 都是?1上的符号串 |x|=4 |y|=3?，1，10，100，1001都是x的头，1是x的头符号 ?，1，01，001，1001都是x的尾，1是x的尾符号?，1，10，100，1001都是x的前缀， ?，1，10，100 是真前缀 1001，001，01，1， ?都是x的后缀， 001，01，1，? 是真后缀 2023/2/7华东师大计算机科学技术系7定义3：设A，B是二个符号串集合，定义：A∩B={a|a∈A且a∈B}A∪B={a|a∈A或者a∈B}A0＝{?} An=AAn-1 (n0)A*= A0∪ A1∪A2∪…∪An ∪…… 称为A的闭包A＋= A1∪A2∪…∪An ∪…… 称为A的正闭包 2023/2/7华东师大计算机科学技术系8由定义可知：A+=AA*=A*A例3：令A= ?1＝{0,1}A*={?，0，1，00，10，01，11…….}A+= {0，1，00，10，01，11…….}令A= ?3 则任一FORTRAN4语言所编写的程序P，有 P? A* 2023/2/7华东师大计算机科学技术系92.3 文法和语言2.3.1 文法形式语言是字母表V上所有符号串的集合，当该集合为有限集时可以枚举其全部句子，如为无限集则需找出句子的规律，用文法来表示。定义4：上下文无关文法G是一个四元组： G＝（VT，VN，P，S） 其中，VT是非空有限集合，元素称为终结符。 VN是非空有限集合，元素称为非终结符。 P是由产生式组成的非空有限集合。 S?VN，是文法G的开始符号。常把文法G记为G[S]。 2023/2/7华东师大计算机科学技术系10产生式（又称复写/产生规则）产生式是一有序对偶（U，x）， 一般记以 U→x （或 U