编译原理 文法和语言

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

1、第三章文法和语言语言是一个记号系统，完整的定义包括语法和语义两方面。语法是一组规则，用它可以形成和产生一个合适的程序。文法就是阐明语法的一个重要的形式工具。语义包括静态语义和动态语义，阐明语义要比语法困难的多。本章主要讨论文法和语言的概念，上下文无关文法及其句型的分析。1本章内容3.1文法的直观概念3.2符号和符号串3.3文法和语言的形式定义3.4文法的类型3.5上下文无关文法及其语法树3.6句型的分析3.7有关文法实用中的一些说明3.8典型例题及解答23.1文法的直观概念如何来描述一种语言？如果语言是有穷的(只含有有穷多个句子)，可以将句子逐一列出来表示；如果语言是无穷的，

2、语言的有穷表示有两个途经:生成方式(文法):语言中的每个句子可以用严格定义的规则来构造。识别方式(自动机):用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。参见课本句子组成的实例。33.2符号和符号串1、字母表字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如:1.计算机语言：由符号“0”和“1”组成的字母表,∑={0，1}2.ASCII字符集；3.Pascal字母表为：∑={AZ,az,09,+,-,*,/,<,=,>,:,',',;，.，,(,),{,},[,]}4

3、3.2符号和符号串2、符号串一.符号串的定义(1)ε是∑上的一个符号串。(2)若x是∑上的符号串，而a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作"字"。53.2符号和符号串二术语设s是符号串前缀:移走s的尾部的零个或多于零个符号后缀:删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）逆转:将s中的符号按相反次序写出而得到的符号串。长度:是该符号串中的符号的数目。例

4、aab

5、=3,

6、

7、ε

8、=0。6例：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a,子串:banana,anana,banan,anan,…,真前缀，真后缀，真子串:x≠sx≠子序列:baa(这些符号不要求是连续的）逆转：ananab长度：banana=63.2符号和符号串7三、符号串的运算1.连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.方幂：x0=;x1=x;x2=xx;…;xn=xn-1x;例

9、:x=ba则x1=ba;x2=baba;x3=bababa;…3.2符号和符号串8四.符号串集合(语言）的运算设L和M是两个符号串集合，则1.合并：L∪M＝｛s

10、sLorsM}2.连接：LM＝｛st

11、sLandtM}3.方幂：L0={ε}，L1＝L，L2＝LL,...,Ln＝Ln-1L4.语言L的闭包，记作L*，L*＝∪Li(i>=0)=L0∪L1∪L2∪L3∪…5．语言L的正闭包，记作L+（L+＝LL*）L+＝∪Li(i>=1)=L1∪L2∪L3∪L4∪…3.2符号和符号串9例如：L={A~Z,a~z}D={0~9}1．L∪D={A~Z,a~z,0~9}2．LD是由

12、所有用一个字母后跟一个数字组成的符号串所构成的集合。3．L4是由所有的四个字母的符号串构的集合。4．L（L∪D)*是由所有的字母打头的字母和数字组成的符号串所构成的集合.5．D+是由所有的长度大于等于1的数字串所构成的集合.3.2符号和符号串10文法的定义推导的概念句型、句子和语言的定义3.3文法和语言的形式定义11文法定义文法G定义为四元组(VN，VT，P，S)，其中VN:非终结符号集；VT:终结符号集；P:规则的集合；并且VN，VT和P是非空有穷集。S:称作开始符(识别符)，是一个非终结符，它至少要在一条产生式中作为左部出现。注：VN和VT不含公共的元素，即VN∩VT=φ

13、，用V表示VN∪VT，称为文法G的字母表规则(重写规则、产生式或生成式)，是形如→的(,)有序对,其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。12文法的定义例:文法G=（VN，VT，P，S）VN={S},VT={0,1}P={S→0S1,S→01}S为开始符号13例:文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→