2019-07-26

自己动手用java写编译器-课时6-词法解析算法的一些概念说明

缘起

《自己动手用java写编译器》课时6

分析

深究词法解析的算法之前，我们需要了解一些基本概念

字母表（或者叫符号表、字符集）

数量有限的符号的集合. 符号不一定指的就是26个英文字母. 可以是C语言的ASCII字符集, 也可以是将近91251个汉字. 也可以是八卦中的 {0,1}

字符串（或者叫单词）

有限的符号的组合. 在实际运用中，字符串就是符号数组. 例如，中文中的词组. 有一种特殊的字符串叫空字符串，也就是不包含任何符号的字符串，例如C语言中用’\0’表示空字符串.

字符串的集合上可以定义运算. 例如字符串的连接操作 concat(string1, string2) 就是把 string2连接到string1的后面. 我们把 concat(string1, string2) 简记为 string1.string2（php中就这样表述字符串连接）

句子

有限个字符串组成的集合. 例如 “大家好，我叫影法师”

语言

所有可能的句子组成的集合.

符号–>字符串–>句子–>语言

词组必须要依照某些规则才能组合成有意义的句子. 这里说的规则就称之为语法. 这句话其实透露的信息是

语法和词组是无关的, 语法描述的是词组的组成规则有关.

这就是为什么在编译器的设计和实现中，词法解析和语法解析是分开的. 词法解析的主要任务只是识别有效词组.

关于上面讲的整个语言体系，还有一些衍生出来的，在算法中常常能听到的概念.

以下5个概念都衍生自字符串.

前缀

它是依附于字符串这个概念的. 字符串的前缀就是字符串的前面若干个符号组成的字符串. 例如 “ab” 是 “abc”的前缀. 特别的, 空字符串和原字符串是合法前缀. 例如 ‘\0’ 和 “abc”都是 “abc”的合法前缀.

后缀

它是依附于字符串这个概念的. 字符串的后缀就是字符串的后面若干个符号组成的字符串. 例如 “bc” 是 “abc”的后缀. 特别的, 空字符串和原字符串是合法后缀. 例如 ‘\0’ 和 “abc”都是 “abc”的合法后缀.

子字符串

将字符串的某个前缀和某个后缀删除掉，剩下的就是子字符串，特别的，空串和原串都是子字符串.

真子集

前（后）缀的真子集就是所有前（后）缀中去掉空串和原字符串.

子序列

字符串中任意删除若干个符号之后剩下的字符串. 注意，子序列和子字符串之间的区别在于前者不一定要连续，后者必须要连续. 例如 iiii, ssss 都是字符串”Mississippi”的子序列, 但是显然都不是Mississippi的子字符串

字符串集合的连接（或者称之为笛卡尔积）

两个字符串集合L、R的笛卡尔积就是第一个字符串集L合任取一个字符串A，第二个字符串集合R任取一个字符串B，将这两个字符串concat在一起（即concat(A,B)，即第二个字符串接到第一个字符串的后面）. 然后将所有这些concat的结果组成一个新的集合, 这个新的集合就是L和R的笛卡尔积. 记做L*R

特别的，L和R如果是同一个集合的话，则L*R记做 L^2, 推而广之, L^n(n>=0), 就是从L中取出n个字符串（可以相同）从左至右拼接成的字符串组成的集合.

而对于一个集合L, {L^n, n>=0} 构成的集合就称为L的柯林（Kleene）闭包. 用 L 表示. 注意，是不是有点正则表达式中的的味道? 别急，后面味道会更浓.

举个例子，L1={“Va”}, L2 = {Voom}, 则 concat(L1*, L2) 就是

1	Voom, VaVoom, VaVaVoom, VaVaVaVoom …… （Va在Voom 前面出现零次或多次)

如果把柯林闭包的定义中的 n>=0 改成 n>=1, 则 L* 改成 L+（正则表达式的既视感）

多举几个柯林闭包的例子

L(digit) = {0, 1, 2, 3, 4, 5, 6,7 ,8 ,9,.}
L(alpha)= {a, b, c, …, z}

L(digit)+ 就是C语言中的所有数字常量
L(aphpa) . ( L(alpha) . L(digit))* 就是C语言中，所有合法的变量名。
例如a, ab12, times13 这些都是C语言变量名;

