编译原理 第2讲.ppt

1、第三章语法和语言，第三章语法和语言，软件编程语言自然语言语法：一组规则上下文相关语法语义：语义是否正确静态语义，动态语义本章的目的：为语言语法描述寻求工具的主要内容：语法和语言的基本概念重点：上下文相关语法，句型分析， 第三章语法和语言3.1语法的直观概念3.2符号和符号串3.3语法和语言的形式定义3.4语法的类型3.5上下文相关语法及其语法树3.6句型的分析3.7语法中的一些实用说明，3.1语法的直观概念，如何表达语言只有有限的句子：列举无限的句子：怎么破吗？ 给出一些规则，用这些个规则来描述(或定义)句子的构成结构。 例如，汉语句子由主语后面的谓语组成，构成谓语的是动词和直接宾语，3.1语

2、法的直观概念，汉语句子的构成规则是句子=主语谓语主语=代词代词=我是你的其他名词=王明大学生劳动者的英语谓语。 3.1语法的直观概念是，有一组规则时，如下用它们导出句子：首先=查找左端的带句子规则，把它们换成=右端的符号串，这个动作表现为句子主语谓语，从得到的主语谓语中选择主语或谓语，换成与之对应的规则的=右端比如，选择主语，规则主语=代词，得到主语谓语代词谓语，重复句：“我是大学生”的所有动作过程，句子主语谓语代词谓语我是直接宾语我是名词我是大学生，3.1语法的直观概念， 规则：判断句子结构是否符合语言的汉语-符合汉语语法的所有句子的整体英语-符合英语语法的所有句子的整体软件编程语言-该语言

3、程序的所有句子构成的规则研究语言各句的含义各句与使用者的关系，3.1语法的直观概念， 研究软件编程语言各程序的含义各程序计程仪程序和利用者的关系语言研究三个方面语法：构成语言句子的符号之间的语用：在各符号出现的行为中，表示它们的来源、使用、影响。 3.1语法的直观概念，各语言具有语言形式和与其形式相关的意义这两个可识别的特性。 如果语言的实例在语法上是正确的，那么其相关意义可以从两个角度看出来。 其中一个是该句的缔造者想表达的意思，另一个是接收者验证的意思。 这两个意思不一定相同，前者叫语言的意思，后者是其语用的意思。 幽默的、双关语、谜语就是利用这两个意思的不同。 3.1语法的直观概念是，如

4、果不考虑意义和语用，只能从语法这一方面来看语言，这种意义上的语言称为形式语言。 形式语言抽象地被定义为数学系统。 所谓“形式”，是语言的所有规则只出现什么符号串的事实。 形式语言理论是关于符号串集合的表现法、构造及其特性的研究。 是软件编程语言语法解析研究的基础。 3.2符号和符号串、符号：能够相互区分的符号(要素)。 字母：符号(要素)的天空有贫穷的集合。 符号串：由字母符号组成的贫穷序列称为该字母符号串。 (顺序)1.空符号串(没有符号的符号串)是上面的符号串2.x以上的符号串，如果a是要素，则xa是上面的符号串3. y以上的符号串，其只能从1和2导出。例如：=a、b、a、b、aa、ab，

5、 aabba都是上述符号串，3.2个符号和符号串，符号串s的开头(前缀):删除了符号串s末尾的0个以上符号的符号串，例如，b是符号串banana的一个前缀，符号串s的末尾(后缀):删除了符号串s开头的0个以上符号的符号串， 例如，nana是符号串banana，例如，ana是符号串banana的一个部分串.3.2符号和符号串，符号串的计算符号串的长度：符号串中的符号的个数.符号串s的长度用|s|表示。 的长度为0的符号串的连接：符号串x，y的连接是将在x的符号之后写入了y的符号的符号串xy定义为x=ab，如果y=cd，则xy=abcd有a=a的符号串的平方：将符号串本身连接了n次而成的符号串an

6、定义为aaaa n个aa1=的两个符号串的集合a和b的乘积，aa1=。 若yB是集合A=ab、cde0、1，则AB=ab1、ab0、cde0、cde1表示由*以上所有符号串(包含)构成的集合。 把由除上面以外的所有符号串构成的集合记作。 叫正闭包。3.2符号和符号串，例如=a、b *=、a、b、aa、ab、ba、bb、aaa、aab、=a、b、aa、ab语言贫乏(只包含贫乏的多个句子)时，将句子一个一个列出，如果语言无限，则将语言贫乏的表现语言的贫乏表现有两个路径：展成法(语法):语言中的各句可以用严格定义的规则来建构。 识别方式(自动机):在一个过程中，输入的任意字符串属于语言时，该过程有限

