问题： a1、b1、b2、a3为什么不是短语？
3.7文法实用性的一些说明
一、有关文法的实用限制
1、在实用中，文法中不得含有害规则或多余规则。 2、形如U→U的规则为有害规则。
3、不可达规则或不可终止规则为多余规则。 例：G[S]：S→Ab|Cd A→b D→e C→Ca
二、限制使用ε规则
即形如A→ε的规则，它会使有关文法的证明和讨论变得复杂。
习题讲解
P48第11题扩展： 令文法G［E］为：E→T|E+T|E-T T→F|T*F|T/F F→(E) |i
要求证明F+T*F是它的一个句型，构造其语法树，并指出这个句型的所有短语、直接短语和句柄。
解：1）证明：因为E? E+T? T+T? F+T? F+T*F，即有E=*> F+T*F，故：F+T*F是G［E］的一个句型。语法树如下图所示。
2）句型分析
该句型相对于E的短语： F+T*F、F； 该句型相对于T的短语： T*F、F；
该句型相对于T→F的直接短语F，相对于T→T*F的直接短语：T*F； 该句型的句柄：F。
作业：P47练习 2、5、9、11、16
授课顺序：4
教学目的：让学生了解词法分析程序的概念及设计原则、单词的分类，掌握正
规文法、正规式的相关概念及等价转换方法。
教学重点：正规文法和正规式的相关概念及等价转换 教学难点：正规文法和正规式的等价转换
授课学时：2学时 教学方式：多媒体讲授 教学内容：
第四章词法分析 4.1 词法分析程序的设计
一、词法分析程序的设计思想
通常将词法分析程序（扫描器）设计为子程序形式，当语法分析程序需要单词时，则调用该子程序。
二、单词分类
通常分为5类： (1)基本字(关键字、保留字)：具有特殊含义的标识符，不作他用，有分隔语法的作用； (2)标识符：表示各种名字；
(3)常量：整型、实型、布尔型、字符型； (4)运算符：算术、逻辑、关系运算符； (5)界符：包括.，;，(，)，:，，等，有时也把运算符称作界符。
三、词法分析程序的设计原则 (1）把扫描器当作语法分析的一个过程，当语法分析需要一个单词时，便调用扫描器。 (2)扫描器从初态出发，当识别一个单词后便进入终态，同时输出二元组。
四、词法分析程序的输出
词法分析程序扫描后输出单词序列表示为如下二元组形式： 二元组：（单词种别，单词自身值或指针）
例：若规定标识符、常数、基本字、运算符、界符的种别用整数编码分别为1、2、3、4、5，则对程序段 ： “ if k=7 then a:=b ; ” ，则其经扫描器扫描后输出的单词符号及其二元组为：
基本字if (3， ?if?)
标识符k (1，?指向k的符号表入口的指针 )
等号= (4， ?=?)? 常数7 （2，?7?） 基本字then (3， ?then?)
标识符a (1， 指向a的符号表入口的指针) 赋值号:= (4， ?:=?)
标识符b (1， 指向b的符号表入口的指针) 分号； (5， ?;?)
五、词法分析程序独立设计的优点
(1)使整个编译程序的结构更加简洁、清晰、条理化； (2)改进了编译程序的效率；
(3）增加了编译程序的可移植性。
4.2?单词的描述工具
一、正规文法
3型文法，又称右线性文法或正规文法(Regular Grammars)，其表达式形如：A→aB或
A→a。正规文法描述的语言是VT*上的正规集。绝大部分程序设计语言的单词都能用正规文法来描述。
二、正规式和正规集 1、定义
正规式也称正规表达式，是表示正规集的工具，递归定义如下：
1)ε和φ都是字母表?上的正规式，表示正规集为{ε}和φ； 2)?a∈?，a是?上的正规式，表示正规集{a}；
3)假定e1、e2都是?上的正规式，对应正规集为L(e1)、L(e2)，则(e1)、e1|e2、e1.e2、e1*也是正规式，分别表示的正规集为L(e1)，L(e1)∪ L(e2)，L(e1).L(e2)，和L(e1)*；
4)仅由有限次运用上述步骤产生的表达式才是?上的正规式，仅由这些正规式产生的字集才是?上的正规集。
例: 设?={0，1}，则有：
正规式 正规集 0 {0}
0|1 01 1* (0|1)*
{0，1} {01}
{ε，1，11，111...} {ε，0，1，01，10......}
3、正规式服从的代数规则
设r，s，t为正规式，则正规式服从如下的代数规则：
r|s=s|r ('或'满足交换律) r|(s|t)=(r|s)|t ('或'满足结合律) r(st)=(rs)t ('连接'满足结合律) r(s|t)=rs | rt (分配律)
rε=εr=r (ε是连接的恒等元素)
注意： rs?sr r|(st)?rs | rt
三、正规式和正规文法的等价性
任意一个正规语言既可以由正规式定义，也可由正规文法来定义。正规式和正规文法之间可进行等价转换。
1、正规式转换成正规文法
将?=VT上的正规式r换成正规文法G =(VN， VT，P，S)方法如下：
(1)令S→r
(2)对形如A→xy的产生式，可分解成A→xB，B→y (3)对形如A→x*y的产生式，可分解成为A→xA， A→y (4)对形如A→x|y 的产生式，可分解为 A→x ，A→y 反复利用上述规则，直至所有产生式中最多只含一个终结符。 例：将R=a(a|d)*转换成相应的正规文法。 解：步骤如下： (1) S→a(a|d)*
(2) S→aB， B→(a|d)B， B→ε
(3) S→aB， B→aB ，B→dB， B→ε
相应的正规文法如(3)式所示，即G[S]: S→aB B→aB|dB|ε 2、正规文法转换成正规式
将正规文法G=(VN， VT，P，S)换成?=VT上的正规式r的转换规则：
1）将产生式A→xB B→y 合写为A=xy；
2）将产生式A→xA A→y 合写为A=x*y； 3）将产生式A→x A→y 合写为A= x|y
反复利用上述规则，直至只剩下一个由开始符定义的产生式，且该产生式右部不含一个非终结符。
例：将正规文法G[S]: S→dA|eB A→aA|b B→bB|c换成正规式。 解：步骤如下：
(1)由A→aA|b，将A转换成a*b；由B→bB|c，将 B转换成b*c； (2)由 S→dA|eB，将S可转换成(da*b)|(eb*c) 故所求正规式为R=(da*b)|(eb*c)。