第二章-文法和语言基本知识课件

本章知识点：第二章文法和语言基本知识字母表和符号串的概念文法和语言的形式定义直接推导、推导、句型、句子短语、直接短语、句柄语法树、文法的二义性了解文法和语言的分类2.1概述程序设计语言的精确定义和描述：语法：语言结构的定义语义：描述语言的含义语用：从使用的角度来描述语言非形式化描述形式化描述：用一整套带有严格规定的符号体系来描述问题。编译程序是针对某种程序设计语言的。2.2字母表和符号串的基本概念1、字母表字母表：字母表是元素的非空有穷集合。任何程序语言都有自己的字母表，例如:机器语言：由符号“0”和“1”组成的字母表，∑={0，1}ASCII字符集；C语言字母表为：∑={AZ,az,09,+,-,*,/,<,=,>,:,‘,’,;，.，!,~,%,&,

¦,^,(,),{,},[,]}2.2.1字母表和符号串2.2字母表和符号串的基本概念1、字母表：元素的非空有穷集合。2、符号：字母表∑中的元素。3、符号串（字）符号串：字母表∑中的符号所构成的一个有穷序列。空字ε：不包含任何符号的序列。φ：不含任何元素的空集{}2.2.1字母表和符号串2.2字母表和符号串的基本概念符号串的连接εy=yε=y集合的乘积{ε}A=A{ε}=A符号串的幂运算y0=εy1=yy2=yy集合的幂运算A0={ε}A1=AA2=AA集合A的闭包A*与正闭包A+∑的闭包∑*：∑上所有符号串的全体例如，若∑={a,b}，则∑+={a,b,aa,ab,ba,bb,aaa,…}则∑*={ε，a,b,aa,ab,ba,bb,aaa,…}=∑0U∑+2.2.2符号串的运算设L和M是两个符号串集合，则1.合并：L∪M＝｛s|sLorsM}2.乘积：LM＝｛st|sLandtM}3.幂：L0={ε}，L1＝L，L2＝LL,...,Ln＝LLn-14.L的闭包，记作L*，L*＝∪Li(i>=0)=L0∪L1∪L2∪L3∪…5．L的正则闭包，记作L+（L+＝L

L*）L+＝∪Li(i>=1)=L1∪L2∪L3∪L4∪…例如：L={A~Z,a~z}D={0~9}1．L∪D={A~Z,a~z,0~9}2．LD是由所有用一个字母后跟一个数字组成的符号串所构成的集合。3．L4是由所有的四个字母的符号串构成的集合。4．L（L∪D)*是由所有的字母开头的字母和数字组成的符号串所构成的集合。5．D+是由所有的长度大于等于1的数字串所构成的集合。

形式语言：符号串的集合

不考虑语义

程序←→符号串2.3文法和语言的形式定义2.3.1形式语言

有穷集合的语言描述：枚举法

无穷集合的语言描述：文法（含递归）例∑={0,1},则集合

∑+表示为递归文法：A→0A→1A→A0A→A12.3文法和语言的形式定义2.3.2文法的形式定义

文法：描述语言的语法结构的形式规则。

上下文无关文法(Context-freeGrammar)：即文法所定义的语法范畴（语法单位）完全独立于这种范畴可能出现的环境。2.3.2文法的形式定义规则（Backus-NaurForm，简记为BNF）

规则：也叫产生式，是一个符号与一个符号串的有序对（A,β），通常写作：A→β(或A::＝β)

其中，A是规则的左部，β是规则的右部→表示生成或定义为语言的语法结构用一组规则来表示。终结符号、非终结符号例赋值语句→变量=表达式2.文法文法是规则的非空有穷集合，通常表示成四元式G=（VT，VN,S,P），其中：VT是一个非空有穷终结符号集合；VN是一个非空有穷的非终结符号集合，且VT∩VN＝Φ；P是一个产生式的非空有穷集合，每个产生式的形式是A(或A::＝)，其中A∈VN，∈（VT∪VN）*。SVN，称为开始符号，S必须至少在某个产生式的左部出现一次。左部相同的产生式可以缩写成：A

1|

2|

3文法是对语言结构的定义和描述，规则是其关键。例,定义一类含+、*的算术表达式如:“变量是一个算术表达式;若E1和E2是算术表达式，则E1+E2、E1*E2和(E1)也是算术表达式。”用产生式描述为：E→iE→E+EE→E*EE→(E)见课本p12-14，例2.1—2.4例2.1∑={a，b}

语言

L={a2n,b2n|n≥1}对应文法？例2.2表示所有标识符的文法？例2.4∑={a，b}语言L={abna|n≥0}对应文法？语言对应的文法示例：

等价文法2、推导如果存在一个直接推导序列：

0

12…

n（n＞0）称为

0至n的一个长度为n的推导，表示成0

n2.3.3语言的形式定义1、直接推导令G=(VT,VN,S,P),若Aγ∈P,且,β,γ∈(VT∪VN)*,则称Aβ直接推导出γβ，表示成

Aβγβ+3、广义推导0n表示

0=

