编译原理之有限自动机解析

【编译原理】词法分析：正则表达式与有限⾃动机基础引⾔： 编译语⾔设计的精髓在于⾃动化过程，即如果要设计⼀门编程语⾔，那么⼀定要设计⼀个⾃动化系统，能够⾃⾏读⼊分析程序员写⼊的程序，将其翻译为机器能够识别的指令等信息。

当然⾼级语⾔的编译不是⼀蹴⽽就的，⽽是通过若⼲步的分解、规约、转换、优化，最后得到⽬标程序。

具体的编译步骤如下： 源程序就是我们写⼊的⾼级语⾔，编译的第⼀步叫做“词法分析”。

词法分析的本质，就是要拆解出语句的每⼀个单词，然后对这个单词的类型进⾏辨识。

⾸先拿中⽂来举例。

⽐如有⼀句话是“我喜欢你”，那么⾸先我们要把这句话拆成“我”、“喜欢”、“你”，然后再逐个分析他们的类型，得到“我”->主语；“喜欢”->谓语；“你”->宾语。

这样我们就把这句话每个单词都分析出来了，也就完成了中⽂的“词法分析”。

那么回到编程语⾔，它的词法分析就是将字符序列转换为单词（Token）序列的过程。

翻译成俗话，就是把我们写的⼤⽚语⾔⽂本分解为⼀个⼀个单词，再输出每个单词的类型。

举⼀个例⼦：int p = 3 + a; 这个语句⾮常简单，即定义⼀个变量p，它的初值为变量a与3的加和。

那么接下来我们要对这个语句进⾏词法分析，⾸先我们要把这段⽂本拆解成单词，拆出来就是'int'、'p'、'='、'3'、'+'、'a'、';'。

对这些单词再进⾏类型的辨识，那么就得到以下结果：语素语⾔类型int关键字p标识符=运算符3数字+运算符a标识符 这样我们就把这段⽂本中的每个单词的类型都分析出来了。

乍⼀看⾮常简单对不对，对于⼈类⽽⾔你只需要⽤⾁眼就可以轻松观察出来每个单词的类型，但对于计算机⽽⾔，它可没有⼈类那样的智能。

如果想要计算机能够识别并分析语素的类型，那就需要我们⼈类来为它构造⼀个⾃动化输⼊和分析的系统。

有限自动机算法
有限自动机算法是一种常见的计算机科学算法，也称为状态机算法或有限状态自动机算法。

它是一种用来识别字符串的算法，通常被用于文本处理、编译器设计、自然语言处理等领域。

有限自动机算法基于有限状态自动机的理论，将一个字符串视为一个字符序列，通过状态转移来确定字符串是否符合特定的语法规则。

有限自动机算法通常分为两种类型：确定有限自动机（DFA）和非确
定有限自动机（NFA）。

DFA是一种状态转移图，其中每个状态都有一个唯一的出边，对于一个输入字符，只有一种可能的转移路径。

NFA则允许一个状态拥有多个出边，每一条出边代表一个可能的转移路径，同时，NFA还可以在不确定的情况下选择一条转移路径。

有限自动机算法的核心思想是将一个字符串逐个字符地输入到
状态机中，根据状态转移的规则，判断当前字符是否满足预定的语法规则。

如果符合规则，状态机将进入下一个状态，直到整个字符串被处理完毕。

如果最终状态符合预定要求，那么这个字符串将被认为是合法的。

总的来说，有限自动机算法是一种高效的字符串处理算法，它可以用来判断字符串是否符合特定的语法规则。

在文本处理、编译器设计、自然语言处理等领域中有广泛的应用。

- 1 -。

第三章有限自动机与词法分析器3.1词法分析3.1.1词法分析器的功能在第二章里我们已介绍了词法分析的基本问题。

计算机存储是二进制式的，因此，任何一种程序和数据在计算机内部均被表示为二进制表示。

实际上，当程序员每按键盘中的一个键时，自动往计算机里输入一个相应的八位二进制码，称这种码为ASCII码。

当程序员敲完程序时将它保存到自己事先起好名的文件中，因此，程序在计算机文件中的表示是ASCII码序列(末尾有文件结束码)。

编译器总是要用某种程序设计语言来写，而任何一种语言的程序其操作对象必须是该语言所规定的数据。

编译器的操作对象是程序中的各种语法单位，如<常量声明>,<类型声明>,<变量声明>,<过程声明>,<表达式>,<语句>,<变量>等等，因此，必须把它们都表示成某种数据结构形式，而它们的最小单位是所谓的单词，故首当其充的是要把每个单词转换成一种数据形式，通常称它们为TOKEN。

词法分析器的任务就是，从源程序的ASC码(用高级语言的术语来说是字符串)序列逐个地拼出单词，并将构造相应TOKEN数据表示。

词法分析器可有两种，一种是它作为语法分析的一个子程序，一种是它作为编译器的独立一遍。

