编译原理 chapter3.ppt

1、第一，第三章语法和语言，本章的目的是为了语言的语法记述寻求工具，给与软件编程语言正确无意义的语法记述。 (严密、简洁、易读)形式工具：形式语言抽象地定义为数学系统，用数学符号和规则记述语言。 (“形式”是指语言的所有规则仅仅出现怎样的符号串而叙述的事实。 2、本章内容为语言符号、符号串语法和语言形式定义语法的类型上下文相关语法及其语法树句上下文相关语法的句型分析在语法实用上的一些说明，3、3.1语言相关语言是句子组成的集合，是一组符号组成的集合。 中文-所有符合汉语语法的句子整体英语-所有符合英语语法的句子整体软件编程语言-所有该语言的计划整体，4，如何描述一种语言？ 如果语言贫穷(只包含多个

2、贫穷的句子)，可以一个一个列出句子来显示。 如果语言无限，找到语言的贫乏表现。 语言的贫乏表现有两个路径：展成法(语法):语言中的各句可以用严格定义的规则来建构。 识别方式(自动机):在一个过程中，输入的任意字符串属于语言时，该过程有限次修正后停止并回答“是”，不属于时回答“否”或永远继续。 3.1关于语言，5、语法用展成法描述语言：用有限的规则描述无限的语言。 语言的所有句子都可以从规则中导出，也就是说，一个句子是否合法，就要看它能否从规则中建构。 关于符号和符号串语法定义导出的概念句型、句子和语言定义、3.1语言、6、形式语言和自动机理论的生成，语言学家Chomsky首先从语言生成的角度对

3、语言进行了研究。 1956年，抽象地说，他把语言形式定义为由字母组成的字符串集合。 字母表上可以根据一定的规则定义语法(Grammar )，该语法生成的所有句子的集合就是该语法生成的语言。 清洁(Kleene )在1951年到1956年期间，从语言认识的观点研究语言，提出了语言的别的记述。 克林在研究神经元细胞的过程中，对于按照一定规则建构的任何一个自动机，制作了定义由该自动机能认识的所有句子组成的语言的自动机。 7、形式语言和自动机理论的产生，1959年，Chomsky经过深入研究，将他自身的研究成果和克林的研究成果结合起来，不仅确定了语法和自动机分别从生成和认识的角度来表达语言，还证明了语

4、法和自动机的等价性。 在20世纪50年代，人们成功地使用Backus Nour Form或者Backus Normal Form，缩写为BNF )记述了高级语言ALGOL-60。 实际上，巴科斯范式是上下文无关语法(Context Free Grammar )的表现形式。 由于这项成功，形式语言在六零年代有了很大的发展。8、3.2符号和符号串、符号：相互能区分的符号(要素)。 字母：一个非空的非穷集合，也称为符号集合。 不同语言可以具有不同字母对外汉语的字母c的字母符号串：由字母中的符号组成的任何贫穷序列被称为该字母上的符号串。 1 .空符号串(没有符号的符号串)在上面的符号串2.x是上面的符

5、号串，如果a是元素，则xa在上面的符号串3. y是上面的符号串，并且只能从1和2导出。例如，=a、b、a、b、aa、ab、aabba都是上述符号串中符号的顺序符号串的长度，例如x=“abc” |x|=3、|=0，9，符号，如果x不是空，则y是固有的尾部，如果y不是空，则x是固有的开头。 例如，bbababanbanabanananbanananana是代码串banana前缀，前六个是真前缀a na ana nana anana banana是代码串banana的后缀，且， 前6个是真后缀的符号串s的部分串：从s中删除1个前缀和1个后缀的符号串。例如，ana是符号串banana的部分串。3.2符

6、号和符号串，10，3.2符号和符号串，符号串的运算连接：符号串x， 如果y=cd，则xy=abcd存在a=a=a的幂：通过连接符号串a本身n次获得的符号串被称为符号串a的幂，并且标记为an=aaaa(n个a )、a1=a、a2=aa的两个符号串的集合a和b的乘积被表示为a=a=a cde0、1是被定义为AB=ab0、ab1、cde0、cde1的符号串的集合的幂： a0=的闭包。 把由除上面以外的所有符号串构成的集合记作。 叫正闭包。 例如，=a、b *=、a、b、aa、ab、ba、bb、aaa、aab、=a、b、aa、ab、ba、bb、bb、aa、aab、集合ab、aabb、aabbb、anb

