形式语言及自动机理论基础1

1、编译编译原理原理第二章第二章 程序语言程序语言22022-2-17第二章第二章 程序程序语言语言 v常用的高级程序常用的高级程序 FORTRANFORTRAN数值计算数值计算 COBOLCOBOL事务处理事务处理 PASCALPASCAL结构程序设计结构程序设计 ADAADA大型程序、嵌入式实时系统大型程序、嵌入式实时系统 PROLOGPROLOG逻辑程序设计逻辑程序设计 ALGOLALGOL算法语言算法语言 C/C+C/C+系统程序设计系统程序设计 JavaJavaInternetInternet程序设计程序设计32022-2-17v与机器语言或汇编语言比较与机器语言或汇编语言比较，高级语言

2、的高级语言的优点优点： 较接近于数学语言和工程语言较接近于数学语言和工程语言，比较直观、自比较直观、自然和易于理解然和易于理解; ; 便于验证其正确性便于验证其正确性，易于改错易于改错; ; 编写效率高编写效率高; ; 易于移植易于移植. .4n 自然语言自然语言（Natural LanguageNatural Language）是人类在社）是人类在社会生活中发展起来的，用于日常相互交流的符会生活中发展起来的，用于日常相互交流的符号系统。号系统。n 形式语言形式语言（Formal LanguageFormal Language）是为了特定）是为了特定应用而设计的人工语言，形式语言是用精确的应用

3、而设计的人工语言，形式语言是用精确的数学或机器可处理的公式定义的语言，公式由数学或机器可处理的公式定义的语言，公式由人们公认的数学和逻辑符号组成。人们公认的数学和逻辑符号组成。5n语法和语义语法和语义一个程序设计语言是一个一个程序设计语言是一个记号系统记号系统，它的完整，它的完整定义包括语法和语义两个方面。定义包括语法和语义两个方面。语法（语法（GrammarGrammar）是一组规则，用它可以产生是一组规则，用它可以产生一个与其所包含的符号含义无关的合法程序一个与其所包含的符号含义无关的合法程序, ,语法是语言的形式。语法是语言的形式。语义语义(Semantic )(Semantic )是语

4、言的内容，是语言的内容，以语法为媒以语法为媒介来说明语义是语言的实质介来说明语义是语言的实质。62022-2-17v词法规则词法规则：单词符号的形成规则：单词符号的形成规则。 单词符号是语言中具有独立意义的最基本结构单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符一般包括：常数、标识符、基本字、算符、界符等。等。 描述工具：有限自动机描述工具：有限自动机v语法规则语法规则：语法单位的形成规则：语法单位的形成规则。 语法单位通常包括：表达式、语句、分程序、过语法单位通常包括：表达式、语句、分程序、过程、函数、程序等程、函数、程序等; ; 描述工具：上下文无关文

5、法描述工具：上下文无关文法72022-2-17三程序语言的基本功能和层次结构三程序语言的基本功能和层次结构v程序语言的基本功能：程序语言的基本功能：描述数据和对数据的运算描述数据和对数据的运算。v所谓程序，本质上说是所谓程序，本质上说是描述一定数据的处理过程描述一定数据的处理过程。82022-2-17程序的层次结构：程序的层次结构：程序程序| |子程序或分程序、过程、函数子程序或分程序、过程、函数| |语句语句| |表达式表达式|数据引用数据引用 算符算符 函数调用函数调用92022-2-172.1 2.1 高级语言的一般特性高级语言的一般特性 2.1.1 2.1.1 高级语言的分类高级语言的

6、分类 强制式语言强制式语言(Imperative Languge)(Imperative Languge)也称过程式语也称过程式语言：命令驱动，面向语句言：命令驱动，面向语句 FORTRANFORTRAN、C C、PascalPascal，Ada Ada 应用式语言应用式语言（Applicative LanguageApplicative Language）：注重程）：注重程序所表示的功能，而不是一个语句接一个语句地序所表示的功能，而不是一个语句接一个语句地执行执行 LISPLISP、ML ML 102022-2-17 基于规则的语言基于规则的语言（Rule-based LanguageRul

