第3章--词法分析

第三章 词法分析知识结构：功能 词法分析器的要求 单词符号分类 词法分析 单词内部形式器的设计 设计方发词法分析器的设计 状态图词法分析器组成正规表达式单词描述工具 正规集词法分析器 正规文法确定有限自动机（DFA ）单词识别工具 非确定有限自动机（NFA ）DFA 的最小化正规式与FA 的等价转换等价转换正规文法与FA 的等价转换第一节 对词法分析器的要求一、词法分析器的功能输入源程序，输出单词符号（二元式表示）。

关键字：是由程序语言定义的具有固定意义的标识符。

标识符：用来表示各种名字，如变量等。

常数：常数的类型有整型，实型等。

运算符：算术运算符，关系运算符，逻辑运算符。

界限符：逗号，分号等。

三、单词符号内部的表示形式内部的单词符号TOKEN字（二元式），TOKEN字占用机器字的长度，依据信息量的多少而定。

1、TOKEN字结构CLASS：用整数表示。

VALUE：表示单词符号的属性（符号表指针）。

2、TOKEN的作用CLASS：用于语法分析器对源程序结构的分析。

VALUE：用于语义分析器对源程序具体操作的分析。

3、单词种别码划分原则CLASS：关键字，运算符，界限符（编译程序定义的符号）使用一字一种编码。

VALUE值省略。

VALUE：标识符，常数（用户定义的符号），存放符号表常数表的指针。

标识符，常数每一类为一种编码。

例：BEGIN A：= B END；词法分析结果：符号表（BEGIN，---- ）Array（A ，K1 ） K1（：= ，--- ）（B ，K3 ） K3（END ，--- ）（；，--- ）四、词法分析器的结构1、一遍扫描（交互式结构）。

2、多遍扫描（独立式结构）。

第二节词法分析器的设计一、设计步骤1、确定词法分析器的接口关系；2、确定单词分类和TOKEN字的结构；3、对每一类单词构造状态转换图；4、根据状态转换图设计算法。

二、功能描述1、组织源程序输入；2、按词法规则拼读单词符号，并转换成二元式；3、删除注解行，空格和无用符号；4、检查词法错误。

三、设计方法1、输入(读取原文件)原文件存储方式：一种方式将原文件一次读入内存，另一种方式利用缓冲区技术将原文件分批读入内存。

缓冲区的设置：输入（扫描）缓冲区，存放输入的原文件（双缓冲区）。

2、预处理功能描述：删除无用符号，出错信息的列表打印。

单词符号的识别：⑴语句格式①标识符不能被无效字符隔开。

②标识符与关键字，关键字与关键字之间用空格符隔开。

②标识符的个数不能超过限定的个数。

⑵单词符号的格式①标识符，关键字的首字符必须是字母。

②常数的首字符必须是数字。

3、识别算法(P39)标识符的识别；常数的识别；算符的识别；界符的识别。

四、状态转换图1、状态转换图的表示形式是一张有向图,结点代表状态（用○表示），结点间用箭弧线连接（ ），箭弧线上的符号，表示射出结点到达射入结点可能识别的输入符号，终态结点代表分析结束。

初态⇒⑴ ⇒⊙初始状态,表示识别符号串的开始。

⑵双圈◎终态，表示识别符号串的结束。

⑶◎*表示多读入一个字符。

例1：标识符的状态转换图状态转换矩阵字母，数字例2：标识符“AB1”的识别 例4 状态转换矩阵 数字2、识别过程从初态开始，逐步读入字符，转到下一个状态（或出错），直至终态（或不能到达终态出错）。

例3：字符串“AB+12”的识别识别出单词AB,多读入一个字符 +。

由另一张状态转换图识别单词符号 +。

继续识别剩余字符12(数字)：上述识别过程把AB ＋12字符串分解为三个单词符号“AB ”、“ + ” 、“12”。

3、状态转换图的实现状态转换图非常容易用程序实现，每一个状态对应一段程序。

