第3章 词法分析

1、第章词法分析第章词法分析 任务：从左至右逐个字符地对源程序进行扫任务：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串。字符串的源程序改造成为单词符号串。内容简介内容简介 3.1 对于词法分析器的要求对于词法分析器的要求 一功能和输出形式一功能和输出形式 二接口设计二接口设计 3.2 词法分析器的设计词法分析器的设计 一输入和预处理一输入和预处理 二单词符号的识别二单词符号的识别 三状态转换图及其实现三状态转换图及其实现 3.3 正规表达式与有限自动机正规表达式与有限自动机 一单词符号的描述一单词符号的描述 1.

2、正规式与正规集正规式与正规集 2. 正规文法正规文法 二有限自动机二有限自动机 1.DFA 2.NFA 3. NFA与与DFA的等价的等价 4. DFA的化简的化简 三正规式与有限自动机的等价性三正规式与有限自动机的等价性 四正规文法与有限自动机的等价性四正规文法与有限自动机的等价性 3.4 词法分析器的自动产生（词法分析器的自动产生（LEX） 2. . 对于词法分析器的要求对于词法分析器的要求一、功能和输出形式、功能：输入源程序，输出单词符号、单词符号的分类（）（）关键字：由程序语言定义的具有固定意义的标识符， 也称为保留字或基本字。 例如：Pascal 语言中的begin，end，if，w

3、hile等。（）（）标识符：用来表示各种名字。例如变量名、数组名、过程名等。（）（）常数：整型、实型、布尔型、文字型等例如：100，3.14159，true，sample（）（）运算符：+、-、*、/（）（）界符：，；（）等3、输出的单词符号形式二元式：（单词种别，单词符号的属性值）. . 对于词法分析器的要求对于词法分析器的要求单词符号的编码：单词符号的编码： 标识符：一般统归为一种标识符：一般统归为一种 常数：常按整型、实型、布尔型等分类常数：常按整型、实型、布尔型等分类 关键字：全体视为一种一字一种关键字：全体视为一种一字一种 运算符：一符一种运算符：一符一种 界符：一符一种界符：一符一

4、种通常用通常用“整数编码整数编码”“单词符号的特征或特性单词符号的特征或特性”4例：例：考虑下述+代码段：while ( i = j ) i- -;. . 对于词法分析器的要求对于词法分析器的要求经词法分析器处理后，它将被转换为如下的单词符号经词法分析器处理后，它将被转换为如下的单词符号序列：序列： = , - 5. . 对于词法分析器的要求对于词法分析器的要求二、接口设计、词法分析器作为独立的一遍、词法分析器作为独立的一遍、词法分析器作为一个独立的子程序，但并不、词法分析器作为一个独立的子程序，但并不一定作为独立的一遍一定作为独立的一遍语法分析器词法分析器调用（取下一个单词）调用（取下一个单

5、词）单词单词优点：优点：使整个编译程序的结构更简洁、清晰和条理化。 词法分析字符流单词序列（源程序）（输出在一个中间文件上）6、预处理：剔掉空白符、跳格符、回车符、换、预处理：剔掉空白符、跳格符、回车符、换行符、注解部分等行符、注解部分等.一、输入、预处理. . 词法分析器的设计词法分析器的设计 编辑性字符除了出现在文字常数中之外，在编辑性字符除了出现在文字常数中之外，在别处的任何出现都无意义别处的任何出现都无意义. 注解部分不是程序的必要组成部分，它的作注解部分不是程序的必要组成部分，它的作用仅在于改善程序的易读性和易理解性用仅在于改善程序的易读性和易理解性.7 每当词法分析器调用时，就处理

6、出一串确定长每当词法分析器调用时，就处理出一串确定长度（如度（如120个字符）的输入字符，并将其装进词法个字符）的输入字符，并将其装进词法分析器所确定的分析器所确定的扫描缓冲区扫描缓冲区中。中。、预处理子程序、预处理子程序. . 词法分析器的设计词法分析器的设计8 起点指示器起点指示器搜索搜索指示器指示器一个指向当前正在识别的单词的一个指向当前正在识别的单词的开始位置开始位置（即新（即新单词的首字符）单词的首字符）起点指示器起点指示器一个用于向前搜索以寻找单词的一个用于向前搜索以寻找单词的终点终点搜索指示器搜索指示器图图 _ _ 源程序输入缓冲区的对半互补结构源程序输入缓冲区的对半互补结构.

