编译原理ch2剖析课件

2023/7/22华东师大计算机科学技术系1第二章文法与语言的基本知识2.1概述程序设计语言是一种形式语言，与自然语言既有相似的性质又有本质的不同。最主要的区别是：形式语言的规则简单、严格、无例外、无二义性。编译程序的正确转换建立在对程序设计语言的精确定义和描述基础上。语法——文法是描述语言语法的形式规则语义——语言中各语句的含义语用——从使用者的角度对语言的描述本章将介绍形式语言和形式文法的基本概念，这是整个编译原理的基础。2023/7/22华东师大计算机科学技术系2基本概念2.2基本概念2.2.1符号与符号串用程序语言书写的程序一般由一些基本符号组成。下面是一些常见的基本符号： 字母：a,b,c,…,x,y,z

数字：0,1,…,9

其他符号：+,-,*,/,=,:，等

在这些符号的基础上，组成如if,then,else,for等关键字、程序的标识符和常量，并进一步组成用户程序。

定义1符号的非空有限集合称为字母表。常用V、表示。

2023/7/22华东师大计算机科学技术系3符号与符号串例1：1＝{0,1} 1是二进制数的字母表

2＝{a,b…….z} 2是英文小写字母 3＝{A….Z,0….9,+,-,*,/,.,(,),=,$,’,:}3是FORTRAN4语言的字母表注意：符号可能是字符的组合如：5＝{ASCII码}则<=为一个符号再如：pascal语言的:＝C语言的&&等等2023/7/22华东师大计算机科学技术系4符号与符号串

定义2：字母表(符号的非空有限集合)V上的符号 串的递归定义如下：①空串（一个不含任何元素的符号串）是字母表 V上的符号串。空串用希腊字母表示。②字母表V中任何一个元素a，是字母表V上的符 号串。

③

若x，y是字母表V上的符号串，则它们的并置（将符号串y的符号依次写在符号串x后面所得的符号串）也是字母表V上的符号串，记以xy。

注意：‘’与‘’的不同！

2023/7/22华东师大计算机科学技术系52.2.2符号串的运算符号串x中的元素的个数称为符号串x的长度，记以|x|。设z＝xy是字母表V上的符号串，则x是符号串z的头（或符号串z的前缀），而y是符号串z的尾（或符号串z的后缀）。若|x|＝1，则x是符号串z的头符号。同样，若|y|=1，则y是符号串z的尾符号。注意，空串是任何一个符号串的头和尾。当y≠

称x是z的真前缀。当x≠

称y是z的真后缀。并置（连接）是一种运算，满足结合律，但不满足交换律。2023/7/22华东师大计算机科学技术系6例2：字母表1＝{0,1}，0，1，00，11，10，01，……是1上的符号串如x=1001 y=010 则连接xy=1001010 yx=0101001 都是1上的符号串|x|=4 |y|=3，1，10，100，1001都是x的头，1是x的头符号 ，1，01，001，1001都是x的尾，1是x的尾符号，1，10，100，1001都是x的前缀，，1，10，100是真前缀

1001，001，01，1，都是x的后缀，001，01，1，是真后缀2023/7/22华东师大计算机科学技术系7定义3：设A，B是二个符号串集合，定义：A∩B={a|a∈A且a∈B}A∪B={a|a∈A或者a∈B}A0＝{} An=AAn-1(n>0)A*=A0∪

A1∪A2∪…∪An

∪……

称为A的闭包A＋=A1∪A2∪…∪An∪……

称为A的正闭包

2023/7/22华东师大计算机科学技术系8由定义可知：A+=AA*=A*A例3：令A=1＝{0,1}A*={，0，1，00，10，01，11…….}A+={0，1，00，10，01，11…….}令A=3

则任一FORTRAN4语言所编写的程序P，有PA*2023/7/22华东师大计算机科学技术系92.3文法和语言2.3.1文法形式语言是字母表V上所有符号串的集合，当该集合为有限集时可以枚举其全部句子，如为无限集则需找出句子的规律，用文法来表示。定义4：上下文无关文法G是一个四元组：

