编译原理正则文本与有限状态机

一、参考

正则文法和有限自动机:纯手工打造词法分析器

PlayWithCompiler source code

compile learning with java ch2

compile learning with golang ch2

二、有限状态机

词法分析的工作是将一个长长的字符串识别出一个个的单词,这一个个单词就是 Token。

而且词法分析的工作是一边读取一边识别字符串的,不是把字符串都读到内存再识别

2.1 词法规则

(1) 标识符:第一个字符必须是字母,后面的字符可以是字母或数字。

(2) 比较操作符:> 和 >=(其他比较操作符暂时忽略)

(3) 数字字面量:全部由数字构成(像带小数点的浮点数,暂时不管它)

2.2 解析示例

解析 age >= 45

(1) 初始状态

刚开始启动词法分析的时候,程序所处的状态

(2) 标识符状态:

在初始状态时,当第一个字符是字母的时候,迁移到状态 2

当后续字符是字母和数字时,保留在状态 2

如果不是,就离开状态 2,写下该 Token,回到初始状态

(3) 大于操作符(GT)

在初始状态时,当第一个字符是 > 时,进入这个状态

(4) 大于等于操作符(GE)

如果状态 3 的下一个字符是 =,就进入状态 4,变成 >=

(5) 数字字面量

在初始状态时,下一个字符是数字,进入这个状态

如果后续仍是数字,就保持在状态 5

2.3 词法原理

依据构造好的有限自动机,在不同的状态中迁移,从而解析出 Token 来。

三、关键字

3.1 什么是关键字

关键字是语言设计中作为语法要素的词汇

例如

(1) 表示数据类型的 int、char

(2) 表示程序结构的 while、if

(3) 表述特殊数据取值的 null、NAN 等

3.2 保留字

保留字在当前的语言设计中还没用到,但是保留下来,因为将来会用到

命名自己的变量、类名称,不可以用到跟关键字和保留字相同的字符串

3.3 如何区分标识符和关键字?

以“int age = 40”为例

在识别普通的标识符之前,你先看看它是关键字还是保留字就可以了

具体做法是:

(1) 当第一个字符是 i 的时候,我们让它进入一个特殊的状态

(2) 接下来,如果它遇到 n 和 t,就进入状态 4

(3) 但这还没有结束,如果后续的字符还有其他的字母和数字,它又变成了普通的标识符

原文地址:https://www.cnblogs.com/thewindyz/p/14377864.html