7、. 词法分析器的设计词法分析器的设计9二. 单词符号的识别超前搜索 1关键字的识别 2标识符的识别 3常数的识别 4算符和界符的识别. . 词法分析器的设计词法分析器的设计10三、状态转换图及其实现1 1、状态转换图及其示例、状态转换图及其示例 . . 词法分析器的设计词法分析器的设计例例: :012 数字数字数字数字 其它其它 *012 字母或数字字母或数字字母字母 其它其它 *11例例: : ( (课本课本4242页表页表3.1; 433.1; 43页图页图3.3)3.3). . 词法分析器的设计词法分析器的设计122 2、状态转换图的实现、状态转换图的实现 实现方法：用程序实现，让每个状

8、态结点对应一小段程序。实现方法：用程序实现，让每个状态结点对应一小段程序。A、变量和过程说明、变量和过程说明 ch字符变量，存放最新读进的源程序字符。字符变量，存放最新读进的源程序字符。 strToken 字符数组，存放构成单词符号的字符串。字符数组，存放构成单词符号的字符串。 GetChar 子程序过程，将下一输入字符读到子程序过程，将下一输入字符读到ch中，搜索指中，搜索指 示器前移一字符位置。示器前移一字符位置。 GetBC子程序过程，检查子程序过程，检查ch中的字符是否为空白。若是，中的字符是否为空白。若是， 则调用则调用GetChar直至直至ch中进入一个非空白字符。中进入一个非空白

9、字符。 Concat子程序过程，将子程序过程，将ch中的字符连接到中的字符连接到strToken之后。之后。. . 词法分析器的设计词法分析器的设计13 IsLetter和和IsDigit 布尔函数过程，它们分别判断布尔函数过程，它们分别判断ch中的中的字符是否为字母和数字。字符是否为字母和数字。 Reserve整型函数过程，对整型函数过程，对strToken中的字符串查找中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返保留字表，若它是一个保留字则返回它的编码，否则返回回0值（假定值（假定0不是保留字的编码）。不是保留字的编码）。 Retract 子程序过程，将搜索指示器回调一个

10、字符位置，子程序过程，将搜索指示器回调一个字符位置，将将ch置为空白字符。置为空白字符。 InsertId整型函数过程，将整型函数过程，将strToken中的标识符插入中的标识符插入符号表，返回符号表指针。符号表，返回符号表指针。 InsertConst 整型函数过程，将整型函数过程，将strToken中的常数插入中的常数插入常数表，返回常数表指针。常数表，返回常数表指针。. . 词法分析器的设计词法分析器的设计14B、示例、示例图中结点图中结点i所对应的程序段可表示为：所对应的程序段可表示为：GetChar （）（）; if ( IsLetter( ) ) 状态状态j的对应程序段的对应程序段

11、； else if ( IsDigit( ) ) 状态状态k的对应程序段的对应程序段； else if ( ch=/ ) 状态状态l的对应程序段的对应程序段； else 错误处理错误处理;图中结点图中结点i所对应的程序段可表示为：所对应的程序段可表示为： GetChar （）（）; while (IsLetter ( ) or IsDigit ( ) ) GetChar ( );状态状态j的对应程序段的对应程序段lkji字母字母数字数字/ji字母或数字字母或数字 其它其它. . 词法分析器的设计词法分析器的设计15C、例、例课本课本43页图页图3.3；45-46页页. .词法分析器的设计词法分

