编译原理语言概述

编译原理语言概述演示文稿目前一页\总数七十四页\编于十点2.1语言概述什么是语言？目前二页\总数七十四页\编于十点2.1语言概述语言特征自然语言(NaturalLanguage)是人与人的通讯工具语义(semantics):环境、背景知识、语气、二义性——难以形式化计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(semantics)——易于形式化：严格目前三页\总数七十四页\编于十点2.1语言概述语言的描述方法——现状自然语言：自然、方便-非形式化数学语言（符号）：严格、准确-形式化形式化描述高度的抽象，严格的理论基础和方便的计算机表示。目前四页\总数七十四页\编于十点2.1语言概述语言——形式化的内容提取语言(Language)：满足一定条件的句子集合句子(Sentence)：满足一定规则的单词序列单词(Token)：满足一定规则的字符(Character)串语言是字和组合字的规则例（自然语言：第译始一天课今开编上节）今天开始上第一节编译课目前五页\总数七十四页\编于十点2.1语言概述语言是字及其组合规则的统一体目前六页\总数七十四页\编于十点2.1语言概述程序设计语言——形式化的内容提取程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合。程序(Program)：满足语法规则的语句序列。语句(Sentence)：满足语法规则的单词序列。单词(Token)：满足词法规则的字符串。例：变量:=表达式if条件then语句while条件do语句call过程名(参数表)目前七页\总数七十四页\编于十点2.1语言概述描述形式——文法语法——语句语句的组成规则描述方法：BNF范式、语法(描述)图词法——单词单词的组成规则描述方法：BNF范式、正规式目前八页\总数七十四页\编于十点形式语言于自动机理论的产生与作用语言学家Chomsky最初从产生语言的角度研究语言。1956年，通过抽象，他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法（Grammar），该文法所能产生的所有句子组成的集合就是该文法产生的语言。克林（Kleene）在1951年到1956年间，从识别语言的角度研究语言，给出了语言的另一种描述。克林是在研究神经细胞中，建立了自动机，他用这种自动机来识别语言：对于按照一定的规则构造的任一个自动机，该自动机就定义了一个语言，这个语言由该自动机所能识别的所有句子组成。目前九页\总数七十四页\编于十点形式语言于自动机理论的产生与作用1959年，Chomsky通过深入研究，将他本人的研究成果与克林的研究成果结合了起来，不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性。20世纪50年代，人们用巴科斯范式（BackusNourForm或BackusNormalForm，简记为BNF）成功地对高级语言ALGOL-60进行了描述。实际上，巴科斯范式就是上下文无关文法（ContextFreeGrammar）的一种表示形式。这一成功，使得形式语言在20世纪60年代得到了大力的发展。目前十页\总数七十四页\编于十点形式语言于自动机理论的产生与作用形式语言与自动机理论除了在计算机科学领域中的直接应用外，更在计算学科人才的计算思维的培养中占有极其重要的地位计算思维能力的培养，主要是由基础理论系列课程实现的，该系列主要由从数学分析开始到形式语言结束的一些数学和抽象程度比较高的内容的课程组成。它们构成的是一个梯级训练系统。在此系统中，连续数学、离散数学、计算模型等三部分内容要按阶段分开，三个阶段对应与本学科的学生在大学学习期间的思维方式和能力的变化与提高过程的三个步骤。目前十一页\总数七十四页\编于十点计算思维能力的培养过程中学数学 数学分析离散数学

具体.静止 变量.运动 离散.抽象 形式.模型

(基本运算系统) (计算系统)

实数 抽象集合

单一、具体的计算 一般、形式化的计算 （实例计算） （模型化计算）

形式语言与自动机理论运算范围特征高水平计算专业人才的计算思维能力的渐进培养目前十二页\总数七十四页\编于十点2.2基本定义字母表（Alphabet）∑是一个非空有穷集合，字母表中的元素称为该字母表的一个字母（Letter），也叫字符（Character）。例以下是不同的字母表： ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}

(4)ASCII字母表目前十三页\总数七十四页\编于十点2.2基本定义符号串的定义(1)ε是∑上的一个符号串。(2)若x是∑上的符号串，而a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的任何有穷序列被称之为该字母表上的符号串,也称作"字"。目前十四页\总数七十四页\编于十点2.2基本定义设s是符号串，则s的前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零或多于零个符号(这些符号不要求连续）逆转（用SR表示）：将S中的符号按相反次序写出而得到的符号串长度：是该符号串中的符号的数目。例如|aab|=3,|ε|=0。目前十五页\总数七十四页\编于十点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,……目前十六页\总数七十四页\编于十点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}目前十七页\总数七十四页\编于十点2.2基本定义定义3设∑是一个字母表，∑的正闭包(PositiveClosure)定义为：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林闭包(KleeneClosure)为：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……

目前十八页\总数七十四页\编于十点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……}目前十九页\总数七十四页\编于十点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，…}

