授课顺序：6

教学目的：让学生掌握正规文法、正规式和有穷自动机的等价转换方法，了解

词法分析程序自动构造工具LEX的工作原理及基本使用方法。

教学重点：正规文法、正规式和有穷自动机的等价转换 教学难点：正规文法、正规式和有穷自动机的等价转换 授课学时：2学时 教学方式：多媒体讲授 教学内容：

4.4 正规式和NFA的等价性

一、概述

对于?上的每个NFA M，可以构造一个相应的?上的正规式R，使得L(R)=L(M)。 对于?上的每个正规式R，可以构造一个相应的?上的NFA M，使得L(R)=L(M)。

二、为NFA M构造相应的正规式R

首先，引入两个新结点x，y;x经ε弧到所有初态，所有终态经ε弧到y；然后，再用如下消解规则消去除x，y外的所有结点，最后x，y间弧上的标记串就是所求正规式。

例：给出与图示NFA M等价的正规式R。

解：R=(0|1)*(00|11)(0|1)*

三、由正规式R构造相应的NFA N

其过程与上述过程相反。用如下规则构造NFA：

对R=ε、R=a和R=st（其中，s、t分别为正规式）分别构造:

对R=s|t和R=s*分别构造：

例：为R=(a|b)*abb构造NFA N，使L(R)=L(N)。 解：与R=(a|b)*abb等价的NFA N如下：

4.5 NFA和正规文法的转换

一、概述

对于?上的每个NFA M，可以构造一个相应的?上的正规文法G，使得L(G)=L(M)。 对于?上的每个正规文法G，可以构造一个相应的?上的NFA M，使得L(M)=L(G)。

二、构造正规文法G等价的NFA M

(1)为G中每个非终结符生成M一个状态，开始符为初态。 (2)增加一新状态Z，做为NFA M的终态。

(3)对形如A→aB或A→B的产生式，构造M的转换函数f(A，a)=B或f(A，ε)=B。 (4)对形如A→a的产生式，构造M的转换函数f(A，a)=

授课顺序：7

教学目的：让学生了解自顶向下语法分析思想，掌握LL(1)文法的概念及判别方

法。

教学重点：FIRST(α)集和FOLLW(A)集的计算、LL(1)文法的判别 教学难点：FIRST(α)集和FOLLW(A)集的计算、LL(1)文法的判别 授课学时：2学时

教学方式：多媒体讲授 教学内容：

第五章 自顶向下语法分析方法

语法分析是编译程序的核心部分，其作用是检查由扫描器输出的单词符号序列是否是符合该语言文法的句子。语法分析器的输入是单词符号序列，输出是分析树。 语法分析方法（当今编译程序构造的实用方法）：

1、自顶向下分析：确定的自顶向下分析（递归下降法、预测分析法）、不确定(带回溯)的自顶向下分析。

2、自底向上分析：算符优先分析、LR分析（LR(0)分析、SLR(1)分析、 LR(1)分析、LALR(0)分析）

5.1 自顶向下分析思想

一、自顶向下的分析方法的基本思想(面向目标) 寻找输入符号串最左推导，试图根据当前输入单词判断使用哪个产生式。基本过程是 从根开始，按与最左推导相对应的顺序，构造输入符号串的分析树。

例：根据下面文法G[E]，对符号串 i + i * i进行分析，并按照最左推导构造分析树。

E → T E? E?→ + T E?｜ε T → F T? T?→ * F T?｜ε F → ( E )｜i

解：与最左推导对应的语法树：

二、候选式的确定与回溯

给定文法S→cAd A→ab|a，判断句子cad是否该文法定义语言的句子。

产生式(候选式)的选择与回溯(Backtracking)：当要进行关于某个语法变量的推导时，希望能够根据当前符号确定候选式。

三、FIRST(α)集 1、定义

对于α?、 β∈(ＶT∪ＶN) *， 定义α的首符号集为：FIRST(α)={a|α=*> aβ， a∈ＶT}。

2、各文法符号的FIRST集

各文法符号的 FIRST集计算方法如下：

(1)对X∈?ＶT，FIRST(X)={X}；

(2)对X∈?ＶN，且X→a…，a∈ＶT，则 a∈FIRST(X)； (3)对X∈?ＶN，且X→ε， 则ε∈ FIRST(X)；

(4)对X∈?ＶN，Y1，Y2，…都∈ＶN，且X→Y1Y2…Yn， 则： ① 当Y1不能=*>ε时，FIRST(X)=FIRST(Y1)；

② 当Yi都能=*>ε( i∈[1，n-1] )时，FIRST(X)={ FIRST(Yi)的并集-{ε}}∪ FIRST(Yj)，其中 i∈[1，n-1]，j∈[1，n]。 即：当规则右部Y1Y2…Yn只有前面部分能推导出ε时，FIRST(X)中不含ε。

