《高级语言及其语法描述-有限自动机理论》由会员分享，可在线阅读，更多相关《高级语言及其语法描述-有限自动机理论（59页珍藏版）》请在金锄头文库上搜索。
1、1,形式化的方法,用一整套带有严格规定的符号体系来描述问题的方法。 Noan Chomsky 1956 形式语言理论 形式语言理论是编译的理论基础 编译理论中用到的有关形式语言理论的最基本概念 字母表和符号串 文法和语言的形式定义 语法树和文法的二义性 文法和语言的分类,2,2.3 程序语言的语法描述,1. 相关概念,考虑一个有穷 字母表 字符集 其中每一个元素称为一个符号 上的符号串 (也叫字) 是指由中的符号所构成的一个有穷序列,空字，不包含任何符号的序列,* 上所有符号串的全体，包括,例：若=a, b，则*=, a, b, aa, ab, ba, bb, aaa, ,3,：空集，不包含任
2、何元素的集合,* 的子集U和V的积定义为：(连接),UV= |U& V, 注意，一般UVVU, 但(UV)W=U(VW), V0 = , 令V* = V0V1 V2 V3 ，则令V*是V的闭包, V+ = VV* ，称V+是V的正则闭包,如、分别表示符号串01和110，则表示符号串01110，表示符号串11001。 空串是连接运算的恒等元素，s=s=s,4,例 令LA, B, , Z, a, b, , z，表示L是由大、小写字母组成的字母表，D0, 1, , 9，表示D是由10个数字组成的字母表。L和D可以分别看成是有穷的语言集。用集合的运算作用于L和D所得到的6种新语言： （1）LD是字母和
3、数字的集合； （2）LD是所有一个字母后随一个数字的符号串的集合； （3）L6是由6个字母构成的符号串的集合； （4）L*是所有字母串（包括）的集合； （5）L(LD )*是以字母开头的所有字母数字串的集合； （6）D+是不含空串的数字串的集合。 从这个例子可以看出，从基本集合开始，利用集合上的运算，可以定义新的语言。,5,2. 上下文无关文法,文法：描述语言的语法结构的形式规则 (语法规则)。必须是准确、易理解的，且应有强描述力 应有利于句子分析和翻译 最好能够自动产生语法分析程序。通常用符号G表示(Grammar)。,上下文无关文法：所定义的语法范畴是完全独立于这种范畴可能出现的环境的，即
4、是和其上下文无关的，不同于自然语言。,6,例：英文例句分析 He gave me a book.,设“” 为“由组成”或“定义为”，则有语法规则： He me a gave book,7,推导He gave me a book 的语法的合法性。, He He He gave He gave He gave me He gave me He gave me a He gave me a book 语法正确,8,得到语法分析树:,9,上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：
5、文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P， PVN， (VT VN)* 开始符S至少必须在某个产生式的左部出现一次。,10,上下文无关文法G包括四个组成部分：,一组终结符号：组成语言的基本符号，不可再分，如基本字、标识符、常数等。,一组非终结符号：规则中用尖括号括起来的符号，表示一些语法成分，可以推导出其他的语法成分,表示一定符号串的集合,11,一个开始符号：特殊的非终结符，程序语言中，最终感兴趣的是“程序”。,一组产生式：定义语法范畴的书写规则，A，A是一个非终结符，称左部符号， 称为产生式的右部，是由终结符号或|与非终结符号组成的一个符号串。产生式A称为关于A的
6、一条产生规则。,这种表示法称巴科斯范式，简称BNF范式。有的书用“:=”代替“”。,12,对于一个语法范畴，有时需几个产生式，特别需含递归的产生式。,例，定义只含+，*的算术表达式的文法 G=， 其中，P由下列产生式组成： E i E E+E E E*E E (E),13,几点规定： P 1 P 2 可缩写为 P 1|2|n P n 其中，“|”读成“或”，称为P的一个候选式。 表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为： G(E)： E i | E+E | E*E | (E),合并：E i | EAE | (E) A +|,14,上下文无关文法如何定义语言:从文法的开始符号
7、出发,反复连续使用产生式,对左边的非终结符进行替换和展开 直接推导：又称一步推导(用 符号=表示),就是用某条规则的右部去替换该规则的左部 连续使用某个产生式右部去替换左部某个非终结符的过程,得到的连续序列称为推导,从到我是大学生是一个推导.,15,约 定 大写字母A, B, C, 或汉语词组代表非终结符号； 小写字母a, b, c, 代表终结符； , , 等代表由终结符和非终结符组成的符号串。,16,定义：称A直接推出，即 A 仅当A 是一个产生式， 且， (VT VN)* 。 例：S-01, 0S0=0010(直接推导, ) v直接推导出w,也称w直接归约到v, 记作 v w 。 直接推导
8、就是用产生式的右部替换产生式的左部的过程 直接归约就是用产生式的左部替换产生式的右部的过程,17,如果1 2 n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n 。 例：对文法G(E)： E i | E+E | E*E | (E) E (E) (E+E) (i+E) (i+i),18,19,三种推导的比较,直接推导（）的长度为1 直接推导序列（ +）的长度n1 广义推导（ *）的长度0,20,例 : G = (E, i, +, *, (, ) , P , E) (1.1) P： E E + E | E * E | ( E ) | i 表达式(i)和(i+i)
9、*i的推导：,E (E) (i) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i,E E 0步推导 E (i + i)*i 6步推导 E (i + i)*i 6步推导 E (E) 直接推导,21,句型、句子、语言的定义,句型和句子 设有文法GS，若符号串是从开始符推导出来的,即 S =* ，则称是文法G的句型。 若仅由终结符组成,即 S =* ，且VT*，则称是文法G的句子。 例 文法GS： S0S1， S01 因为S 0S1 00S11 000S111 00001111 所以S,0S1 ,00S11 ,000S111,00001111都
10、是G的句型00001111是G的句子,22,语言的定义 由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)=x|S =+x，且 xVT* 例 文法G： S0S1， S01 S0S1 00S11 03S13 0n-1S1n-1 0n1n L(G)=0n1n|n1 文法和语言的关系： 文法G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成,23,根据文法，可以通过推导得到该文法相应的语言； 例：GE：EE+T|T TTF|F F(E)|a E E+T T+T F+T a+T a+TF a+FF a+aF a+aa 表示一切能用符号a，+，(，)构成的算术表达式 有
11、了语言的要求，也可以为该语言设计文法 例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法为： A 0B|1C B 1|1A|0BB C 0|0A|1CC,24,例：文法(A,B,S,a,b,c,P,S) S-Ac|aB A-ab B-bc 写出(G)的全部元素,L(G) = abc,25,例1：考虑文法G1：SbA AaA|a,定义了一个什么语言,分析：SbAba SbAbaAbaa SbAbaA.baa,. . .,所以：L(G1)=ban | n1,得到一个语言，是通过利用所有的侯选式推导出所有句子，构成一个集合。,L(G1) = 以b开头后跟一个或多个a的串,26,推导例题2
12、,27,e.g. 文法产生的语言,文法G2对句子aaabb的推导： S = A B S A B = a A B A a A = a a A B A a A = a a a B A a = a a a b B B b B = a a a b b B b,A= aB = ab A= Ab = ab,S A B A a A | a B b B | b,28,e.g. 文法产生的语言,文法G3对句子aaaabbbb的推导： S = a S b S a S b = a a S b b S a S b = a a a S b b b S a S b = a a a a b b b b S a b,S a
13、S b | ab,29,例4：文法G3(A)： A c|Ab G3(A)的语言? L(G3)=c，cb，cbb， 以c开头，后继若干个b,30,从一个句型到另一个句型的推导往往不唯一。 E+Ei+Ei+i E+EE+ii+i 最左推导：任何一步 都是对中的最左非终结符进行替换。 最右推导：任何一步 都是对中的最右非终结符进行替换。,31,举例,例: 文法GS: SAB AA0|1B B0|S1 请给出句子101001的最左和最右推导。 最左推导： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推导： S AB AS1AAB1 AA01 A1B01
14、 A1001 1B1001 101001,32,3. 语法分析树与二义性,语法树(推导树Parse Tree) 作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树,33,语法树的相关概念,结点：每个树的结点对应于一个符号。结点的名字就是该符号。 边：两个结点之间的连线。 根结点：没有边进入的结点。 分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点） 子树：语法树的某个结点和它向下射出的部分 末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。,34,语法树的概念,定义：语法树的结点由符号组成。根结点对应于识别符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。 引入语法树的意义：作为识别句子的辅助工具，语法树可以表示句子的结构。这一点对于其后的语义分析有非常重要的意义。,35,语法树的特征,给定文法G，G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树具有下列特征： 1、根结点的标记是开始符号S； 2、每个结点的标记都是V中的一个符号； 3、若一棵子树的根结点为A，且其所有直接子孙的标记从左向右的排列
