下载文档原格式
【编译原理】词法分析：正则表达式与有限⾃动机基础引⾔： 编译语⾔设计的精髓在于⾃动化过程，即如果要设计⼀门编程语⾔，那么⼀定要设计⼀个⾃动化系统，能够⾃⾏读⼊分析程序员写⼊的程序，将其翻译为机器能够识别的指令等信息。
当然⾼级语⾔的编译不是⼀蹴⽽就的，⽽是通过若⼲步的分解、规约、转换、优化，最后得到⽬标程序。
具体的编译步骤如下： 源程序就是我们写⼊的⾼级语⾔，编译的第⼀步叫做“词法分析”。
词法分析的本质，就是要拆解出语句的每⼀个单词，然后对这个单词的类型进⾏辨识。
⾸先拿中⽂来举例。
⽐如有⼀句话是“我喜欢你”，那么⾸先我们要把这句话拆成“我”、“喜欢”、“你”，然后再逐个分析他们的类型，得到“我”->主语；“喜欢”->谓语；“你”->宾语。
这样我们就把这句话每个单词都分析出来了，也就完成了中⽂的“词法分析”。
那么回到编程语⾔，它的词法分析就是将字符序列转换为单词（Token）序列的过程。
翻译成俗话，就是把我们写的⼤⽚语⾔⽂本分解为⼀个⼀个单词，再输出每个单词的类型。
举⼀个例⼦：int p = 3 + a; 这个语句⾮常简单，即定义⼀个变量p，它的初值为变量a与3的加和。
那么接下来我们要对这个语句进⾏词法分析，⾸先我们要把这段⽂本拆解成单词，拆出来就是'int'、'p'、'='、'3'、'+'、'a'、';'。
对这些单词再进⾏类型的辨识，那么就得到以下结果：语素语⾔类型int关键字p标识符=运算符3数字+运算符a标识符 这样我们就把这段⽂本中的每个单词的类型都分析出来了。
乍⼀看⾮常简单对不对，对于⼈类⽽⾔你只需要⽤⾁眼就可以轻松观察出来每个单词的类型，但对于计算机⽽⾔，它可没有⼈类那样的智能。
如果想要计算机能够识别并分析语素的类型，那就需要我们⼈类来为它构造⼀个⾃动化输⼊和分析的系统。
确定有限状态⾃动机⽬录思路确定有限状态⾃动机确定有限状态⾃动机（以下简称「⾃动机」）是⼀类计算模型。
它包含⼀系列状态，这些状态中：有⼀个特殊的状态，被称作「初始状态」。
还有⼀系列状态被称为「接受状态」，它们组成了⼀个特殊的集合。
其中，⼀个状态可能既是「初始状态」，也是「接受状态」。
起初，这个⾃动机处于「初始状态」。
随后，它顺序地读取字符串中的每⼀个字符，并转移到下⼀个状态。
当字符串全部读取完毕后，如果⾃动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」。
本题使⽤有限状态⾃动机。
根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码即可。
按照字符串从左到右的顺序，定义以下 9 种状态：0. 开始的空格1. 幂符号前的正负号2. ⼩数点前的数字3. ⼩数点、⼩数点后的数字4. 当⼩数点前为空格时，⼩数点、⼩数点后的数字5. 幂符号6. 幂符号后的正负号7. 幂符号后的数字8. 结尾的空格结束状态：合法的结束状态有 2, 3, 7, 8 。
代码class Solution {public boolean isNumber(String s) {Map[] states = {new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.new HashMap<>() {{ put('d', 2); put('.', 4); }}, // 1.new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }}, // 3.new HashMap<>() {{ put('d', 3); }}, // 4.new HashMap<>() {{ put('s', 6); put('d', 7); }}, // 5.new HashMap<>() {{ put('d', 7); }}, // 6.new HashMap<>() {{ put('d', 7); put(' ', 8); }}, // 7.new HashMap<>() {{ put(' ', 8); }} // 8.};int p = 0;char t;for(char c : s.toCharArray()) {if(c >= '0' && c <= '9') t = 'd';else if(c == '+' || c == '-') t = 's';else if(c == 'e' || c == 'E') t = 'e';else if(c == '.' || c == ' ') t = c;else t = '?';if(!states[p].containsKey(t)) return false;p = (int)states[p].get(t);}return p == 2 || p == 3 || p == 7 || p == 8;}}。
正规⽂法与正规式 3型⽂法也叫作正规⽂法，它对应于有限状态⾃动机，它是在2型⽂法的基础上满⾜：A->a|aB（右线性）或A->a|Ba（左线性）。
如果有A->a,A->aB,B->a,B->cB则符合3型⽂法的要求。
但是A->ab,A->aB,B->a,B->cB或A->a,A->Ba,B->a,B->cB则不符合3型⽂法的要求。
也就是说，不能够推导出两个终结符，⽽且左线性和右线性只能使⽤⼀种，不能够同时出现。
1.分别写出描述以下语⾔的正规⽂法和正规式：（1）L1={ab n a|n≥0}。
（2）L2={a m b n|n≥1,m ≥1}（3）L3={（ab）n|n≥1}答：（1） S → aA A → bA | a L1 = ab*a （2）S → aAA → aA | bB | b B → bB | b L2 = a*b* （3）S → aA A → bB B → aA | ε L3 = (ab)*2.将以下正规⽂法转换到正规式·Z→0A· A→0A|0B· B→1A|ε答：Z = 0A A = 0A + 0B B = 1A + ε A = 0A + 0(1A + ε) = 0A + 01A + 0 A = aA | b Z = 0(0 | 01)*0Z→U0|V1 U→Z1|1 V→Z0|0答：Z = U0 + V1 U = Z1 + 1 V = Z0 + 0 Z = (Z1+1)0 + V1 Z = (Z1+1)0 +(Z0+0)1 Z = Z10 + 10 +Z01 + 01 Z = Z(10+01)+10+01 Z = (10+01)*1001 Z = (10 | 01)*1001S→aA A→bA|aB|b B→aA答：S = aAA = bA + aB + b B = aA A = bA + a(aA) +b = (b + aa)A +b S = (b | aa)*bI→l|Il|Id答： I = l + Il + Id I = l + I(l +d) I = l(l | d)*。
dfa经典案例以下是15个DFA（确定性有限自动机）经典案例：确定型有限自动机（DFA）：一个经典的例子是识别由0和1组成的字符串是否只包含一个数字。
比如，一个DFA可以识别输入的字符串是否只包含数字00-99之间的数字。
识别是否为一个有效的括号序列：使用DFA可以判断一个由“{”，“}”，“(”，“)”组成的字符串是否为有效的括号序列。
例如，输入的字符串为“()”或“(()”或“((()))”或“{()}”都是有效的，但“(({()))”或“(()){}”都是无效的。
识别单词是否为回文字符串：可以使用DFA来识别一个单词是否是回文的。
识别一个字符串是否是交替的“01”序列：DFA可以识别一个字符串是否由交替的0和1组成。
识别一个字符串是否是一个质数：DFA可以识别一个字符串是否表示一个质数。
识别一个字符串是否是一个阿姆斯特朗数：DFA可以识别一个字符串是否表示一个阿姆斯特朗数。
识别一个字符串是否是一个水仙花数：DFA可以识别一个字符串是否表示一个水仙花数。
识别一个字符串是否是一个卡布奇诺数：DFA可以识别一个字符串是否表示一个卡布奇诺数。
识别一个字符串是否是一个完全平方数：DFA可以识别一个字符串是否表示一个完全平方数。
确定一个字符串中的最长重复子串：DFA可以用来确定一个字符串中的最长重复子串的长度。
确定一个字符串中的最长回文子串：DFA可以用来确定一个字符串中的最长回文子串的长度。
确定一个字符串中的最长公共子串：DFA可以用来确定两个字符串之间的最长公共子串的长度。
确定一个字符串中的最长递增子串：DFA可以用来确定一个字符串中的最长递增子串的长度。
确定一个字符串中的最长递减子串：DFA可以用来确定一个字符串中的最长递减子串的长度。
词法分析器的设计：在编译原理中，词法分析器是一个将输入的字符流转化为记号流的有限自动机，记号是一些有意义的单词或符号。
例如，词法分析器可以识别输入的字符流中的关键字、标识符、运算符、常量等记号，并输出相应的记号流。
第2章程序语⾔基础知识（⽂法-正规式-有限⾃动机第2章程序语⾔基础知识编译原理2-781.⽂法认识终结符（不可拆分，⼩写）和⾮终结符（可拆分，⼤写）终结符不可单独置前eg:有⽂法G2[S]为：S->ApS->BqA->aA->cAB->bB->dB则：S为开始符，S,A,B为⾮终结符，p,q,a,b,c,d为终结符⽂法的类型0型⽂法（限制最少的⼀个）设G=（V N，V T ，P，S），如果它的每个产⽣式α---→β是这样结构：α属于（V N并V T）*（闭包）且⾄少含有⼀个⾮终结符，⽽β属于（V N并V T）*，则G是⼀个0型⽂法。
0型⽂法也称短语⽂法。
⼀个⾮常重要的理论结果是：0型⽂法的能⼒相当于图灵机（Turing）。
或者说，任何0型语⾔都是递归可枚举的，反之，递归可枚举集必定是⼀个0型语⾔。
1型⽂法也叫上下⽂有关⽂法，此⽂发对应于线性有界⾃动机。
它是在0型⽂法的基础上每⼀个α---→β,都有|β|>=|α|。
这⾥的|α|表⽰的是α的长度。
注意：虽然要求|β|>=|α|，但有⼀特例：α---->空也满⾜1型⽂法。
如有A->Ba 则|β|=2，|α|=1 符合1型⽂法要求。
反之，如aA->a,则不符合1型⽂法要求。
2型⽂法也叫上下⽂⽆关⽂法，它对应于下推⾃动机。
2型⽂法是在1型⽂法的基础上，再满⾜每⼀个α-→β都有α是⾮终结符。
如A->Ba,符合2型⽂法要求。
如Ab->Bab虽然符合1型⽂法要求，但是不符合2型⽂法要求，其中α=Ab,Ab 不是⼀个⾮终结符。
3型⽂法也叫正规⽂法，它对应于有限状态⾃动机。
它是在2型⽂法满⾜的基础上满⾜：A->α|αB（右线性）或A->α|Bα(左线性)如：A->a,A->aB,B->a,B->cB,则符合3型⽂法的要求。
但如果推导为：A->ab,A->aB,B->a,B->cB或：A->a,A->Ba,B->a,B->cB则不符合3型⽂法的要求。
正规文法与有限自动机的相互转换二零一五年十二月二十七日目录摘要 (1)关键词 (1)1课题综述 (1)1.1目的 (1)1.2设计内容 (1)1.3设计原则 (1)2系统分析 (2)2.1正规式 (2)2.2有限自动机（有穷自动机） (2)2.3NFA向DFA的转换 (3)2.4正规式与有限自动机之间的转换 (3)3系统设计 (4)3.1从正规文法到有限自动机 (4)3.11正规文法到有限自动机的等价性证明 (4)3.12 正规文法到有限自动机的构造方法 (5)3.2从有限自动机到正规文法 (6)3.21 有限自动机到正规文法的等价性证明 (6)3.22 有限自动机到正规文法的构造方法 (7)4 运行与测试 (7)总结 (9)参考文献 (9)附录 (10)摘要：正规文法包括左线性文法和右线性文法。
由于正规文法和正规表达式在描述语言的能力上是等价的，而正规表达式和有限自动机在描述语言的能力上也是等价的，因此，正规文法和有限自动机之间也存在着等价性。
通常，对于正规文法G和有限自动机M，G所定义的语言记作L(G)，M所能识别的语言记作L(M)，如果有L(G)=L(M),则称G和M是等价的。
关键词：正规文法；有限自动机；等价性；构造方法1课题综述1.1目的1.理解正规文法与有限自动机（FA）的本质联系；2.掌握正规文法与有限自动机之间相互转化的算法原理；3.学会使用Visual C++等编程工具实现正规文法与有限自动机之间的相互转化；1.2设计内容使用Visual C++/Visual C#等工具，设计软件MySoft_3，可以实现以下功能：1.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取文法的产生式、非终结符、终结符、开始符等基本信息；2.判断该文法是否为正规文法，若是，则将其转化为有限自动机；3.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取有限自动机的状态集、字母表、初态、终态集、转移函数等基本信息；4.判断该自动机是否合法，若合法，则将其转化为正规文法；1.3设计原则正规文法与有穷自动机有着特殊的关系，采用下面的规则可从正规文法G直接构造一个有穷自动机NFA M；使得L(M)=L(G)：（1）M的字母表与G的终结符相同；（2）为G中的每一个非终结符生成M的一个状态，G的开始符S是开始状态；（3）增加一个新状态Z，作为NFA的终态；（4）对G中的形如A->tB的规则（其中T为终结符或，A为非终结符的产生式），构造M的一个转换函数f(A,t)=B；（5）对G中形如A->t的产生式，构造M的一个转换函数f（A，t）=Z。
第二部分正规语言和有限自动机语言往往是无限集，但描述的方法往往是有限的，一种方法是描述如何通过字符串操作由简单的字符串产生整个语言，或者描述如何通过集合操作由简单语言产生复杂语言。
另一种方法是描述识别字符串是否属于某个语言的机制，也就是描述一个算法过程。
本书考察的最简单的语言类是正规语言，正规语言能够通过应用有限次的某个标准操作从一元语言产生。
正规语言能够被有限自动机识别，有限自动机是空间严格受限的简单机器。
在第二部分，我们还考察正规语言的另外一些特点：1）导出将一种语言的描述翻译成另一种语言的描述的算法；2）使用形式化方法描述语言；3）正规语言在实际中的应用。
3 正则表达式和有限自动机3.1 正则语言和正则表达式注意：regular language和regular expression有时也翻译成正规语言和正规表达式。
正则语言可以从非常简单的表达式得到，初始语言的字符串为空或单字母，仅使用合并、连接和K leene连接运算，因此正则语言可用一个清楚的表达式描述，通常用小括号()代替大括号{}，+代替⋃，称为正则表达式。
下面是一些定义在字母表{0, 1}上的正则表达式，通过这些例子，能够感受到书写正则表达式的一些规律。
语言相应的正则表达式{Λ} Λ{0} 0{001}或{0}{0}{1} 001{0, 1}或{0}⋃{1} 0+1{0, 10}或{0}⋃{10} 0+10{1, Λ}{001} (1+Λ)001{110}*{0, 1} (110)*(0+1){1}*{10} 1*10{10, 111, 11010}* (10+111+11010)*{0, 10}*({11}*⋃{001, Λ}) (0+10)*((11)*+001+Λ)我们认为正则表达式表示的是相应语言的“最典型的字符串”，比如，1*10表示一个字符串，它以10结束，前面可以有任意多个数目的1。
我们在前面将正则语言描述成：在最简单的语言上仅仅使用三种运算合并、连接、Kleene 连接所得到的语言。
正则文法与有限状态自动机Regular Grammar and FSM☐⏹建立正则文法和有限状态自动机的等价性☐定理⏹可以由确定性有限状态自动机 M =(S , I , f , A , S 0) 构造一个正规文法 G =(S , I , P , S 0)，使得L (G )=L (M )： ⏹假设 X , Y ∈S ，a ∈I ，若 f (X , a )=Y ，则在 P 中有 X →aY ；若 X ∈A ，则在 P 中有 X →λ。
☐例S 2 S 0 1t S 0 1 0 0 0 11 1 S 1 → 0S 1, S 1 → 1S 2, S2 → 0S 3, S 2 → 1S 2, S3 → 0S 3, S 3 → 1S 0, S 0 → 0S 1, S 0 → 1S 0, S 0 → λ , S 1 → λ☐定理⏹可以由确定性有限状态自动机 M =(S , I , f , A , S 0) 构造一个正规文法 G =(S , I , P , S 0)，使得L (G )=L (M )： ⏹假设 X , Y ∈S ，a ∈I ，若 f (X , a )=Y ，则在 P 中有 X →aY ；若 X ∈A ，则在 P 中有 X →λ 。
☐证明 ⏹容易看到 S 0→λ 当且仅当 S 0∈A ，故 λ∈L (G ) 当且仅当 λ∈L (M )⏹证明 L (M )⊆L (G )⏹证明 L (G )⊆L (M )☐证明⏹容易看到S0→λ当且仅当S0∈A，故λ∈L(G) 当且仅当λ∈L(M)⏹证明L(M)⊆L(G)☐对于w=w1w2…w n，记S i = f (i)(w)，☐则有S0⇒w1S1⇒w1w2S1⇒...⇒w1w2…w n S n⇒w1w2…w n⏹证明L(G)⊆L(M)☐对于任意w∈L(G)，假设S0⇒α1⇒...⇒w☐则一定是经过|w| 次“X→aY”型直接推导之后再进行一次“X→λ”型直接推导。
离散数学是计算机科学中的基础课程，其中有限状态自动机（Finite State Automaton, FSA）和正则表达式（Regular Expression, RegExp）是重要的概念和工具。
有限状态自动机是一种抽象的计算模型，用于描述在给定的输入序列下系统的行为。
它由一组有限个状态和一组转移函数组成，根据输入字符的不同，自动机在状态之间转移。
有限状态自动机被广泛应用于编译器设计、自然语言处理、模式匹配等领域。
在正则表达式中，有限状态自动机通常用于实现模式匹配操作。
正则表达式是一种描述字符串模式的语言。
它提供了一种简洁而强大的方式来匹配、查找和替换文本中的模式。
正则表达式由字母表、操作符和一组规则构成，可以用来描述具体的字符串。
正则表达式可以在编程语言（如Python、Perl、Java等）中实现，也可以在文本编辑器和命令行工具中使用。
有限状态自动机和正则表达式之间有一种密切的联系：正则表达式可以被转换为等价的有限状态自动机，有限状态自动机可以被转换为等价的正则表达式。
这种等价关系在理论上被称为“Kleene定理”，可以用于证明正则语言和有限自动机的等价性。
对于给定的正则表达式，可以通过构造等价的有限状态自动机来实现模式匹配。
在自动机的转移函数中，每个字符对应于一个状态转移，并根据正则表达式的规则选择相应的转移。
通过遍历自动机的状态转移路径，可以检测输入字符串是否与正则表达式相匹配。
另一方面，有限状态自动机可以通过反向构造来生成等价的正则表达式。
该过程被称为“状态消除”，通过消除自动机中的状态，并将其转换为正则表达式的形式。
最后，将所有状态消除为一个正则表达式，就得到了等价的正则表达式。
有限状态自动机和正则表达式在计算机科学中有着广泛的应用。
正则表达式可以用来进行文本的查找、分割和替换操作，提供了一种便捷的方式来处理复杂的字符串模式。
有限状态自动机则被广泛应用于编译器设计、模式匹配等领域，用于解析和分析文本数据。
举例说明正则文法与dfa之间的转换关系正则文法（Regular Grammar）和确定有限状态自动机（DFA，Deterministic Finite Automaton）是形式语言理论中的两个重要概念，它们之间存在一定的转换关系。
下面将通过一个例子来说明这种转换关系。
假设我们有一个正则文法 G，它由两个产生式A → aBb 和B → b 组成。
这个文法描述的语言是所有以一个 'a' 开头，后跟一个或多个 'b' 的字符串，即 L(G) = {a^n b^n n >= 1}。
我们可以将这个正则文法转换为确定有限状态自动机。
首先，我们需要为文法中的每个非终结符（A 和 B）创建一个状态。
对于产生式A → aBb，我们将创建一个状态 s_1，并将转移函数δ(s_0, a) = s_1 和δ(s_1, b) = s_2，其中 s_0 是初始状态。
对于产生式B → b，我们将创建一个状态 s_3，并将转移函数δ(s_1, b) = s_3。
终止状态集合将包括所有产生式右边的状态，即{s_2, s_3}。
这样，我们就可以得到一个确定有限状态自动机，它的初始状态是 s_0，终止状态集合是 {s_2, s_3}，转移函数是δ(s_0, a) = s_1, δ(s_1, b) = s_2, 和δ(s_1, b) = s_3。
这个自动机接受的语言就是由正则文法 G 描述的语言L(G)。
总的来说，正则文法转换为 DFA 的过程可以概括为：对于文法中的每个非终结符，创建一个状态；对于每个产生式，定义转移函数；将所有产生式右边的状态标记为终止状态。
通过这种方式，我们可以将正则文法转换为确定有限状态自动机，从而实现对正则语言的有效识别和匹配。
