戴老师的博客 - 编译原理
type: channel
link: https://www.tushu.info/tag/%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86/
items: 词法分析(NFA与DFA.html)
items: Yacc 与 Lex 快速入门

词法分析(NFA与DFA.html)
type: item
date: 2026-07-09T04:29:45+00:00
description: 编者注：本文为历史博文归档；涉及 JDK、框架与工具链版本请以当前官方文档为准。引用外链图片可能失效，阅读时请注意时效性。词法分析 (1.html)：概念与转换图词法分析是编译过程的第一个阶段。正如前文简介所述，词法分析器的主要任务是将字符流转换为词法记号流（Token Stream）。在实际编译过程中，词法分析与语法分析通常是交错进行的。词法分析器不会一次性读取所有词法记号再交给语法分析器，而是每识别出一个词法记号，就立即送入语法分析器进行处理。流程图解如下：词法分析器是编译器中直接与源程序接触的部分，因此它可以承担以下任务：去掉注释：某些情况下可自动生成文档（如 C# 中的 /// 注释）。提供错误位置：通过记录行号来定位错误。一旦字符流变成词法记号流，行的概念就会消失。完成预处理：例如处理宏定义。1. 词法记号、词法单元与模式模式（Pattern）：一种规则，规定了什么样的字符串属于某个词法记号。词法单元（Lexeme）：源代码中匹配某个模式的具体字符串。词法记号（Token）：每个词法单元所属的类别。例如，对于代码 int a=3：int、a、=、3 都是词法单元。每个词法单元都属于某个词法记号。例如，3 是记号 num 的一个词法单元。模式规定了什么样的字符串对应什么样的记号。某一特定模式规定了某个词法记号下的一类词法单元。例如：模式：用字母开头的、包含字母和数字的串。词法记号：id（所有符合上述模式的字符串的记号都是 id）。词法单元：a123 或者 aabc 等。词法记号举例（简称记号）：每个关键字都有属于自己的记号。例如关键字 for 使用记号 for，关键字 int 使用记号 int。所有的关系运算符只有一个记号。例如 >=、<= 都用记号 relation。所有的标识符只有一个记号。例如 a123、aab 使用记号 id。所有的常数只有一个记号。例如 123、22、32.3、23E10 使用记号 num。所有的字符串只有一个记号。例如 "123"、"ab1" 使用记号 literal。在实际的编译器设计中，词法记号一般用一个整型数字表示。词法记号的属性：我们通常用 <词法记号，属性> 这个二元组来描述一个词法单元。对于源代码 position := initial + rate * 60 中的 +，可以使用 <add_op, '+'> 来表示。对于 position，表示为 <id, 指向符号表中 position 元素的指针>。具体来说，假定属性是一个字符串，那么 id 将指向字符串 "position\0"，存放这个字符串的地方叫做符号表。有些时候属性是不必要的。例如 := 表示赋值，我们可以使用 <assign_op, 257> 来表示。但这显得有些多余，因为 assign_op 和词法单元是一对一的，额外信息（属性）显得冗余。词法错误：词法分析器很难检测所有错误（有些错误还是可以检测的）。因为词法分析器的目的是产生词法记号流，它没有能力分析程序结构，因此无法检测到与程序结构有关的错误。例如：fi(a == b.html)。词法分析器不会发现这个错误，它认为 fi 是一个标识符而不是关键字 if。只有在后续阶段，这个错误才会被发现。词法分析器只能检测到词法单元上的问题。例如 12.ab 作为一个词法单元，没有对应的模式，就会产生错误。2. 正规式（Regular Expression）前面说过模式是一种规则，为了使用，我们需要一种规范的方式来表达模式，这就是正规式。1) 串和语言字符类（字母表）：关于字符的有限集合。串：字符类上字符的有穷序列。具体来说，是某个字符类上的串。串的长度：串中字符的个数。例如串 s = abc，长度为 3，用 |s| 表示。空串：用 ε 表示。语言：某字符类上的串的集合。属于语言的串，称为语言的句子或字。例如：{abc, a} 就是一个语言，abc 和 a 就是句子。另外空集也属于语言。连接：x 是串，y 是串，x 和 y 连接，结果就是 xy 这个串。假如 x 是串，x^3 为 xxx。对于 x^n (n>=0.html)，x^0 = ε。语言的运算（假定 L 和 M 是语言）：L U M = {s | s 属于 L 或者 M}。例如：L={1,2}, M={3,4}，那么 L U M = {1,2,3,4}。LM = {st | s 属于 L 且 t 属于 M}。例如：L={a,b}, M={1,2}，那么 LM = {a1,a2,b1,b2}，ML={1a,1b,2a,2b}。L^n = LLL...LLL（n 个 L）。例如：L={a,b}，那么 L^3 = {aaa,aab,aba,abb,baa,bab,bbb,bba}。注意 n 可以为 0，L^0 = {ε}…

