词法分析程序的设计课件

主要任务：扫描源程序，产生单词符号序列。其他任务：滤掉空格，跳过注释、换行符；追踪换行标志，复制出错源程序；宏展开，……4.1词法分析程序的设计源程序词法分析程序语法分析程序Tokengettoken….主要任务：扫描源程序，产生单词符号序列。4.1词法分析程序词法分析工作可以是独立的一遍。把字符流的源程序转换为单词序列，输出在一个中间文件上，这个文件作为语法分析程序的输入。更通常情况，常将词法分析程序（扫描器）设计成一个子程序。每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每得到一次调用，便从源程序文件中读入一些字符，直到识别出一个单词，或说直到下一单词的第一个字符为止。词法分析程序与语法分析程序的接口方式词法分析工作可以是独立的一遍。把字符流的源程序转换为单词序列二.单词符号一般可分为下列五种基本字(关键字、保留字)：具有特殊含义的标识符，不作他用，有分隔语法的作用。标识符：表示各种名字，如常量名、变量名、过程名。常数（量）：包括整型、实型、布尔型、字符型常常量，如25、3.1415、true、“ABC”。运算符：包括算术、逻辑、关系运算符，如：＋、－、*、＜=。界符：包括.，;，(，)，:，,等，有时也把运算符称作界符。词法分析程序的输出二.单词符号一般可分为下列五种词法分析程序的输出扫描器的输出表示扫描器从初态出发，当识别一个单词后便进入终态，同时输出二元组形式的单词序列。二元组：（单词种别，单词自身值或指针）单词种别：语法分析需要的信息，可以用整数编码表示，假如标识符编码为1，常数为2，关键字为3，运算符为4，界符为5。单词自身的值或指针：编译其他阶段需要的信息。对于标识符，其值为指向该标识符所在符号表中位置的指针。扫描器的输出表示例：ifi=5thenx:=y，词法分析后输出的二元组形式的单词序列如下：关键字if

(3,‘if’)标识符i（1，指向i的符号表入口）等号＝（4,‘=’）常数5（2,‘5’）关键字then（3,‘then’）标识符x（1,指向x的符号表入口）赋值号:=（4,‘：=’）标识符y（1,指向y的符号表入口）分号;（5,‘;’）例：ifi=5thenx:=y，词法分析后输出的二元使整个编译程序的结构更简洁、清晰和条理化；编译程序的效率会改进；增强编译程序的可移植性。将词法分析工作分离的考虑使整个编译程序的结构更简洁、清晰和条理化；将词法分析工作分离4.2.1正规文法3型文法：又称右线性文法或正规文法(RegularGrammars),其表达式形如：A→aB或A→a。其中A、B∈VN，a∈VT*。正规文法描述的语言是VT*上的正规集。绝大部份程序设计语言的单词都能用正规文法来描述。4.2

单词的描述工具4.2.1正规文法3型文法：又称右线性文法或正规文法(R程序设计语言中的几类单词可用下述规则描述<标识符>→l|l<字母数字><字母数字>→l|d|l<字母数字>|d<字母数字><无符号整数>→d|d<无符号整数><运算符>→+|-|*|/|=|<<等号|><等号>……<等号>→=<界符>→,|;|(|)|……其中l表示a~z中的任何一个英文字母，d表示0~9中的任何一个数字。程序设计语言中的几类单词可用下述规则描述例：<无符号数>→d<余留无符号数>|.<十进小数>|e<指数部分><余留无符号数>→d<余留无符号数>|.<十进小数>|e<指数部分>|<十进小数>→d<余留十进小数><余留十进小数>→e<指数部分>|d<余留十进小数>|<指数部分>→d<余留整指数>|s<整指数><整指数>→d<余留整指数><余留整指数>→d<余留整指数>|其中，s表示正或负号(+,-)。即：s→+|-

判断：4+10e和4.2e+10是否为有效的无符号数。例：正规式，即正规/则表达式是描述单词符号的方便工具，也是定义正规集的工具。递归定义（正规式和它所表示的正规集）：设字母表为，辅助字母表’={，，，，，，}；和都是上的正规式，所表示的正规集分别为：{}和{}；任何a，a都是上的一个正规式，它所表示的正规集为{a}；假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1

也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1))

；4.2.2正规式正规式，即正规/则表达式是描述单词符号的方便工具，也是定义正仅由有限词使用上述三个步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。注意：“”读为“或”（可用“+”代替“”）；“