7、次修正后停止并回答“是”，不属于时回答“否”或回答“永远继续”。 3.3语法和语言的形式定义、语法是展成法描述语言的：语言中的各句可以由严格定义的规则构成，被称为规则的左部，被称为规则的右部。3.3语法和语言的形式定义，定义1 :语法g被定义为四组(VN、VT、p、s )，其中VN是非终止符(或者语法实体或者变量)定径套。 VT是终止符定径套p是生成式(也称为规则)的集合VN，VT和p不是空的贫困定径套。 s被称为标识符符号或者起始符号，它是非终止符并且应当在至少一个生成公式中作为左边部分出现。 VN和VT不包含共同的要素，即vnVT=vnVT用v表示，称为语法g的字母和词汇表，3.3语法和语

8、言的形式定义，例句法G=(VN，vt，p，S) VN=S，vt=0，p，S) VN=识别符，字母，数字VT=a。 9 P=a、z 0、9 S=、3.3语法和语言的形式定义，定义2 :直接导出是语法g的生成式，如果有v，则w满足v=、w=、其中的V*、V*，v直接导出到w，标记为v w，w直接归属于v定义3 :长度n(n )或w约为v定义4 :长度n 或者如果有v= w，则记作v=* w，3.3语法和语言的形式定义，定义5 :句型，句子中有记作语法g，s=*的语法g，如果是S=* x，并且xVT*，则x被称为语法g的句子。例如： G: S0S1，S01 S 0S1 00S11 000S111 0

9、0001111 G的句型s，0 s 1，00 s 11，000 s 111，000111 g的句型000111，01， 3.3语法和语言的形式这是语法g的所有句子的集合L(G)=x|S=* x，其中，s是语法的开始符号，x VT*例： G: S0S1，s01 l (g )=0n|n 1，3.3语法和的例句法GS:(1) SAS be (2) sabe (3) ebbe (3) 采用SAS be (SAS be ) a abebe (sabe ) a abebe (abab ) AABB ee (ebbe ) AABB ee (Bebe ) AABB ee发生式(1)的n-1次，导出系列： s=

10、* an-1 s (be 并且从an(BE)n继续导出，始终用生成式(3)的右部替换EB，在最终得到的串中，所有的b先于所有的e。 例如，如果n=3，则为aabebebeaabbeebeabbebeeabbeeabbeee。 即，接着S=* anBnEn，使用发生式(4) 1次得到S=* anbBn-1En，然后使用发生式(5) n-1次得到S=* anBnEn的语法G1A:A0R与G2S:S0S1等价的a01s01ra1、3.4语法的类型Chomsky将语法分类为4种类型： 0型语法：对于任何生成式，(VNVT )，只有s除了2型语法：对于任何生成式都有VN，(VNVT)* 3型语法：任何生

11、成式的形式都是AaB或Aa，其中AVN，BVN，aVT，3.4语法3.4语法的类型，例如2型(上下文无关)语法语法GS:sababs|0 BSA|1，3.4语法的类型，3型语法(正规语法):gs:s0a|1b|0a0a 4种语法之间的阶段性的“包含”关系，3型语法，3.4语法的类型0型语法生成的语言为0型语言1型生成的语言称为1型语言或上下文相关语言(CSL) 2型语法或上下文相关语法(CFG )生成的语言称为2型语言或上下文相关语言(CF L ) 3型语法或正则(正规)语法(rg )3. 5上下文相关语法及其语法树， 上下文相关语法对于描述软件编程语言的语法结构语法树句型导出的直观表现具有一

12、盏茶能力，3.5上下文相关语法及其语法树，给出的语法G=(VN，VT，p，s )为cfg， 可以对g中的任何句型结构的这个标签条是v的一个符号2 .根的标签条是S 3.节点n中至少有一个自己以外的子孙，并且如果有标签条a，则AVN 4.节点n中有标签条a，其直接子孙节点从左起依次为n1、n2、nk，其标签条分别为A1、 作为记述A2的上下文相关语法句型导出的直观方法，例如： GS: SaAS ASbA ASS Sa Aba，sasbaaaba，句型aabbaa的语法树(导出树)，叶结点： 从左向右读出导出树叶标签连接的语法符号串，作为GS的句型。 此导出树也称为此句型的语法树。3.5上下文无关

13、语法及其语法树，在导出过程中应用生成表达式的顺序，例如： GS: SaAS ASbA ASS Sa Aba、sasbaaba、saasaaasbaaaabbaaasaabaaasaabaaasabaaasabaasabaaasabaasabaasabasabasabasaba 3.5上下文相关语法及其语法树， 对于任何导出步骤：=最左导出：全部替换中的最左非终止符的最右导出(规范导出):全部替换中的最右非终止符，3.5上下文相关语法及其语法树，一个语法树表示一个句型的各种可能(但并非全部)的不同导出过程，包括最左一个句型是只对应唯一的语法树还是一个句型只导出唯一的最左(最右)，3.5上下文无关语法及其语法树，例如ge : e iee e * e (e )、高能效以太网* EII、ee*eei句型i* I的两个不同的最左导出：