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

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

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

则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作“字”(Word)。第九页，共七十三页，编辑于2023年，星期二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}第十页，共七十三页，编辑于2023年，星期二2.2基本定义定义3设∑是一个字母表，∑的正闭包(PositiveClosure)：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林闭包(KleeneClosure)：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……第十一页，共七十三页，编辑于2023年，星期二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……}第十二页，共七十三页，编辑于2023年，星期二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，…}第十三页，共七十三页，编辑于2023年，星期二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}*第十四页，共七十三页，编辑于2023年，星期二2.2基本定义设s是符号串：01290273前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）长度：是该符号串中的符号的数目。例如|aab|=3,|ε|=0。第十五页，共七十三页，编辑于2023年，星期二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,…...第十六页，共七十三页，编辑于2023年，星期二2.3文法的定义如何实现语言结构的形式化描述？第十七页，共七十三页，编辑于2023年，星期二考虑一个句子——文法要素的提取分析：Thegraywolfwilleatthegoat〈谓语〉〈主语〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词〈句子〉动原冠词名词Thegraywolfwilleatthegoat〈冠词〉第十八页，共七十三页，编辑于2023年，星期二句子

→

主语

谓语主语

→

冠词

形容词

名词谓语

→

动词

直接宾语动词

→

助动词

动词原形直接宾语

→

冠词

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

→

the形容词

→

gray助动词

→

will动词原形

→

eat名词

→

wolf名词

→

goat第十九页，共七十三页，编辑于2023年，星期二终结符号集VT={the，gray,wolf,will,eat,goat}非终结符号集VN={句子，主语，谓语，冠词，形容词，名词，动词，直接宾语，助动词，动词原形

}语法规则集P={句子→主语谓语，……}开始符号S=句子句子的语法组成

——终结符号集，非终结符号集，语法规则，开始符号第二十页，共七十三页，编辑于2023年，星期二文法G的形式定义文法G为一个四元组:

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

第二十二页，共七十三页，编辑于2023年，星期二句子主语

谓语

冠词

形容词

名词

谓语

the形容词

名词

谓语

thegray名词

谓语

thegraywolf谓语

thegraywolf

动词

直接宾语

thegraywolf助动词

动词原形

直接宾语

thegraywolfwill动词原形

直接宾语

thegraywolfwilleat直接宾语

thegraywolfwilleat

冠词

名词

thegraywolfwilleatthe名词

thegraywolfwilleatthegoat句子的派生（推导）___根据规则第二十三页，共七十三页，编辑于2023年，星期二句子

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

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

、∑*、a∈∑，x∈∑*、L∑*、x∈L前缀、后缀、子串、串长、串的连接、串的幂第二十六页，共七十三页，编辑于2023年，星期二上次课主要内容文法通过刻画语言的结构描述语言用有穷描述无穷Ｇ=(ＶT，ＶN，Ｐ，Ｓ)表达式的递归定义第二十七页，共七十三页，编辑于2023年，星期二例2-1算术表达式的文法考虑用式子表示这个定义标识符(id)是表达式表达式加一个表达式是表达式E→idE→E+E表达式减一个表达式是表达式E→E-E表达式乘一个表达式是表达式E→E*E表达式除一个表达式是表达式E→E/E表达式加上括号后是表达式E→(E)第二十八页，共七十三页，编辑于2023年，星期二例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第二十九页，共七十三页，编辑于2023年，星期二产生式的简写对一组有相同左部的产生式α→β1，α→β2…，α→βn可以简单地记为：α→β1|β2|…|βn读作：α定义为或者β1，或者β2，…，或者βn。并且称它们为α产生式。β1，β2，…，βn称为候选式(Candidate)。第三十页，共七十三页，编辑于2023年，星期二产生式规定的一些变换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第三十一页，共七十三页，编辑于2023年，星期二文法使用举例EE+E （1）

id+E （4）

id+E*E （2）

id+id*E （4）