⑴不含回路的分叉状态结点的程序设计利用多分支语句CASE 或选择语句IF...THEN...ELSE...。

⑵含回路状态结点的程序设计利用循环语句WHILE...DO。

⑶词法分析程序的组成状态转换图是一种特殊的流程，它可直观清晰地描述单词符号的识别过程，只要把每一个结点加入语义动作，就构成了词法分析程序。

4、词法分析程序的组成（八个模块）主控模块；初始化模块；判定源程序文件是否存在模块；从源程序文件中读一个字模快；拼读一个单词模块；查关键字模块；输出单词模块；错误处理模块。

第三节正规式、正规集、正规文法一、正规式的定义∑中的符号为正规式的基本符号，单个符号或由符号与运算符组成的表达式称正规式。

运算符优先级：重复用“ * ”表示；连接用“•”表示或省略；选择用“∣”表示。

例：a，ab *，a∣b ，（a∣b）c都是正规式。

二、正规集由正规表达式所表示的字符串的集合称为正规集。

如正规式用V表示，正规集L（V）表示。

三、正规文法正规文法是上下文无关文法的一种特殊情况，所有产生式的右部至多含有一个非终结符号，左线性文法，右线性文法都属于正规文法。

左线性文法：A →B αA → α右线性文法：A → αBA → α 其中：A ，B ∈V N ，α∈V * T * T四、正规式与正规集的递归定义1、正规式与正规集的递归定义P46⑴ε和Ф都是Σ上的正规式，正规集为{ε}和Ф。

⑵任何a ∈Σ，a 是∑上的正规式，正规集为{a}。

⑶假定U 和V 是∑上的正规式，正规集为L(U)，L(V)U ∪V 是正规式，正规集为L(U)∪L(V)。

UV 是正规式，正规集为L(U)L(V)。

(U)*是正规式，正规集为 (L(U))*。

例1：令Σ= {a, b}，则⑴正规式a | b 的正规集是{ a, b }。

⑵正规式（a | b ）（a | b ）的正规集是{aa, ab, ba, bb}。

⑶正规式a * 的正规集是{ε，a, aa, aaa ……}。

⑷正规式（a | b ）* 的正规集是{ε,a, b, aa, ab, ba, bb,aaa……}。

（a | b）*＝（a*b*）*，即所有a和b的符号串集合。

⑸（a | b）*(aa| bb)（a | b）*的正规集是所有含有两个相继a或两个相继b的字符串集合。

例2：∑ ={a, b, c……z，0, 1,……9}正规式（a | b…|z）（a | b|…z|0|1|…|9）*代表标识符。

2、正规式与正规集的等价性若两个正规式代表的正规集相同，则认为正规式等价。

U=V，表示L（U）=L（V）例3：U=10**， L(U)={1}{0}*V=10*， L(V)={1}{0}*则10**=10*例4：b(ab)*= (ba)*b （ab）*≠a*b*(a|b)*= (a*b*)*(a|b)*≠(a*|b*)3、正规式的代数定律（1）U∣V=V∣U 交换律（2）U∣V∣W=（U∣V）∣W 结合律（3）U（VW）=（UV）W 结合律（4）U（V∣W）=UV∣UW 分配律（5）εU = Uε= U（6）U *=U+∣ε（7）U **=U*（8）U +=U*U=UU*例1：选择规则U∣V，则描述的正规集L(U∣V)=L(U)∪L(V)。

令 U=a,V=b：则 L(U∣V)= L(U)∪L(V)=L(a)∪L(b)={a}∪{b}={a，b}例2：连接规则UV，则描述的正规集L(UV)=L(U)L(V)。

令 U=a∣b，V=c：则 L(UV)= L(U)L(V)=L(a∣b )L(c)= {a，b}{c}={ac,bc}例3：重复规则U *，则描述的正规集L(U*)=(L(U))*。