7、e-based Language）：检查）：检查一定的条件，当它满足值，则执行适当的动作一定的条件，当它满足值，则执行适当的动作 Prolog Prolog 面向对象语言面向对象语言（Object-Oriented LanguageObject-Oriented Language）：）：封装性封装性、继承性继承性和和多态性多态性 SmalltalkSmalltalk，C+C+，Java Java 112022-2-17程序结构程序结构v FORTRANFORTRAN 一个程序由一个主程序段和若干辅程序段组成。一个程序由一个主程序段和若干辅程序段组成。 辅程序段可以是子程序、函数段或数据块。辅程

8、序段可以是子程序、函数段或数据块。 每个程序段有一系列的说明语句和执行语句组成。每个程序段有一系列的说明语句和执行语句组成。各段可以独立编译。各段可以独立编译。 模块结构，没有嵌套和递归模块结构，没有嵌套和递归 各程序段中的名字相互独立各程序段中的名字相互独立，同一个标识符在不，同一个标识符在不同的程序段中代表不同的名字同的程序段中代表不同的名字。122022-2-17主程序主程序 PROGRAM PROGRAM end end辅程序辅程序1 1 SUBROUTINE SUBROUTINE end end辅程序辅程序2 2 FUNCTION FUNCTION end end132022-2-1

9、7vJAVA Java是一种面向对象的高级语言是一种面向对象的高级语言 类（类（Class） 继承继承(Inheritance) 多态性多态性(Polymorphism)和动态绑定和动态绑定(Dynamic binding)142022-2-17class Car int color_number; int door_number; int speed; push_break ( ) add_oil ( ) class Trash_Car extends car double amount; fill_trash ( ) 2.22.2节节 中间语言中间语言v后延至后延至第八章语法制导翻译第八章

10、语法制导翻译第三章第三章 语言分析基础语言分析基础17 基本基本概念概念1.1.字母表字母表（alphabet )alphabet )v 字母表是元素的字母表是元素的非空有穷非空有穷集合集合, ,字母表中的一个字母表中的一个元素称为该字母表的一个元素称为该字母表的一个字母字母（letterletter）, ,也可叫也可叫做做符号符号（symbolsymbol）或者）或者字符字符(character)(character)。v注意：字母表具有非空性和有穷性。注意：字母表具有非空性和有穷性。v字母表有时也称为符号表字母表有时也称为符号表, ,通常用通常用表示。表示。 182.2.符号串符号串v由字

11、母表中的符号组成的由字母表中的符号组成的任何有穷序列任何有穷序列称为字母表称为字母表上的符号串。符号串还可以称为上的符号串。符号串还可以称为“字符串字符串”、“字字”或或“句子句子”，一般用，一般用 ， ，.，x x，y y，z z，表示。表示。v表示表示空串。空串。对任一字母表对任一字母表，都，都有有 是是上的符号上的符号串。串。v空串集空串集 不同于空集不同于空集 。 = a = a，b b， c c，dd193 3. .符号串连接符号串连接l 设设 和和 均是字母表均是字母表上的符号串，上的符号串， 和和 的连接是的连接是把把 的所有符号顺次地接在的所有符号顺次地接在 的所有符号之后所得

12、到的的所有符号之后所得到的符号串。记为符号串。记为: : 。例如例如: : 设设 = abc , = abc , = de , = de ,则则 和和 的连接的连接: : = abcde = abcdel由于由于 是不包含任何符号的字符串，是不包含任何符号的字符串，特别有：特别有： = = = = l 连接运算不满足交换律。连接运算不满足交换律。 204 4. .符号串的方幂符号串的方幂 设设x x是字母表是字母表上的符号串，把上的符号串，把x x自身连接自身连接n n次得次得到的符号串到的符号串z, z, 即即z = xxxx (nz = xxxx (n个个x),x),称作符号串称作符号串x

13、 x的的n n次幂，记作次幂，记作 z = xz = xn n 。根据定义有：。根据定义有： x x0 0 = = x x1 1 = x = x x x2 2 = xx = xxx xn n = x = xn-1n-1x = xxx = xxn-1n-1 = xxxx (n = xxxx (n个个x)x)例例 设设x = 001x = 001，则有，则有: x: x0 0 = = x x1 1 = 001 = 001 x x2 2 = 001001 = 001001 x x3 3 = 001001001 = 001001001 215 5. .符号串集的乘积符号串集的乘积 设设A A、B B