id+id*id （4）E5id+id*id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E第三十二页，共七十三页，编辑于2023年，星期二直接推导与归约根据产生式对符号串进行变换的过程Ａ→γ是文法Ｇ的一个产生式，且α、β∈（ＶT∪ＶN）*，称αＡβ的直接推导/派生(Derive)出αγβ，也称αγβ直接归约(Reduce)为αＡβ。记为αＡβαγβ例：id+Eid+E*E第三十三页，共七十三页，编辑于2023年，星期二（多步）推导α0α1α2…αn记为α0nαn

(恰用n步)α0+αn

（至少一步）

α0*αn

（若干步:零步或多步）第三十四页，共七十三页，编辑于2023年，星期二推导/归约举例EE+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第三十五页，共七十三页，编辑于2023年，星期二句型与句子E5id+id*id定义:如果S*x，且x∈ＶT*，则称x是G产生的一个句子(Sentence)EE+EE+E*EE4id+id*E定义:如果S*α，α∈(ＶT∪ＶN)*则称α是G产生的一个句型(SententialForm)第三十六页，共七十三页，编辑于2023年，星期二文法G产生的语言定义： L(G)={x|S*xandx∈VT*}文法E→E+E|E*E|(E)|id可以派生出多少个句子？文法G的作用——语言的有穷描述以有限的规则描述无限的语言现象有限:产生式集合、终结符集合、非终结符集合无限：可以导出无穷多个句子（注：L也可是有穷）第三十七页，共七十三页，编辑于2023年，星期二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-~)（最右归约）

E5

id+id*id第三十八页，共七十三页，编辑于2023年，星期二最左推导与最右推导最左推导(Left-mostDerivation)每次推导都施加在句型的最左边的语法变量上。——与最右归约对应最右推导(Right-mostDerivation)每次推导都施加在句型的最右边的语法变量上。——与最左归约（规范规约）对应的规范(Canonical)句型第三十九页，共七十三页，编辑于2023年，星期二短语(Phrase)自然语言中什么叫短语？如果Ｓ*

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

αＡβ&Aγ，则称γ是句型αγβ的相对于变量A的直接短语最左直接短语叫做句柄(Handle)第四十页，共七十三页，编辑于2023年，星期二例：(直接)短语EE+TT+TF+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第四十一页，共七十三页，编辑于2023年，星期二句柄(Handle)：最左直接短语E→E+T|TT→T*F|FF→(E)|idEE+TT+TF+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第四十二页，共七十三页，编辑于2023年，星期二例2-2标识符的文法1S→L|LT T→L|N|TL|TN L→a|b|c|d letter N→0|1|2|3|4|5 digit?正整数的文法；正实数的文法第四十三页，共七十三页，编辑于2023年，星期二2.４文法的分类(Chomsky体系)语言结构的复杂程度（形式语言）涉及文法的复杂程度、分析方法的选择如果G满足文法定义的要求，则Ｇ是０型文法（短语结构文法PSG:PhraseStructureGrammar）。L(G)为PSL。第四十四页，共七十三页，编辑于2023年，星期二上下文有关文法(CSG)若产生式集合中所有｜α｜≤｜β｜，除Ｓ→ε外，则Ｇ是１型文法即：上下文有关文法（CSG——ContextSensitiveGrammar）L(G)为1型/上下文有关/敏感语言(CSL)第四十五页，共七十三页，编辑于2023年，星期二上下文无关文法(CFG)若α∈ＶN，β∈(ＶN∪ＶT)*，则Ｇ是２型文法即：上下文无关文法(CFG:ContextFreeGrammar)L(G)为2型/上下文无关语言（CFL）例：程序设计语言的多数语法特征第四十六页，共七十三页，编辑于2023年，星期二例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第四十七页，共七十三页，编辑于2023年，星期二正规文法(RG)设Ａ、Ｂ∈ＶN，ａ∈ＶT或为右线性(RightLinear)文法：Ａ→ａＢ或Ａ→ａ左线性(LeftLinear)文法：Ａ→Ｂａ或Ａ→ａ都是３型文法(正规文法RegularGrammar-RG)L(G)为3型/正规集/正则集/正则语言（RL）例：程序设计语言的多数词法特性左、右线性文法不可混用第四十八页，共七十三页，编辑于2023年，星期二例非CFL的文法L={anbncn|n>0}的文法SaBC|aSBCCBBCaBabbBbbbCbc“可以证明”不存在CFGG,使L(G)=L第四十九页，共七十三页，编辑于2023年，星期二

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

