第2章形式语言

《第2章形式语言》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《编译原理简明教程》21世纪高等学校计算机学科系列教材第一章引言第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章符号表第十章代码优化目录第二章形式语言理论基础学习目标学习形式语言理论中的一些基本概念和基础知识掌握程序设计语言的语法描述方法需要着重掌握的内容为字母表产生式、上下文无关文法推导、句型、句子、语言语法树二义性Chomsky文法分类语法：程序的结构形式语义：语言所代表的含义语用：语言的实际应用例如：x:=a*b+c语法：变量:=表达式v:=e语义：对e求值，再赋给变量

2、语用：计算和保存e的值以上非形式化的描述不够清晰明确。程序设计语言探讨形式化方法:用一套带有严格规定的符号体系来描述问题的理论和方法。形式语言：是一种不考虑含义的符号语言（只谈语法不谈语义）。形式语言理论：主要研究组成这组符号串的集合，它们的表示法、结构及特性，只能用于程序语言的语法描述和语法分析。1956年著名语言学家NoamChomsky首先描述形式语言，已成为计算机科学的一个重要组成部分，是编译理论重要基础。2.1形式语言的基本概念2.2文法和形式语言的定义2.3语法树和二义性2.4文法的实用限制2.5文法和语言的Chomsky分类目录2.1形式语言的基本概念2.1.1符号和

3、符号串形式语言和编译技术中两个主要概念任何一种语言都是由该语言的基本符号组成的基本符号串集合。英文：26个字母、数字、标点符号等PASCAL：字母、数字、关键字、专用符号等中文：汉字、数字、标点符号等1.字母表：是一个非空的有限集合。用Σ表示。例Σ={a，b，c}（a,b,c均为字符或符号,是字母表中的元素）2.符号串：符号的有序序列。用小写希腊字母表示如：ω，φ，λa，b，ab，abc等。ε表示空字符串，不包含任何符号的符号串。ε≠空格另外ab≠ba3.符号串集合：字母表上若干符号串的组成集合。用大写字母表示。例：A={a，ab，bc}4.语言（形式语言）：字母表上所有符号串组成

4、的集合的子集,用L表示。LΣ*，L可抽象地看成所有句子的集合。句子又可抽象看成是某个有限字母表Σ的符号串。字母表上的符号串不可能都是句子。例：Σ={a}，L={a2k

5、k≥0}Σ={0，1}，L1={(01)n

6、n≥0}={ε，01，0101，……}L2={0n1n

7、n≥0}={ε，01，0011,……}ф空集或者空语言，不含任何符号串的语言。ф≠{ε}2.1.2符号串的运算1.符号串相等：同一字母表的两个符号串所有符号依次相等。如Σ={a，b，c}ω=abc，ψ=abc，则ω=φ；若ω=abc，ψ=cba，则ω≠φ2.字符串长度：符号串中包含的字符的个数。记

8、ω

9、例

10、abc

11、=3

12、，

13、ε

14、=0,

15、aω

16、=

17、ωa

18、=1+

19、ω

20、，a∈Σ。3.符号串的连接:把符号串ψ的所有符号相继写在ω之后，记ωψ或ω·ψω=ab，ψ=bc，则ωψ=abbc4.符号串的逆：符号串ω的倒置，记ω-1如ω=abc则ω-1=cbaε-1=ε（ω-1）-1=ω（ωψ）-1=ψ-1ω-15.符号串的前缀、后缀和子串设ω，ψ，φ是字母表Σ上的字符串，则ω为符号ωψ的前缀，ψ为字符串ωψ的后缀，ψ是字符串ωψφ的子串。前缀和后缀都是子串，但子串不一定是前缀或者后缀。前缀：ε，a，ab，abc后缀：ε，bc，c，abc子串：ε，a，b，c，ab，bc，abc例：abc6.符号串集合的乘积A·B=

21、{ωψ

22、ω∈A，ψ∈B}例：A={ab,ba}B={bc,b}则AB={abbc,abb,babc,bab}特别：{ε}A=A{ε}=A7.符号串的幂（一个符号串与它自己的n次连接）ω0=εω1=ωω2=ωω……ωn=ωn-1ω例：ω=abω0=εω1=abω2=abab……ωn=abab……ab8．符号串集合的幂A0={ε}A1=AA2=AA……An=An-1A=AAn-1(n>0)例：A={ab,c}A0={ε}A1={ab,c}A2={abc,cab,abab,cc}……9.集合A的闭包和正闭包A*=A0∪A1∪……=正闭包A+=A1∪A2……=A*=A0∪A+A+=AA*=

23、A*AΣ字母表Σ*：Σ上所有符号串的集合Σ+：Σ上所有非空符号串的集合例：A={0，1}则A1={0，1}A0={ε}A2={00，01，10，11}……A*={ε，0，1，00，01，10，11，000，……}A+={0，1，00，01，10，11，000，……}2.2文法和语言的形式定义语言L：可抽象地看成是所有句子组成的集合（有限集：用枚举；无限集：文法）句子：可抽象地看成是某个有限字母表Σ上的符号串。例：英语Σ={26个字母，数字，标点符号，……}文法：在形式