目前二十页\总数七十四页\编于十点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}*目前二十一页\总数七十四页\编于十点2.3文法的定义如何实现语言结构的形式化描述？目前二十二页\总数七十四页\编于十点考虑一个句子——文法要素的提取分析：Thegreywolfwilleatthegoat〈谓语〉〈主语〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词〈句子〉动原冠词名词Thegreywolfwilleatthegoat〈冠词〉目前二十三页\总数七十四页\编于十点句子主语谓语（1）主语冠词形容词名词（2）冠词the形容词grey谓语

动词直接宾语（5）

动词助动词动词原形（6）助动词will动词原形eat直接宾语

冠词名词（9）名词wolf名词goat句子的组成规则问题：如何用符号来描述？即如何形式化？目前二十四页\总数七十四页\编于十点终结符号集VT= {the，grey,wolf,will,eat,goat}非终结符号集VN= {句子，主语，谓语，冠词，形容词，名词，

动词，直接宾语，助动词，动词原形}语法规则集P={句子

主语谓语，……}开始符号S=句子定义句子的规则的语法组成

__终结符号集，非终结符号集，语法规则，开始符号问题：有了定义句子的规则，如何判定某一句子是否属于某语言？目前二十五页\总数七十四页\编于十点句子主语谓语冠词形容词名词谓语the形容词名词谓语thegrey名词谓语thegreywolf谓语thegreywolf

动词直接宾语

…...thegreywolfwilleatthegoat句子的派生（推导）-从产生语言的角度

句子的归约-从识别语言的角度-均根据规则目前二十六页\总数七十四页\编于十点句子thegreywolfwilleatthegoat

thegreywolfwilleatthewolf

thegreygoat

willeatthewolfthegreygoat

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

thegreywolfwilleatthegoat句子的语义要求目前二十七页\总数七十四页\编于十点文法G的形式定义文法G为一个四元组: Ｇ=(ＶT，ＶN，Ｐ，Ｓ)ＶT：终结符(Terminal)集ＶN：非终结符(Variable)集，ＶT∩ＶN=Φ语法成分——代表某个语言的各种子结构Ｓ：开始符号(StartSymbol)，S∈ＶN代表文法所定义的语言，至少在产生式左侧出现一次目前二十八页\总数七十四页\编于十点文法G的形式定义Ｐ：产生式(Product)集合α→β，被称为产生式（定义式），读作：α定义为β。其中α∈(ＶT∪ＶN)+，且α中至少有ＶN中元素的一个出现。β∈(ＶT∪ＶN)*。α称为产生式α→β的左部(LeftPart)，β称为产生式α→β的右部(RightPart)。产生式定义各个语法成分的结构（组成规则）目前二十九页\总数七十四页\编于十点例2-1算术表达式的文法递归定义——中缀表示标识符(id)（常数、变量）是表达式(E)；表达式加一个表达式是表达式；表达式减一个表达式是表达式；表达式乘一个表达式是表达式；表达式除一个表达式是表达式；表达式加上括号后是表达式；目前三十页\总数七十四页\编于十点例2-1算术表达式的文法考虑简单算术表达式组成的语言G=({id，+，*，(，)}，{E}，P，E)P:E→E+EE→E*EE→(E)E→id约定：只写产生式简写E→E+E|E*E|(E)|id（2.1）目前三十一页\总数七十四页\编于十点产生式的简写对一组有相同左部的产生式α→β1，α→β2…，α→βn可以简单地记为：α→β1|β2|…|βn读作：α定义为或者β1，或者β2，…，或者βn。并且称它们为α产生式。β1，β2，…，βn称为候选式(Candidate)。目前三十二页\总数七十四页\编于十点基于产生式的变换--推导或归约E→E+E|E*E|(E)|idE由第一个候选式可以变成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+id目前三十三页\总数七十四页\编于十点直接推导与归约根据产生式对符号串进行变换的过程Ａ→γ是文法Ｇ的一个产生式，且α、β∈（ＶT∪ＶN）*，称αＡβ直接推导/派生(Derive)出αγβ，也称αγβ直接归约(Reduce)为αＡβ。记为αＡβαγβ例：id+Eid+E*E目前三十四页\总数七十四页\编于十点（多步）推导α0α1α2…αn记为α0n

αn

(恰用n步)

α0+

αn

（至少一步）

α0*

αn

（若干步:零步或多步）目前三十五页\总数七十四页\编于十点推导/归约举例EE+E （1）串中含有变量

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

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

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

id+id*id （4）串中没有变量到此串中已经没有（语法）变量了，不能再推导了1、E→E+E2、E→E*E3、E→(E)4、E→id目前三十六页\总数七十四页\编于十点句型与句子E5id+id*id句子:如果S*x，且x∈ＶT*，则称x是G产生的一个句子(Sentence)EE+EE+E*EE4id+id*E句型:如果S*α，α∈(ＶT∪ＶN)*则称α是G产生的一个句型(SententialForm)目前三十七页\总数七十四页\编于十点文法G产生的语言 Ｌ(Ｇ)＝{x｜Ｓ*

xandx∈ＶT*}文法E→E+E|E*E|(E)|id可以派生出多少个句子？文法G的作用——语言的有穷描述以有限的规则描述无限的语言现象有限：产生式集合、终结符集合、非终结符集合无限：可以导出无穷多个句子（L也可是有穷）目前三十八页\总数七十四页\编于十点id+id*id的不同推导E→E+E|E*E|(E)|idEE+Eid+E