”读为“连接”，连接符“

”一般可省略不写；“

”读为“闭包”（即，任意有限次的自重复连接）；在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“

”、“

”、“”。“

”、“

”和“”都是左结合的。仅由有限词使用上述三个步骤而定义的表达式才是上的正规式，仅例：令={a，b},上的正规式和相应的正规集为：正规式 正规集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a

{,a,a,……任意个a的串}(ab)

{,a,b,aa,ab……所有由a和b组成 的串}(ab)

(aabb)(ab)

{

上所有含有两个相继的a或两个相继的b组成的串}例：令={a，b},上的正规式和相应的正规集为：说明：

程序设计语言的单词都能用正规式来定义。例：

={d，l},l表示字母，d数字，则上的正规式e1=l(l|d)表示所有标识符集;e2=dd（？）表示无符号整数。例：

={d，，e，+，-}，则上的正规式d(dd)(e(+-)dd)表示无符号数的集合。

(+-)

d

(dd)

(e(+-)dd)表示的是有符号数的集合。其中，d为0~9的数字。说明：若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：

e1=(ab)，e2=bae1=b(ab),e2=(ba)b e1=(ab),e2=(ab)词法分析程序的设计课件设r,s,t为正规式，正规式服从的代数规律rs=sr “或”服从交换律r(st)=(rs)t “或”的可结合律(rs)t=r(st) “连接”的可结合律r(st)=rsrt (st)r=srtr 分配律

r=rr=r 是“连接”的恒等元素（零一 律）rr=r r

=rrr… “或”的抽取律注意：

rssrr|(st)rs|rt设r,s,t为正规式，正规式服从的代数规律正规式和正规文法之间具有等价性，可相互转换。将

=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。反复利用上述规则，直至所有产生式都符合正规文法的定义。4.2.3正规文法和正规式的等价性正规式和正规文法之间具有等价性，可相互转换。4.2.3正例：将R=a(a|d)*转换成相应的正规文法.解：

(1) S→a(a|d)* (2) S→aA,A→(a|d)*ε (3) S→aA,A→(a|d)A，A→ε (4) S→aA,A→aA，A→dA，A→ε

相应的正规文法如(4)式所示，即

G[S]: S→aA A→aA A→dA A→ε例：将R=a(a|d)*转换成相应的正规文法.将正规文法G=(VN,VT,P,S)换成

=VT上的正规式r的转换规则：（1）将产生式A→xBB→y合写为A=xy；（2）将产生式A→xAA→y合写为A=x*y；（3）将产生式A→xA→y合写为A=x|y。反复利用上述规则，直至只剩下一个由开始符定义的正规式。将正规文法G=(VN,VT,P,S)换成=VT上的正例：将正规文法G[S]转换成正规式。G[S]:S→dA|eBA→aA|bB→bB|c解：

(1) 由A→aA|b，有A=a*b；

(2) 由B→bB|c，有B=b*c；

(3) 由S→dA|eB，有S=d(a*b)|e(b*c)

故正规式d(a*b)|e(b*c)为所求。例：将正规文法G[S]转换成正规式。有穷自动机

(FiniteAutomata)：可准确的识别正规集。分类确定的有穷自动机(DeterministicFiniteAutomata,简称DFA);不确定的有穷自动机(NondeterministicFiniteAutomata,简称NFA).4.3有穷自动机有穷自动机(FiniteAutomata)：可准确的4.3.1确定的有穷自动机(DFA)确定的有穷/有限自动机（DFA）定义为五元组DFAM=(K,,f,S,Z),其中：(1)K是一有穷状态集；(2)

是一有穷字母表，称输入符号字母表；(3)f是转换函数，是在K→K上的映射。如f(ki,a)=kj；(4)S是唯一的一个初态；(5)ZK，是一终态集，终态也称结束态或可接受态或可识别态。4.3.1确定的有穷自动机(DFA)确定的有穷/有限自动机例：DFAM=（{S,U,V,Q}，{a,b}，f，S，{Q}）其中f定义为:f（S，a）=U f（V，a）=Uf（S，b）=V f（v，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q例：DFAM=（{S,U,V,Q}，{a,b}，f，S一个DFA可以表示成一个状态图（状态转换图）假定DFA