12、析器的设计16. . 正规表达式与有限自动机正规表达式与有限自动机一、正规式，正规集，正规文法二、确定有限自动机（DFA)三、非确定有限自动机(NFA)四、NFA=DFA=化简五、正规式有限自动机六、左线性正规文法有限自动机 右线性正规文法有限自动机17. . 正规表达式与有限自动机正规表达式与有限自动机一、正规式与正规集、递归定义、递归定义正规式正规式，a (a）若若U U，V V是正规式是正规式 U U. .V, U|V, UV, U|V, U* * 正规集正规集，a L(U)L(U)，L(V)L(V) L(U)L(V),L(U)L(V),(L(U)L(U)L(V),L(U)L(V),(L

13、(U)* * 18. . 正规表达式与有限自动机正规表达式与有限自动机例题：例题： 、令，下面是，下面是上的正规式和相应的正规集上的正规式和相应的正规集ba*a(a|b)* (a|b)*(aa|bb)(a|b)*上所有以上所有以b为首后跟任为首后跟任意多个意多个a的字的字上所有以上所有以a为首的字为首的字上所有含有两个相继的上所有含有两个相继的a或两个相继的或两个相继的b的字的字19. . 正规表达式与有限自动机正规表达式与有限自动机 (A|B)(A|B|0|1)* (0|1)(0|1)*、令，则：，则：一个正规式的正规集与之完全等价，只是表达形式不同。一个正规式的正规集与之完全等价，只是表达

14、形式不同。上的“标识符”的全体上的“数”的全体20. . 正规表达式与有限自动机正规表达式与有限自动机、运算、运算“”（或）：表示从各选择对象中选择（或）：表示从各选择对象中选择“”（连接积）：表示（连接积）：表示“连接连接”起来起来 “*”（闭包）：任意有限次的自重复连接（闭包）：任意有限次的自重复连接注：注：S*= Sn= SSSL(r*)=L(r)*优先级：优先级：*”|”n=021. . 正规表达式与有限自动机正规表达式与有限自动机例题：例题： 、L(r|s) L(rs) L(a|b)c)B、 L(a|b)*)=,a,b,aa,ab,ba,bb, L(a|(b*)=,a,b,bb,bb

15、b,C、a|bc* a|(b(c*) ab|c*d (ab)|(c*)d)=L(r) L(s)=r s=r,s=L(r) L(s)=r s=rs=L(a|b) L(c)=a,bc=ac,bc223、等价：、等价：若两个正规式所表示的正规集相同，则认若两个正规式所表示的正规集相同，则认为二者等价。为二者等价。 两个等价的正规式和，记为两个等价的正规式和，记为. . 正规表达式与有限自动机正规表达式与有限自动机例：例：b(ab)*=(ba)*b(a|b)*=(a*b*)*(a*b*)*=(a|b)* L(a*b*)*=(L(a)* (L(b)*=,a,b,aa,bb,.*=,a,b,ab,. L(

16、a|b)* =a,b*=,a,b,ab, 23、令、均为正规式，则：、令、均为正规式，则： （交换律）（交换律） （）（）（）（）（结合律）（结合律） （）（）（）（）（结合律）（结合律） U（V|W）=UV|UW（分配律）（分配律） （V|W）U=VU|WU U=U =U U*=(U| )* (U*)*=U*. . 正规表达式与有限自动机正规表达式与有限自动机24例题：例题：、已知字母表=a，b，c，试求在该字母表上的仅包括一个b的所有串的集合相对应的正规式. . 正规表达式与有限自动机正规表达式与有限自动机B、已知字母表=a，b，c，若集合是包括了最多一个b的所有串，求其相应的正规式(a|

17、c)*b(a|c)*(a|c)*(b|)(a|c)*25. . 正规表达式与有限自动机正规表达式与有限自动机二、确定有限自动机DFA（Deterministic Finite Automata）1、DFA M是一个五元式是一个五元式M=（S， ，s0，F）其中：其中： S S有限集，其中的每个元素称为一个状态有限集，其中的每个元素称为一个状态 有穷字母表，其中的每个元素称为一个输入字符有穷字母表，其中的每个元素称为一个输入字符 ：S SS S（即（即状态状态ssS S，aa，(s,a(s,a) )唯一的确定下一状态）唯一的确定下一状态） (s,a (s,a) =s) =s: :当现行状当现行状

18、态为态为s s，输入字符为输入字符为a a时，将转换到下一状态时，将转换到下一状态s s s s0 0SS，唯一的初态，唯一的初态 F FS S，是一个终态集（可空），是一个终态集（可空）26. . 正规表达式与有限自动机正规表达式与有限自动机2、DFA的两种表达方式的两种表达方式（1）状态转换矩阵）状态转换矩阵例：例：DFA M=（0，1，2，3，a，b，0，3）其中其中为：为：（0，a）=1 （0，b）=2（1，a）=3 （1，b）=2（2，a）=1 （2，b）=3（3，a）=3 （3，b）=327则其状态转换矩阵为：则其状态转换矩阵为：状态状态ab012132213333. . 正规表达

19、式与有限自动机正规表达式与有限自动机（0，a）=1 （0，b）=2（1，a）=3 （1，b）=2（2，a）=1 （2，b）=3（3，a）=3 （3，b）=328（2）状态转换图）状态转换图. . 正规表达式与有限自动机正规表达式与有限自动机DFA M:m个状态：图中有个状态：图中有 个状态结点个状态结点;n个输入符号：个输入符号： 每个结点顶多有每个结点顶多有 条箭弧射出条箭弧射出; 每条箭弧用每条箭弧用中的一个中的一个 （相同（相同/不同不同) 输入字符输入字符作标记作标记; 整张图含有整张图含有 个初态结点和若干个个初态结点和若干个 （可为（可为0）终态结点）终态结点. 0132 a a

20、a a b a a b a a， b b b b29例题：例题：构造一个构造一个DFA M，它接受字母表，它接受字母表a，b，c上以上以a或或b开开始的字符串，或者以始的字符串，或者以c开始但所含的开始但所含的a不多于一个的字不多于一个的字符串。符串。. . 正规表达式与有限自动机正规表达式与有限自动机30. . 正规表达式与有限自动机正规表达式与有限自动机3、识别（读出、识别（读出/接受）接受） 对于任何对于任何*中的任何字中的任何字，若存在一条从初态结，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于记符连接成

21、的字等于，则称，则称可为可为DFA M所识别所识别（接受（接受/读出）。读出）。若若MM的初态结点同时又是终态结点，则空字的初态结点同时又是终态结点，则空字 可为可为MM所识别所识别/ /接接受。受。DFA MDFA M所能识别的字的全体记为所能识别的字的全体记为L L（MM）。）。若一个若一个DFA MDFA M的输入字母表为的输入字母表为，则称，则称MM是是上的一个上的一个DFADFA。310132 a a a a b a a b a a， b b b b32. . 正规表达式与有限自动机正规表达式与有限自动机4、定理、定理上的一个字集上的一个字集V*是正规的，当且仅是正规的，当且仅当存在

22、当存在上的上的DFA M，使得，使得V=L（M）33. . 正规表达式与有限自动机正规表达式与有限自动机三、非确定有限自动机（NFA）1、一个、一个NFA是一个五元式是一个五元式M=（S， ，S0，F）其中：其中： S S有限集，其中每个元素称为一个状态有限集，其中每个元素称为一个状态 有穷字母表，其中的每个元素称为一个输入字符有穷字母表，其中的每个元素称为一个输入字符 ：S S* *2 2S S S S0 0S S，是一个非空初态集，是一个非空初态集 F FS S，是一个终态集（可空），是一个终态集（可空）34. . 正规表达式与有限自动机正规表达式与有限自动机三、非确定有限自动机（NFA）

23、DFANFAS初态终态F有限状态集字母表SS初态唯一初态唯一可为空可为空 同左同左S*2S初态不一定唯一初态不一定唯一同左同左35. . 正规表达式与有限自动机正规表达式与有限自动机2、状态转换图、状态转换图注：注：含有含有m个状态和个状态和n个输入符号个输入符号（1）整张图含有）整张图含有 个状态结点。个状态结点。（2）每个结点可以射出）每个结点可以射出 条弧，每条弧用条弧，每条弧用 作为输入字，箭弧上的作为输入字，箭弧上的 标记标记 （ 允许允许/不允许）相同。不允许）相同。（3）整张图）整张图 至少至少 含有一个初态结点以及含有一个初态结点以及 若干个若干个 （可为（可为0个）个） 终态

24、结点。终态结点。（4）某些结点既可为初态结点也可为终态结点。）某些结点既可为初态结点也可为终态结点。*中一个字（可以是空字中一个字（可以是空字）允许允许36m若干若干例：q0q111000DFA? NFA?37. . 正规表达式与有限自动机正规表达式与有限自动机3、识别（读出、识别（读出/接受）接受）对于对于*中的任何一个中的任何一个，若存在一条从某，若存在一条从某一初态结点到某一终态结点的通路，且这条通路一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标上所有弧的标记字依序连接成的字（忽略那些标记为记为的弧）等于的弧）等于，则称，则称可为可为NFA M所识别

25、所识别（读出（读出/接受）。接受）。若若MM的某些结点既是初态结点又是终态结点，或者存在的某些结点既是初态结点又是终态结点，或者存在 一条从某个初态结点到某个终态结点的一条从某个初态结点到某个终态结点的通路，则空字通路，则空字 可为可为MM所接受。所接受。38. . 正规表达式与有限自动机正规表达式与有限自动机4、定理、定理 对于每个对于每个NFA M，存在一个，存在一个DFA M，使得，使得L（M）= L（M）。即，假设）。即，假设L是一个是一个NFA接受的接受的正规集，则存在一个正规集，则存在一个DFA也接受也接受L。39. . 正规表达式与有限自动机正规表达式与有限自动机四、NFA=DF

26、A(确定化）=化简（最少化）401、_CLOSURE（I）：(a) I中的每个状态 _CLOSURE（I）；(b) 若s _CLOSURE（I），则状态s经过标记为的弧到达的状态s _CLOSURE（I）。_CLOSURE（x）= x,5,1412、Ia=_CLOSURE（J）若sIs经过1条标记为a的弧到达的状态s JI=x,5,1Ia=x,5,1a= _CLOSURE(5,3)=5,3,1Ib=x,5,1b= _CLOSURE(5,4)=5,4,142IIaIbX,5,1_CLOSURE(初态）（一）NFA=DFA5,3,15,4,15,3,15,4,15,2,3,1,6,Y5,4,15,

27、2,3,1,6,Y5, 3,15,2,4,1,6,Y5,2,4,1,6,Y5,2,3,6,1,Y5, 4,6,1,Y5, 4,6,1,Y5, 3,6,1,Y5,2,4,6,1,Y5, 3,6,1,Y5,6,3,1,Y5, 2,6,4,1,Y5,2,6,3,1,Y5,6,4,1,Y. . 正规表达式与有限自动机正规表达式与有限自动机解解：（：（1）构造构造DFA的状态转换矩阵的状态转换矩阵 （2）构造重新命名后的状态转换矩阵）构造重新命名后的状态转换矩阵DFA M L(M)=L(M)=L(M)Sab0121322143354645646354445（二）DFA的化简 状态s和t等价：s和t到达终

28、态能够识别相同的字。 461、首先分为非终态集和终态集0,1,2和3,4,5,62、分别对每个集合进行试探：（1）0,1,2a=1,3,1 把集合分为0,2和1 0,2b=2,5 把集合划分为0和2 把集合0,1,2划分为0、1和2472、（1）0、1、2、3,4,5,6 （2）3,4,5,6a=3,6,6,3 3,4,5,6b=4,5,5,4 集合3，4，5，6不必再划分。3、最终形成的划分0123,4,5,6480123,4,5,6用一个状态代表一个状态子集。0132abababa,b49. . 正规表达式与有限自动机正规表达式与有限自动机五、正规式有限自动机关系定理定理： 上的NFA M

29、所能识别的语言L(M)可以用上的正规式来表示。即：对上的NFA M ，可构造一个正规式，使得L()=L(M)。定理： 上任何正规式 ，存在DFA M使得L(M)=L()。即：由正规式可以构造一个DFA M，使得L(M)L()。50. . 正规表达式与有限自动机正规表达式与有限自动机五、正规式有限自动机1 1、 有限自动机有限自动机=正规式正规式1) 1) 把状态转换图的概念拓广把状态转换图的概念拓广，令每条弧上都可以用一个，令每条弧上都可以用一个正规式作标记。正规式作标记。2) 2) 在在MM的转换图上加两个结点：的转换图上加两个结点：x x、y y。从从 x x用用 弧连接到弧连接到MM的所

30、有初态结点；从的所有初态结点；从MM的终态结点用的终态结点用 弧连接到弧连接到y y。这个新的这个新的NFANFA为为MM，且，且L(M)=L(M)L(M)=L(M)。3) 3) 通过引入的通过引入的3 3条有限自动机替换规则条有限自动机替换规则逐步消去逐步消去MM中的中的所有结点，直到只剩下所有结点，直到只剩下x x和和y y为止。为止。这样，在这样，在x x至至y y的弧的弧线上的标记就是线上的标记就是 上的正规式，也就是上的正规式，也就是MM接受的正规式。接受的正规式。 51. . 正规表达式与有限自动机正规表达式与有限自动机五、正规式有限自动机1 1、 有限自动机有限自动机=正规式正规

