编译原理课程教学中的词法分析及其应用

摘要：针对编译原理课程中的词法分析，介绍相关原理，重点探讨词法分析技术在非编译系统中的广泛应用。通过实际应用的分析，加深学生对理论知识的理解，提高学生对编译原理课程重要性的认识，调动学生的学习积极性和主动性。

关键词：编译原理；词法分析；实际应用

1.词法分析概述

词法分析是编译过程的第一个阶段，其主要任务是对构成源程序的字符流进行扫描和分解，把它识别为一个个具有独立意义的最小语法单位，即单词，从而产生一个个的单词序列，用于语法分析。执行词法分析的程序称为词法分析程序或扫描程序，它按构词规则识别单词，将作为字符串的源程序改造成为单词符号串。单词一般采用形如的二元组形式表示，其中单词类别是语法分析需要的信息，而单词自身值则是其他编译阶段需要的信息。编译程序是在单词的级别上来分析和翻译源程序的，因此词法分析是整个编译的基础。词法分析程序除了识别单词这个基本任务外，还可完成以下任务：对源程序进行处理，如组织源程序的输入、删除注释、空格及无用符号；行、列计数；列表打印源程序；发现并定位词法错误；建立、查填符号表。

词法分析程序与语法分析程序的接口方式有两种，如图1所示。（1）词法分析作为独立的一遍，将字符流的源程序变为单词序列输出到中间文件上，此中间文件作为语法分析的输入继续编译；（2）词法和语法分析在同一遍，即将词法分析作为语法分析的一部分，把词法分析程序设计为一个子程序，每当语法分析程序需要单词时，就调用该子程序。为了使整个编译程序的结构更简洁、清晰和条理化，便于使用自动构造工具，提高编译效率，以及增强编译程序的可移植性，通常采用第1种接口方式，即把词法分析从语法分析中独立出来。

程序设计语言的词法描述机制是正规表达式，识别机制是有穷自动机。词法分析程序可以通过手工编写和自动生成两种方式来构造：手工编写需要借助状态图来实现；而自动生成的原理是将正规式转换为有穷自动机，即首先将单词描述成正规式，然后把正规式转换为一个NFA（不确定有穷自动机），进而转换为相应的DFA（确定有穷自动机）。Lex（Lexical Analyzer）是美国Bell实验室研制的一个词法分析程序的自动生成工具，此后，GNU工程推出的Flex（Fast Lex）对Lex进行了扩充，使用它们可以很方便地构建词法分析程序。

2.词法分析的典型应用

词法分析技术在软件工程、信息安全、计算机测评、网络管理与协议解析、自然语言处理以及数据采集与处理等领域得到了广泛应用，见表1。

2.1软件工程

词法分析的主要任务是对构成源程序的字符流进行扫描，然后根据构词规则识别单词符号，这正是源代码逆向分析过程中必不可少的一步。因此，词法分析被广泛应用于软件逆向工程中的源代码逆向分析，以获得逆向分析后续工作所需的单词符号的各类信息。

利用词法分析可以实现B/S构架应用系统和三层构架应用系统中超文本链接的自动测试。超文本词法分析主要根据超文本的词法和关键词，分析查找超文本文件的链接类和应用类链接关键词，确定超文本的调用关系，完成各类链接分析（href、src、cite和background），并将分析结果存储到数据库中。测试时对设定的目录进行分析处理，列出根目录下的文件和目录结构，并对目录下的HTML文件进行词法分析，接着对分析后的链接标记进行分类、字符解析与转换等处理，然后进行链接的分析预验证，最后统计页面文件大小和生成不同的分析报告。基于超文本词法分析的超文本链接自动测试不仅可提高链接测试的覆盖率，而且可有效提高测试验证的效率和准确性，降低超文本链接的测试验证工作量。

2.2信息安全

C/C++语言中许多库函数存在安全漏洞，攻击者常常利用这些函数产生的漏洞来进行缓冲区溢出、格式化字符串溢出和竞争条件等攻击。源代码审核技术通过对软件代码进行分析，从特征数据库里抽取感兴趣的内容进行上下文分析，并对可能存在危险的代码位置进行报警，从而能在编码阶段及时发现和修正软件源代码中存在的安全漏洞。词法分析能够完成自动化的快速漏洞检测，是源代码审核中的一项重要技术，它通过对自定义的漏洞模型与根据待分析源程序确定的程序模型进行分析比较，验证程序模型是否满足漏洞模型的条件。其实质是访问包含在危险函数数据库中的函数（如gets、strcpy、scanf、printf、sprintf、snprinff等）来寻找可能存在的危险，当有潜在危险符合数据库特征时，就会发出警告。目前最具代表性的词法检测工具包括ITS4、Rats和FlawFinder等。