前一种情形，词法分析器不断地被语法分析器所调用，每调用一次词法分析器将从源程序的字符序列拼出一个单词，并将其TOKEN值返回给语法分析器。

后一种情形则不同，即不是被别的部分不断地调用，而是完成编译器的独立一遍任务，具体说将整个源程序的字符序列转换成TOKEN序列，并将其交给语法/语义分析器。

实际的编译器一般都采用子程序方式，但是为了独立地介绍词法分析、语法分析和语义分析的概念和技术，我们将词法分析部分分离出来即作为独立一遍的词法处理器来介绍。

从实际的角度来说，这种方法有以下缺点:一是因为它要生成TOKEN列，自然多占用空间；二是因为要保存所有的TOKEN，需要耗费更多的时间。

编译原理dfa编译原理DFA。

有限自动机（DFA）是编译原理中的重要概念，它在词法分析和语法分析中扮演着重要的角色。

在编译原理中，DFA用于识别和分析输入的字符序列，帮助编译器理解源代码的结构和含义。

本文将介绍DFA的基本概念、原理和应用，以及它在编译原理中的重要作用。

DFA的基本概念。

DFA是有限自动机（Deterministic Finite Automaton）的缩写，它是一种抽象的数学模型，用于描述有限个状态和在这些状态之间转移的输入字符序列。

DFA由五元组（Q, Σ, δ, q0, F）组成，其中：Q是有限状态集合；Σ是输入字符的有限集合；δ是状态转移函数，描述了状态之间的转移关系；q0是初始状态；F是接受状态集合。

DFA的原理。

DFA的工作原理是通过状态转移函数δ来识别和分析输入字符序列。

编译器将源代码转换为字符流，然后通过DFA进行词法分析，将字符流转换为标记流。

在词法分析过程中，DFA根据输入字符的转移关系，逐步从初始状态转移到接受状态，从而识别出源代码中的各种标记，如关键字、标识符、常量和运算符等。

DFA的应用。

DFA在编译原理中有着广泛的应用，它是词法分析器和语法分析器的核心组成部分。

在词法分析阶段，编译器利用DFA识别并提取源代码中的各种标记，为后续的语法分析和语义分析提供输入。

在语法分析阶段，DFA可以帮助编译器理解源代码的结构和语法，从而生成抽象语法树（AST）或中间代码。

此外，DFA还可以应用于模式匹配、文本搜索和自动机器人等领域。

在模式匹配和文本搜索中，DFA可以帮助我们快速地识别和匹配目标字符串；在自动机器人中，DFA可以帮助我们设计和实现自动化的决策系统。

DFA在编译原理中的重要作用。

在编译原理中，DFA是词法分析和语法分析的基础，它可以帮助编译器理解源代码的结构和含义。

通过DFA的识别和分析，编译器可以将源代码转换为抽象语法树（AST）或中间代码，为后续的优化和代码生成提供基础。

设计目的：1、 理解有限自动机的作用2、 利用转态图和状态表表示有限自动机3、 以程序实现有限自动机的运行过程设计内容：（注：题目详细要求）利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个有效的符号串，具体可以选择下面之一：无符号定点实数、自然数、整数、十六进制数或其它自己定义的符号串。

一、分析原理词法分析：就是从左至右逐个字符地对源程序进行扫描，产生单词序列，用以语法分析。

在这里，我们先把文法转换成有穷自动机，然后构造出状态表，再由状态表构造出程序。

二、分析的算法将G[<无符号数>]文法转换成有穷自动机：构造状态矩阵；将有穷自动机的状S 1 S 2 ……S n 及输入的字a 1 a 2 ……a m 构成一个n*m 的矩阵。

再写一个程序，把状态矩阵用二维数组表示。

程序通过输入的字符转换状态，从而可以识别出单词。

本程序的关键在状态表和缓冲区的运用。

首先定义了一个布尔型函数ReadALine把输入的字符串送到缓冲区中；然后定义了布尔型函数Run 和Getchar实现对输入字符串的正确性判断，更改Run函数可以改变程序功能：如可将状态表改变成识别“偶数”的有限自动机的状态表。

三、程序流程图四、课程设计出现的问题及解决的方法刚开始写该程序时，虽然感觉个人的编程能力不错，但由于对编译原理的自动机的实现掌握不足，难以入手。

但经过对问题的更深入了解和分析，再通过网上和书本的资料的细读，最后终于把程序编写出来了。

程序中，碰到的最大的问题就是状态表的构造和如何把它转变为一个程序的实现过程。

解决的方法当然是看书。

五、课程设计的体会首先，题目给出的文法是有小毛病的。

我个人认为<无符号数>不可能推出 . <十进制数> 或者e <指数部分>的。

在写这个程序是只要对编译原理书本词法分析分析很熟悉就可以比较容易地写出该程序。

通过这次课程设计，我对程序的编译和运行有了更进一步的了解，更好地掌握了编译原理的词法分析过程。

第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型⽂法的要求。