Yacc 与 Lex 快速入门
type: item
date: 2026-07-09T04:29:31+00:00
description: Lex 代表 Lexical Analyzer（词法分析器），Yacc 代表 Yet Another Compiler Compiler（另一个编译器编译器）。让我们从 Lex 开始吧。LexLex 是一种生成扫描器（Scanner）的工具。扫描器是一种识别文本中词汇模式的程序。这些词汇模式（或者常规表达式）在一种特殊的句子结构中定义，我们将在下文讨论。一种匹配的正常表达式可能会包含相关的动作。这一动作可能还包括返回一个标记（Token）。当 Lex 接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够找到一个匹配的模式，Lex 就执行相关的动作（可能包括返回一个标记）。另一方面，如果没有可以匹配的常规表达式，将会停止进一步的处理，Lex 将显示一个错误消息。Lex 和 C 是强耦合的。一个 .lex 文件（Lex 文件具有 .lex 的扩展名）通过 lex 公用程序来传递，并生成 C 的输出文件。这些文件被编译为词法分析器的可执行版本。Lex 的常规表达式常规表达式是一种使用元语言的模式描述。表达式由符号组成。符号一般是字符和数字，但是 Lex 中还有一些具有特殊含义的其他标记。下面两个表格定义了 Lex 中使用的一些标记并给出了几个典型的例子。用 Lex 定义常规表达式字符含义A-Z, 0-9, a-z构成了部分模式的字符和数字。.匹配任意字符，除了 \n。-用来指定范围。例如：A-Z 指从 A 到 Z 之间的所有字符。[ ]一个字符集合。匹配括号内的 任意 字符。如果第一个字符是 ^ 那么它表示否定模式。例如：[abC] 匹配 a, b, 和 C 中的任何一个。*匹配 0 个 或者多个上述的模式。+匹配 1 个 或者多个上述模式。?匹配 0 个或 1 个 上述模式。$作为模式的最后一个字符匹配一行的结尾。{ }指出一个模式可能出现的次数。例如：A{1,3} 表示 A 可能出现 1 次或 3 次。**用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。^否定。**\**表达式间的逻辑或。"<一些符号>"字符的字面含义。元字符具有。/向前匹配。如果在匹配的模版中的"/"后跟有后续表达式，只匹配模版中"/"前面的部分。如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。( .html)将一系列常规表达式分组。常规表达式举例常规表达式含义joke[rs]匹配 jokes 或 joker。A{1,2}shis+匹配 AAshis, Ashis, AAshi, Ashi。(A[b-e].html)+匹配在 A 出现位置后跟随的从 b 到 e 的所有字符中的 0 个或 1 个。Lex 中的标记声明类似 C 中的变量名。每个标记都有一个相关的表达式。（下表中给出了标记和表达式的例子。）使用这个表中的例子，我们就可以编一个字数统计的程序了。我们的第一个任务就是说明如何声明标记。标记声明举例标记相关表达式含义数字 (number.html)([0-9].html)+1 个或多个数字字符 (chars.html)[A-Za-z]任意字符空格 (blank.html)" "一个空格字 (word.html)(chars.html)+1 个或多个 chars变量 (variable.html)(字符.html)+(数字.html)*(字符.html)*(数字.html)* Lex 编程Lex 编程可以分为三步：以 Lex 可以理解的格式指定模式相关的动作。在这一文件上运行 Lex，生成扫描器的 C 代码。编译和链接 C 代码，生成可执行的扫描器。注意: 如果扫描器是用 Yacc 开发的解析器的一部分，只需要进行第一步和第二步。关于这一特殊问题的帮助请阅读 Yacc 和 将 Lex 和 Yacc 结合起来 部分。现在让我们来看一看 Lex 可以理解的程序格式。一个 Lex 程序分为三个段：第一段是 C 和 Lex 的全局声明，第二段包括模式（C 代码），第三段是补充的 C 函数。例如，第三段中一般都有 main() 函数。这些段以 %% 来分界。那么，回到字数统计的 Lex 程序，让我们看一下程序不同段的构成。C 和 Lex 的全局声明这一段中我们可以增加 C 变量声明。这里我们将为字数统计程序声明一个整型变量，来保存程序统计出来的字数。我们还将进行 Lex 的标记声明。字数统计程序的声明%{ int wordCount = 0; %} chars [A-Za-z_'\."] numbers ([0-9].html)+ delim [" "\n\t] whitespace {delim}+ words {chars}+ %%两个百分号标记指出了 L…