1. 词法分析器的作用

为语法分析器服务

• 读入字符流，组成词素，输出
• 过滤空白、换行、制表符、注释等
• 将词素添加到符号表中
• 在逻辑上独立于语法分析，但是通常和语法分析器处于同一趟中

<aside> 💡 为什么要设立独立的词法分析器？

• 简化编译器设计

  • 首先处理简单工作

• 提高编译器效率

  • 相对语法分析过程简单，可以高效实现

• 增强编译器的可移植性 </aside>

• 词法单元 (Token) → 名字

  • <词法单元名、属性值 (可选) >
  • 单元名是表示词法单位种类的抽象符号，语法分析器 通过单元名即可确定词法单元序列的结构
  • 属性值通常用于语义分析之后的阶段

• 模式 (Pattern) → 名字代表什么意思

  • 描述了一类词法单元的词素可能具有的形式

• 词素 (Lexeme) → 具体的例子

  • 源程序中的字符序列
  • 它和某个词法单元的模式匹配，被词法分析器识别为 该词法单元的实例

<aside> 💡 词法单元的属性：一个模式匹配多个词素时，必须通属性来传递附加的信息

</aside>

2. 词法单元的规约 (正则表达式)

2.1 串和语言

• 字母表 Alphabet → 一个有穷的符号集合
• 串 String → 是该字符表中符号的有穷序列
• 语言 Language → 是某给定字母表上的串的可数集合

<aside> 💡 术语

前缀、后缀、子串

真前缀、真后缀、真子串

</aside>

<aside> 💡 运算

• 连接 Concatenation
• 指数运算 / 幂运算 → 自连接 </aside>

2.2 语言上的运算

<aside> 💡 语言的运算

• 并 → $L \cup M$
• 连接 → $LM$
• Kleene 闭包 → $L^* = \cup_{i = 0}^{\infty}L^i$
• 正闭包 → $L^+ = \cup_{i = 1}^{\infty}L^i$ </aside>

2.3 正则表达式和正则定义