1、源程序词法分析程序语法分析程序Tokenget token.扫描器二.u单词符号一般可分为下列五种l基本字(关键字、保留字)：具有特殊含义的标识符，不作他用，有分隔语法的作用。l标识符：表示各种名字，如常量名、变量名、过程名。l常数（量）：包括整型、实型、布尔型、字符型常常量，如25、3.1415、true、“ABC”。l运算符：包括算术、逻辑、关系运算符，如：、*、=。l界符：包括.，;，(，)，:，,等，有时也把运算符称作界符。u扫描器的输出表示l扫描器从初态出发，当识别一个单词后便进入终态，同时输出二元组形式的单词序列。 l二元组：（单词种别，单词自身值或指针）l单词种别：语法分析需要的
2、信息，可以用整数编码表示，假如标识符编码为1，常数为2，关键字为3，运算符为4，界符为5。l单词自身的值或指针：编译其他阶段需要的信息。对于标识符，其值为指向该标识符所在符号表中位置的指针。例：if i=5 then x:=y，词法分析后输出的二元组形式的单词序列如下： l关键字if(3, if)l标识符i （1，指向i的符号表入口）l等号 （4, = ）l常数5 （ 2, 5 ）l关键字then （ 3, then ）l标识符x （ 1,指向x的符号表入口）l赋值号:= （ 4, ：= ）l标识符y （ 1, 指向y的符号表入口 ）l分号; （ 5, ; ）u使整个编译程序的结构更简洁、清晰
3、和条理化；u编译程序的效率会改进；u增强编译程序的可移植性。VN， aVT*VT*u程序设计语言中的几类单词可用下述规则描述ll|lll|d|l|dld|dl+|-|*|/|=|l=l,|;|(|)| 其中l表示az中的任何一个英文字母，d表示09中的任何一个数字。u例：ld|.|el d|.|e| l d le| d |l d |sl d ld |其中，s表示正或负号(+,-)。即：s+ |- 判断：4+10e 和 4.2e+10 是否为有效的无符号数。u正规式，即正规/则表达式是描述单词符号的方便工具，也是定义正规集的工具。u递归定义（正规式和它所表示的正规集）：l设字母表为，辅助字母表=
4、，；l和都是上的正规式，所表示的正规集分别为：和 ；l任何a，a都是上的一个正规式，它所表示的正规集为a；l假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)；l仅由有限词使用上述三个步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。注意：l“”读为“或”（可用“+”代替 “”）；l“ ”读为“连接”，连接符“ ”一般可省略不写 ；l“”读为“闭包”（即，任意有限次的自重复连接）；l在
5、不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”、“ ”、“” 。 l“”、“ ”和“” 都是左结合的。u例： 令=a，b, 上的正规式和相应的正规集为：正规式 正规集a aab a,bab ab(ab)(ab) aa,ab,ba,bba ,a,a, 任意个a的串(ab) ,a,b,aa,ab 所有由a和b组成的串(ab)(aabb)(ab) 上所有含有两个相继的a或两个相继的b组成的串说明： 程序设计语言的单词都能用正规式来定义。例：=d，l,l表示字母，d数字，则上的正规式 e1= l(l|d) 表示所有标识符集; e2 =dd （？）表示无符号整数。u例：=d，e，+，-，
6、则上的正规式ud(dd )(e(+- )dd )表示无符号数的集合。u (+- ) d (dd ) (e(+- )dd )表示的是有u符号数的集合。其中，d为09的数字。u若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。u例如：l e1= (ab)， e2 = bal e1= b(ab) , e2 =(ba)ble1= (ab) , e2 =(ab)u设r,s,t为正规式，正规式服从的代数规律lrs=sr“或”服从交换律lr(st)=(rs)t“或”的可结合律l(rs)t=r(st)“连接”的可结合律lr(st)=rsrt (st)r=srtr分配律lr=r r=
7、r 是“连接”的恒等元素（零一律）lrr=r r=rrr“或”的抽取律l注意： rssr r|(st)rs | rtu正规式和正规文法之间具有等价性，可相互转换。u例：DFA M=（S,U,V,Q，a,b，f，S，Q）其中f定义为:lf（S，a）=U f（V，a）=Ul f（S，b）=V f（v，b）=Ql f（U，a）=Q f（Q，a）=Qlf（U，b）=V f（Q，b）=QNFADFANFA和和DFA的比较的比较NFAu对于任何两个有穷自动机M1 和M2，若L(M1)=L(M2)，则称有穷自动机M1 和M2等价。u对于每个NFA M，必存在一个DFA N，使得L(M)=L(N)。u子集转换
8、法中对状态集合I的几个有关运算lI的闭包表示为-closure（I） ，表示状态集I中任何状态A经任意条弧而能到达的状态集；l状态集合I的任何状态都属于-closure(I)。l状态集I的a弧转换，表示为J=move（I,a），J是所有那些从I中某一个状态A经一条a弧而到达的后继状态全体；l对于一个NFAN=（K，f，K0，Kt）来说，若I是K的一个子集，设IS1, S2,. Sj，a是中的一个元素，则：move(I,a)=f(S1,a) f(S2,a) f(Sj,a)。l令记号Ia=-closure (J) =-closure (move (I,a) )u子集构造算法假设NFA N=(K,
9、,f,K0,Kt)按如下办法构造一个DFA M=(S, ,d,S0,St)，使得L(M)=L(N)：l M的状态集S由K的一些子集组成。l用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的状态。并且约定，状态S1, S2,. Sj是按某种规则排列的，即对于子集S1, S2= S2, S1,来说，S的状态就是S1 S2；lM和N的输入字母表是相同的，即是；l转换函数定义为：D(S1 S2,. Sj,a)= R1R2. Ri，其中， R1,R2,. , Ri = -closure(move(S1, S2,. Sj,a)l S0=-closure(K0)为M的开始状态；l St=Sj
10、 Sk. Se，其中：Sj Sk. SeS且Sj , Sk,. Se Kt u构造NFA N的状态K的子集的算法，见图4.5：l 假定所构造的子集族为C，即C= (T1, T2,. Ti),其中T1, T2,. Ti为状态K的子集。u例：应用图4.5的算法对教材图4.4的NFA N构造子集步骤如下：l 1.首先计算-closure(0)：令T0=-closure(0) =0,1,2,4,7，T0未被标记，它现在是子集族C的唯一成员；l2.标记T0：令T1=-closure(move(T0,a) =1,2,3,4,6,7,8，将T1加入C中，T1未被标记；令T2=-closure(move(T0
11、,b)=1,2,4,5,6,7，将T2加入C中，T2未被标记；l3.标记T1：-closure(move(T1,a)=1,2,3,4,6,7,8，即T1，T1已在C中；令T3=-closure(move(T1,b)=1,2,4,5,6,7,9，将T3加入C中，T3未被标记；l4.标记T2：-closure(move(T2,a)=1,2,3,4,6,7,8，即T1，T1已在C中。-closure(move(T2,b) =1,2,4,5,6,7，即T2，T2已在C中；l5.标记T3：-closure(move(T3,a)=1,2,3,4,6,7,8，即T1。-closure(move(T3,b)=
12、1,2,4,5,6,7,10,令其为T4，在入C中，T4未被标记；l6.标记T4：-closure(move(T4,a)=1,2,3,4,6,7,8，即T1；-closure(move(T4,b)=1,2,4,5,6,7，即T2。l 至此，算法终止共构造了5个子集：T0=0,1,2,4,7T1=1,2,3,4,6,7,8T2=1,2,4,5,6,7T3=1,2,4,5,6,7,9T4=1,2,4,5,6,7,10l 那么图4.4的NFA N构造的DFA M为：1、状态集S= T0, T1, T2, T3, T4 2、字母表=a,b3、状态转换函数 D(T0,a)=T1 D(T3,a)=T1 D
13、(T0,b)=T2 D(T3,b)=T4 D(T1,a)=T1 D(T4,a)=T1 D(T1,b)=T3 D(T4,b)=T2 D(T2,a)=T1 D(T2,b)=T24、初态S0=T0；5、终态St=T4为便于书写，将T0、 T1、 T2、 T3、 T4重新命名为A、B、C、D、E或用0、1、2、3、4分别表示，若采用后者，该DFA M的状态转换图如图4.6所示：图图4.6DFAMu将NFA确定化过程用造表法表示如下： l (1)表的第0行和第0列作标识行列得值。l (2)将-closure(k0)作为表中第1行第1列。l (3)假定=a1,a2,.an,设第i行第一列已确定状态集为I,
14、则置该行第i列为Iai,如Iai未曾在任何行第一列出现过，则将Iai加入下一空行i+1的第一列,并在第0列标记为Ti+1。l (4)反复重复第(2)步，直至无新状态出现为止。l (5)重新命名新状态。第5步：重新命名新状态u例：将图4.8中的DFA M最小化。l根据是否终态划分：P0=(1,2,3,4,5,6,7) l根据a弧划分1,2,3,4 ：P1=(1,2,3,4,5,6,7)l根据a弧划分3,4 ：P2=(1,2,3,4,5,6,7) l根据a弧划分5,6,7 ：P3=(1,2,3,4,5,6,7)l不可再分。令1代表1,2消去2，令6代表6,7，消去7，得到图4.8(b)的DFA M
15、，它是4.8(a)的DFA M的最小化。图图4.8(b)化简后化简后 DFA M图图图图4.8（a)化简前化简前 DFA M图图化简前的化简前的DFA化简后的化简后的DFAu例: 以例4.7的NFA M为例，M的状态图如图4.3，求正规式r,使L(r)=L(M)。u例：为R=(a|b)*abb构造NFA N，使L(R)=L(N)。 解 ：- a b XYu例：构造与文法GS等价的NFA M如图4.11所示。GS: Sa A |bB| AaB|bABbA|aS|u以LEX/FLEX为例介绍如何从正规式产生识别该正规式所描述的单词的词法分析程序。uLEX/FLEX是一个广泛使用的工具，用于构造各种
16、各样语言的词法分析程序。UNIX系统中使用lex命令调用。图 4.13 LEX编译系统的作用 图 4.14 使用LEX生成词法分析器 u LEX程序由三部分组成l说明部分：变量说明、常量说明、正规定义l%l转换规则：Pn action nl%l辅助过程：容纳的是action所需要的辅助过程u注意：以上三部份及其中任何一子部份均可省去。如无第三部分，第二个%也可省去，但第一个%决不可省。u1）由代码、模式的宏定义、条件模式的开始说明等组成。u2）代码由顶格的%和% 或不顶格的文字定义； %和% 各单独占一行，由它们说明的部分将被原样拷贝至文件lexyy.c中。u3）宏定义要顶格写。u模式包括%
17、/*此模块为定义模块中语言代码部份*/ %模式宏名1 模式1% start s1 s2 s3% /*此模块为规则模块中语言代码部份*/%模式1 动作1%/*此模块为用户附加C语言部份*/一个完成对键盘输入的文件进行字符数统计的LEX源程序 TEST.Lu教材P67图图4.15给出一个给出一个识别识别PL/O单词的单词的LEX程序片断程序片断。IDENTa-zA-Z a-zA-Z0-9*NUMBER0-9 0-9*%#include stdio.h#include code.h“#include symbol.h“#include y.tab.h“extern int level;int cc=
18、0;% cc+;t tablize(); /*adjustcc to tabposition*/n cc=0; line-copy(); /*copy a line of input file*/ cc+; return GT;= cc+; return EQ; # cc+; return NE; , cc+; return colon; . cc+; return Period;( cc+; return Lparen;) cc+; return Rparen; = cc+;cc+;return GE; = cc+; cc+;return ASGN; cc+; return Semicolo
19、n;NUMBER int n;cc += yyleng;sscanf(yytext,%d, &n);yylval.number=n;return NUMBER; IDENT Symbol *s;cc += yyleng;if(s=lookup(yytext)=0) /*new identifier*/s=install(yytext,VARIABLE,level,0); /* install symbol*/if (stype=C)yylval.number=s-adr;else /*its a VARIABLE or PROC*/yylval.sym=s;return s-type;%yyw
20、rap( ) ; 1.构造正规式构造正规式1（01）*101相应的相应的DFA。4.74.7典型例题及解答典型例题及解答2.将图将图4.18所示的所示的DFA最小化。最小化。3.下面是用于生成词法分析器下面是用于生成词法分析器scanner的的LEX的源文的源文件，请给出件，请给出scanner对输入串对输入串ababcbacaabaababaa的的输出结果：输出结果：%a+b*a printf( 1%sn,yytext);(ab)+c? printf( 2%sn,yytext);aa printf( 3%sn,yytext);(a|b)*c printf( 4%sn,yytext);u词法分
21、析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词,交由语法分析程序接下去。u本章讲述了词法分析程序设计原则，并介绍了正规式和有穷动机分别作为正规集描述和识别机制。在此基础上给出了词法分析程序自动构造工具如LEX的原理。u要求掌握：lNFA，正规式，正规文法三者间的等价转换。lNFA化为DFA称为确定化，一般用造表法或子集法。lDFA最小化称为化简，用分割法。u词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作。通过LEX，说明词法分析程序的语言，可以看成是一个模式动作语言。u词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。