M含有m个状态，n个输入符号,则其状态图含有m个结点，每个结点最多有n个弧射出；整个图含有唯一一个初态结点(=>、－)和若干个终态结点(双圈、+)；若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧。前例的DFA的状态图表示如右：一个DFA可以表示成一个状态图（状态转换图）DFA的矩阵表示行表示状态；列表示输入字符则；矩阵元素表示相应状态行和输入字符列下的新状态，即第k行a列为f(k,a)的值；用“=>”标记行或“+”第一行表示初态；终态行右端标以1，非终态行右端标以0。前例的DFA的矩阵表示如下：DFA的矩阵表示方便起见，对DFA中转换函数定义进行扩充：

f是转换函数，是在K*→K上的映射，有

(1)f(k1,ε)=k1(2)f(k1,aα)=f(f(k1,a),α)

其中，k1∈K,a∈

,α∈*。接受(识别)

设DFA=(K,,f,S,Z)，若f(S,α)=P∈Z,则称符号串α∈*可被该DFA接受(识别)。方便起见，对DFA中转换函数定义进行扩充：例:试证串abbc可被图示DFA识别。证：f(S,abbc)=f(f(S,a),bbc)=f(f(A,b),bc)=f(f(A,b),c)=f(A,c)=BB为终态，得证。例:试证串abbc可被图示DFA识别。重要结论：上的一个字符串集V*是正规集，当且仅当存在着一个上的确定有穷自动机M，使得V=L(M)。DFA的确定性表现在状态转换函数是一个单值函数，即f(k,a)唯一确定一个后继状态。重要结论：上的一个字符串集V*是正规集，当且仅当存在着不确定的有穷自动机可以定义为五元组NFAM=(K,,f,S,Z),其中：(1)K是一有穷状态集；(2)