7、n或w|w 选择语言。 由于语言是符号串集合，因此符号串集合的运算适用于语言，并还适用于语言、正交、差异、校正集合运算。14，3.3语法和语言的形式定义，15，语法g表示四组：=(T，n，) t :终止符定径套n :不终止符(Variable，也称为语法实体的Start Symbol )，SN表示语法所定义的语言，至少在生成式的左侧出现一次，语法的其中TN是语法g的格式定义、产品或规则的集合(或：=)，并且其中出现至少n个元素体中的一个。 被称作生成式的左部(Left Part )，并且被称作生成式的右部(Right Part )。 生成式将各语法成分的结构(组成规则)、17，语法G=(VT，

8、VN，p，S) VN=S，vt=0，1 p=s0s 1，S01 S作为开始符号来记述是什么语言？ S=0S1=00S11=，例如，将语法G=(VN、VT、p、S) VN=识别符、字母、数字VT=a、b、c、c 1、2、 n称为候选式。例如| |、20，例如算术表达式的语法，递归定义中的后缀标识符(id ) (常数、变量)为表达式(e )； 将表达式与表达式相加，形成表达式。将表达式与表达式相乘，形成表达式。将表达式加括弧，形成表达式。21，例如，考虑语言G=(id，*，(，)，e，p，e ) p 3360 ee ee * e (e ) Eid的一般约束，其中包括算术表达式的语法和简单算术表达式

9、。 语法的写法元符号：=|习惯：大写字母表示非终止符，小写字母表示终止符，希腊字母表示符号串，第一条生成式左部是语法开始符号。 (1)g:saabaaba、(2) GS:Saab aaba (3) GS : Saab aab|aab |、练习题、23、语法是无限语言的有限表现。 如何判断某个句子是否正当？ (导出/归约)、24、导出的定义、直接导出“” 如果是语法g的生成式，则v、w如有： v=、w=，其中的V*、V*如v直接导出至w (w是v的直接导出)。 如果存在v=w0 w1 . wn=w、(n0)则记作v w，称为v导出w，或者w属于v (长度n的导出，至少为一头地)，如果存在v w或

10、者v=w则记作v w (多个步骤：零步骤)0s 11000 s 1110000 s 11000 s 11000 句子中有语法g，如果S=* x，并且xVT*，那么x就称为语法g的句子。 例如：由s0s 1、s01s0s11000s111000001111g的句型s，0 s 1，00 s 11，000 s 111，00001111 g的句型0000111 (对其他导出有其他句子)、句子：符号a、*、(和)构成的算术式、29、(语法GS 3360 (1) SAS be (2) sabe (3) ebbe (4) abbe (5) bbbb (6) Bebe (7) eeee，l (g ) s=aa

11、bebebe=aabbb ebe=aabbb高能效以太网=aabbb高能效以太网=aabbb高能效以太网=abbb语法G1A:ADB等价于g2s:s0s1ade s 01 eab d0b 1在我们先前看到的语法中，哪两个语法是等价的？32、3.4语法的类型，通过对生成式施加不同的限制，Chomsky将语法对0型语法(子句结构语法PSG: Phrase Structure Grammar )的任何生成式都有(vnvt ) (vnvt ) * 1型语法(上下文相关语法CSGContext Sensitive Grammar )对于任何生成式都有|除了只有s是2型语法(上下文相关语法CFG: Con

12、text Free Grammar )以外都是VN 3型语法(正规语法RG Regular Grammar ) 任何一个生成式的形式是AaB或Aa (右线性语法)，其中AVN，BVN，aVT * (类似，也有左线性语法)，33，语法的类型，例如1型(上下文关联)语法GS:scdabbacacababcbbbadcabddbbdb 例如2型(上下文无关)语法GS:SAB ABS|0 BSA|1 CFG可以描述软件编程语言的多个语法成分、35、语法的类型，例如3型语法gs:s0a|1b|0a0a|1b。 RG是要不得、36、语法类型、4种语法之间的分阶段“包含”关系、37、语法和0型语法生成的语言为0型语言1型语法或上下文相关语法(CSG )生成的语言为1型语言或上下文相关语言(CSL )的软件编程语言中的许多单词的左、右线性语法混合2型语法或上下文相关语法(CFG )生成的语言称为2型语言或上下文相关语言(CFL) 3型语法或正则(正规)语法(RG )其能力相当于图灵机*|:G为1型语法，L(G )为1型语言(除外)。 其识别系统是线性边界自动机*N : G是2型语法，L(G )