n或者

0

n+*2.3.3语言的形式定义4、句型和句子设有文法G＝（VT，VN，S,P）。如果S,则称是一个句型。*5、语言由文法G产生的所有句子所组成的集合就是语言L(G)。L(G)＝{|S且∈VT*}+仅含终结符号的句型是一个句子。注：L(G)是VT*的子集见课本p16，例2.7—2.9S→01|0S1S→0S|1S|εA→yBB→xB|x文法对应的语言示例：例S→aB|bAA→a|aS|bAAB→b|bS|aBB2.3.4规范推导和规范归约最左推导：推导中的每一步β,都是替换中最左的非终结符号。例如：EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a最右推导：推导中的每一步β,都是替换中最右的非终结符号。例如：EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*a2.3.4规范推导和规范归约最左推导：推导中的每一步β,都是替换中最左的非终结符号。最右推导：推导中的每一步β,都是替换中最右的非终结符号。规范归约（最左归约）规范推导、规范句型归约：推导的逆过程β.A…A2.3.5递归规则与文法的递归性1、递归规则规则形如：A→A…或A→…A或A→…A…2、文法的递归性

有推导AA…++A…A…+注：语言是无穷集合，描述的文法一定是递归的。2.4短语、直接短语、句柄短语：设文法Ｇ＝(ＶT，ＶN，Ｐ，Ｓ)

若有ＳαＡδ且Ａβ，句柄：一个句型的最左直接短语。则称β是句型αβδ相对于非终结符Ａ的短语。若ＳαＡδ且Ａ=>β，则称β是直接短语。*+*2.5语法树与二义性2.5.1推导和语法树

语法树有助于理解句子(句型)语法结构的层次。

语法树通常表示成一颗倒立的树，根在上，枝叶在下。1、语法树：用一张图来表示一个句型的推导,这张图称为语法树,也称推导树。例G=(VT,VN,S,P),其中P:SaASaASbASSba3124657891011SaASSbAaaba

根据推导序列，对每步推导画相应分枝ASaSbSAabaa

aSbAS

aabAS

aabbaS

aabbaa

aASS如何画出分析树(自顶向下）

根据归约序列，对每步归约画相应分枝abaabaSASAS

aAa

aSbAa

aSbbaa

aabbaa

aASS

如何画出分析树(自底向上）1.一个句型推导或分析用一棵树结构图示出来，它反应了一个句型语法结构的层次。2.对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程，画出的分析树是一样的。分析树并未描述推导过程，它是不同推导过程的抽象共性。3.在书中，用画分析树的过程解释语法分析过程，用分析树图解语法结构。关于分析树的几点说明SAbSaSbaAaa一棵分析树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记。例如：2、

子树3、简单

子树与短语等概念的对应关系一个句型是否只对应一颗语法树？考虑表达式下面的文法G[E],其产生式如下：EE+EE*E(E)a对于句子a+a*a,有如下两个最左推导：EE+Ea+Ea+E*Ea+a*Ea+a*aEE*EE+E*Ea+E*Ea+a*Ea+a*a2.5.2文法的二义性（ambiguity）的定义EE+Ea+Ea+E*Ea+a*Ea+a*aEE*EE+E*Ea+E*Ea+a*Ea+a*aEE+EE*EaaaEE*E+EEaaa最左推导EE+EE+E*EE+E*aE+a*aa+a*aEE*EE*aE+E*aE+a*aa+a*aEE+EE*EaaaEE*E+EEaaa最右推导结论：一个句型可能有不止一个最左（最右）推导，对应不同的语法树，可以用完全不同的办法生成一个句型。如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是某个句子有两个不同的最左（最右）推导。人们已经证明，二义性问题是不可判定的。为无二义性找寻一组充分条件例如文法G[E],其产生式如下：EE+EE*E(E)i是二义性文法，加上限制规则：‘*’优先级高于‘+’且都服从左结合，则有无二义文法如：E→T|E+TT→F|T*FF→(E)|i例如,对于条件语句，经常使用二义性文法描述它：SifexprthenSifexprthenSelseSother二义性的句子:ifc1thenifc2thenS1elseS2

下面是描述if语句的无二义性文法的产生式:Smathed_sunmathed_smathed_sifexprthenmathed_selsemathed_sotherunmathed_sifexprthenSifexprthenmathed_selseunmathed_s它显然比较复杂，因此：在能驾驭的情况下，可以使用二义性文法。化简了的文法（限制条件）1．产生式：

A→AP；

2.每个非终结符号A必须都有用处。即，

SαAβ，且Aγ，γ∈VT*

*+2.7文法的实用限制2.6文法和语言分类语言的分类：

对文法中的规则施加不同的限制

四种类型：0型，1型，2型，3型0型(无限制)：G=(VT,VN,S,P)

规则形式：,(VTVN)*,

并且至少含有一个非终结符号；1型（上下文有关）：Auu(VTVN)+,

Au，S除外；2型（上下文无关）：规则形式：A

AVN，

(VTVN)*；3型（右线性）：A

B或A

（左线性）A

B或A，