31、式替换规则替换规则: :jiABAB jiA|BA|B jiA A* *A A B Bjkijki A A代之以代之以代之以代之以代之以代之以jiA AB B52练习练习1：53练习1：练习练习2：55练习2：56. . 正规表达式与有限自动机正规表达式与有限自动机五、正规式有限自动机2 2、正规式、正规式=有限自动机有限自动机57证明过程证明过程如下：（1）若正规式有零个运算符时： 正规式，构造NFA为： 对应正规式，构造NFA为： 对应正规式a，构造NFA为： （2）假设正规式有k(k=1)个运算符时结论成立。（3）则正规式有k+1(k=1)个运算符时：xyxyxya58 R=st R=s

32、*xyN(s)N(s)N(t)xyN(s)N(t) R=s|t59 书上例子P5660 转换规则转换规则： 1)由正规式 构造一个如下仅有两个结点x，y的状 态图。 2)按所引入的3条正规式分裂规则分裂 。3)重复步骤2直到每个弧上的标记是上的一个字符或为止。4)将所得的NFA M(因为包含弧)进行确定化就得到DFA。 x y 61正规式分裂规则 12| 1 22 1 123 1 12 * 2362例、根据正规式(a|b)*(aa|bb)(a|b)*，构造DFA M，使之等价。 x y (a|b)*(aa|bb)(a|b)* 1y(a|b)*(a|b)* 2 x(aa|bb) 1y 2 xaa