G＝（VT，VN，P，<S>）其中，VT是非空有限集合，元素称为终结符。

VN是非空有限集合，元素称为非终结符。

P是由产生式组成的非空有限集合。

<S>VN，是文法G的开始符号。常把文法G记为G[<S>]。2023/7/22华东师大计算机科学技术系10产生式（又称复写/产生规则）产生式是一有序对偶（U，x），一般记以 U→x（或U::=x)

其中：U称为产生式左部，x称为产生式的右部。符号‘→’（或‘::=’）称为元符号含义为“由…..构成”或“被定义为”记V＝VN∪VT

一般要求：VN∩VT＝φ

、UV，xV*，特别：

UVN

xV

*

且<S>至少在某产生式左部 出现一次，称文法G[<S>]为上下文无关文法。

2023/7/22华东师大计算机科学技术系11例4：简单算术表达式文法G[<E>]定义为：

VT＝{+，*，(，)，i} VN＝{<E>，<T>,<F>}P:<E>→<E>+<T> <E>→<T> <T>→<T>*<F> <T>→<F> <F>→(<E>) <F>→i

文法G是上下文无关文法2023/7/22华东师大计算机科学技术系12扩展的BNF表示(见P62）扩展的BNF（BackusNaurForm)表示引入一些元符号‘|’ 表示‘或’ 对<U>→x <U>→y: 可表示为：<U>→x|y|…..|z:<U>→z}2023/7/22华东师大计算机科学技术系13‘{’

‘}’表示重复出现n次。 如：{α}表示α连续出现i次，0<=i<=n {α}表示α可连续出现n次，i<=n<=j

例5：产生式<序列>→<语句> <序列>→<序列>；<语句>

与<序列>→<语句>{；<语句>}等价‘[’

‘]’表示重复出现0次或1次。

‘(’

‘)’表示提取公共符号后留下的 例6：<A>→+<T>|-<T>与<A>→(+|-)<T>等价2023/7/22华东师大计算机科学技术系14语言2.3.2语言定义5：设G是一个文法。如果v=x<U>y，w=xuy

其中：x，yV*，且<U>→uP， 则称字符串v直接推导出字符串w。有时候也称为w是v的一个直接推导，或者称w直接归约为v，记为vw。如果存在一个直接推导序列：v=u0u1u2…un=w，则称v推导出字符串w，或者称w归约为v，记为v+w。若v=w或v+w，则为以v*w。2023/7/22华东师大计算机科学技术系15直接推导与推导例7：设有文法G1[<S>]的产生式集P为：

<S>→<N><N>→<D>|<N><D><D>→0|1|2|…|9

对如下推导：<S><N><N><D><N><D><D><D><D><D>0<D><D>02<D>028

称这样的推导为最左推导。2.<S><N><N><D><N>8<N><D>8<N>28<D>28028

称这样的推导为最右推导。2023/7/22华东师大计算机科学技术系16直接推导与推导最右推导又称规范推导，记为。规范推导的逆过程称为规范归约。R2023/7/22华东师大计算机科学技术系17句型、句子与语言定义6：设G[<S>]是一文法，若<S>*w，w

(VN∪VT)*，则称w为文法G[<S>]一个句型。特别：若w