14、是两个符号串集合，是两个符号串集合，ABAB表示表示A A与与B B的乘的乘积，具体定义为：积，具体定义为： AB = xy | ( xA ) ( yB ) , AB = xy | ( xA ) ( yB ) , 运算结果仍然表示符号串的集合。运算结果仍然表示符号串的集合。 例例2.3 2.3 设设 A = a, bc A = a, bc ， B = de, f ,B = de, f ,则：则： AB = ade, af, bcde, bcf AB = ade, af, bcde, bcf 特别有：特别有：1 1、A = AA = A = = ，其中其中表示空集。表示空集。 2 2、 A =

15、AA = A = = A A226 6. .符号串集合的方幂符号串集合的方幂 设设A A为符号串的集合，则称为符号串的集合，则称i i为符号串集的方幂。具体定义如下：为符号串集的方幂。具体定义如下： 1 1 A A2 2 AAAA n n n-1n-1A A AAAA (n AAAA (n个）个）例：例： a,b a,b 则：则：0 0 1 1 a,b a,b 2 2 AA AA aa,ab,ba,bb aa,ab,ba,bb 3 3 A A2 2A A aaa,aab,abaaaa,aab,aba, ,abbabb, ,baa,bab,bba,bbb baa,bab,bba,bbb n n

16、n-1n-1A A AAAA AAAA237 7. .符号串集合的正闭包符号串集合的正闭包 设设A A为符号串的集合，则称为符号串的集合，则称为符号串集的正为符号串集的正闭包具体定义如下：闭包具体定义如下： 1 1 A A2 2 A A3 3 248 8. .符号串集合的星符号串集合的星闭包（闭包（自反闭包自反闭包） 设设A A为符号串的集合，则称为符号串的集合，则称为符号串集的为符号串集的星闭包具体定义如下：星闭包具体定义如下： A A0 0 1 1 A A2 2 A A3 3 注意注意: : A A 请证明请证明25例例: :设设A = ab, cdA = ab, cd，则，则 : : A

17、 A+ + = ab, cd, = ab, cd, abab, abcd, cdab, cdcdabab, abcd, cdab, cdcd, , ababab, ababcd, ababab, ababcd, A A* * = = , ab, cd, abab, abcd, cdab, cdcd, , ab, cd, abab, abcd, cdab, cdcd, ababab, ababcd, ababab, ababcd, 程序题程序题字母表字母表为为 aa，bb1.1. 长度小于长度小于5 5的字符串的个数的字符串的个数2.2. 请列出所有字符串请列出所有字符串提示：递归方法提示：递归

18、方法具体要求见赛课内容。具体要求见赛课内容。提问提问v设设A = ab, cdA = ab, cd1.1. A A0 0 2.2. 2 23.3. 4.4. A A+ + 本节重点本节重点v文法文法v语言语言v句型、句子句型、句子v相关概念相关概念v文法与语言文法与语言2. 2. 文法和语言的形式定义文法和语言的形式定义一一、文法的定义、文法的定义文法：文法：描述语言的语法结构的形式规则（即语法规则）。描述语言的语法结构的形式规则（即语法规则）。描述语法规则描述语法规则例：例：英语中，一般句子是由英语中，一般句子是由主主谓宾谓宾三三部分部分构成。构成。302022-2-17vHe gave m

19、e a book.He gave me a book.v、产生句子的规则、产生句子的规则从产生语言的角度从产生语言的角度 He He me me book book a a gave gave2. 2. 文法和语言的形式定义文法和语言的形式定义312022-2-17 He me book a gave He He He gave He gave He gave me He gave me He gave me a He gave me a bookB B、句子的派生（推导）句子的派生（推导）根据规则根据规则322022-2-172. 2. 文法和语言的形式定义文法和语言的形式定义用图表示：用图

20、表示：He gave me a book.He gave me a book.2. 2. 文法和语言的形式定义文法和语言的形式定义C C、句子的语义要求句子的语义要求 he gave me a book. he gave he a book. me gave me a book. me gave he a book.符合语法且符合语义的句子仅是：符合语法且符合语义的句子仅是： He gave me a book. He He产生式产生式A A-(A)(A)A A-a a等价于等价于 A-(A)|aA-(A)|a产生式形式简单，内容丰富产生式形式简单，内容丰富定义表达式、句子等定义表达式、句子等

21、a, (a), (a), (a)a, (a), (a), (a)都是有意义的都是有意义的文法文法 A-(A)|aA-(A)|a嵌套性质嵌套性质三类符号三类符号1. 1. 元符号元符号 - |- |2. 2. 非终结符非终结符 可以被替换，至少出现在左边可以被替换，至少出现在左边一次一次3. 3. 终结符终结符 不可被替换，不能单独出现在不可被替换，不能单独出现在产生式的左侧产生式的左侧概念：概念：产生式产生式 -|1. 1. ， ， 符号串符号串2. 2. 为产生式的左部为产生式的左部3. 3. |为产生式的右部为产生式的右部4. 4. ， 为候选式为候选式文法一般由多个产生式组成文法一般由多

22、个产生式组成372022-2-17 He me book a gave如何准确定义一个文法如何准确定义一个文法产生式类型产生式类型1. 1. 基本式基本式 A- A- ， 为终结符串，该语法为终结符串，该语法所定义的语言，只有一个字符串所定义的语言，只有一个字符串2. 2. A- BA- B， ， 为终结符，为终结符，B B为非终结符为非终结符3. 3. 递归式，递归式， A-A | A-A | 或者或者 A-A| A-A| 4. 4. 成对符号递归，成对符号递归， A- A| A- A| 2. 2. 文法和语言的形式定义文法和语言的形式定义3 3、文法、文法的形式定义的形式定义是一个四元组（

23、是一个四元组（，），）终结符号集，非空有限集终结符号集，非空有限集非终结符号集，非空有限集非终结符号集，非空有限集 终结符号：终结符号：描述单词符号描述单词符号, ,组成语言的基本符号，是一个组成语言的基本符号，是一个 语言的不可再分的基本符号。语言的不可再分的基本符号。例如：基本字，标识符，常数，算符，界符等例如：基本字，标识符，常数，算符，界符等非终结符：非终结符：代表语法范畴，一个非终结符代表一个一定的语代表语法范畴，一个非终结符代表一个一定的语 法概念，每个非终结符表示一定符号串的集合。法概念，每个非终结符表示一定符号串的集合。例如：算术表达式，布尔表达式，赋值句，分程序，过程等例如：

24、算术表达式，布尔表达式，赋值句，分程序，过程等2. 2. 文法和语言的形式定义文法和语言的形式定义开始符号，一个特殊的非终结符号开始符号，一个特殊的非终结符号产生式集合，有限集产生式集合，有限集产生式：定义语法范畴的一种书写规则产生式：定义语法范畴的一种书写规则形式：形式：A AVN, (VTVN)*注：注： “”: “定义为定义为”“”： “或或” 非终结符号非终结符号:用大写字母、用大写字母、或汉语组代表或汉语组代表 终结符终结符:用小写字母用小写字母代表代表至少必须在某个产生至少必须在某个产生式的左部出现一次式的左部出现一次412022-2-17非终结符非终结符终结符终结符2. 2. 文

25、法和语言的形式定义文法和语言的形式定义分析分析：He gave me a book.He gave me a book.2. 2. 文法和语言的形式定义文法和语言的形式定义终结符号集终结符号集 VT=He, gave, me, a, book非终结符号集非终结符号集 VN=, , ,语法规则集语法规则集 P= ,开始符号开始符号 S=分析句子：分析句子：He gave me a book. .2. 2. 文法和语言的形式定义文法和语言的形式定义例例1 1：文法文法：E Ei | EAEi | EAE A A+|+|* *非终结符号：非终结符号：开始符号：开始符号：终结符号：终结符号：E，AE+

26、，*，iGE 或者或者 G(E)Identifier 标示符标示符Expression 表达式表达式语言，满足一些格式要求的符号串的集合语言，满足一些格式要求的符号串的集合格式格式 文法文法2. 2. 文法和语言的形式定义文法和语言的形式定义例例2：算术表达式的文法：算术表达式的文法标识符标识符(id)(常量、变量常量、变量)是表达式是表达式(E)；表达式加一个表达式是表达式；表达式加一个表达式是表达式； 表达式减一个表达式是表达式；表达式减一个表达式是表达式； 表达式乘一个表达式是表达式；表达式乘一个表达式是表达式；表达式除一个表达式是表达式；表达式除一个表达式是表达式；表达式加上括号是表达

27、式；表达式加上括号是表达式； Eid EE+E EE-E EE*E EE/E E(E)P: Eid|E+E|E-E|E*E|E/E|(E)Identifier 标示符标示符2. 2. 文法和语言的形式定义文法和语言的形式定义、文法与语言的关系、文法与语言的关系中心思想：从文法的开始符号出发，反复连续使用产中心思想：从文法的开始符号出发，反复连续使用产 生式，对非终结符施行替换和展开生式，对非终结符施行替换和展开。一一个文法个文法如何定义一个语言呢？如何定义一个语言呢？给定一个句子，如何判断其是否符合所给定的文法？给定一个句子，如何判断其是否符合所给定的文法？2. 2. 文法和语言的形式定义（提

28、问）文法和语言的形式定义（提问）( () ) ( (+ +) ) ( (+ +) ) ( (+ +) )例：例：Eid | E+E | E-E | E*E | E/E | (E) (i+i)注：注：我们可以从出发，进行一系列的推导，推出种种不我们可以从出发，进行一系列的推导，推出种种不 同的算术表达式出来同的算术表达式出来该推导过程证明了（该推导过程证明了（+ +）是文法所定义的一个算术）是文法所定义的一个算术表达式。表达式。你能推出哪些表达式？你能推出哪些表达式？2. 2. 文法和语言的形式定义文法和语言的形式定义“”：若若 ，则称该序列是从，则称该序列是从至至的一个推导（的一个推导（可推导

29、出可推导出） ： ：+*表示表示“直接推出直接推出”，即仅推出一步。，即仅推出一步。AA ,仅当仅当 是一个产生式，是一个产生式，且且,(,() )* * “推导推导”：从从出发，经过出发，经过步步或或若干步若干步，可推导出，可推导出从从出发，经出发，经一步一步或或若干步若干步，可推导出，可推导出注：符号的含义注：符号的含义文法所产生的句子的全体是一个语言，文法所产生的句子的全体是一个语言，记为（）记为（）*2. 2. 文法和语言的形式定义文法和语言的形式定义+5 5、语言、语言与自然语言相联系与自然语言相联系设是一个文法，是其开始符号，设是一个文法，是其开始符号，, (VN)*,则则称为文法

30、称为文法G的一个的一个句型句型仅含终结符号的句型是一个句子仅含终结符号的句型是一个句子“句子句子”：“语言语言”：“句型句型”：*492022-2-17 He me book a gave He He He gave He gave He gave me He gave me He gave me a He gave me a book句型与句子句型与句子2. 2. 文法和语言的形式定义文法和语言的形式定义6 6、最左右推导、最左右推导定义：任何一步定义：任何一步 都是对都是对 中的最左最右中的最左最右非终结符非终结符进行进行替换的。替换的。+ + +（）（） （+） （* *+ +） （*

31、*+ +）（+ +）（）+ +（）（） （+ +） （）（） （）（） （）（） （）（）最左推导：最左推导：最右推导最右推导：Ei | E+E | E-E | E*E | E/E | (E)练习：练习：GS:GS: S Sa|a|(T)|(T) T TT,S|ST,S|S分别给出下列句子的最左和最右推导过程：分别给出下列句子的最左和最右推导过程： （1 1）（）（a,(a,a) a,(a,a) （2 2）(a,(a,)(a,(a,)（1 1）最左推导：）最左推导：S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S) S=(T)=(T,S)=(S,S)=(a,S)=(

32、a,(T)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)=(a,(S,S)=(a,(a,S)=(a,(a,a)（2 2）最左推导：）最左推导：S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S) S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,)=(a,(S,S)=(a,(a,S)=(a,(a,)2. 2. 文法和语言的形式定义文法和语言的形式定义7 7、例题、例题例、考虑一个文法例、考虑一个文法：定义了一个什么样的语言？定义了一个什么样的语言？. （）（）

33、？2. 2. 文法和语言的形式定义文法和语言的形式定义例、考虑文法例、考虑文法：定义了一个什么样的语言？定义了一个什么样的语言？分析：分析：与类似与类似由由可知，其必产生可知，其必产生，且以，且以此终结此终结 ？（）（），提问提问G: E-E+E|EG: E-E+E|E* *E|(E)|iE|(E)|i1. 1. 上式什么含义上式什么含义2. 2. 终结符终结符集集V VT T3. 3. 非终结符非终结符集集V VN N4. 4. 开始符号开始符号S S5. 5. 请列举其中三个请列举其中三个句型句型6. 6. 请列举其中三个请列举其中三个句子句子7. 7. 形成的形成的语言语言是什么是什么8

34、. 8. 最左推导（）最左推导（）9. 9. 最右推导（）最右推导（）2. 2. 文法和语言的形式定义文法和语言的形式定义例：构造例：构造一个文法一个文法， 使使（ ）分析：分析：与与的区别在于，的区别在于，必须使、出现必须使、出现的的次数次数相等相等，故而、必须，故而、必须同时出现。同时出现。GG：2. 2. 文法和语言的形式定义文法和语言的形式定义二、二、语法分析树语法分析树、语法树（推导树、生成树或分析树）语法树（推导树、生成树或分析树）用用树的形式表示一个句型的推导生成树的形式表示一个句型的推导生成，有助于理解，有助于理解一个句子语法结构的层次一个句子语法结构的层次。树根：开始符号树根

35、：开始符号中间结点：非终结符中间结点：非终结符叶结点：终结符叶结点：终结符非终结符非终结符一个非叶节点一个非叶节点A A按从左到右顺序有按从左到右顺序有n n个儿子节点个儿子节点B B1 1、B B2 2、B Bn n，则，则: A: AB B1 1B B2 2BBn n 一定是一定是G G的一个产生式。的一个产生式。572022-2-172. 2. 文法和语言的形式定义文法和语言的形式定义二、二、语法分析树语法分析树产生式：产生式： 句型句型句子句子2. 2. 文法和语言的形式定义文法和语言的形式定义例例：（）的最左推导和最右推导）的最左推导和最右推导（根）（根） （ E E ）+ +* *

36、 E Ei i | | E+E E+E | | E-E E-E | | E E* *E E | | E/E | (E/E | (E)E)E E (E)(E)( (E+EE+E) )( (E E* *E+EE+E) )(i (i* *E+EE+E) )(i (i* *i+Ei+E) )(i (i* *i+ii+i) )E E (E)(E)( (E+EE+E) )( (E+iE+i) )(E(E* *E+iE+i) )(E(E* *i+ii+i) )(i (i* *i+ii+i) ) 一棵语法树是不同推导过程的共性抽象。一棵语法树是不同推导过程的共性抽象。592022-2-17v如果使用最左如果使

37、用最左( (右右) )推导，则一个最左推导，则一个最左( (右右) )推导与推导与语法树一一对应。语法树一一对应。v一个句型是否只对应唯一一棵语法树？一个句型是否只对应唯一一棵语法树？Ei+*()EiiEEEEE+*()EiEEiiEE2. 2. 文法和语言的形式定义文法和语言的形式定义2. 2. 文法和语言的形式定义文法和语言的形式定义2 2、二义文法、二义文法若若一个文法中存在某个句子，它有两个不同的一个文法中存在某个句子，它有两个不同的最左右推导，则该文法为二义文法最左右推导，则该文法为二义文法例：上述文法例：上述文法* *（）（）2. 2. 文法和语言的形式定义文法和语言的形式定义注意：注意：、区分：文法的二义性、区分：文法的二义性语言的二义性语言的二义性二义文法二义文法无二义文法无二义文法但（）（但（）（）例如：例如：+*（）（）：+*（）（）（）（）（）语言语言的二义性：一个的二义性：一个语言是二义性的语言是二义性的，如果对它，如果对它不存在无二义性的不存在无二义性的文法文法。表达式表达式 项项|表达式表达式+项项项项 因子因子 | 项项*因