高级语言及其文法编译原理三

高级语言及其文法编译原理三2.1语言概述2.2基本定义2.3文法(Grammar)的定义2.4CFG的语法(分析)树(ParseTree)2.5文法的分类2.6文法的构造本章主要内容第2页,共73页，2024年2月25日，星期天2.1语言概述什么是语言自然语言(NaturalLanguage)是人与人的通讯工具语义(Semantics):环境、背景知识、语气、二义性——难以形式化计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(Semantics)——易于形式化：严格语言是用来交换信息的工具——功能性描述第3页,共73页，2024年2月25日，星期天2.1语言概述语言的描述方法——现状自然语言：自然、方便-非形式化数学语言（符号）：严格、准确-形式化形式化描述高度的抽象，严格的理论基础和方便的计算机表示。第4页,共73页，2024年2月25日，星期天2.1语言概述语言——形式化的内容提取单词(Token)：满足一定规则字符(Character)串句子(Sentence)：满足一定规则单词序列语言(Language)：满足一定条件的句子集合语言是字和组合字的规则——结构性描述例：一译开天第课今始编节上今天开始上第一节编译课第5页,共73页，2024年2月25日，星期天2.1语言概述程序设计语言——形式化的内容提取程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合程序(Program)：满足语法规则的语句序列语句(Sentence)：满足语法规则的单词序列单词(Token)：满足词法规则的字符串例变量=表达式if条件then语句while条件do语句call过程名(参数表)第6页,共73页，2024年2月25日，星期天2.1语言概述描述形式——文法语法——语句语句的组成规则描述方法：BNF范式、语法(描述)图词法——单词单词的组成规则描述方法：BNF范式、正规式第7页,共73页，2024年2月25日，星期天2.2基本定义字母表（Alphabet）是一个非空有穷集合，字母表中的元素称为该字母表的一个字母（Letter），也叫字符（Character）。例以下是不同的字母表： ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}第8页,共73页，2024年2月25日，星期天2.2基本定义字母表上符号串(String)的定义

(1)ε是∑上的一个符号串，叫做空串。(2)若x是∑上的符号串，而a是∑的元素,

则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作“字”(Word)。第9页,共73页，2024年2月25日，星期天2.2基本定义定义1设∑1、∑2是两个字母表，∑1与∑2

的乘积(Product)∑1∑2={ab|a∈∑1，b∈∑2}例:∑1={0,1},∑2={a,b},∑1∑2={0a,0b,1a,1b}定义2设∑是一个字母表，∑的n次幂(Power)递归地定义为：⑴∑0={ε}⑵∑n=∑n-1∑ n≥1例：∑13={000,001,010,011,100,101,110,111}第10页,共73页，2024年2月25日，星期天2.2基本定义定义3设∑是一个字母表，∑的正闭包(PositiveClosure)：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林闭包(KleeneClosure)：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……

第11页,共73页，2024年2月25日，星期天2.2基本定义例{0,1}+={0，1，00，01，11，000，001，010，011，100，……}{a，b，c，d}+={a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc……}第12页,共73页，2024年2月25日，星期天2.2基本定义例{0,1}*={ε，0，1，00，01，11，000，001，010，011，100，…}{a，b，c，d}*={ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc，…}第13页,共73页，2024年2月25日，星期天2.2基本定义定义5设∑是一个字母表，

L

∑*，L称为字母表∑上的一个语言（Language），

x∈L，x叫做L的一个句子。例：字母表{0，1}上的语言{0，1}{00，11}{0，1，00，11}{0，1，00，11，01，10}{00，11}*{01，10}*第14页,共73页，2024年2月25日，星期天2.2基本定义设s是符号串：01290273前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）长度：是该符号串中的符号的数目。例如|aab|=3,|ε|=0。第15页,共73页，2024年2月25日，星期天2.2基本定义符号串的连接和幂1.连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.幂：x0=

;x1=x;x2=xx;

……;xn=xn-1x;

