第二章 形式语言基础(3).ppt

※上节课主要内容回顾:
2. 主要语法成分的定义
句型,句子,语法树,
短语,简单短语,句柄
※从语法树上看句型(句子)、短语、简单短语和句柄:
语法树的树叶全体--句型(句子);
语法树的子树树叶全体—短语(简单短语);
语法树的最左简单子树树叶全体—句柄!
1. 怎样用文法定义语言
一个文法所定义的语言,就是由该文法开始
符号推导出的所有仅含终结符的符号串之集合。
其中的每个符号串皆称为句子。
L(G)={ x | Z x,x∈VT* }
=>
+
〖〗
【内容提要】
第 2 章形式语言基础(续)
语言是符号串集合
文法是定义语言的规则集
怎样用文法定义语言
主要语法成分的定义与求解
两种特性文法
文法变换方法
形式语言的分类
G2(S): S -> b S | a --- 直接右递归文法。
两种特性文法
递归文法
设有文法:G(Z)=(VN,VT,Z,P)
【定义】设 A∈VN,α,β∈(VN+VT)*,则;
若 A αAβ,:称文法具有递归性;
=>
+
特别: 若 A -> A,称文法具有直接左递归性;
A -> A ,称文法具有直接右递归性。
※递归文法是定义无限语言的工具(递归文法定义的语言有无限个句子)!!
如:G1(S): S -> S b | a --- 直接左递归文法;
※递归文法示例
【】 G(Z):
=>
+
A
即 A
( ≠且≠又称为A具有自嵌套性)
∴可以统称文法G(Z)具有递归性。
Z -> a A b B | c Z
A -> b B c | 
B -> B b A c |a
A
Z -> cZ
B -> BbAc
∵
特别:
∴直接右递归性;
∴直接左递归性;
∴ A具有递归性
=> bBc
=>
二义性文法
【定义】若文法中存在这样的句型,它具有两棵不同的语法树,则称该文法是二义性文法。
【】算术表达式的另一种文法:
∵句型 i+i*i 有两棵不同的语法树(右图):
∴ G`(E) 是二义性文法。
G´(E):E -> E+E|E-E|E*E|E/E|(E)|i ;
i(变量或常数)
E E
E + E E * E
i E * E E + E i
i i i i
二义性文法会引起歧义,应尽量避免之!
先乘后加
先加后乘
  文法的等价性
文法变换方法
即:文法的等价性是指他们所定义的语言是一样的。
【定义】设G1、G2是两个文法,若 L(G1) = L(G2),
【】:G1:S -> aS|a;
G2:S -> Sa|a
L(G1)={a, aa, aaa, …}={an | n≥1}
L(G2)={a, aa, aaa, …}={an | n≥1}
∴ L(G1)=L(G2) 即 G1≡G2
【注】一个语言,通常可用多种文法形式来描述。
则称 G1与 G2等价,记作 G1≡G2。
文法变换方法
文法变换–
Ⅰ. 文法的化简
※文法化简是指消除如下无用产生式:
⒈删除 A->A 形式的产生式(自定己);
⒉删除不能从其推导出终结符串的产生式(不终结);
⒊删除在推导中永不使用的产生式(不可达)。
下面介绍几种文法变换方法:
把文法从一种形式改写为另一种形式,而改写后
的文法与改写前的文法等价。
※文法的化简算法:
⒈删除不终结产生式算法:
⑴构造可以达的非终结符集 VAR(初值为空) :
①首先令 Z∈VAR ; (Z 为文法开始符号);
=>
+
②若有 Z …A…,则令 A∈VAR ;
③重复步骤②,直到VAR不再扩大为止。
⑵删除不在VAR中的所有非终结符(连同其产生式)。
⒉删除不可达产生式算法:
⑵删除不在VVT中的所有非终结符(连同其产生式)。
⑴构造可终结的非终结符集 VVT(初值为空):
①若有 A->且∈VT* ;则令 A∈VVT ;
②若有 B->且∈(VT+ VVT)* ;则令 B∈VVT ;
③重复步骤①②,直到VVT不再扩大为止。
※文法化简示例:
化简步骤:
⒈删除 A -> A ;
⒉删除不终结产生式:
∵ VVT={ };
⒊删除不可达产生式:
∵ VAR={ S,B,A };
得:G`(S): S -> Be ; A -> Ae | e ; B -> Af ;
D -> f ; G -> b ;
※整理后得:
S -> Be | Ec
A -