VT*，称w是文法G[<S>]一个句子。文法G[<S>]句子的全体所组成的集合称为该文法所产生的语言，记以L（G[<S>]）。即L(G[<S>]）={w|<S>*w，且wVT*}。例8：对例7的G1[<S>]

<S>

、<N><D>、0<D><D>、028是文法的句型

028是G1的一个句子。语言L(G1[<S>])是什么？如何表示一个语言？2023/7/22华东师大计算机科学技术系18语言语言L(G1[<S>])是一个具有无限多句子的集合，称为无限语言。可以用有限的集合的形式来定义一个无限多句子的语言。给定一个文法，就能唯一确定其语言。给定一种语言，能确定其对应的文法，但文法不唯一。对给定的文法G及任意的符号串w，能否用有限的方法来判定w是否是G的一个句子（句型）？2023/7/22华东师大计算机科学技术系19语言语言L(G)有无限多个句子，这与G的产生式集合P中某些产生式的递归性有关：1.

若<U>→<U>……

P称为直接左递归若<U>→……<U>……

P称为直接递归若<U>→………<U>

P称为直接右递归2.

若<U>

+<U>………

称为左递归若<U>

+…<U>……

称为递归若<U>

+………<U>

称为右递归对文法G1、G2，如L(G1)=L(G2)

称文法G1、G2等价2023/7/22华东师大计算机科学技术系20短语与句柄2.3.3短语与句柄定义7：设G[<S>]是一个文法，并设w=xuy是该文法的一个句型。若<S>*x<U>y且<U>+u，则称u为句型w=xuy对非终结符<U>的一个短语。若<S>*x<U>y且<U>u，则称u为句型w=xuy相对于非终结符<U>的一个简单(直接）短语。任何一个句型的最左简单短语称为柄短语（句柄）。含有终结符的短语，并且不存在也具有这种性质真子串的短语称为素短语。2023/7/22华东师大计算机科学技术系21P30习题22.12.22.32.42.72.10补充题： 试为如下的语言构造二个（或二个以上的）等价文法，它们接受相同的语言。 ①L1={a2n

b|n≥1}②L2={aibjck|i,j,k≥1}习题2023/7/22华东师大计算机科学技术系22语法树（推导树）2.4语法树与二义性2.4.1语法树（又称推导树、分析树）用特殊的树的形式来表示推导一个推导 一棵推导树注意：这是一种专为推导的表示而设计的特 殊的树 2023/7/22华东师大计算机科学技术系23推导树的构造与表示方法：对文法G=（VT，VN，P，<S>）树的每个结点对应一个文法符号，vV∪{}根结点是文法开始符号<S>对<A>VN为标记的结点，其所有的子结点（若有的话）则从左至右标记为x1,x2,…xn,且<A>→x1,x2,…xnP若某结点标记为，则必为叶结点，且为其 父结点的唯一子结点。2023/7/22华东师大计算机科学技术系24例1：表达式文法G[<E>]：

<E>→<E>+<T>|<T> <T>→<T>*<F>|<F> <F>→(<E>)|i对句型i*(<E>)的推导为：

<E><T><T>*<F><F>*<F>i*<F> i*(<E>)2023/7/22华东师大计算机科学技术系25对应的推导树为：

注意推导树的特殊性2023/7/22华东师大计算机科学技术系26语法树与短语使用推导树计算句型（句子）的短语简单、明了推导<S>*x<U>y <U>+u等价于： 等价于：

<S> <U> x<U>y u2023/7/22华东师大计算机科学技术系27因此称u是句型xuy(对<U>)的一个短语等价于：

<S> x<U>y u以为子树根的叶结点的全体<U>2023/7/22华东师大计算机科学技术系28若子树高度为1，则u还是简单短语，最左简单短语为句柄。若u是含有终结符的最小的短语，则为素短语，句型最左边的素短语称为最左素短语（P74）。例2：例1的文法G[<E>]和句型i*(<E>)容易从推导树中看出：短语：i,i*(<E>),(<E>)简单短语：i，(<E>)句柄：i素短语：i，(<E>)2023/7/22华东师大计算机科学技术系29文法的二义性2.4.2文法的二义性定义8：若文法G的一个句子有两棵（或两棵以上）的分析树，则称该句子是二义性的。若文法含有二义性句子，称该文法是二义性文法，否则称该文法是无二义的。例3：文法G1[<E>] <E>→<E>+<E>|<E>*<E>|(<E>)|i

对句子i+i*i有两棵不同的推导树2023/7/22华东师大计算机科学技术系30文法的二义性<E><E><E>*<E><E>+iii表示先‘＋’后‘*’表示先‘*’后‘＋’<E><E><E>+<E><E>*iii2023/7/22华东师大计算机科学技术系31对文法的二义性讨论一个句子有两棵不同的推导树，说明其含义（语义）是不唯一的，这给编译带来问题（不确定）。对某些二义性文法，如果确定其中一种含义（语义）而排除另一种（或多种）含义（称为消除二义性规则），则可将其改造成等价的无二义性文法。例4：若规定先‘*’后‘＋’及‘＋’、‘*’都是左结合 的。则文法G1[<E>]可改造为算术表达式 文法G[<E>]。这样句子i+i*i只能有一棵推 导树。2023/7/22华东师大计算机科学技术系32对文法的二义性讨论（续）对二义性文法所产生的语言，有的可找到等价的无二义性文法，因此只说文法的二义性，而不说语言的二义性。当然存在这样的语言，不存在它们的无二义性文法。例如：L={aibjck|i=j或j=k,i,j,k1}。文法的二义性是不可判定的，即不存在一种算法能在有限步内判定该文法是否是二义性的。通常的做法是：找出无二义性文法的一个充分条件，即满足条件的一定是无二义性文法。2023/7/22华东师大计算机科学技术系33形式语言分类2.5形式语言分类1956年Chomsky将文法分成四类：0型、1型、2型和3型文法G＝（VT，VN，P，<S>）

VN∪VT＝

V

、

VN∩VT＝φ

P中产生式的一般形式是α→β，αV+,α至少含有一个非终结符，βV*，β可以是空串。 称文法G为

0型文法（短语结构文法）2023/7/22华东师大计算机科学技术系34形式语言分类在0型文法的基础上，再规定：|α|<=|β|

∵

α中至少含有一个非终结符

β不能为 称文法G为1型文法（上下文有关文法）等价定义：

wαz→wβzw,zV*

αVN，βV＋

2023/7/22华东师大计算机科学技术系35形式语言分类在0型文法的基础上，再规定：

<A>→α，其中<A>VN，αV*

称文法是2型文法（上下文无关文法）任何含有<U>→ε的产生式（称为ε产生式）的文法不是1型文法。但是含有ε产生式的2型文法可以转化为不含ε产生式的2型文法，转化前后的两个文法所生成的语言至多相差一个ε。2023/7/22华东师大计算机科学技术系36例1：试将如下的含有产生式的上下文无关文法 （2型文法）G[<S>]转换成等价的不含产生式的 上下文无关文法。 ①<S>a<A><S> ②<S>b ③<A>c<S> ④<A>

解：引入非终结符<AN>与<AY>,<AN>表示不可空， 而<AY>表示可空。随后消除可空的产生式以及 在产生式的右部去除非终结符<AY>即可，因此 G[<S>]可等价表示为：①<S>a<AN><S> ①’<S>a<AY><S>②<S>b ③<AN>c<S>④<AY>2023/7/22华东师大计算机科学技术系37最后得到等价的无产生式的文法G1[<S>]为：①<S>a<AN><S> ②<S>a<S>③<S>b ④<AN>c<S>注意：两文法不同，但等价！∵语言相同。问题：什么情况下转换前后的二个文法的语言 会 相差呢？2023/7/22华东师大计算机科学技术系38在2型文法的基础上，再规定：

产生式形式是<A>→x，<A>→x<B>，

<A>,<B>VN，xVT*

则称文法是右线性文法。 若规定：xVT

即<A>→a，<A>→b<B>， <A>,<B>VN，a,bVT

则称文法是3型文法（正则文法）。正则文法也可以是左线性文法的特例。适当地引入新的非终结符可以把一个右线性文法转换为等价的正则文法。2023/7/22华东师大计算机科学技术系39例2：试将如下文法G[<S>]转换为等价的正则文法（3型文法）： ①<S>a<A> ②<S><A> ③<A>ab