例如,x=ba,x1=ba,x2=baba,x3=bababa,…...第16页,共73页，2024年2月25日，星期天2.3文法的定义如何实现语言结构的形式化描述？第17页,共73页，2024年2月25日，星期天考虑一个句子——文法要素的提取分析：Thegraywolfwilleatthegoat〈谓语〉〈主语〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词〈句子〉动原冠词名词Thegraywolfwilleatthegoat〈冠词〉第18页,共73页，2024年2月25日，星期天

句子

→

主语

谓语

主语

→

冠词

形容词

名词

谓语

→

动词

直接宾语

动词

→

助动词

动词原形

直接宾语

→

冠词

名词

产生句子的规则——从产生语言的角度

冠词

→

the

形容词

→

gray

助动词

→

will

动词原形

→

eat

名词

→

wolf

名词

→

goat第19页,共73页，2024年2月25日，星期天终结符号集VT={the，gray,wolf,will,eat,goat}非终结符号集VN={

句子

，

主语

，

谓语

，

冠词

，

形容词

，

名词

，

动词

，

直接宾语

，

助动词

，

动词原形

}语法规则集P={

句子

→

主语

谓语

，……}开始符号S=

句子

句子的语法组成

——终结符号集，非终结符号集，语法规则，开始符号第20页,共73页，2024年2月25日，星期天文法G的形式定义文法G为一个四元组:

Ｇ=(ＶT，ＶN，Ｐ，Ｓ)ＶT：终结符(Terminal)集ＶN：非终结符(Variable)集，ＶT∩ＶN=Φ语法范畴——某个语言结构Ｓ：开始符号(StartSymbol)，S∈ＶN至少在产生式左侧出现一次第21页,共73页，2024年2月25日，星期天文法G的形式定义Ｐ：产生式(Product)集合α→β，被称为产生式（定义式），读作：α定义为β。其中α∈(ＶT∪ＶN)+，且α中至少有ＶN中元素的一个出现。β∈(ＶT∪ＶN)*。α称为产生式α→β的左部(LeftPart)，β称为产生式α→β的右部(RightPart)。

第22页,共73页，2024年2月25日，星期天

句子

主语

谓语

冠词

形容词

名词

谓语

the

形容词

名词

谓语

thegray

名词

谓语

thegraywolf

谓语

thegraywolf

动词

直接宾语

thegraywolf

助动词

动词原形

直接宾语

thegraywolfwill

动词原形

直接宾语

thegraywolfwilleat

直接宾语

thegraywolfwilleat

冠词

名词

thegraywolfwilleatthe

名词

thegraywolfwilleatthegoat句子的派生（推导）___根据规则第23页,共73页，2024年2月25日，星期天

句子

thegraywolfwilleatthegoatthegraywolfwilleatthewolfthegraygoatwilleatthewolfthegraygoatwilleatthegray符合语法且符合语义的句子仅是：

thegraywolfwilleatthegoat还可以“得出”其他的句子第24页,共73页，2024年2月25日，星期天例2-1算术表达式的文法考虑简单算术表达式组成的语言递归定义——中缀表示标识符(id)（常数、变量）是表达式；表达式加一个表达式是表达式；表达式减一个表达式是表达式；表达式乘一个表达式是表达式；表达式除一个表达式是表达式；表达式加上括号后是表达式。第25页,共73页，2024年2月25日，星期天上次课主要内容编译程序实现技术自展自动生成：lex、Yacc语言信息交流的工具字和组合字的规则的统一体字母表上的语言字母表∑+

、∑*、a∈∑，x∈∑*、L

