形式语言与自动机理论PPT学习教案.pptx

会计学
1
形式语言与自动机理论
语言和文法
字母表
符号串
符号串的连接
符号串的方幂
前缀和后缀
子字符串
符号串集合
符号串集合的乘积
符号串集合的方幂
符号串集合的正闭包
符号串集合的星闭包
语言
给定字母表∑，则 ∑上任一字符串集合就是∑上的一个语言
基本概念
第1页/共48页
文法能清晰地描述程序设计语言的语法构成
易于理解。
文法能自动地构造有效的语法分析器，检
查源程序是否符合语言规定的语法形式。
文法定义可以了解程序设计语言的结构，有
利于将源程序转化为目标代码，以及检查出
语法错误。
基于文法实现的语言易于扩展
文法 之 概述
第2页/共48页
文法 之 定义
文法G定义为四元组(VT,VN,S,P)
VT是有限的终极符集合
VN是有限的非终极符集合
S是开始符，S VN
P是产生式的集合，且具有下面的形式：
 ，其中，(VTVN )*
第3页/共48页
文法 之 分类
O型文法: 也称为短语文法，其产生式具有形式: →，其中,(VTVN)*，并且至少含一个非终极符 。
1型文法: 也称为上下文有关文法。它是0型文法的特例，要求||  || (S→例外，但S不得出现于产生式右部)。
2型文法: 也称为上下文无关文法。它是1型文法的特例，即要求产生式左部是一个非终极符: A→ 。
3型文法: 也称为正则文法。它是2型文法的特例，即产生式的右部至多有两个符号，而且具有下面形式之一: A →a ，A →a B
其中A,BVN ，aVT 。
第4页/共48页
上下文无关文法（CFG）
定义为四元组(VT,VN,S,P)
VT是有限的终极符集合
VN是有限的非终极符集合
S是开始符，S VN
P是产生式的集合，且具有下面的形式：
AX1X2…Xn
其中AVN，Xi (VTVN) ，右部可空。
第5页/共48页
推导：如果A是一个产生式，则有A ,其中表示一步推导(用A →)。这时称是由A直接推导的。 的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串
 + : 表示通过一步或多步可推导出
 *  : 表示通过0步或多步可推导出
第6页/共48页
句型：
如果有S*  ，则称符号串为CFG的 句型 。我们用SF(G)表示文法G的所有句型的集合
句子：
如果只包含终极符，则称为CFG的句子，其中S是文法的开始符
语言：
L(G)={ u| S + u ,u  VT* }。
文法G所定义的语言是其开始符所能推导的所有终极符号串(句子)的集合。
第7页/共48页
最左（右）推导：
如果进行推导时选择的是句型中的最左(右）非终极符，则称这种推导为最左(右)推导，并用符号lm（rm）表示最左（右）推导。
左（右）句型：
用最左推导方式导出的句型，称为左句型，而用最右推导方式导出的句型，称为右句型(规范句型)。
结论：
每个句子都有相应的最右和最左推导（但对句型此结论不成立）
第8页/共48页
短语：设S是文法的开始符，是句型(即有S *），如果满足条件：
S * A
A + 
则称是句型的一个短语。
直接短语（简单短语）：如果满足条件：
S * A
A  
则称是句型的一个简单短语。
句柄：一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。
第9页/共48页