词法分析

小例子

if (i == j)
    z = 0;
else
    z = 1;

如上，词法分析需要将其转换成token（词法单元），例如关键字if，else，变量i，j，z，关系运算符==

对于词法分析器来说，这段代码是以下这样一个线性字符串：

1	\tif (i == j)\n\tz = 0;\n\telse\n\t\tz = 1;

词法分析器将对此字符串进行切割和划分，根据不同字符串元素作用进行分类

符号

在日常语言中，分为动词，名词，形容词……

在编程语言中，分为关键字，数字，标识符……

标识符（Identifier）：以字母开头的字母或数字字符串
整数（Integer）：非空数字字符串
关键字（Keyword）：if，else，begin
空白（Whitespace）：空格换行制表符

工作过程

总结来说，词法分析的工作过程如下所示：

词法分析器会对输入的字符串进行切割和分类，给子字符串(substring)赋予标记类(class)，然后将<class, substring>的序列对传给语法分析器，其中，<class, substring>就称为token(词法单元)

例如，"foo = 42"的处理结果即为：

<Identifier, “foo”>
<Operator, “=”>
<Integer, “42”>

词法分析中的歧义问题

有时，词法分析从左往右分析是不够的，可能会存在歧义，例如如何确定"=="是"=="而不是"="？

因此，有时需要看后面，从后往前看才能确定

而这无疑会增加词法分析工作的复杂性，因此尽量减少从后向前看的内容也是词法分析器的一个目标

再例如，c++中就有stream input和嵌套模板之间的语法冲突：

一个解决方案就是在嵌套模板的”>>”处加空格予以区分

正则语言

正则表达式

正则表达式表示一个集合

单个字符

epsilon

并集（Union）

级联（concatenation）

迭代（Iteration）

补充

形式语言

正则表达式就是一种形式语言

定义：令Σ是一组字符（字母）的集合，关于Σ的语言是由Σ中字符构成的字符串的集合

例：

英文字母-句子
ASCII-C语言

当英文字母被赋予规则，字母集合组成句子，这就是形式语言

我们用一个函数L来表示字符集在语言中对应的含义，如下：

表示语法，如正则表达式，到语义（集合）的映射

关于这种映射的用处，例如在优化时，不同的语法可能含有相同的语义

词法规范

例子

整数（Integer）

如果用digits来表示0123456789的集合：

那么整数就表达为：

标识符（Identifier）

标识符通常以字母开头，可包含字母、数字

将字母记为：

则标识符可以这样表示：

空白

构造过程

为每个符号写一个rexp：

构建一个能够匹配所有词法单元的正则表达式

假设输入，进行判断

如果成功，我们知道：

失败，从输入中删除x1…xi，返回步骤(3)

关于该步骤的一些疑问：

使用多少输入？

最长匹配，例如对于”==”选择”==”而非”=”

如果匹配到多个词法单元，该选择哪一个？

例如，”if”既符合Keywords也符合Identifier，这时候应该优先调度，优先选择第一个列出的标记类，Keywords

如果没有规则匹配？

针对不规范字符，编写一类错误字符串：

优先级最低