id+E*Eid+id*E

id+id*idEE+E

E+E*E

E+E*idE+id*id

id+id*idEE*EE+E*EE+id*Eid+id*Eid+id*id不做限制句型(sententialForm)（归约）E*

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

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

id+id*id目前三十九页\总数七十四页\编于十点最左推导与最右推导最左推导(Left-mostDerivation)每次推导都施加在句型的最左边的语法变量上。——与最右归约对应最右推导(Right-mostDerivation)每次推导都施加在句型的最右边的语法变量上。——与最左归约（规范规约）对应的规范(Canonical)句型目前四十页\总数七十四页\编于十点短语(Phrase)什么叫短语？如果Ｓ*

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

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

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

例2.10L2={anbmcndm|n,m≥0}，它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象。非上下文无关的语言结构目前五十一页\总数七十四页\编于十点Chomsky体系——总结Ｇ=(ＶT，ＶN，Ｐ，Ｓ)是一个文法,α→β∈P* G是0型文法，L(G)是0型语言；---其能力相当于图灵机* |α|≤|β|:G是1型文法，L(G)是1型语言(除Ｓ→ε);---其识别系统是线性界限自动机* α∈ＶN:G是2型文法，L(G)是2型语言;---其识别系统是不确定的下推自动机* A→aB或A→a:G是右线性文法，L(G)是3型语言

A→Ba或A→ａ:G是左线性文法，L(G)是3型语言---其识别系统是有穷自动机目前五十二页\总数七十四页\编于十点文法的类型四种文法之间的关系是将产生式作进一步限制而定义的。四种文法之间的逐级“包含”关系如下：2型文法1型文法0型文法3型文法目前五十三页\总数七十四页\编于十点ＢＮＦ范式——Backus-NaurForm

Backus-NormalFormα→β表示为α∷＝β非终结符用“<”和“>”括起来终结符：基本符号集其他β(α1|α2…|αn)≡βα1|βα2…|βαn[α]≡α|ε……目前五十四页\总数七十四页\编于十点ＢＮＦ范式——BackusNormalForm例简单算术表达式(只写产生式)<算术表达式>∷＝<简单表达式>+<简单表达式><简单表达式>∷＝<简单表达式>*<简单表达式><简单表达式>∷＝(<简单表达式>)<简单表达式>∷＝id即：<算术表达式>∷＝<简单表达式>+<简单表达式>|<简单表达式>*<简单表达式>|(<简单表达式>)|id哪些是终结符？哪些是变量？目前五十五页\总数七十四页\编于十点例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一棵树！目前五十六页\总数七十四页\编于十点2.5CFG的分析树ParseTree用树的形式表示句型的生成树根：开始符号中间结点：非终结符叶结点：终结符或者非终结符每个推导对应一个中间结点及其儿子——一个二级子树-直接短语又称为语法分析树目前五十七页\总数七十四页\编于十点短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。用子树解释短语，直接短语，句柄目前五十八页\总数七十四页\编于十点EE+TT+TF+T

a1+T

a1+T*F

a1+F*F

a1+a2*FE+TT,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短语目前五十九页\总数七十四页\编于十点例短语与分析树

(文法E→E+E|E*E|(E)|id）EE+EidEE*idid一棵子树的叶子！目前六十页\总数七十四页\编于十点二义性文法与先天二义性语言对同一句子存在两棵语法分析树在理论上不可判定EE*EidEE+ididEE+EEEid*idid目前六十一页\总数七十四页\编于十点1.描述一个句子的文法不是唯一的；2.对于一个句子的分析应是唯一的。考虑表达式下面的文法G[E],其产生式如下：

EE+EE*E(E)a

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

EE+Ea+Ea+E*Ea+a*Ea+a*a

EE*EE+E*Ea+E*Ea+a*Ea+a*a文法的二义性目前六十二页\总数七十四页\编于十点

EE+Ea+Ea+E*Ea+a*Ea+a*a

EE*EE+E*Ea+E*Ea+a*Ea+a*aEE+EE*EaaaEE*E+EEaaa最左推导目前六十三页\总数七十四页\编于十点

EE+EE+E*EE+E*aE+a*aa+a*a

EE*EE*aE+E*aE+a*aa+a*aEE+EE*EaaaEE*E+EEaaa最右推导目前六十四页\总数七十四页\编于十点如果一个文法的句子存在两棵分析树,那么,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的;否则，该文法是无二义性的。几点说明：1.一般来说，程序语言存在无二义性文法，对于表达式来说，文法（2.1）是二义性的。对于条件语句，经常使用二义性文法描述它：SifexprthenSifexprthenSelseSother二义性的句子:ife1thenife2thens1elses2

二义性（歧义性，ambiquity)的定义目前六十五页\总数七十四页\编于十点

下面是

Smatched_sunmatched_smatched_sifexprthenmatched_s