词法分析器

扫描器

词法分析（lexical analysis）是计算机科学中将字符序列转换为单词（Token）序列的过程。进行词法分析的程序或者函数叫作词法分析器（Lexical analyzer，简称Lexer），也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。

基本定义

词法分析的第一阶段即扫描器，通常基于有限状态自动机。扫描器能够识别其所能处理的标记中可能包含的所有字符序列（单个这样的字符序列即前面所说的“语素”）。例如“整数”标记可以包含所有数字字符序列。很多情况下，根据第一个非空白字符便可以推导出该标记的类型，于是便可逐个处理之后的字符，直到出现不属于该类型标记字符集中的字符（即最长一致原则）。

词法分析器的工作是低级别的分析：将字符或者字符序列转化成记号。在谈论词法分析时，使用术语“词法记号”（简称记号）、“模式”和“词法单元”表示特定的含义。

在分析时，一是把词法分析器当成语法分析的一部分，另一种是把词法分析器当成编译程序的独立部分。在前一种情况下，词法分析器不断地被语法分析器调用，每调用一次词法分析器将从源程序的字符序列拼出一个单词，并将其Token值返回给语法分析器。后一种情况则不同，词法分析器不是被语法分析器不断地调用，而是一次扫描全部单词完成编译器的独立一遍任务。

有限状态自动机

有限状态自动机自动机理论的研究对象。

有限状态自动机是具有离散输入和输出的系统的一种数学模型。

其主要特点有以下几个方面：

– (1)系统具有有限个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。

– (2)我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。

– (3)系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。

– (4)系统中有一个状态，它是系统的开始状态。

– (5)系统中还有一些状态表示它所读入的字符构成的字符串是语言的一个句子。

形式定义

· 定义：有限状态自动机(FA—finite automaton)是一个五元组：

– M=(Q, Σ, δ, q0, F)

· 其中，

– Q——状态的非空有穷集合。∀q∈Q，q称为M的一个状态。

– Σ——输入字母表。

– δ——状态转移函数，有时又叫作状态转换函数或者移动函数，δ：Q×Σ→Q，δ(q,a)=p。

– q0——M的开始状态，也可叫作初始状态或启动状态。q0∈Q。

– F——M的终止状态集合。F被Q包含。任给q∈F，q称为M的终止状态。

语法分析器

在计算机科学和语言学中，语法分析（英：Syntactic analysis，也叫Parsing）是根据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程。

语法分析器（Parser）通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建由输入的单词组成的数据结构（一般是语法分析树、抽象语法树等层次化的数据结构）。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”，并将单词流作为其输入。实际开发中，语法分析器可以手工编写，也可以使用工具（半）自动生成。

语法分析器的任务主要是确定是否可以以及如何从语法的起始符号推导出输入符号串（输入文本），主要可以通过两种方式完成：

自顶向下分析：根据形式语法规则，在语法分析树的自顶向下展开中搜索输入符号串可能的最左推导。单词按从左到右的顺序依次使用。

自底向上分析：语法分析器从现有的输入符号串开始，尝试将其根据给定的形式语法规则进行改写，最终改写为语法的起始符号。

Lex词法分析器

Lex常常与yacc 语法分析器产生程序（parser generator）一起使用。Lex(最早是埃里克·施密特和迈克·莱斯克制作）是许多UNIX系统的标准词法分析器（lexical analyzer）产生程序，而且这个工具所作的行为被详列为POSIX标准的一部分。

Lex读进一个代表词法分析器规则的输入字符串流，然后输出以C语言实做的词法分析器源代码。

词法分析器的设计

以下是源词法分析器的设计与实现程序的输入与预处理步骤：

输入缓冲区

成对且对半互补的输入缓冲区模式。

n: 取2的整次幂；每个半区的末尾设置标志“ eof ” 表示读入该半区的源程序的结束；

B：单词w开始指针； F：扫描w的指针。