正则表达式

正则表达式其实就是上面的concat和闭包的组合运用. 它其实就是表述一种规则——来看某个字符串是否符合这个规则. 正则表达式完全可以写成一本书，在这里我们只关注用得到的一些内容，我们只要关注以下几种规则：

单字符匹配。字母表中每一个字符都是一个正则表达式。例如字符c, 匹配单个字符”c”.
ee 两个正则表达式前后连接，用于判断输入的字符串中，是否存在前一部分匹配第一个正则表达式，后一部分匹配第二个正则表达式。例如字符a, n ,d分别匹配字母”a”, “n” , “d”, 那么正则表达式and 则匹配输入字符串中的”and”
通用匹配符 . ，. 可以匹配任何单个字符，例如a . y 可以匹配any, amy, agy。
^开头匹配符，例如^and 匹配任何以and开头的字符串
\$末尾匹配符，例如and$，用于匹配任何以and结尾的字符串。
字符类，任何包含在[和]之间的字符构成字符类，例如[0123456789]匹配任何单个数字，一般简写成[0-9]. [0-9A-Fa-f]匹配任何一个十六进制数。[a-zA-Z]匹配任何字母，^如果出现在括号里，那表示取反，例如[^a-z]匹配任何不是小写字母的字符。
三种符号 *+？,如果正则表达式后面跟着*号，例如a*, 它匹配字母a的零次或多次从复。a+ 匹配字母a的一次或多次重复。a? 匹配字母a的零次或一次重复。ll?ama匹配llama, lama. l+ama 匹配 lama, llama, lllllllllllama(很多个l和ama). l*ama 匹配ama(l出现零次), lama, llama, lllllllama….等等. 0[xX][0-9a-fA-F]+ 匹配所有十六进制数。
e | e, 两个正则表达式被一个竖杆分开，如果一个字符串匹配其中任何一个表达式，那么该字符串就匹配这个表达式。例如either | or 匹配字符串either 和 or. (frank | john)ie匹配字符串frankie 和 johnie。而(frank | john)(ie)? 匹配 frankie, john, frankie, johnie。

正则表达式作用有限，它可以匹配字母组成的字符串，但无法识别例如：

((()()(())) 这种括号是否正确匹配的问题，这种问题其实是语法解析器的工作。

FSM （Finite State Machine）有限状态自动机

一组有限的状态集合
一组从一个状态到另一个状态的转换，每一个转换对应一个输入字符。
一个特殊状态叫初始状态（下图的0），FSM最初就在这个状态
一组特殊状态叫接收状态（下图的双圈圈，到双圈圈为止，都是有效的单词哦~）。

FSM的例子如下

连线就表示读取了字符引发了FSM的状态转换.

例如从初始状态0开始，如果读入字符h, 那么状态机就从状态0转到状态1. 如果接下来读到字符e那就从状态1转到状态2. 如果读到的字符是i那么就从状态1转到状态5. 如果读取字符c 使得状态机从状态N转到状态M, 我们用next(N, c) = M 来表示。next就叫做状态机的转换函数。状态机一旦进入接收状态，就表明当前进入状态机的字符组成的字符串可以被状态机接受。一般来说，一旦进入接受状态后会采取一些业务代码，根据我们以前的编译器中的词法解析器为例，进入接受状态要做的操作就是打标签（token）。如果输入的字母没有对应的转换，那么状态机会默认的进入错误状态，例如从状态0开始，如果输入的字母是x, 但图中没有对应x的转换，因此状态机进入错误状态。

程序中，我们一般用二维数组Transition_table来表示FSM的next转换函数。另外用一个数组Accepting来表述状态机中的状态，我们看看一组伪码：

Transition_table 是有限状态自动机
Accepting 数组是状态数组
下一个状态可以从输入字符input_character, 和当前状态current_state读出
next_state = Transition_table[input_character][current_state]; // 得到下一个状态
If (Accepting[next_state] == true) { // 如果下一个状态是可接受的
    do_an_accepting_action(next_state); // 搞事情
}
其中 Transition_table用来表示有限状态机中的转换关系，Accepting数组用来表示各个状态，如果给定状态是接收状态，那么它在数组中的值为true.

下一节课，我们将实现一个FSM来判断读入的是整型还是浮点型.