例L2={anbmcndm|n,m≥0}，它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象。非CFL结构第五十页，共七十三页，编辑于2023年，星期二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)第五十一页，共七十三页，编辑于2023年，星期二四种文法之间的关系是将产生式作进一步限制而定义的。四种文法之间的逐级“包含”关系如下：2型文法1型文法0型文法3型文法Chomsky体系——总结第五十二页，共七十三页，编辑于2023年，星期二ＢＮＦ范式——Backus-NaurForm

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

[α]≡α|ε……第五十三页，共七十三页，编辑于2023年，星期二ＢＮＦ范式——BackusNormalForm例简单算术表达式(只写产生式)<简单表达式>∷＝<简单表达式>+<简单表达式><简单表达式>∷＝<简单表达式>*<简单表达式><简单表达式>∷＝(<简单表达式>)<简单表达式>∷＝id即：<简单表达式>∷＝<简单表达式>+<简单表达式>| <简单表达式>*<简单表达式>|(<简单表达式>)|id哪些是终结符？哪些是变量？第五十四页，共七十三页，编辑于2023年，星期二例2-5句子结构的表示

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

）EE+EE→E+EidE→idEE*E→E*EidE→ididE→idEE+Eid+Eid+E*Eid+id*Eid+id*id一棵树！第五十五页，共七十三页，编辑于2023年，星期二上次课主要内容产生式的简写：

α→β1|β2|…|βn（候选式）文法的简写：只写产生式集、开始符约定直接派生/归约：αＡβαγβＡ→γN步派生/归约：αＡβNαγβＡNγ句子与句型：S*x S*α语言：L(G)={x|S*xandx∈VT*}第五十六页，共七十三页，编辑于2023年，星期二上次课主要内容短语：短语、直接短语、句柄Chomsky体系BNF范式最左推导（最右归约）最右推导（最左归约）规范推导/归约，规范句型例:(a1+a2)*a3E→E+T|E-T|TT→T*F|T/F|FF→(E)|id第五十七页，共七十三页，编辑于2023年，星期二2.5CFG的语法树ParseTree用树的形式表示句型的结构树根：开始符号中间结点：非终结符叶结点：终结符或者非终结符每个推导对应一个中间结点及其儿子——一个二级子树-直接短语又称为语法分析树第五十八页，共七十三页，编辑于2023年，星期二例短语与语法(分析)树

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

）EE+Eid(a1)EE*id(a2)id(a3)短语——一棵子树的叶子！第五十九页，共七十三页，编辑于2023年，星期二短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。用子树解释短语，直接短语，句柄第六十页，共七十三页，编辑于2023年，星期二EE+TT+TF+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*FFa2a3a1+a2*a3短语第六十一页，共七十三页，编辑于2023年，星期二二义性文法与先天二义性语言对同一句子存在两棵语法分析树在理论上不可判定EE*EidEE+ididEE+EEEid*idid第六十二页，共七十三页，编辑于2023年，星期二

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

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

EE+EE*E(E)id

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

EE+Ea1+Ea1+E*Ea1+a2*Ea1+a2*a3EE*EE+E*Ea1+E*Ea1+a2*Ea1+a2*a3文法的二义性第六十三页，共七十三页，编辑于2023年，星期二

EE+Ea1+Ea1+E*Ea1+a2*Ea1+a2*a3

EE*EE+E*Ea1+E*Ea1+a2*Ea1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3最左推导第六十四页，共七十三页，编辑于2023年，星期二

EE*EE*a3

E+E*a3E+a2*a3

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

EE+Ea1+Ea1+E*Ea1+a2*Ea1+a2*a3第六十五页，共七十三页，编辑于2023年，星期二如果一个文法的句子存在两棵分析树,那么,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的;否则，该文法是无二义性的。几点说明：1.一般来说，程序语言存在无