33、 5 bba|b 6 a|b 1y 2 xa 5 ba 6 abb34ab63练习1：L(R) =(a|b)*abb，构造NFA使L(N)=L(R)练习2：L(R) =a*b*abb，构造NFA使L(N)=L(R)64练习练习1：L(R) =(a|b)*abb，构造，构造NFA使使L(N)=L(R)解：解：xy(a|b)*abbxyabbabxyabba,bxyababb65x(a|b)*abby练习练习2：L(R) =a*b*abb，构造，构造NFA使使L(N)=L(R)解：解：xybab abxa*b*abby661、右线性正规文法GR 有限自动机2、左线性正规文法GL 有限自动机3、有限

34、自动机 右线性正规文法GR4、有限自动机 左线性正规文法GL. 正规表达式与有限自动机六、正规文法六、正规文法有限自动机有限自动机671、右线性正规文法GR 有限自动机. 正规表达式与有限自动机六、正规文法六、正规文法有限自动机有限自动机引例：GR: S aA A bB B cSABfabc(S, a)=A(A, b)=B(B, c)=f681、右线性正规文法GR 有限自动机.正规表达式与有限自动机六、正规文法六、正规文法有限自动机有限自动机GR(VT,VN,S,P)P: A aB BbFA(,S, ,S0,F)字母表：VT状态集S： VN fS0：开始符号：开始符号S对应的状态对应的状态F：

35、f：(A, a)=B(B, b)=f69 GR: A 0|0B|1D B 0D|1C C 0|0B|1D D0D|1D702、左线性正规文法GL 有限自动机. 正规表达式与有限自动机六、正规文法六、正规文法有限自动机有限自动机引例：GL: S Ac A Bb B aSABfcba(A, c)=S(B, b)=A(q0, a)=Bq0S71. 正规表达式与有限自动机六、正规文法六、正规文法有限自动机有限自动机GL(VT,VN,S,P)P: A Ba BbFA(,S, ,S0,F)字母表：VT状态集S： VN q0S0：q0F：开始符号：开始符号S对应的状态对应的状态：(B, a)=A( q0, b)=B722、左线性正规文法GL 有限自动机 GL: f 0|C0 B 0|C0 C B1 D1|C1|D0|D1|B0733、有限自动机 右线性正规文法GR. 正规表达式与有限自动机六、正规文法六、正规文法有限自动机有限自动机引例1：SABCabc引例2：SABCabcd743、有限自动机 右线性正规文法GR. 正规表达式与有限自动