某些嵌入网页的病毒通过插入无效的字符即可得到病毒变种，利用Lex和Yacc等工具可以得到查杀此类病毒的有限自动机软件，即虚拟机。这种方式的查病毒虚拟机在进行词法规则分析时对“空格、注释”等信息置之不理，因此不会影响对病毒代码的定位。

在业务监控系统中可通过报警规则来描述用户所提出的报警条件，并结合词法分析技术在系统运行过程中对报警规则进行匹配。如基于银行业务系统的网络安全审计和监控系统，采用报警规则设计和词法分析方法，能够快速、准确地判断是否为可疑交易和大额交易。

2.3计算机测评

利用自动化的手段将已有试题文档导入在线考试系统时，为保证录入试题的准确性和保密性，提高试题录入的效率，可通过词法分析将试题文本打断为孤立的单词，进而将各个单词进行归类和封装（包括单词种类、行号、起始位置、内容等信息）。之后，利用封装后的单词对象，使用预定义的语法树进行匹配和验证。同时，单词表对整个过程涉及的临时数据进行存储和必要支持。

在程序设计自动评分系统中，当考生的程序不能成功运行时说明程序存在语法错误，可先对考生的源程序进行词法分析，即扫描源程序，生成单词文件；然后根据此文件进行语法分析，在保证不对考生程序正确部分产生破坏的前提下，尽最大可能将考生程序修改正确，并对新程序进行编译链接和测试，从而避免考生因编程中的很小失误而导致大量丢分的问题。如果仍不能编译运行，则可依据正规表达式描述的知识要点进行匹配，使得即使错误严重或结果不正确的程序也能得到应得的分数，从而使评分结果更接近于人工阅卷。

此外，对某类文本范畴的试题，在一定复杂度范围内通过对文本的词法扫描、文法定义、语义分析、等价替换等技术将标准答案与错误答案按特定文法规则进行语义转换后产生唯一等价表达式，通过对转换后的规范表达式进行比较，检查考生答案是否与标准答案等价。

2.4网络管理与协议解析

在网络管理系统中，不同运营商通常对网络设备有不同的实际需求，如对于网管设备告警信息的内容和格式有不同的要求。如果针对这些不同的需求开发不同的网管版本，会成倍增加软件开发和运行维护的成本。为灵活适应各种需求，网管软件通常给出一套脚本语言，用户把特定的需求用脚本语言写入—个脚本文件中，然后网管软件在运行时动态分析脚本文件，获取用户的特定需求并把结果显示在界面上。实现这一方案的关键是脚本文件中关键字的识别，这可以利用Flex等工具生成的词法分析器来完成。网管软件只需要定义脚本文件中用到的所有关键字，并在程序中实现对于关键字的处理即可，从而可以减少网管软件设计和编码的工作量，提高网管编程的效率。

在通信协议解析与处理中，可以借鉴自动生成词法分析器的实现思想，先将通信协议采用正规式集的方式进行形式化描述，然后由一个状态图生成程序产生对应这些正规式的状态图，最后由一个主控程序根据状态转换图对接收到的数据帧进行分析识别，输出用户希望的数据格式。采用形式化描述的方法对协议进行描述，可以实现与协议无关的协议解析和处理，避免针对不同通信协议均要编写相应的解析和处理程序，从而使协议的解析和处理具有更好的灵活性和普适性。如利用PCCTS工具中的DLG根据词法描述文件生成词法分析程序，从输入的字符流中识别词法描述文件中定义的记号；再利用其中的ANTLR根据语法描述文件定义的语法规则生成语法分析程序，在此过程中调用DLG生成的词法分析程序来识别具体的记号，从而实现SIP、MGCP和H.248/GEGACO等通信协议的解析和处理。

2.5自然语言处理

词法分析是各种自然语言处理系统中首要的源语言分析模块，是进行句法分析、语义分析的基础。

词法分析是自然语言检索中一项十分重要的工作，它同时应用于用户提问分析和源文本处理。词法分析首先对文本、网页等进行词语切分，然后通过词频统计和词出现位置的判断，在文本和网页中提取主题词和概念词。之后利用多个关键词的布尔逻辑运算构成检索式，在索引库中逐个进行匹配。由于它能够根据词的位置关系发掘出词的修饰限定关系，因此与传统基于关键词的检索方法相比，其检索内容的相关度更高。

借助计算机信息技术，按照中华古典诗词一些声韵格式要求对提交的诗词作品进行可有限追溯的词法分析，可以实现自动智能审查辨别，并反馈订正建议，从而帮助诗词创作者更好地运用计算机工具创作出符合格律的好作品，进一步弘扬中华诗词文化传统。

通过词法分析可以从语素中获得许多语言学信息，比如在维吾尔文词根与附加成分切分法的基础上，通过分析维吾尔文词的词法结构和音节结构，可以实现对维吾尔语元音弱化现象的算法处理。

