1、高级语言及其文法高级语言及其文法本章主要内容本章主要内容2.1 2.1 语言概述语言概述什么是语言？什么是语言？2.1 2.1 语言概述语言概述n语言特征语言特征n自然语言自然语言(Natural Language)Natural Language)n是人与人的通讯工具是人与人的通讯工具n语义语义(semantics):semantics):环境、背景知识、语气、环境、背景知识、语气、二义性二义性难以形式化难以形式化n计算机语言计算机语言(Computer Language)Computer Language)n计算机系统间、人机间通讯工具计算机系统间、人机间通讯工具n严格的语法严格的语法(G
2、rammar)Grammar)、语义语义(semantics)semantics)易于形式化：严格易于形式化：严格2.12.1语言概述语言概述n语言的描述方法语言的描述方法现状现状n自然语言：自然、方便自然语言：自然、方便-非形式化非形式化n数学语言（符号）：严格、准确数学语言（符号）：严格、准确-形式化形式化n形式化描述形式化描述n高度的抽象，严格的理论基础和方便的计高度的抽象，严格的理论基础和方便的计算机表示。算机表示。2.1 2.1 语言概述语言概述n语言语言形式化的内容提取形式化的内容提取n语言语言(Language)Language)：满足一定条件的句子集合满足一定条件的句子集合n句
3、子句子(Sentence)Sentence)：满足一定规则的单词序列满足一定规则的单词序列n单词单词(Token)Token)：满足一定规则的字符满足一定规则的字符(Character)Character)串串n语言是字和组合字的规则语言是字和组合字的规则n例（自然语言：第译始一天课今开编上节）例（自然语言：第译始一天课今开编上节）n今天开始上第一节编译课今天开始上第一节编译课2.1 2.1 语言概述语言概述语言是字及其组合规则的统一体语言是字及其组合规则的统一体2.1 2.1 语言概述语言概述n程序设计语言程序设计语言形式化的内容提取形式化的内容提取n程序设计语言程序设计语言(Program
4、ming Language)Programming Language)：组成程序组成程序的所有语句的集合。的所有语句的集合。n程序程序(Program)Program)：满足语法规则的语句序列。满足语法规则的语句序列。n语句语句(Sentence)Sentence)：满足语法规则的单词序列。满足语法规则的单词序列。n单词单词(Token)Token)：满足词法规则的字符串。满足词法规则的字符串。n例：变量例：变量:=:=表达式表达式nif if 条件条件 then then 语句语句nwhilewhile条件条件 do do 语句语句ncall call 过程名过程名(参数表参数表)2.1 2
5、.1 语言概述语言概述n描述形式描述形式文法文法n语法语法语句语句n语句的组成规则语句的组成规则n描述方法：描述方法：BNFBNF范式、语法范式、语法(描述描述)图图n词法词法单词单词n单词的组成规则单词的组成规则n描述方法：描述方法：BNFBNF范式、正规式范式、正规式形式语言于自动机理论的产生与作用形式语言于自动机理论的产生与作用n语言学家语言学家ChomskyChomsky最初从产生语言的角度研究语言。最初从产生语言的角度研究语言。n19561956年，通过抽象，他将语言形式地定义为是由一个字母表年，通过抽象，他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字母表上按
6、照一定的中的字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法（规则定义一个文法（GrammarGrammar），该文法所能产生的所有句），该文法所能产生的所有句子组成的集合就是该文法产生的语言。子组成的集合就是该文法产生的语言。n克林（克林（KleeneKleene）在）在19511951年到年到19561956年间，从识别语言的年间，从识别语言的角度研究语言，给出了语言的另一种描述。角度研究语言，给出了语言的另一种描述。n克林是在研究神经细胞中，建立了自动机，他用这种自动机克林是在研究神经细胞中，建立了自动机，他用这种自动机来识别语言：对于按照一定的规则构造的任一个自动机，该
7、来识别语言：对于按照一定的规则构造的任一个自动机，该自动机就定义了一个语言，这个语言由该自动机所能识别的自动机就定义了一个语言，这个语言由该自动机所能识别的所有句子组成。所有句子组成。形式语言于自动机理论的产生与作用形式语言于自动机理论的产生与作用n19591959年，年，ChomskyChomsky通过深入研究，将他本人的研究成果通过深入研究，将他本人的研究成果与克林的研究成果结合了起来，不仅确定了文法和自与克林的研究成果结合了起来，不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且证明动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性。了文法与自动机的等价性。n
8、2020世纪世纪5050年代，人们用巴科斯范式（年代，人们用巴科斯范式（Backus Backus NourNour Form Form 或或 Backus Normal FormBackus Normal Form，简记为，简记为BNFBNF）成功地对）成功地对高级语言高级语言ALGOL-60ALGOL-60进行了描述。实际上，巴科斯范式进行了描述。实际上，巴科斯范式就是上下文无关文法（就是上下文无关文法（Context Free GrammarContext Free Grammar）的一）的一种表示形式。这一成功，使得形式语言在种表示形式。这一成功，使得形式语言在2020世纪世纪6060
9、年年代得到了大力的发展。代得到了大力的发展。形式语言于自动机理论的产生与作用形式语言于自动机理论的产生与作用n形式语言与自动机理论除了在计算机科学领域中的直形式语言与自动机理论除了在计算机科学领域中的直接应用外，更在计算学科人才的计算思维的培养中占接应用外，更在计算学科人才的计算思维的培养中占有极其重要的地位有极其重要的地位 n计算思维能力的培养，主要是由基础理论系列课程实计算思维能力的培养，主要是由基础理论系列课程实现的，该系列主要由从数学分析开始到形式语言结束现的，该系列主要由从数学分析开始到形式语言结束的一些数学和抽象程度比较高的内容的课程组成。的一些数学和抽象程度比较高的内容的课程组成
10、。n它们构成的是一个梯级训练系统。在此系统中，连续数学、它们构成的是一个梯级训练系统。在此系统中，连续数学、离散数学、计算模型等三部分内容要按阶段分开，三个阶段离散数学、计算模型等三部分内容要按阶段分开，三个阶段对应与本学科的学生在大学学习期间的思维方式和能力的变对应与本学科的学生在大学学习期间的思维方式和能力的变化与提高过程的三个步骤。化与提高过程的三个步骤。计算思维能力的培养过程计算思维能力的培养过程 中学数学中学数学数学分析数学分析 离散数学离散数学 具体具体.静止静止变量变量.运动运动离散离散.抽象抽象 形式形式.模型模型 (基本运算系统基本运算系统)(计算系统计算系统)实实 数数 抽
11、象抽象 集合集合 单一、具体的计算单一、具体的计算 一般、形式化的计算一般、形式化的计算 （实例计算）（实例计算）（模型化计算）（模型化计算）形式语言与形式语言与自动机理论自动机理论运算运算范围范围特征特征高水平计算专业人才的计算思维能力的高水平计算专业人才的计算思维能力的渐进培养渐进培养2.2 2.2 基本定义基本定义n字母表字母表（AlphabetAlphabet）是一个非空有穷集合，是一个非空有穷集合，字母表中的元素称为该字母表的一个字母字母表中的元素称为该字母表的一个字母（LetterLetter），），也叫字符（也叫字符（CharacterCharacter）。）。n例例 以下是不同
12、的字母表：以下是不同的字母表：aa，b b，c c，dd a a，b b，c c，zz 0 0，11 (4)ASCII(4)ASCII字母表字母表2.2 2.2 基本定义基本定义n符号串符号串的定义的定义(1)(1)是是上的一个符号串。上的一个符号串。(2)(2)若若x x是是上的符号串，而上的符号串，而a a是是的元素的元素,则则xaxa是是上的符号串。上的符号串。(3)(3)y y是是上的符号串上的符号串,当且仅当它由当且仅当它由(1)(1)和和(2)(2)导出。导出。由字母表中的符号所组成的任何有穷序列被称由字母表中的符号所组成的任何有穷序列被称之为该字母表上的符号串之为该字母表上的符号
13、串,也称作也称作 字字。2.2 2.2 基本定义基本定义设设s s是符号串，则是符号串，则s s的的前缀前缀：移走：移走s s的尾部的零个或多于零个符号的尾部的零个或多于零个符号后缀后缀：删去：删去s s的头部的零个或多于零个符号的头部的零个或多于零个符号子串子串:从从s s中删去一个前缀和一个后缀中删去一个前缀和一个后缀子序列子序列:从从s s中删去零或多于零个符号中删去零或多于零个符号(这些符号不要求连续）这些符号不要求连续）逆转逆转（用（用SRSR表示）：将表示）：将S S中的符号按相反次序写出而得到的符号串中的符号按相反次序写出而得到的符号串长度长度：是该符号串中的符号的数目。例如：是
14、该符号串中的符号的数目。例如|aabaab|=3,|=0|=3,|=0。2.2 2.2 基本定义基本定义符号串的连接和方幂符号串的连接和方幂1.1.连接：设连接：设x x和和y y是符号串，它们的连接是符号串，它们的连接xyxy是把是把y y的符号的符号写在写在x x的符号之后得到的符号串。例如，的符号之后得到的符号串。例如，x=x=ba,yba,y=nana,xynana,xy=banana.=banana.2.2.方幂：方幂：x x0 0=;x x1 1=x;x=x;x2 2=xx;=xx;；x xn n=x=xn-1n-1x;x;例如例如,设设x=x=baba,则则 x x1 1=bab
15、a,x,x2 2=babababa,x,x3 3=babababababa,2.2 2.2 基本定义基本定义n定义定义1 1 设设1 1、2 2是两个字母表，是两个字母表，1 1与与2 2 的的乘积乘积(Product)Product)定义为定义为1 12 2=ab|a=ab|a1 1，bb2 2 n例例:1 1=0,1,=0,1,2 2=a,b,a,b,1 12 2=0a,0b,1a,1b=0a,0b,1a,1bn定义定义2 2 设设是一个字母表，是一个字母表，的的n n次幂次幂(Power)Power)递归递归地定义为：地定义为：n 0 0=n n n=n-1n-1 n1 n1n例：例：1
16、 13 3=000,001,010,011,100,101,110,111=000,001,010,011,100,101,110,1112.2 2.2 基本定义基本定义n定义定义3 3 设设是一个字母表，是一个字母表，的的正闭包正闭包(Positive Closure)Positive Closure)定义为：定义为：n+=2 23 34 4n的的克林闭包克林闭包(KleeneKleene Closure)Closure)为：为：n*=0 0+n =0 02 23 3 2.2 2.2 基本定义基本定义n例例0,10,1+=00，1 1，0000，0101，1111，000000，001001
17、，010010，011011，100100，a a，b b，c c，d d+=a a，b b，c c，d d，aaaa，abab，acac，adad，baba，bbbb，bcbc，bdbd，aaaaaa，aabaab，aacaac，aadaad，abaaba，abbabb，abcabc 2.2 2.2 基本定义基本定义n例例0,10,1*=，0 0，1 1，0000，0101，1111，000000，001001，010010，011011，100100，a a，b b，c c，d d*=，a a，b b，c c，d d，aaaa，abab，acac，adad，baba，bbbb，bcbc，b
18、dbd，aaaaaa，aabaab，aacaac，aadaad，abaaba，abbabb，abcabc，2.2 2.2 基本定义基本定义n定义定义5 5 设设是一个字母表，是一个字母表，L L *，L L称为字称为字母表母表上的一个上的一个语言语言（LanguageLanguage），），xLxL，x x叫做叫做L L的一个的一个句子句子。n例：例：字母表字母表00，11上的语言上的语言00，110000，111100，1 1，0000，111100，1 1，0000，1111，0101，10100000，1111*0101，1010*2.3 2.3 文法的定义文法的定义如何实现语言结构如何
19、实现语言结构的形式化描述？的形式化描述？考虑一个句子考虑一个句子文法要素的提取文法要素的提取分析分析：The grey wolf will eat the goat谓语谓语主语主语形容词形容词名词名词动词动词直接宾语直接宾语助动词助动词句子句子动原动原冠词冠词名词名词The grey wolf will eat the goat冠词冠词 句子句子 主语主语 谓语谓语 （1 1）主语主语 冠词冠词 形容词形容词 名词名词 （2 2）冠词冠词the the 形容词形容词 greygrey 谓语谓语 动词动词 直接宾语直接宾语 （5 5）动词动词 助动词助动词 动词原动词原形形 （6 6）助动词助动
20、词will will 动词原动词原形形 eat eat 直接宾语直接宾语 冠词冠词 名词名词 （9 9）名词名词wolf wolf 名词名词 goatgoat句子的组成规则句子的组成规则问题：如何用符号来描述？即如何形式化？问题：如何用符号来描述？即如何形式化？终结符号集终结符号集V VT T=thethe，greygrey,wolf,will,eat,goat,wolf,will,eat,goat非终结符号集非终结符号集V VN N=句子句子，主语主语，谓语谓语，冠词冠词，形容词形容词，名词名词 ，动词动词 ，直接宾语直接宾语 ，助动词助动词 ，动词原动词原形形 语法规则集语法规则集P P=
21、句子句子 主语主语 谓语谓语，开始符号开始符号S S=句子句子 定义句子的规则的语法组成定义句子的规则的语法组成_终结符号集，非终结符号集，语法规则，开始符号终结符号集，非终结符号集，语法规则，开始符号问题：有了定义句子的规则，如何判定某一问题：有了定义句子的规则，如何判定某一句子是否属于某语言？句子是否属于某语言？句子句子 主语主语 谓语谓语 冠词冠词 形容词形容词 名词名词 谓语谓语 thethe 形容词形容词 名词名词 谓语谓语 the the greygrey 名词名词 谓语谓语 the grey the grey wolfwolf 谓语谓语 the grey wolf the gre
22、y wolf 动词动词 直接宾语直接宾语 .the grey wolf the grey wolf will eat the goatwill eat the goat句子的派生（推导）句子的派生（推导）-从产生语言的角度从产生语言的角度句子的归约句子的归约 -从识别语言的角度从识别语言的角度-均均根据规则根据规则 句子句子 the grey wolf will eat the goat the grey wolf will eat the wolf the grey goat will eat the wolf the grey goat will eat the grey wolf符合语法
23、且符合语义的句子仅是：符合语法且符合语义的句子仅是：the grey wolf will eat the goat句子句子的的语义要求语义要求文法文法G G 的形式定义的形式定义文法文法G G为一个四元组为一个四元组:=(=(T T，N N，)nT T：终结符终结符(Terminal)Terminal)集集nN N：非终结符非终结符(Variable)Variable)集，集，T TN N=n语法成分语法成分代表某个语言的各种子结构代表某个语言的各种子结构n：开始符号：开始符号(Start Symbol)Start Symbol)，SSN Nn代表文法所定义的语言，至少在产生式左侧出现一次代表
24、文法所定义的语言，至少在产生式左侧出现一次文法文法G G 的形式定义的形式定义n：产生式：产生式(Product)Product)集合集合，被称为产生式（定义式），读作：被称为产生式（定义式），读作：定义为定义为。其中其中(T TN N)+，且且中至少有中至少有N N中元素中元素的一个出现。的一个出现。(T TN N)*。称为产生式称为产生式的的左部左部(Left Part)Left Part)，称为产生式称为产生式的的右部右部(Right Part)Right Part)。产生式定义各个语法成分的结构（组成规则）产生式定义各个语法成分的结构（组成规则）例例2-1 2-1 算术表达式的文法算术
25、表达式的文法n递归定义递归定义中缀表示中缀表示n标识符标识符(id)id)（常数、变量）是表达式常数、变量）是表达式(E)E)；n表达式加一个表达式是表达式；表达式加一个表达式是表达式；n表达式减一个表达式是表达式；表达式减一个表达式是表达式；n表达式乘一个表达式是表达式；表达式乘一个表达式是表达式；n表达式除一个表达式是表达式；表达式除一个表达式是表达式；n表达式加上括号后是表达式；表达式加上括号后是表达式；例例2-1 2-1 算术表达式的文法算术表达式的文法n考虑简单算术表达式组成的语言考虑简单算术表达式组成的语言nG=(idG=(id，+，*，(，)，EE，P P，E)E)nP:EE+E
26、 P:EE+E n EE EE*E E n E(E)E(E)n Eid Eidn约定：只写产生式约定：只写产生式 n简写简写nE E+E|E E E+E|E*E|(E)|id E|(E)|id（2.12.1）产生式的简写产生式的简写n对一组有相同左部的产生式对一组有相同左部的产生式1 1，2 2，n n可以简单地记为：可以简单地记为：1 1|2 2|n n读作：读作：定义为或者定义为或者1 1，或者或者2 2，或者或者n n。并且称它们为并且称它们为产生式。产生式。1 1，2 2，n n称为称为候选式候选式(Candidate)Candidate)。基于产生式的变换基于产生式的变换-推导或归约
27、推导或归约nE E+E|E E E+E|E*E|(E)|id E|(E)|idnE E由第一个候选式可以变成由第一个候选式可以变成E+EE+EnE+EE+E中的第一个中的第一个E E由第二个候选式可以变由第二个候选式可以变成成E E*E E，从而从而E+EE+E变成变成E E*E+EE+En根据第根据第4 4个候选式，个候选式，E E*E+EE+E中的中的E E都可以变成都可以变成id:id:nE E*E+E E+E 变成变成idid*E+EE+Enidid*E+EE+E变成变成idid*E+idE+idnidid*E+idE+id变成变成idid*id+idid+idn也就是说，根据第也就是
28、说，根据第4 4个候选式，个候选式，E E*E+EE+E经经3 3步变步变换变成换变成idid*id+idid+id直接推导与归约直接推导与归约n根据产生式对符号串进行变换的过程根据产生式对符号串进行变换的过程n是文法的一个产生式，是文法的一个产生式，n且且、（T TN N）*，n称称直接推导直接推导/派生派生(Derive)Derive)出出，也称也称 直接归约直接归约(Reduce)Reduce)为为。n记为记为 n例：例：nid+Eid+Eid+E id+E*E E（多步）推导（多步）推导n0 01 12 2 n nn记为记为 0 0n n n n (恰用恰用n n步步)n 0 0+n
29、n （至少一步）至少一步）n 0 0*n n （若干步若干步:零步或多步）零步或多步）推导推导/归约举例归约举例E E E+E E+E （1 1）串中含有变量串中含有变量n id+E id+E（4 4）串中含有变量串中含有变量n id+E id+E*E E（2 2）串中含有变量串中含有变量n id+id id+id*E E（4 4）串中含有变量串中含有变量n id+id id+id*id id（4 4）串中没有变量串中没有变量n到此串中已经没有（语法）变量了，不能再推导了到此串中已经没有（语法）变量了，不能再推导了句型与句子句型与句子nE E 5 5 id+id id+id*id idn句子句
30、子:如果如果S S*x x，且且xxT T*，则称则称x x是是G G产生的一个产生的一个句子句子(Sentence)Sentence)nE E E+E E+E E E+E +E*E EnE E 4 4 id+id id+id*E En句型句型:如果如果S S*，(T TN N)*则称则称是是G G产生的一个产生的一个句型句型(Sentential Form)Sentential Form)文法文法G G产生的语言产生的语言()x x*x and xx and xT T*n文法文法 EE+E|EEE+E|E*E|(E)|idE|(E)|id可以派生出多少个句子？可以派生出多少个句子？n文法文法
31、G G的作用的作用语言的有穷描述语言的有穷描述n以有限的规则描述无限的语言现象以有限的规则描述无限的语言现象n有限：有限：n产生式集合、终结符集合、非终结符集合产生式集合、终结符集合、非终结符集合n无限：无限：n可以导出无穷多个句子（可以导出无穷多个句子（L L也可是有穷）也可是有穷）id+idid+id*idid的不同推导的不同推导EE+E|EEE+E|E*E|(E)|idE|(E)|id最左推导与最右推导最左推导与最右推导n最左推导最左推导(Left-most Derivation)Left-most Derivation)n每次推导都施加在句型的最左边的语法每次推导都施加在句型的最左边的
32、语法变量上。变量上。与最右归约对应与最右归约对应n最右推导最右推导(Right-most Derivation)Right-most Derivation)n每次推导都施加在句型的最右边的语法每次推导都施加在句型的最右边的语法变量上。变量上。与最左归约（规范规约）对与最左归约（规范规约）对应的规范应的规范(Canonical)Canonical)句型句型短语短语(Phrase)Phrase)n什么叫短语？什么叫短语？n 如果如果*and A and A+，则称则称是句型是句型的相对于变量的相对于变量A A的短语的短语n 如果如果*and A and A，则称则称是句型是句型的相对于变量的相对于
33、变量A A的直接短语的直接短语n最左直接短语叫做句柄最左直接短语叫做句柄(Handle)Handle)例：例：(直接直接)短语短语EE+T T+TF+T(E)+T(E+T)+T句柄句柄(Handle)Handle)：最左直接短语最左直接短语例例2-2 2-2 标识符的文法标识符的文法1 1nS L|LTS L|LTT L|N|TL|TN T L|N|TL|TN L a|b|c|dL a|b|c|d letter letterN 0|1|2|3|4|5N 0|1|2|3|4|5 digit digitn问题：正整数的文法问题：正整数的文法?正实数的文法？正实数的文法？2.2.文法的分类文法的分类
34、(ChomskyChomsky体系体系)n根据语言结构的复杂程度（形式语言）根据语言结构的复杂程度（形式语言）n涉及文法的复杂程度、分析方法的选择涉及文法的复杂程度、分析方法的选择n反映文法描述语言的能力反映文法描述语言的能力n如果如果G G满足文法定义的要求，则是型文满足文法定义的要求，则是型文法（短语结构文法法（短语结构文法PSG:Phrase Structure PSG:Phrase Structure Grammar Grammar）。）。nL(G)L(G)为为PSLPSL。上下文有关文法上下文有关文法(CSG)CSG)n若产生式集合中所有若产生式集合中所有，除除 外，则是型文法外，则
35、是型文法n即：上下文有关文法（即：上下文有关文法（CSGCSGContext Context Sensitive GrammarSensitive Grammar）nL(G)L(G)为为1 1型型/上下文有关上下文有关/敏感语言敏感语言(CSL)CSL)上下文无关文法上下文无关文法(CFG)CFG)n若若 N N，(N NT T)*，则则 是型文法是型文法n即：上下文无关文法即：上下文无关文法(CFG:Context Free CFG:Context Free Grammar)Grammar)nL(G)L(G)为为2 2型型/上下文无关语言（上下文无关语言（CFLCFL）nCFGCFG能描述程
36、序设计语言的多数语法成分能描述程序设计语言的多数语法成分例例2-3 2-3 标识符的文法标识符的文法2 2nS L|LTT L|N|TL|TN L a|b|c|dN 0|1|2|3|4|5正规文法正规文法(RG)RG)n设、设、N N，T T或为或为 n右线性右线性(Right Linear)Right Linear)文法：文法：或或n左线性左线性(Left Linear)Left Linear)文法：文法：或或n都是型文法都是型文法(正规文法正规文法 Regular Grammar-RG)Regular Grammar-RG)nL(G)L(G)为为3 3型型/正规集正规集/正则集正则集/正则
37、语言（正则语言（RLRL）n能描述程序设计语言的多数单词能描述程序设计语言的多数单词n左、右线性文法不可混用左、右线性文法不可混用例例 非非CFLCFL的文法的文法L=L=a an nb bn nc cn n|n|n00的文法的文法S SaBC|aSBCaBC|aSBCCBCBBCBCaBaBababbBbBbbbbbCbCbcbc 在我们使用的程序设计语言中在我们使用的程序设计语言中,有些语言结有些语言结构不能用上下文无关文法来描述。构不能用上下文无关文法来描述。例例2.9 2.9 L L1 1=wcw|wwcw|wa,ba,b+。例例,aabcaabaabcaab就就是是L L1 1的一个
38、句子。这个语言是检查程序中标的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。识符的声明应先于引用的抽象。例例2.10 2.10 L L2 2=a=an nb bm mc cn nd dm m|n|n,m m00，它是检查过，它是检查过程声明的形参个数和过程引用的参数个数是程声明的形参个数和过程引用的参数个数是否一致问题的抽象。否一致问题的抽象。非上下文无关的语言结构非上下文无关的语言结构ChomskyChomsky体系体系总结总结=(=(T T，N N，)是一个文法是一个文法,P P*G G是是0 0型文法，型文法，L(G)L(G)是是0 0型语言；型语言；-其能力相当于图灵机其
39、能力相当于图灵机*|:G|:G是是1 1型文法，型文法，L(G)L(G)是是1 1型语言型语言(除除););-其识别系统是线性界限自动机其识别系统是线性界限自动机*N N:G:G是是2 2型文法，型文法，L(G)L(G)是是2 2型语言型语言;-其识别系统是不确定的下推自动机其识别系统是不确定的下推自动机*AaBAaB或或Aa:Aa:G G是右线性文法，是右线性文法，L(G)L(G)是是3 3型语言型语言ABaABa或或AA:G G是左线性文法，是左线性文法，L(G)L(G)是是3 3型语言型语言 -其识别系统是有穷自动机其识别系统是有穷自动机文法的类型文法的类型四种文法之间的关系是将产生式作
40、进一步限制而定义的。四种文法之间的关系是将产生式作进一步限制而定义的。四种文法之间的逐级四种文法之间的逐级“包含包含”关系如下：关系如下：2型文法型文法1型文法型文法0型文法型文法3型文法型文法范式范式Backus-Naur FormBackus-Naur FormBackus-Normal FormBackus-Normal Formn表示为表示为n非终结符用非终结符用“”“”“”括起来括起来n终结符：基本符号集终结符：基本符号集n其他其他n(1 1|2 2|n n)1 1|2 2|n nn|n范式范式Backus Normal FormBackus Normal Formn例例 简单算术表
41、达式简单算术表达式(只写产生式只写产生式)n +n *n()n ididn即：+|*|(|()|)|ididn哪些是终结符？哪些是变量？哪些是终结符？哪些是变量？例例2-5 2-5 句子结构的表示句子结构的表示 (文法文法EE+E|EEE+E|E*E|(E)|idE|(E)|id ）2.5 2.5 CFGCFG的分析树的分析树Parse TreeParse Treen用树的形式表示句型的生成用树的形式表示句型的生成n树根：树根：开始符号开始符号n中间结点：中间结点：非终结符非终结符n叶结点：叶结点：终结符或者非终结符终结符或者非终结符n每个推导对应一个中间结点及其儿子每个推导对应一个中间结点及
42、其儿子一个二级子树一个二级子树-直接短语直接短语n又称为语法分析树又称为语法分析树短语：一棵子树的所有叶子自左至右排列起来形成短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。的子树的所有叶子的自左至右排列。例如，对表达式文法例如，对表达式文法GEGE和句子和句子a a1 1+a+
43、a2 2*a a3 3，挑选出挑选出推导过程中产生的句型中的短语，直接短语，句柄。推导过程中产生的句型中的短语，直接短语，句柄。用子树解释短语，直接短语，句柄用子树解释短语，直接短语，句柄EE+TT+TF+T a1+T a1+T*F a1+F*F a1+a2*FE+T T,T+T F,F+T a1,a1+T a1,T*F,a1+T*Fa1,F,F*F,a1+F*F a1,a2,a1+a2*F,a2*F a1,a2,a3,a2*a3 a1+a2*a3EE+TTFa1T*FFa2a3a1+a2*a3短语短语 例例 短语与分析树短语与分析树 (文法文法EE+E|EEE+E|E*E|(E)|idE|(
44、E)|id ）二义性文法与先天二义性语言二义性文法与先天二义性语言n对同一句子存在两棵语法分析树对同一句子存在两棵语法分析树n在理论上不可判定在理论上不可判定 1.描述一个句子的文法不是唯一的；描述一个句子的文法不是唯一的；2.对于一个句子的分析应是唯一的。对于一个句子的分析应是唯一的。考虑表达式下面的文法考虑表达式下面的文法 GE,其产生式如下：其产生式如下：EE+E E*E (E)a 对于句子对于句子a+a*a,有如下两个最左推导：有如下两个最左推导：EE+E a+E a+E*E a+a*E a+a*a E E*E E+E*E a+E*E a+a*E a+a*a文法的二义性文法的二义性 E
45、E+E a+E a+E*E a+a*E a+a*a E E*EE+E*E a+E*Ea+a*E a+a*aEE+EE*EaaaEE*E+EEaaa最左推导最左推导 EE+E E+E*E E+E*a E+a*a a+a*a E E*EE*a E+E*aE+a*a a+a*aEE+EE*EaaaEE*E+EEaaa最右推导最右推导如果一个文法的句子存在两棵分析树如果一个文法的句子存在两棵分析树,那么那么,该句子该句子是二义性的。如果一个文法包含二义性的句子是二义性的。如果一个文法包含二义性的句子,则则称这个文法是二义性的称这个文法是二义性的;否则，该否则，该文法是无二义性文法是无二义性的。几点说明
46、：的。几点说明：1.一般来说，程序语言存在无二义性文法，一般来说，程序语言存在无二义性文法，对于对于表达式来说，文法（表达式来说，文法（2.1）是二义性的。对于条件）是二义性的。对于条件语句，经常使用二义性文法描述它：语句，经常使用二义性文法描述它：S if expr then S if expr then S else S other二义性的句子二义性的句子:if e1 then if e2 then s1 else s2 二义性（歧义性，二义性（歧义性，ambiquityambiquity)的定义的定义 下面是下面是 Smatched_s unmatched_s matched_s if
47、expr then matched_s else matched_s other unmatched_s if expr then S if expr then matched_s else unmatched_s 它显然比较复杂，因此：它显然比较复杂，因此：2.在能驾驭的情况下，使用在能驾驭的情况下，使用二义性文法二义性文法。描述描述ifif语句的无二义性文法的产生式语句的无二义性文法的产生式3.3.对于任意一个上下文无关文法，不存在一个算法，对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文
48、法是无二义性的。足这组充分条件的文法是无二义性的。4.4.存在先天二义性语言。例如，存在先天二义性语言。例如，a ai ib bi ic cj j i,ji,j 1 1 a ai ib bj jc cj j i,ji,j 1 1 存在一个二义性的句子存在一个二义性的句子a ak kb bk kc ck k。(抽象抽象)语法树与分析树不同语法树与分析树不同2.6 2.6 文法的构造文法的构造n明确描述对象明确描述对象语言语言n合法的语言结构合法的语言结构n确定基本符号集确定基本符号集T Tn引入非终结符引入非终结符n各种语法成分的结构各种语法成分的结构n定义句子的组成规则定义句子的组成规则nBN
49、FBNF范式或产生式范式或产生式文法举例文法举例n x|xx|x是长度为偶数的是长度为偶数的0 0、1 1串串 S00S|01S|10S|11S|S00S|01S|10S|11S|n0 0 m m 1 1 n n|m,n 1|m,n 1RLRLS0S|0AS0S|0AA1A|1A1A|1n0 0 n n 1 1 n n|n 1|n 1CFLCFLS0S1|01S0S1|01n wwww|wa,b|wa,b+PSLPSLSaCAE|bCBESaCAE|bCBE AaaAAaaA AbbAAbbAAEaREAEaRERED RED aRRaaRRa bRRbbRRb CRaCA|bCBCRaCA|
50、bCBBaaBBaaB BbbBBbbB BEbREBEbRE aRRaaRRa bRRbbRRbCRaCA|bCBCRaCA|bCB aDDaaDDa bDDbbDDb ED ED例例2-72-7：w|ww|w为十进制数为十进制数 D N|N.TN|N.TN 1|2|3|4|5|6|7|8|9N 1|2|3|4|5|6|7|8|9N N0|N1|N2|N3|N4|N5|N6|N7|N8|N9N N0|N1|N2|N3|N4|N5|N6|N7|N8|N9T 1|2|3|4|5|6|7|8|9T 1|2|3|4|5|6|7|8|9T 0T|1T|2T|3T|4T|5T|6T|7T|8T|9TT