∑*、x∈L前缀、后缀、子串、串长、串的连接、串的幂第26页,共73页，2024年2月25日，星期天上次课主要内容文法通过刻画语言的结构描述语言用有穷描述无穷Ｇ=(ＶT，ＶN，Ｐ，Ｓ)表达式的递归定义第27页,共73页，2024年2月25日，星期天例2-1算术表达式的文法考虑用式子表示这个定义标识符(id)是表达式表达式加一个表达式是表达式E→idE→E+E表达式减一个表达式是表达式E→E-E表达式乘一个表达式是表达式E→E*E表达式除一个表达式是表达式E→E/E表达式加上括号后是表达式E→(E)第28页,共73页，2024年2月25日，星期天例2-1算术表达式的文法P:E→E+EE→E-EE→E*EE→E/EE→(E)E→idG=（{id，+，-，*，/，(，)}，{E}，P，E）约定：只写产生式简写E→E+E|E*E|(E)|id第29页,共73页，2024年2月25日，星期天产生式的简写对一组有相同左部的产生式α→β1，α→β2…，α→βn可以简单地记为：α→β1|β2|…|βn读作：α定义为或者β1，或者β2，…，或者βn。并且称它们为α产生式。β1，β2，…，βn称为候选式(Candidate)。第30页,共73页，2024年2月25日，星期天产生式规定的一些变换E由第一个候选式可以变成E+EE+E中的第一个E由第二个候选式可以变成E*E，从而E+E变成E*E+E根据第4个候选式，E*E+E中的E都可以变成id:E*E+E变成id*E+Eid*E+E变成id*E+idid*E+id变成id*id+id也就是说，根据第4个候选式，E*E+E经3步变换变成id*id+id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E第31页,共73页，2024年2月25日，星期天文法使用举例E

E+E （1）

id+E （4）

id+E*E （2）

id+id*E （4）

id+id*id （4）E

5id+id*id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E第32页,共73页，2024年2月25日，星期天直接推导与归约根据产生式对符号串进行变换的过程Ａ→γ是文法Ｇ的一个产生式，且α、β∈（ＶT∪ＶN）*，称αＡβ的直接推导/派生(Derive)出αγβ，也称αγβ直接归约(Reduce)为αＡβ。记为αＡβ

αγβ例：id+E

id+E*E第33页,共73页，2024年2月25日，星期天（多步）推导α0

α1

α2

…

αn记为α0

nαn

(恰用n步)α0

+αn

（至少一步）

α0

*αn

（若干步:零步或多步）第34页,共73页，2024年2月25日，星期天推导/归约举例E

E+E （1）串中含有变量

id+E （4）串中含有变量

id+E*E （2）串中含有变量

id+id*E （4）串中含有变量

id+id*id （4）串中没有变量到此串中已经没有（语法）变量了，不能再推了——得到句子1E→E+E2E→E*E3E→(E)4E→id第35页,共73页，2024年2月25日，星期天句型与句子E

5id+id*id定义:如果S

*x，且x∈ＶT*，则称x是G产生的一个句子(Sentence)E

E+E

E+E*EE

4id+id*E定义:如果S

*α，α∈(ＶT∪ＶN)*则称α是G产生的一个句型(SententialForm)第36页,共73页，2024年2月25日，星期天文法G产生的语言定义： L(G)={x|S

*xandx∈VT*}文法E→E+E|E*E|(E)|id可以派生出多少个句子？文法G的作用——语言的有穷描述以有限的规则描述无限的语言现象有限:产生式集合、终结符集合、非终结符集合无限：可以导出无穷多个句子（注：L也可是有穷）第37页,共73页，2024年2月25日，星期天id+id*id的不同推导E→E+E|E*E|(E)|idE

E+E

id+E

id+E*E

id+id*E

id+id*idE

E+E

E+E*E

E+E*id

E+id*id

id+id*idE

E*E

E+E*E

E+id*E

id+id*E

id+id*id不做限制句型

(sententialForm)（归约）E

*

id+id*id施于最右变量右句型/规范句型 (canonical~)(最左/规范归约)E

+

id+id*id施于最左变量左句型(left-~)（最右归约）

E

5

id+id*id第38页,共73页，2024年2月25日，星期天最左推导与最右推导最左推导(Left-mostDerivation)每次推导都施加在句型的最左边的语法变量上。——与最右归约对应最右推导(Right-mostDerivation)每次推导都施加在句型的最右边的语法变量上。——与最左归约（规范规约）对应的规范(Canonical)句型第39页,共73页，2024年2月25日，星期天短语(Phrase)自然语言中什么叫短语？如果Ｓ

*

αＡβ&A

+γ，则称γ是句型αγβ的相对于变量A的短语如果Ｓ

*

αＡβ&A

γ，则称γ是句型αγβ的相对于变量A的直接短语最左直接短语叫做句柄(Handle)第40页,共73页，2024年2月25日，星期天例：(直接)短语E

E+T

T+T

F+T