U *={ε}∪U1∪U2∪...∪UnU=（a∣ab）L(U *)=(L(U))*=(L(a∣ab))*=(L(a)∪L(ab))* ={a,ab}*={a,ab}0∪{a,ab}1∪{a,ab}2∪⋯={ε}∪{a,ab}∪{a,ab}{a，ab}∪⋯={ε，a，ab，aa，aab，aba，abab，⋯ }五、正规式与正规文法的转换正规式与正规文法都有相同的表达能力，用以描述语言（单词符号）的结构，使得所描述的语言是等价的（即L（V）=L（G））。

1、正规式与正规文法的特点正规式描述的语言结构清晰，简洁；而正规文法描述的语言于识别。

2、正规定义式d1→ r1d2→ r2...其中:d i 为定义式的名字；r i是∑∪{d1，d2，...，d i-1}构成的正规式；r i中不含有d i，d i+1，...。

3、正规式与正规文法的转换算法例：高级语言标识符的正规式字母（字母∣数字）*⑴根据正规定义式规则，给正规式分量、正规式定义名称字母→ A ∣ B ∣ C数字→ 0 ∣ 1 ∣ 2id →字母（字母∣数字）*⑵对定义式的子表达式定义名称rid →（字母∣数字）*⑶对定义式的子表达式展开（字母∣数字）*= ε∣（字母∣数字）+= ε∣（字母∣数字）（字母∣数字）*= ε∣字母（字母∣数字）*∣数字（字母∣数字）*⑷把展开式代入定义式rid →ε∣字母（字母∣数字）*∣数字（字母∣数字）*⑸把rdi →（字母∣数字）*代入定义式id、rid，将得到正规文法：id →字母ridrid →ε∣字母rid∣数字rid其中:id，rid ∈ V N；字母，数字∈V T。

六、正规文法与正规式的转换建立正规文法的联立方程组，求描述同一语言的正规式。

1、右线性文法到正规式，使得L（G）=L（V）。

产生式 X → rX ∣ t，其中 r，t∈ V T X∈V N。

论断1：方程 X=rX + t ，有形如 X=r *t的解。

例：文法GS →aS ∣bA ∣bA →aS⑴立联立方程组S = aS + bA + b ①A = aS ②⑵②式，代入①式S = aS + baS + bS =（a + ab）S + b ⑶由论断得方程解S =（a + ab）*b= （a∣ab）*b对于同一方程式采用不同的结合方式，可以得到不同形式的正规式，但是所描述的语言（正规集）是等价的。

S = aS + baS + b= aS +（baS + b）= a *（baS + b）= a *baS + a*b= （a *ba）*a*b所以（a *ba）*a*b = （a∣ab）*b。

2、左线性文法与正规式的转换算法产生式 X → Xr ∣ t，其中 r，t∈ V T X∈V N。

论断2：方程 X=Xr + t ，有形如 X=tr *的解。

例：文法Gid → id 字母∣ id 数字∣字母其中:id ∈ V N；字母，数字∈V T。

建立方程id = id 字母 + id 数字 + 字母= id（字母 + 数字）+ 字母= 字母（字母∣数字）*3、正规文法与正规式的转换规则⑴产生式 A→xB，B→y 对应的正规式 A=xy；⑵产生式 A→xA∣y 对应的正规式 A=x * y；⑶产生式 A→x ，A→y 对应的正规式 A=x∣y例：文法GS→aA，S→aA→aA，A→dA，A→a，A→d⑴根据规则⑶先有正规式S = aA∣aA = （aA∣dA）∣（a∣d）⑵再将A的正规式变换为A = （a∣d）A∣（a∣d）⑶根据规则⑵将A的正规式变换为A = （a∣d）*（a∣d）⑷再将A式的结果代入S的正规式S = a（a∣d）*（a∣d）∣a⑸再利用正规式的代数性质得到的正规表达式为S = a（（a∣d）*（a∣d）∣ε）因为（a∣d）*（a∣d）=（a∣d）+,所以S = a（a∣d）+∣a= a（（a∣d）+∣ε）。