前言

今天我们来谈一谈第一个部分词法分析模块中的第一块内容,主要涉及到token的定义,正则表达式等内容

正文

定义以及问题

首先我们要明确词法分析这一阶段主要做什么,词法分析器主要由两个阶段组成:

  1. 扫描阶段:处理不需要生成词法单元(token),例如删除注释,压缩连续的空白字符等操作
  2. 词法分析阶段:处理扫描阶段的输出并生成正确的token

然后我们需要明确token的定义

一个token主要是由两个部分组成一个是语素(lexemes),另一个是每一个语素相对应的词法名(token class)

语素就是一个字符串,符合某个词法名模式,被词法分析器分析出的实例

词法名类似数字,关键词,Identifier(靠我不太会翻译这个,就是类似变量名),这些不同类型的定义,

根据上面的定义,词法分析最后会输出一对对词素和词法名的组合,也就是一个token。由此我们就明确了词法分析阶段需要完成的任务

  • 识别子序列,也就是语素
  • 确认语素对应的类别,也就是词法名

我们从左到右进行对输入序列的扫描,并分析输出token,但是实事上并没有那么简单,词法分析时我们往往会碰到很多歧义发生,如果不结合之后的输入可能无法进行正确的分别,也就是lookahead,龙书上的例子

一直到,和.的位置之前我们都无法识别这个DO究竟是表示循环还是和后面的5I连在一起表示变量名,所以需要lookahead。

综上我们现在需要解决的问题就是识别语素,消除歧义。

正则表达式

最常用的方式是正则,我们首先来看一些定义。

语言是由一些符号用不同的形式进行组成的(我的口语化定义,书面定义看龙书)

然后最基础的原子正则表达式:

  • 单字符:'c' = {"c"},表示一个字符
  • Epsilon:ε = {""},表示一个空,注意不等于空符号

然后三个基本操作

  • 并:A + B = { s | s属于A or s属于B }
  • 交:AB = {s | s属于A and s属于B }
  • 迭代:A* = Ui>=0 A^i,就是A的i次方

定义正则表达式在字符集合S上是包含以上五要素的最小表达式(我晕了感觉我翻译的有问题)

然后L()表示从一个表达式映射到符合这个表达式的集合

总结

今天大致到这里后面继续分析词法分析包括形式语言,有限状态自动机等相应的知识。