③ 当Yi都能=*>ε( i∈[1，n] )时，FIRST(X)= FIRST(Yi)的并集，其中 i∈[1，n]。即：当规则右部Y1Y2…Yn都能推导出ε时，FIRST(X)中才会含ε(因为FIRST(Yi)中都含ε)。 ④ 对X∈?ＶN，重复如上述过程，直到所有FIRST集不变为止。 3、符号串的FIRST集

计算符号串（设串α = X1 X2…Xn）的FIRST集方法如下：

1)当X1不能=*>ε时，则FIRST(α)=FIRST(X1)。即：当串α的第一个符号X1不能推导出ε时，只考虑FIRST(X(1)。

(2)当X1能=*>ε，但存在Xi不能=*>ε ( i∈[2，n] )时，则 FIRST(α)=FIRST(Xi)的并集-{ε}。即：当串α的第一个符号能推导出ε，但串中存在某个符号不能推导出ε时， FIRST(α)不含ε。

(3)当X1能=*>ε，其余所有Xi也都能=*>ε ( i∈[2，n] )时，则FIRST(α)=FIRST(Xi)的

并集。即：当串α的所有符号都能推导出ε时，FIRST(α)才含ε。 例：计算表达式文法的语法符号的 FIRST集。

G[E]：E→TE' E'→+TE? E'→ε T→FT' T'→*FT? T'→ε F→(E) F→i 解：FIRST(E')={+，ε} FIRST(+)={+} FIRST(T')={*，ε} FIRST(*)={*}

FIRST(( )={( } FIRST( ))={ )} FIRST(i)={i}

FIRST(F)={(，i} FIRST(T)=FIRST(F)={(，i} FIRST(E)=FIRST(T)={(，i}

若换成：T→T?F E→E?T

则：FIRST(T)={FIRST(T?)-{ε}}∪ FIRST(F)={(，i，*} FIRST(E)={FIRST(E?)-{ε}}∪ FIRST(T)={(，i，+，*}

四、FOLLOW( A )集

1、定义：对于A∈?ＶN定义A的后续符号集：

FOLLOW(A)={a|S uAβ， a∈ＶT，且a∈ FIRST(β)，u∈ＶT，*， β∈Ｖ+ }; 若β=*>ε，则 #∈FOLLOW(A)。

也可以定义为：FOLLOW(A)={a|S …Aa…， a∈ＶT}。若有S=*>…A，则规定#∈FOLLOW(A)。

2、计算FOLLOW集

对于所有出现在规则右部的非终结符，重复进行以下计算： (1)将 #加入到 FOLLOW(S)，其中#为句子的结束符。

(2)若 A→αBβ，且β不能=*>ε，则 FOLLOW(B)=FIRST(β)。 (3)如果 A→αB，则：FOLLOW(B)= FOLLOW(A)。

(4)如果 A→αBβ，且β=*>ε，则：FOLLOW(B)={FIRST(β)-{ε}}∪FOLLOW(A)。 注意：只考虑FIRST(β)中非空元素。

例：求下列表达式文法G[E]的语法变量（即非终结符）的FOLLOW集。 G[E]：E→TE' E'→+TE?|ε T→FT' T'→*FT?|ε F→(E)|i 解：FOLLOW(E) = FIRST( ))∪{#} = { )，# } 联FOLLOW(E')= FOLLOW(E) = { )，# } FOLLOW(T)={FIRST(E')-{ε}}∪FOLLOW(E)∪ FOLLOW(E') = { +， )， #} FOLLOW(T')= FOLLOW(T) = { +， )， #}

FOLLOW(F) ={FIRST(T') -{ε}}∪FOLLOW(T)∪ FOLLOW(T')={ *， +，)， #} 五、SELECT集

对于 G的每个非终结符 A的候选式 A→α， (1)若α不能=*>ε，则SELECT(A→α)=FIRST(α)

(2)若α=*>ε，则SELECT(A→α)={FIRST(α)-{ε}}∪FOLLOW(A)

5.2 LL(1)文法的判别

一、LL(1)文法的定义

LL(1)文法表示了自顶向下方法能够处理的一类文法。第一个 L表示从左向右扫描输入符号串，第二个 L表示生成最左推导，1表示读入一个符号可确定下一步推导。

G是LL(1)文法的充要条件：对于 G的每个非终结符 A的任何两个不同的候选式 A→α|β，满足：SELECT(A→α)∩SELECT(A→β)=φ。其中，α、β不能同时=*>ε。

二、LL(1)文法的判别

1、判别原则：文法Ｇ是 LL(1)文法的充要条件。 2、判别步骤

1）画出各非终结符能否推导出ε的情况表；