(E)+T

(E+T)+T

(E+T)+T

(T+T)+T

(F+T)+T

(a+T)+T

(a+T*F)+T

(a+F*F)+T

(a+b*F)+T

(a+b*c)+T

(a+b*c)+F

(a+b*c)+dE→E+T|TT→T*F|FF→(E)|id第41页,共73页，2024年2月25日，星期天句柄(Handle)：最左直接短语E→E+T|TT→T*F|FF→(E)|idE

E+T

T+T

F+T

(E)+T

(E+T)+T

(E+T)+T

(T+T)+T

(F+T)+T

(a+T)+T

(a+T*F)+T

(a+F*F)+T

(a+b*F)+T

(a+b*c)+T

(a+b*c)+F

(a+b*c)+d第42页,共73页，2024年2月25日，星期天例2-2标识符的文法1S→L|LT T→L|N|TL|TN L→a|b|c|d letter N→0|1|2|3|4|5 digit?正整数的文法；正实数的文法第43页,共73页，2024年2月25日，星期天2.４文法的分类(Chomsky体系)语言结构的复杂程度（形式语言）涉及文法的复杂程度、分析方法的选择如果G满足文法定义的要求，则Ｇ是０型文法（短语结构文法PSG:PhraseStructureGrammar）。L(G)为PSL。第44页,共73页，2024年2月25日，星期天上下文有关文法(CSG)若产生式集合中所有｜α｜≤｜β｜，除Ｓ→ε外，则Ｇ是１型文法即：上下文有关文法（CSG——ContextSensitiveGrammar）L(G)为1型/上下文有关/敏感语言(CSL)第45页,共73页，2024年2月25日，星期天上下文无关文法(CFG)若α∈ＶN，β∈(ＶN∪ＶT)*，则Ｇ是２型文法即：上下文无关文法(CFG:ContextFreeGrammar)L(G)为2型/上下文无关语言（CFL）例：程序设计语言的多数语法特征第46页,共73页，2024年2月25日，星期天例2-3标识符的文法2S→L|LT T→L|N|TL|TN L→a|b|c|d N→0|1|2|3|4|5S→a|b|c|d S→aT|bT|cT|dT T→a|b|c|d|0|1|2|3|4|5 T→aT|bT|cT|dT|0T T→1T|2T|3T|4T|5T第47页,共73页，2024年2月25日，星期天正规文法(RG)设Ａ、Ｂ∈ＶN，ａ∈ＶT或为

右线性(RightLinear)文法：Ａ→ａＢ或Ａ→ａ左线性(LeftLinear)文法：Ａ→Ｂａ或Ａ→ａ都是３型文法(正规文法RegularGrammar-RG)L(G)为3型/正规集/正则集/正则语言（RL）例：程序设计语言的多数词法特性左、右线性文法不可混用第48页,共73页，2024年2月25日，星期天例非CFL的文法L={anbncn|n>0}的文法S

aBC|aSBCCB

BCaB

abbB

bbbC

bc“可以证明”不存在CFGG,使L(G)=L第49页,共73页，2024年2月25日，星期天

在我们使用的程序语言中,有些语言结构并不是总能用上下文无关文法描述的。例L1={wcw|w∈{a,b}+}。例,aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。

例L2={anbmcndm|n,m≥0}，它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象。非CFL结构第50页,共73页，2024年2月25日，星期天Chomsky体系——总结Ｇ=(ＶT，ＶN，Ｐ，Ｓ)是一个文法,α→β∈P* G是0型文法，L(G)是0型语言；

---其能力相当于图灵机(TM)* |α|≤|β|:G是1型文法，L(G)是1型语言(除Ｓ→ε);

---其识别系统是线性界限自动机(LBA)* α∈ＶN:G是2型文法，L(G)是2型语言;

---其识别系统是不确定的下推自动机(PDA)* A→aB或A→a:G是右线性文法，L(G)是3型语言

A→Ba或A→ａ:G是左线性文法，L(G)是3型语言

---其识别系统是有穷自动机(FA)第51页,共73页，2024年2月25日，星期天四种文法之间的关系是将产生式作进一步限制而定义的。四种文法之间的逐级“包含”关系如下：2型文法1型文法0型文法3型文法Chomsky体系——总结第52页,共73页，2024年2月25日，星期天ＢＮＦ范式——Backus-NaurForm