自动词法学习通过机器学习等方法从语料中自动获取计算机算法能使用的构词和构形的规律。词法分析利用自然语言中形态学的规律对给出的句子进行词汇级处理，随后自动词法学习方法能从未经加工的文本中学习词法分析处理的数据，从而很容易地获得目标语言中的各种形态变化规律，并把这些规律用形式化的语言表示成各种正则表达式的形式。

词法分析是机器翻译的第一阶段，当源语言文本送人计算机后，首先要进行词法分析，即对送人的文本进行断句、切分，识别出单词、标点、数字等句子的基本成分，并确定它们的形态和词性。这也是完成计算机翻译过程的基础和关键阶段，它为后续句法分析和目标语生成创造了条件，其准确程度的高低直接影响着句法分析的准确率和译文的准确性。

2.6数据采集与处理

数据采集的主要工作是获取设备上传的文件，根据预先定义的格式进行解码，然后把解码成功得到的数据存人数据库。在此过程中会遇到数据格式跨平台、需求变更等问题。针对数据格式的通用和跨平台问题，可采用XDR（ExternalData Representation Standard，外部数据描述标准）等跨平台的数据格式来解决；针对需求变更问题，可以使用针对XDR等数据描述语言的词法分析器把对数据描述的解析变成动态的。这样，对于经常变化的数据格式描述，通过动态解析的方式避免了编译和静态链接，同时把业务逻辑的概念变得更通用，将原先的给定数据描述解析数据变为现在的解析数据描述和数据，从而使数据采集的功能更通用。

利用词法分析的良好识别性可以较好地解决非结构化文本库到结构化关系数据库的关键词库的建立问题。例如，中草药资源信息的原始著录数据形式非常复杂，文本数据不仅是变长的，而且其对象的词描述不是简单的关键词而是长句或短文，这种数据的非结构化不利于数据的查询和统计。为此，可利用词法分析对原始著录数据项进行拆分，提取有关关键词，采用建立关键词库的方法来建立中草药数据库，从而实现数据的自动提取和关键词库的建立，并提高中草药著录数据的规范化存储效率和数据查询效率。

为解决RTI（RunTime Infrastructure，运行时间基础设施）中FED（Federation Execution Data，联邦执行数据）文件的解析效率和可重用性问题，可以将解析程序的数据提取模块与解析处理模块分离，同时在数据提取模块中应用词法分析和语法分析技术对FED文件进行解析优化。首先，用正则表达式将FED文件中所涉及的单词符号进行形式化描述，定义出FED文件的词法规则；同时，用LALR（1）文法表示符合相关标准的FED语法的所有状态转换，完成FED文件的语法规则；然后，借助Flex和Bison生成词法分析程序和语法分析程序，再结合定义的解析处理规则最终生成解析程序。采用这种方案，可以将繁杂的解析处理程序的编写简化为可读性较强的词法分析文档和语法分析文档的编写，提高程序的可读性和可维护性，并且对于不同的解析要求，可以重用现有的大部分代码；同时，对各种要求的FED解析处理程序只需扫描一次FED文件即可完成整个解析过程。此外，只需根据Flex和Bison的版本要求简单修改词法分析文档和语法分析文档，即可实现异构平台的移植。因此，其效率、稳定性、可维护性、可重用性以及可移植性都明显优于通常的FED文件解析方案。

Lex/Flex词法分析工具除了构造编译器的词法分析程序外，还可以针对具有结构化输入的程序构建输入识别程序。例如，生物信息基本数据库数量极多，数据存储格式各异，处理方式也有所不同，因此常规的处理方法工作量极大。为此，利用词法分析技术，针对不同格式的生物数据文件，只要构造相对应的正则表达式就可以使用Lex/Flex构建相应的识别程序，对文件中的数据进行检索和分析。

为保证航班计划编排的正确性，可以航班计划编排规则为依据，采用词法分析和语法分析技术对航班计划编排结果进行自动检查。将航班计划等视为按民航特定规则编写出来的“语言”，其中航班号、起止时间、起止地点、机型、机组等基本信息是该“语言”中的关键字，则可以首先采用词法分析扫描航班计划字符流，按照词法规则识别出航班计划中的各类单词符号，检查这些关键字是否符合其组成规则，并产生用于语法分析的符号序列，告诉语法分析这些单词的组织顺序。随后按照语法规则，采用语法分析对词法分析的结果进行处理，识别词法分析给出的单词符号序列是否为给定文法的正确句子，进而检查其是否按照规定的词序及格式编排，是否表达了正确的涵义，从而实现航班计划编排规则的句法检查。

3.结语

在编译原理课程的词法分析教学中，通过介绍词法分析技术在软件工程、信息安全、计算机测评、网络管理与协议解析、自然语言处理以及数据采集与处理等非编译领域中的广泛应用，有助于提高学生对课程的重视程度和学习的积极性与主动性，加深学生对理论知识的理解，培养学生理论联系实际的能力，激发学生的创造性思维，从而切实有效地提高学生的专业素质。