是一有穷字母表，称输入符号字母表；(3)f是转换函数，是在K*→K的子集上的映射；(4)SK，是非空初态集；(5)ZK，是一个终态集，终态也称结束态或可接受态。NFA同样能表示成状态图或矩阵。DFA是NFA的特例。4.3.2不确定的有穷自动机(NFA)不确定的有穷自动机可以定义为五元组NFAM=(K,,f,NFADFANFA和DFA的比较NFANFADFANFA和DFA的比较NFA在NFA中，因为f是转换函数，是在K*→K的子集上的映射，故有：f(k,aα)=f(k1,α)∪f(k2,α)...∪f(kn,α)其中，ki∈K,a∈

,α∈*，且f(k,a)={k1,k2,....kn}设NFA=(K,,f,S,Z)，如果z0∈f(S,α) 且z0∈Z,则称符号串α∈*可被该NFA接受(识别)。有穷自动机M所能接受的所有符号串集称为此自动机可接受的语言L(M)。在NFA中，因为f是转换函数，是在K*→K的子集上的映射例:试证串abc可被图示NFA识别证：f(S,abc)=f(A,bc)=f(A,c)∪f(C,c)=B又因为B∈

终态集{B}，得证。例:试证串abc可被图示NFA识别4.3.3ＮFA到DFA的等价转换对于任何两个有穷自动机M1和M2，若L(M1)=L(M2)，则称有穷自动机M1和M2等价。对于每个NFAM，必存在一个DFAN，使得L(M)=L(N)。子集法是一种将ＮFA转换为能接受同样语言的DFA的等价转换算法。4.3.3ＮFA到DFA的等价转换对于任何两个有穷自动机M子集转换法中对状态集合I的几个有关运算I的ε闭包表示为ε-closure（I），表示状态集I中任何状态A经任意条ε弧而能到达的状态集；状态集合I的任何状态都属于ε-closure(I)。状态集I的a弧转换，表示为J=move（I,a），J是所有那些从I中某一个状态A经一条a弧而到达的后继状态全体；对于一个NFAN=（K，，f，K0，Kt）来说，若I是K的一个子集，设I＝{S1,S2,,...

Sj}，a是∑中的一个元素，则：move(I,a)=f(S1,a)∪f(S2,a)∪…∪f(Sj,a)。令记号Ia=ε-closure(J)=ε-closure(move(I,a))子集转换法中对状态集合I的几个有关运算例：对下图NFA： 取I={S,1},则：

ε-closure(I)＝{S,1,2}, J=move(I,0)={1}, I0=ε-closure(J)={1,2}例：对下图NFA：子集构造算法假设NFAN=(K,,f,K0,Kt)按如下办法构造一个DFAM=(S,,d,S0,St)，使得L(M)=L(N)：

M的状态集S由K的一些子集组成。用[S1S2...

Sj]表示S的元素，其中S1,S2,,...

Sj是K的状态。并且约定，状态S1,S2,,...

Sj是按某种规则排列的，即对于子集{S1,S2}={S2,S1,}来说，S的状态就是[S1S2]；M和N的输入字母表是相同的，即是；子集构造算法转换函数定义为：D([S1S2,...

Sj],a)=[R1R2...

Ri]，其中， {R1,R2,...,Ri}=-closure(move({S1,S2,,...

Sj},a))

S0=-closure(K0)为M的开始状态；

St={[SjSk...

Se]，其中：[Sj

Sk...

Se]

S且{Sj,Sk,,...

Se}∩KtØ}构造NFAN的状态K的子集的算法，见图4.5：

假定所构造的子集族为C，即C=(T1,T2,,...Ti),其中T1,T2,,...Ti为状态K的子集。转换函数定义为：词法分析程序的设计课件例：应用图4.5的算法对教材图4.4的NFAN构造子集步骤如下：

1.首先计算

-closure(0)：令T0=-closure(0)={0,1,2,4,7}，T0未被标记，它现在是子集族C的唯一成员；例：应用图4.5的算法对教材图4.4的NFAN构造子集2.标记T0：令T1=-closure(move(T0,a))={1,2,3,4,6,7,8}，将T1加入C中，T1未被标记；令T2=-closure(move(T0,b))={1,2,4,5,6,7}，将T2加入C中，T2未被标记；3.标记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未被标记；4.标记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中；2.标记T0：令T1=-closure(move(T0,a5.标记T3：-closure(move(T3,a))={1,2,3,4,6,7,8}，即T1。-closure(move(T3,b))={1,2,4,5,6,7,10},令其为T4，在入C中，T4未被标记；6.标记T4：

-closure(move(T4,a))={1,2,3,4,6,7,8}，即T1；-closure(move(T4,b))={1,2,4,5,6,7}，即T2。词法分析程序的设计课件

至此，算法终止共构造了5个子集：T0={0,1,2,4,7}T1={1,2,3,4,6,7,8}T2={1,2,4,5,6,7}T3={1,2,4,5,6,7,9}T4={1,2,4,5,6,7,10}

那么图4.4的NFAN构造的DFAM为：

1、状态集S={[T0],[T1],[T2],[T3],[T4]} 2、字母表∑={a,b}词法分析程序的设计课件

3、状态转换函数

D([T0],a)=[T1]D([T3],a)=[T1] D([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)=[T2] 4、初态S0=[T0]；

5、终态St=[T4]为便于书写，将[T0]、[T1]、[T2]、[T3]、[T4]重新命名为A、B、C、D、E或用0、1、2、3、4分别表示，若采用后者，该DFAM的状态转换图如图4.6所示： 3、状态转换函数图4.6

DFA

M图4.6DFAM将NFA确定化过程用造表法表示如下：

(1)表的第0行和第0列作标识行列得值。

(2)将ε-closure(k0)作为表中第1行第1列。

(3)假定

={a1,a2,...an},设第i行第一列已确定状态集为I,则置该行第i列为Iai,如Iai未曾在任何行第一列出现过，则将Iai加入下一空行i+1的第一列,并在第0列标记为Ti+1。

(4)反复重复第(2)步，直至无新状态出现为止。

(5)重新命名新状态。例：将图示r的NFA确定化(第1-4步：造表)将NFA确定化过程用造表法表示如下：例：将图示r的NFA确词法分析程序的设计课件词法分析程序的设计课件第5步：重新命名新状态第5步：重新命名新状态4.3.4DFA的化简一个DFA是化简(最小化)了的，即是说，它没有多余状态且其状态中没有相互等价的。多余状态是指从自动机的开始状态出发，任何输入串也不可达的状态；或无法到达终态的状态。在DFA中，两个状态s和t等价的条件是：一致性条件：状态s和t必须同时为可接受态和不可接受态。蔓延性条件：对于所有输入符号，状态s和t必须转换到等价的状态里。4.3.4DFA的化简一个DFA是化简(最小化)了的，即对DFA最小化的本质：消除多余状态、合并等价状态。分割法：将不含多余状态的DFA分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而相同子集中状态是等价的。DFA最小化过程首先，将DFA状态分割成终态集合和非终态集合；再根据输出弧所达到状态的性质逐步细分。即对每个集合中的状态分别用输出字母去查看它们到达状态的集合是否在同一个集合中；如果不在同一个集合，将它们划分在不同的集合中；直到不能再划分为止。对DFA最小化的本质：消除多余状态、合并等价状态。例：将图4.8中的DFAM最小化。根据是否终态划分：P0=({1,2,3,4},{5,6,7})根据a弧划分{1,2,3,4}

：P1=({1,2},{3,4},{5,6,7})根据a弧划分{3,4}

：P2=({1,2},{3},{4},{5,6,7})根据a弧划分{5,6,7}：P3=({1,2},{3},{4},{5},{6,7})不可再分。令1代表{1,2}消去2，令6代表{6,7}，消去7，得到图4.8(b)的DFAM`，它是4.8(a)的DFAM的最小化。例：将图4.8中的DFAM最小化。图4.8(b)化简后DFAM’图图4.8（a)化简前DFAM图图4.8(b)化简后DFAM’图图4.8（a)化简前例：对图示DFA最小化。解：P0={{1,2,3},{4,5,6,7}}根据各子集输出弧0和1后所达到状态是否为终态，进一步划分为：P1={{1},{2},{3}，{4,5,6,7}}最小化后DFA为右下图。化简前的DFA化简后的DFA例：对图示DFA最小化。化简前的DFA化简后的DFA词法分析程序的设计课件对于上的每个NFAM，可以构造一个相应的上的正规式R，使得L(R)=L(M)。对于上的每个正规式R，可以构造一个相应的上的NFAM，使得L(R)=L(M)。4.4正规式和有穷自动机的等价性对于上的每个NFAM，可以构造一个相应的上的正规式R，构造过程首先，引入两个新结点x,y;x经ε弧到所有初态，所有终态经ε弧到y；然后，再用如下消解规则消去除x,y外的所有结点，最后x,y间弧上的标记串就是所求正规式。由NFAM构造等价的正规式R构造过程由NFAM构造等价的正规式R例:

以例4.7的NFAM为例，M的状态图如图4.3，求正规式r,使L(r)=L(M)。解：R=(a|b)*(aa|bb)(a|b)*例:以例4.7的NFAM为例，M的状态图如图4.3，求词法分析程序的设计课件例：给出与图示NFAM等价的正规式R解：R=(0|1)*(00|11)(0|1)*例：给出与图示NFAM等价的正规式R由正规式R构造等价的NFAM的过程与上述过程相反。用如下构造规则构造NFA：1、对单个正规式对于正规式Ø，所构造的NFA只含初态和终态两个状态。由正规式R构造等价的NFAM由正规式R构造等价的NFAM的过程与上述过程相反。用如下构词法分析程序的设计课件词法分析程序的设计课件词法分析程序的设计课件例：为R=(a|b)*abb构造NFAN，使L(R)=L(N)。

ε解

：-εaε ε bε εXY例：为R=(a|b)*abb构造NFAN，使L(R)=L(对于上的每个NFAM，可以构造一个相应的上的正规文法G，使得L(G)=L(M)。对于上的每个正规文法G，可以构造一个相应的上的NFAM，使得L(M)=L(G)。4.5

正规文法和有穷自动机的等价性对于上的每个NFAM，可以构造一个相应的上的正规文法G构造过程(0)M的字母表与G的终结符集相同。(1)为G中每个非终结符生成M一个状态，开始符为初态。(2)增加一新状态Z，做为NFAM的终态。(3)对形如A→aB或A→B的产生式，构造M的转换函数f(A,a)=B或f(A,ε)=B。

(4)对形如A→a的产生式，构造M的转换函数f(A,a)=Z。由正规文法G构造等价的NFAM构造过程由正规文法G构造等价的NFAM例：构造与下面文法G等价的NFAM: G[S]: S→aS|bS|aB B→bC C→b解：用1、2、3对应S、B、C，加上终态4，按转换规则得NFAM如下：例：构造与下面文法G等价的NFAM:例：构造与文法G［S］等价的NFAM如图4.11所示。G[S]: S→aA|bB|ε A→aB|bA B→bA|aS|ε例：构造与文法G［S］等价的NFAM如图4.11所示。与前一过程相反，用如下构造规则构造：对转换函数f(A,a)=B或f(A,ε)=B，改成形如A→aB或A→B的产生式对能识别终态Z，增加一个产生式：Z→ε由NFAM构造等价的正规文法G与前一过程相反，用如下构造规则构造：由NFAM构造等价的正例：构造与下面NFAM等价的文法G。解：用S、A、B、C对应状态1、2、3、4，

G[S]: S→aS|bS|aA A→bB B→bC C→ε例：构造与下面NFAM等价的文法G。例：构造与下面NFAM等价的文法G。解：G[A]: A→aB|bD B→bC C→aA|bD|ε D→aB|bD|ε例：构造与下面NFAM等价的文法G。以LEX/FLEX为例介绍如何从正规式产生识别该正规式所描述的单词的词法分析程序。LEX/FLEX是一个广泛使用的工具，用于构造各种各样语言的词法分析程序。UNIX系统中使用lex命令调用。图4.13LEX编译系统的作用

4.6词法分析程序的自动构造工具以LEX/FLEX为例介绍如何从正规式产生识别该正规式所描述图4.14使用LEX生成词法分析器图4.14使用LEX生成词法分析器LEX程序由三部分组成说明部分：变量说明、常量说明、正规定义%%转换规则：Pn{actionn}%%辅助过程：容纳的是action所需要的辅助过程注意：以上三部份及其中任何一子部份均可省去。如无第三部分，第二个%%也可省去，但第一个%%决不可省。LEX程序由三部分组成说明部分1）由Ｃ代码、模式的宏定义、条件模式的开始说明等组成。2）Ｃ代码由顶格的%{和%}或不顶格的文字定义；%{和%}各单独占一行，由它们说明的部分将被原样拷贝至文件lexyy.c中。3）宏定义要顶格写。例：%{intnum_chars,num_lines;%}DIGIT[0-9]ID[a-z][a-z0-9]*或ID[A-Za-z][A-Za-z0-9_]*说明部分1）由Ｃ代码、模式的宏定义、条件模式的开始说明等组成规则部分由模式——动作对组成(顶格书写)，实际上是一张含两列的表，左边一列是表示正规式的模式或表示正规式的词形，右边一列是相应动作，通常是若干Ｃ语言代码。正规式与动作之间必须用空格分开。例：\n{++num_chars;++num_lines;}规则部分由模式——动作对组成(顶格书写)，实际上是一张含两列模式包括运算符（元字符）16种：“、\、^、[]、-、?、.、*、+、()、%、<>、$、/、|、{}匹配元字符需用转义符\或“几个特殊符号：

\n是回车换行

\t是tab\b是退格空白字符的处理:需用“

”或[]括起来模式包括词法分析程序的设计课件词法分析程序的设计课件辅助部分即第二个%%后部分，此处代码将被原样拷贝至文件lexyy.c的尾部；此部分是可省的。辅助部分即第二个%%后部分，此处代码将被原样拷贝至文件lexLEX源文件详细格式如下：%{/*此模块为定义模块中Ｃ语言代码部份*/}%模式宏名1模式1……%starts1s2s3%%%{/*此模块为规则模块中Ｃ语言代码部份*/}%模式1动作1……%%/*此模块为用户附加C语言部份*/LEX源文件详细格式如下：例:一个完成对键盘输入的文件进行字符数统计的LEX源程序TEST.L

intnum_chars=0,num_lines=0;%%\n{++num_chars;++num_lines;}/*要顶格写*/.++num_chars;%%main(){yylex();printf("thelineis%d,thecharis%d",num_lines,num_chars);}intyywrap(){return1;}例:一个完成对键盘输入的文件进行字符数统计的LEX源程序LEX或FLEX的使用方法1、编辑lex源程序test.l。2、在DOS提示符下运行(假定flex.exe在d:\bision目录下),生成lexyy.c：

d:\bision\flextest.l3、将lexyy.c在C编辑器下编译成可执行文件lexyy.exe（或改名为test.c或加入工程文件test中，生成test.exe文件）。4、运行lexyy.exe或test.exe。LEX或FLEX的使用方法1、编辑lex源程序test.l教材P67图4.15给出一个识别PL/O单词的LEX程序片断。IDENT[a-zA-Z][a-zA-Z0-9]*NUMBER[0-9][0-9]*%{#include〈stdio.h〉#include"code.h“#include"symbol.h“#include"y.tab.h“externintlevel;intcc=0;%}%%""{cc++;}教材P67图4.15给出一个识别PL/O单词的LEX程序片断"＼t"{tablize();}/*adjustcctotabposition*/"＼n"{cc=0;line-copy();}/*copyalineofinputfile*/"<"{cc++;returnLT;}">"{cc++;returnGT;}"="{cc++;ret