Backus-NormalFormα→β表示为α∷＝β非终结符用“<”和“>”括起来终结符：基本符号集其他β(α1|α2…|αn)≡βα1|βα2…|βαn{α1|α2…|αn}nm

[α]≡α|ε……第53页,共73页，2024年2月25日，星期天ＢＮＦ范式——BackusNormalForm例简单算术表达式(只写产生式)<简单表达式>∷＝<简单表达式>+<简单表达式><简单表达式>∷＝<简单表达式>*<简单表达式><简单表达式>∷＝(<简单表达式>)<简单表达式>∷＝id即：<简单表达式>∷＝<简单表达式>+<简单表达式>| <简单表达式>*<简单表达式>|(<简单表达式>)|id哪些是终结符？哪些是变量？第54页,共73页，2024年2月25日，星期天例2-5句子结构的表示

(文法E→E+E|E*E|(E)|id

）EE+EE→E+EidE→idEE*E→E*EidE→ididE→idE

E+E

id+E

id+E*E

id+id*E

id+id*id一棵树！第55页,共73页，2024年2月25日，星期天上次课主要内容产生式的简写：

α→β1|β2|…|βn（候选式）文法的简写：只写产生式集、开始符约定直接派生/归约：αＡβ

αγβＡ→γN步派生/归约：αＡβ

NαγβＡ

Nγ句子与句型：S

*x S

*α语言：L(G)={x|S

*xandx∈VT*}第56页,共73页，2024年2月25日，星期天上次课主要内容短语：短语、直接短语、句柄Chomsky体系BNF范式最左推导（最右归约）最右推导（最左归约）规范推导/归约，规范句型例:(a1+a2)*a3E→E+T|E-T|TT→T*F|T/F|FF→(E)|id第57页,共73页，2024年2月25日，星期天2.5CFG的语法树ParseTree用树的形式表示句型的结构树根：开始符号中间结点：非终结符叶结点：终结符或者非终结符每个推导对应一个中间结点及其儿子——一个二级子树-直接短语又称为语法分析树第58页,共73页，2024年2月25日，星期天例短语与语法(分析)树

(文法E→E+E|E*E|(E)|id

）EE+Eid(a1)EE*id(a2)id(a3)短语——一棵子树的叶子！第59页,共73页，2024年2月25日，星期天短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。用子树解释短语，直接短语，句柄第60页,共73页，2024年2月25日，星期天E

E+T

T+T

F+T

a1+T

a1+T*F

a1+F*F

a1+a2*FE+T

T,T+TF,F+Ta1,a1+Ta1,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*FFa2a3

a1+a2*a3短语第61页,共73页，2024年2月25日，星期天二义性文法与先天二义性语言对同一句子存在两棵语法分析树在理论上不可判定EE*EidEE+ididEE+EEEid*idid第62页,共73页，2024年2月25日，星期天

1.描述一个句子的文法不是唯一的；

2.对于一个句子的分析应是唯一的。考虑表达式下面的文法G[E],其产生式如下：

E

E+E

E*E

(E)

id

对于句子a1+a2*a3,有如下两个最左推导：

E

E+E

a1+E

a1+E*E

a1+a2*E

a1+a2*a3E

E*E

E+E*E

a1+E*E

a1+a2*E

a1+a2*a3文法的二义性第63页,共73页，2024年2月25日，星期天

E

E+E

a1+E

a1+E*E

a1+a2*E

a1+a2*a3

E

E*E

E+E*E

a1+E*E

a1+a2*E

a1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3最左推导第64页,共73页，2024年2月25日，星期天

E

E*E

E*a3

E+E*a3

E+a2*a3

a1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3最右推导

E

E+E

a1+E

a1+E*E

a1+a2*E

a1+a2*a3第65页,共73页，2024年2月25日，星期天如果一个文法的句子存在两棵分析树,那么,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的;否则，该文法是无二义性的。几点说明：1.一般来说，程序语言存在无二义性文法，对于表达式来说，文法（2.1）是无二义