编译原理第3章.词法分析.ppt

第三章 词法分析,2019/6/6,2,回忆：词法分析程序的功能：对构成源程序的字符串从左到右进行扫描和分解，并根据语言的词法规则识别出一个个具有独立意义的单词符号。 具体： 设计成单独一遍扫描。 设计成子程序，当语法分析器需要新单词时调用它。,第三章. 词法分析3.0 词法分析程序的功能,源程序,词 法 分 析,单词符号序列,语 法 分 析,源程序,词法 分析 子程序,语 法 分 析,取单词,2019/6/6,3,3.1 词法分析程序的输入输出,一.输入：字符串表示的源程序 二.输出：单词符号或单词符号表示的源程序 1.语言的单词符号：是指语言中具有独立意义的最小语法单位。共分五类： 保留字、标识符、常数、运算符、和界符 2.单词符号的内部表示： 二元组（单词种别码，单词自身值） 继续,2019/6/6,4,单词种别码,保留字： 一字一种：1begin 2end 3if 4then 全体为一种：0 或者 k 标识符： 全体为一种 常数： 数据类型：整型、实型、字符型、布尔型 全体为一种 运算符： 一符一种 全体为一种 界符： 一符一种 全体为一种 返回,2019/6/6,5,单词自身值,如果一个种别码对应一个单词符号，则种别码可以代表单词自身。 如果一个种别码对应多个单词符号，则单词自身值是单词符号的机内码。,机内码： 标识符：自身串（ASCII码） 常数：二进制值、逻辑值,If a 1 then b=100,词 法 分 析 器,（3， ） （6，a） （12， ） （7，1的二进制） （4， ） （6，b） （10， ） （7，100的二进制）,2019/6/6,6,用相应符号表项的指针值来区分同类中不同的单词符号。 K表： I表： C表：,if a 1 then b=100,词 法 分 析 器,（k，3 ） （I，1 ） （P，18） （C，1） （K，4） （I，2 ） （P，10） （C，2）,返回,2019/6/6,7,3.2 词法分析程序的设计 一.输入、预处理,输入缓冲区,预处理 子程序,扫描缓冲区,源程序,词法分析的预处理程序：从源 程序中处理出一串确定长度的 输入字符，并将其装进词法分 析程序的扫描缓冲区。 处理： 删除注解、空格、回车符、 换行符之类非必要信息。 把标识符登录入符号表以及 某些预加工处理等。,扫描缓冲区的设计： 两个指针：起点指针,搜索指针 两个半区：左右半区互补使用,起点指针,搜索指针,2019/6/6,8,二.单词符号的识别以及超前搜索,词法分析程序在识别单词时,对有些单词需要向源程序中多看若干个字符才能被识别,称为超前搜索。 1.关键字的识别: 有些语言中关键字的识别需要超前搜索。例如:FORTRAN语言中: 1 DO99K=1, 10 2 DO99K=1.10 2.标识符的识别: 以运算符、界符、空格等结束。 3.常数的识别: 需要超前搜索。例如: 5.EQ.M 和 5.E08。 4.运算符和界符的识别: 需要超前搜索。例如: =,2019/6/6,9,状态转换图: 是由一组矢线连接的有限个结点所组成的有向图。其作用是识别相应的字符串。 例如: 标识符: I l | I l | I d 初态 = 终态 例如: 数字 | 数字 = ,三.状态转换图,l,非 l,非 d,l/d,d,非d,d,2019/6/6,10,利用状态转换图识别(或接受)字符串的过程: 从初态出发, 按照与符号串余留部分中最左字符相匹配的原则, 游历状态图, 直至符号串的末端为止。如果这时恰好到达终态, 则符号串为该文法的句子；否则不是。例如：识别 num1、1001 初态 = 终态 ,l,非 l,非 d,l/d,d,非d,d,2019/6/6,11,大多数程序设计语言的单词符号都可以用状态转换图来识别。可以用一张状态转换图或若干张状态转换图来描述一个语言的所有单词。例如：图3.3是简单语言词法分析的状态转换图。,2019/6/6,12,2.由正规文法构造状态转换图 (1).右线性文法 = 状态转换图,已知: G=(VN , VT , P , S ) P : AaB | a A , BVN , aVT* 求: 状态转换图M 设: | VN |=k , 则状态转换图M共有k+1个结点 方法: 初态=S , 增设终态结点F 对G中形如AaB 的产生式, 从结点A引一条矢线到结点B , 并用 a 标记。 对G中形如Aa 的产生式, 从结点A引一条矢线到终态结点F , 并用 a 标记。 对G中形如A 的产生式, 从结点A引一条矢线到终态结点F , 并标记为 , 或令A为接受状态。,2019/6/6,13,例如: 文法GZ : Z 0A A 0A | 0B B 1A | 语言为 : L(G)=0 ( 0 | 01 )* 0 求 : 状态转换图。,2019/6/6,14,(2).左线性文法 = 状态转换图,已知: G=(VN , VT , P , S ) P : ABa | a A , BVN , aVT* 求: 状态转换图M 设: | VN |=k , 则状态转换图M共有k+1个结点 方法:新增初态=R , S=终态结点 对G中形如ABa 的产生式, 从结点B引一条矢线到结点A , 并标记为 a 。 对G中形如AB 的产生式, 从结点B引一条矢线到结点A , 并标记为 。 对G中形如Aa 的产生式, 从初态R引一条矢线到结点A , 并 标记为 a 。,2019/6/6,15,例如: 文法GS : S S1 | U1 U U0 | 0,2019/6/6,16,四.状态转换图 = 程序,词法分析程序的设计步骤: 1.画出状态转换图(正规文法、正规式) 2.对于状态转换图中的每一个状态构造一段程序代码。 功能为:从输入串中读一个字符。 判断所读字符与该状态哪条弧相匹配 , 转到匹配弧状态。 都不匹配时便失败(不能到达正常出口) 。 具体: 不含回路的分支结点 , 对应一个switch 或 ifthenelse语句构成的程序段。(P44-45) 含回路的分支结点 , 对应一个while 和 if 语句构成的程序段。(P45) 终态结点,对应一个形如 return ( code , value )的语句。 例如: P4246 简单语言的词法分析程序。,2019/6/6,17,int code value; strToken=“; GetChar();GetBC(); if (IsLetter() while(IsLetter() | IsDidit() ) Concat(); GetChar(); Retrace(); code=Reserve(); if (code=0) value=InsertId(strToken); return($ID,Value); else return(code,-); else if ( Isdigit() ) while(IsDigit() Concat(); GetChar(); Retrace(); value=InserConst(strToken); return($INT,Value); ,2019/6/6,18,else if(ch=) return($ASSIGN,-); else if(ch=+) return($PLUS,-); else if(ch=*) GetChar(); if(ch=*) return($POWER,-); Retract(); return($STAR,-); else if(ch=;) return($SEMICOLON,-); else if(ch=() return($LPAR,-); else if(ch=) return($RPAR,-); else if(ch=) return($LBRACE,-); else if(ch=) return($RBRACE,-); else ProcError();,2019/6/6,19,3.3 单词符号的两种定义方式,正规式,以标识符为例: Il|Il|Id 或 Il|lT Tl|d|lT|dT,以标识符为例: l ( l | d )*,正规文法,2019/6/6,20,一.正规式与正规集的递归定义:,设有字母表=a1 , a2 , a3 , , an , 定义 : ，ai 都是上的正规式，它们所描述的正规集分别为 ，ai。 如果e1和e是上的正规式，它们所描述的正规集分别为L(e1) , L(e2)，则 (e1)也是正规式，相应的正规集L( (e1) )=L(e1) e1 | e2也是正规式，相应的正规集L(e1|e2)=L(e1) L(e2) e1e2也是正规式，相应的正规集L(e1e2)=L(e1) L(e2) e1*也是正规式，相应的正规集L( e1* )=( L(e1) )*,2019/6/6,21,例：令a , b ， 下面是上的正规式和相应的正规集 正规式 正规集 ba* 上b开头任意个a a(a|b)* 上所有以a为首的字 a+b+ 上ambn , m,n1的字 例：令A，B，1 ，则 正规式 正规集 （A|B)(A|B|0|1)* 上的标识符的全体 （0|1)(0|1)* 上数的全体 结论：正规式是正规语言的另一种表示方法 定义：若正规式R1和R2所描述的正规集相同，则称正规式R1和R2等价，并记为： R1R2 。 例如：b(ab)*=(ba)*b (a|b)*=(a* b*)* 。,2019/6/6,22,二、正规文法与正规式 1、正规文法到正规式的转换 1 Z=0A A=0A+0B B=1A+ 2利用求解规则R： 若x=x+ 则解为x= * 若x=x+ 则解为x= * 将代入得 Z=0A Z=0A A=0A+0(1A+ ) A=(0+01)A+0 由R：A=(0|01)*0 Z=0 (0|01)*0,例1：已知文法GZ : Z 0A A 0A | 0B B 1A | ,例2 设有正规文法G：,A aB | bB,B aC | a | b,C aB,试给出该文法生成语言的正规式。,分析 首先给出相应的正规式方程组(方程组中用“”代替正规式中的“ | ” )如下：,A = aB + bB (1),B = aC + a + b (2),C = aB (3),将(3)代入(2)中的C得,B = aaB + a + b (4),对(4)使用求解规则得,B = (aa)*(a + b) (5),(5)代入(1)中的B得,即正规文法GA所生成语言的正规式是,A = (a + b)(aa)*(a + b),R = (a | b)(aa)*(a | b),A = aB + bB (1),B = aC + a + b (2),C = aB (3),例3 设有正规文法G：,相应的正规式方程组为,Z U0 | V1,U Z1 | 1,V Z0 | 0,Z = U0 + V1 (1),U = Z1 + 1 (2),V = Z0 + 0 (3),(2)和(3)代入(1)得,Z = Z10 + 10 + Z01 + 01 (4),对(4)使用求解规则得,即正规文法GZ所生成语言的正规式是,Z = U0 + V1 (1),U = Z1 + 1 (2),V = Z0 + 0 (3),Z = (10 + 01) (10 + 01 )*,R = (10 | 01)(10 | 01)*,例4 已知描述 “标识符” 单词符号的正规 文法为,lld,根据前述求解规则, 可知该文法所描述语言的正规式是 l ( l | d )*,2. 正规式到正规文法的转换,(1) 令 VT= 。,(2) 对任何正规式R选择一个非终结符Z生 成规则ZR并令SZ。,(3) 若a和b都是正规式，对形如 Aab 的 规则转换成 AaB 和 Bb 两规则， 其中B是新增的非终结符。,(4) 对已转换的文法中, 形如A a*b 的规 则，进一步转换 成 A aA | b 。,(5) 不断利用规则(3)和(4)进行变换，直到 每条规则最多含有一个终结符为止。,例1 将 R=(a | b)(aa)*(a | b) 转换成相应的 正规文法,令A是文法开始符号，根据规则(2)变换为,根据规则(3)变换为,A (a | b)(aa)*(a | b),A (a | b)B,B (aa)*(a | b),对B根据规则(4)变换为,根据规则(3)变换为,即前面例2中的文法。,A aB | bB,B aaB | a | b,A aB | bB,B aC | a | b,C aB,A a*b,A aA | b,转换成,B (aa)*(a | b),例2 将描述标识符的正规式 R=l ( l | d )* 转换成相应的正规文法,令I为文法的开始符号，根据规则(2)有,根据规则(3)变换为,根据规则(4)变换为,I l ( l | d )*,I lT,T ( l | d )*,I lT,T ( l | d )T | ,进一步变换为,去掉 规则,即前面描述标识符的右线性文法。,I lT,T lT | dT | ,I l | lT,T l | d | lT | dT,2019/6/6,34,一个确定的有穷自动机M是一个五元组， M（S , , f , s0 , Z) , 其中： S：状态的有穷非空集。 ：有穷的输入字母表 f：状态转移函数，是从SS的单值映射函数f(S1 , a )=S2 表示当前状态为S1，输入字母为a时，将转到下一状态S2 (单值：唯一地确定了下一个要转移的状态) 。 s0：唯一初态。（ s0S) Z：是终态集。,3.4正规式与有穷自动机 一. 确定的有穷自动机(DFA),2019/6/6,35,例如：设有DFA M（q0 , q1 , q2 , a , b , f , q0 , q2 ) 其中f 为 f(q0 , a)=q1 f(q1 , a)=q1 f(q2 , a)=q2 f(q0 , b)=q2 f(q1 , b)=q1 f(q2 , b)=q1 对于这个DFA，还可以用下面的方法来描述： 状态转移矩阵 状态转换图,对中的字符串有一条从初态到终态的路，路上的字符 组成的字符串 时，称自动机可以识别 。语言为 L(M)=ba* 1=baaa(可以到达终态） 2=abbab（不可以到达终态）,2019/6/6,36,一个非确定的有穷自动机N是一个五元组， N（S , , f , s0 , Z) , 其中： S：状态的有穷非空集。 ：有穷的输入字母表 f：状态转移函数，是从SS的多值映射函数f(S1 , a )=某些状态的集合 。 s0：非空初态集。 Z：是终态集。,二非确定的有穷自动机（NFA),2019/6/6,37,例如：设有NFA N=( 1 , 2 , 3 , a , b , f , 1 , 3 , 2 ) f为: f(1,a)=3 f(2,a)= f(3,a)= f(1,b)=1,2 f(2,b)= 3 f(3,b)=2 L( N )=b* (b|ab)(bb) * bbb有三条路 状态转换矩阵 状态转换图,2019/6/6,38,三.正规表达式=确定的有穷自动机,由正规表达式构造确定的有穷自动机共分三步： 第一步： 正规式 R=NFA 采用分裂法 第二步： NFA=DFA 采用子集法 第三步： DFA=最小化DFA 采用分划法,2019/6/6,39,1.正规表达式 R=NFA(分裂法）,理论依据：定理：设 L( R )是正规式R所描述的正规集，则存在一个NFA识别 L( R ) 。 输入：字母表上的 正规式R。 输出：识别L( R )的NFA N。 方法：引进初态结x和终态结y，把R表示成如下形式的拓广转换图。,2019/6/6,40, R= = R= = R=a = 若R是复合正规式，则按下列方式对R进行分裂和加进新结点，直到每条边上留下一个符号为止。,x,y,x,x,y,y,a,2019/6/6,41,例：试构造识别语言(a|b)* abb 的 NFA 。 例：构造正规式 0 (1* )* | 01 的NFA。 返回 解： ( A* )* = A* 0 ( 1* )* | 01 = 01* | 01 = 0 ( 1* | 1 ) = 0 1*,x,0,x,x,y,1,3,2,y,1,2,3,y,=,=,=,(a|b)* abb,(a|b)*,a,a,b,b,b,b,a,b,2019/6/6,42,2. NFA = DFA(子集法）,理论依据：设L是一个由NFA接受的正规集，则存在一个DFA接受L。 基本思想： f(S , a )=某些状态的集合=s1 ，s2 ，sn=A DFA的一个状态是NFA状态集合的子集。 输入：一个NFA N 输出：一个识别相同语言的DFA M 方法：利用构造闭包的方法将NFA确定化为DFA,2019/6/6,43, -闭包的概念：设I是NFA N的一个状态子集，则-closure(I)定义如下： 若SI，则 S -closure(I) 若SI，那么从S出发经任意条弧而能到达的任何状态S都属于-closure(I) 例如： 下图中 I=s 则-closure(I)=s , s , s , s =A,2019/6/6,44, NFA = DFA 的算法 已知： NFA N=( S , , f , x , y ) 求： DFA M=( D , , f, 初态，终态集 ) 算法begin 主要求 开始时D= 求-closure(x) 并置为无标记送入 D while D中存在一个无标记状态 T=s1 , s2 , sn do begin for 每个输入符号 a do begin 求y : J=f(s1 , s2 , sn , a )=x1 , x2 , xn y= -closure(J); if yD and y then 置y为无标记并送入D； if y then 置 fT , a =y ; if y中至少有一个是N的终态 then y为M的终态； end ; for 对T置标记； end ; while end ;,2019/6/6,45,例如：正规式(a|b)* abb = NFA =DFA,-closure(x)=x , 0 , 1 =A f(A , a)=0, 2 -closure(0, 2 )=0, 1, 2=B f(A , b)=0 -closure(0)=0, 1=C f(B , a)=0, 2 -closure(0, 2 )=0, 1, 2=B f(B , b)=0, 3 -closure(0, 3 )=0, 1, 3=D f(C , a)=0, 2 -closure(0, 2 )=0, 1, 2=B f(C , b)=0 -closure(0)=0, 1=C,2019/6/6,46,f(D , a)=0, 2 -closure(0, 2 )=0, 1, 2=B f(D , b)=0, y -closure(0, y )=0, 1, y=E f(E , a)=0, 2 -closure(0, 2 )=0, 1, 2=B f(E , b)=0 -closure(0)=0, 1=C 返回菜单 返回分划1 返回分划2,2019/6/6,47,3. DFA最小化（分划法）,DFA最小化：所谓DFA M最小化是指寻找一个状态数比M更少的DFA M，使得L(M)=L(M)。 等价状态：假设DFA M中有状态s和t，如果从s出发能识别某一字符串 x而停止于终态，则从t出发也能识别某一字符串 x而停止于终态；反之亦然。则称状态s和t是等价的。否则，称s和t是可区分的。 例如： 终态与非终态是可区分的 P51图3.8中状态1和状态2是可区分的,2019/6/6,48,化简的方法： 输入：一个DFA M 输出：接受与M语言相同并且状态数尽可能少的DFA M。 基本思想：采用分划的方法。把M的状态集分划成一些不相干的子集，使得每个子集中任何两个状态是等价的，而不同的两个子集中的状态是可区别的。 步骤：首先将DFA M的状态集分划成两个子集：终态集和非终态集，构成初始分划。 上例中： 1= A , B , C , D , E ,2019/6/6,49,按下面的方法构成新的分划，直到中每个状态子集不能再分划为止。 for 中的的每个状态集G do begin 把G分划成子集，使得G的两个状态s和t 属于同一个子集的条件是：当且仅当对任何 输入符号a，状态s和t转到同一状态子集中的 状态；把这样形成的子集放进新分划中。 end 合并等价状态，删除无用状态。,2019/6/6,50,上例中 1= A , B , C , D , E A , B , C , D a=B A , B , C , D b= C , D , E 2= A , B , C , D , E A , B , C a= B A , B , C b= C , D 3= A , C , B , D , E A , C a= B A , C b= C ,2019/6/6,51,合并等价状态，删除无用状态。 = A , B , D , E 则最小化的DFA为：,2019/6/6,52,例如：构造正规表达式a ( ab* | ba* ) * b的DFA,2019/6/6,53,分划： 1= 0，1，2，5 ， 3，4 2= 0，1，2，5，3，4 1，2，5a=2，5 1，2，5b=3，4 3，4a=5 3，4b= 3，4 将原状态集合分划为0，1，2，5，3，4,2019/6/6,54,四.有穷自动机=正规表达式（消结法）,定理 : 上的NFA N 所能识别的字符串全体 L(N)是上的一个正规式。 引进初态结x与终态结y 合并成复杂正规式(恰与分裂法相反),2019/6/6,55,例如:,例如: 文法GZ : Z 0A A 0A | 0B B 1A | 状态转换图见下图，求正规式。 返回,A,A,2019/6/6,56,举例：试用一种高级语言编写识别实数的词法分析程序,设要识别的实数包含如下各种形式（正号可以省略） d d* （其中d0,1,2,3,4,5,6,7,8,9 ) d d*. d d* （为方便起见，用f代表） d d*. d d*e d d 正规式=NFA,NFA:,2019/6/6,57,将NFA=DFA,2019/6/6,58,DFA=最小化的DFA 1= 0,2,4,7,8,9 , 1,3,5,6,10 0,2,4,7,8,9 分划成 0 , 7 , 8 , 2,4,9 1,3,5,6,10 分划成 1,3 , 5,6 , 10 2=0 , 7 , 8 , 2,4,9 , 1,3 , 5,6 , 10,2019/6/6,59,2,4,9 分划成 2 , 4 , 9 3= 0,7,8,2,4,9,1,3,5,6,10 所以最小化的DFA为：,2019/6/6,60,3.5 正规文法与有穷自动机 一右线性正规文法G = 有穷自动机M,已知：G=(VN , VT , P , S ) P :AaB | a A , BVN , aVT* 求：M（Q , , f , q0 , F) 转换规则： Vt , Q=VnD D增设终态 F=D , q0=S 对G中形如AaB 的产生式, 则令f(A , a)=B 对G中形如Aa 的产生式, 则令f(A , a)=D 对G中形如A 的产生式, 则令A为接受状态或令 f(A , )=D 。,2019/6/6,61,举例：构造下述文法的自动机，该自动机是确定的吗？它相应的语言是什么？ 文法GZ : Z 0A A 0A | 0B B 1A | ,方法一：消结法 正规文法自动机正规式,A,求语言,2019/6/6,62,方法二：方程组法： 正规文法正规式方程组正规式 1 Z=0A A=0A+0B B=1A+ 2利用求解规则R： 若x=x+ 则解为x= * 若x=x+ 则解为x= * 将代入得 Z=0A Z=0A A=0A+0(1A+ ) A=(0+01)A+0 由R：A=(0|01)*0 Z=0 (0|01)*0,2019/6/6,63,二左线性正规文法G = 有穷自动机M,G=(VN , VT , P , S ) P :ABa | a A , BVN , aVT* 求：M（Q , , f , q0 , F) 转换规则： Vt , Q=Vnq0 q0增设初态 F=S 文法开始符号作为M的终态 对G中形如ABa 的产生式, 则令f(B , a)=A 对G中形如Aa 的产生式, 则令f(q0 , a)=A,2019/6/6,64,举例：构造下述文法的自动机，该自动机是确定的吗？它相应的语言是什么？ P: （1）消结法 （2）方程组法,2019/6/6,65,消结法：L=(10|01)(10|01)*=(10|01)+ 返回,2019/6/6,66,方程组法： ,Z=(Z1+1)0+(Z0+0)1=Z(10+01)+(10+01) Z=(10+01)(10+01)*=(10+01)+ L= (10|01)+,2019/6/6,67,三.有穷自动机=正规文法,已知：M（G , , f , q0 , F) 求： G=(VN , VT , P , S ) （以右线性文法为例） P :AaB | a A , BVN , aVT* 转换规则： VN =G , VT= , S= q0 若f(A , a)=B , 则BF时，令AaB 若BF时，令AaB | a 或 AaB , B 如果文法开始符号S是一个终态，则令S ,2019/6/6,68,例如：设DFA M=( A,B,C,D , 0,1 , f , A , B) 其中：f(A,0)=B f(B,0)=D f(C,0)=B f(D,0)=D f(A,1)=D f(B,1)=C f(C,1)=D f(D,1)=D 求右线性文法G使得L(G)=L(M)。,C,右线性文法为： A0B | 0 B1C C0B | 0 语言为： L=0(10)*,3.6 词法分析程序的编写方法,在例中，我们规定所有关键字, 用户不得使用它们作为自己定义的标识符，这样我们可以把关键字作为一类特殊的标识符来处理，不再专设对应的转换图。但需把它们预先安排在一个表格中，此表叫关键字表。当利用状态转换图识别出一个标识符时，就去查关键字表，以确定它是否是一个关键字。,其次规定，若关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔，即此时的空白符是有意义的。,根据状态转换图构造出词法分析程序最简单的办法是让每个状态对应一小段程序。,1. ch 字符变量，存放当前读进的源程序字符。,2. token 字符数组, 存放构成单词符号的字符串。,3. getch( )读字符函数，每调用一次从输入缓冲区中读进源程序的下一个字符放在ch中，并把读字符指针指向下一个字符。,4. getbc( )函数，每次调用时，检查ch中的字符是否为空白字符，若是空白字符，则反复调用getbc( )，直至ch中进入一个非空白字符为止。,首先，我们引进词法分析程序所用的全局变量和需调用的函数如下：,2019/6/6,71,3.6 词法分析程序的编写方法,6. letter(ch) 和 degit(ch)布尔函数，它们分别判定 ch 中的字符是否为字母和数字， 从而给出true 或 false。,7. reserve( )整型函数，对token中的字符串查关键字表，若它是一个关键字, 则回送它的编码，否则回送标识符的种别码10。,5. concat( )函数，每次调用把当前ch中的字符与token中的字符串联接。例如，假定token字符数组中原有值为 “ab”, ch中存放着 “c”,经调用concat( )后，token数组中的值变为“abc”。,2019/6/6,72,3.6 词法分析程序的编写方法,8. retract( )函数，读字符指针回退一个字符。,9. return( )函数，收集并携带必要的信息返回调用程序，即返回语法分析程序。,10. dtb( ) 进制转换函数, 它将token中的数字串转换成二进制数值表示, 并以此作为函数值返回。,根据该语言的状态转换图用C语言编写出词法分析程序如下:,Scaner( ) token=NULL; getch( ); getbc( ); if (letter(ch) while(letter(ch) | digit(ch) concat( ); getch( ); retract( ); c=reserve( ); if(c!=10) return(c,token); else return( 10,token); ,相对于状态转换图用C语言编写出词法分析程序如下:,else if(digit(ch) while (digit(ch) concat( ); getch( ); retract( ); return(11,dtb( ); ,else switch(ch) case+: return(13, ); break ; case-: return(14, ); break ; case*: return(15, ); break ; case/: return(16, ); break ; case) return(18, ); retract( ); return(19, ); break; case: : getch( ); if(ch= = =) return(22, ); retract( ); return(21, ); break; case;: return(23, ); break; default: error( ); break; ,由此可知, 只要构造出识别语言单词符号的有穷自动机, 就很容易构造出识别语言单词符号的词法分析程序。,3.6 词法分析程序的编写方法,本章小结,本章重点介绍了词法分析程序的设计思想和构造方法。主要内容有：,1. 词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号。,输出单词符号的形式是二元组: （单词种别，单词自身值）,例如定义“标识符”单词的正规式是 l (l | d)*,正规文法是 标识符 l |标识符l | 标识符d,2程序语言单词符号的两种定义方式,正规文法,正规式,3有穷自动机有确定的和非确定两大类：,NFA N = (Q ,