编译原理-词法分析笔记

摘要: 词法分析

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

一个编译程序，往往有以下这几部分，这些都是编译原理要研究的内容：

• 词法分析器
• 语法分析器
• 语义分析
• 中间代码生成
• 优化
• 目标代码生成
• 表格管理
• 出错处理

在编译原理中，会涉及到各种计算思维，这些思维在计算机的其它领域也是非常底层的思维：

• 抽象
• 自动化
• 分解
• 递归
• 权衡
• 保护、冗余、容错、纠错、恢复
• 启发式推理
• 不确定情况下的规划、学习和调度

本文是编译原理词法分析部分的笔记。

---

词法分析

• 高级语言及其语法描述
  • 几个概念：字母表、字符、字(字符串)、空字
  • 字的集合的运算
  • 上下文无关文法
  • 产生式规则
  • 推导、语法树
  • 句型、句子、语言
  • 向左推导
  • 向右推导
  • 文法的二义性
  • 语言的二义性
  • 形式语言
    • 0 型: 短语文法，图灵机
    • 1 型: 上下文有关文法，线性界限自动机
    • 2 型: 上下文无关文法，非确定下推自动机
    • 3 型: 正规文法，有限自动机

• 词法分析器
  • 词法分析器结构
  • 状态转换图
  • 正规式和正规集
  • 正规式的性质
  • 确定有限自动机
  • 状态转换图的形式化
  • NFA与DFA
  • 将 NFA 确定化 — 子集法
  • 正规式与有限自动机的等价性定理及其证明
  • 确定有限自动机的化简
  • 词法分析器的自动产生 — LEX

---

计算思维

• 抽象
• 自动化
• 分解
• 递归
• 权衡
• 保护、冗余、容错、纠错、恢复
• 启发式推理
• 不确定情况下的规划、学习和调度

编译程序流程总览

• 词法分析器
• 语法分析器
• 语义分析
• 中间代码生成
• 优化
• 目标代码生成
• 表格管理
• 出错处理

高级语言及其语法描述

• 几个概念：字母表、字符、字(字符串)、空字
• 字的集合的运算
• 上下文无关文法
• 产生式规则
• 推导、语法树
• 句型、句子、语言
• 向左推导
• 向右推导
• 文法的二义性
• 语言的二义性
• 形式语言
  • 0 型: 短语文法，图灵机
  • 1 型: 上下文有关文法，线性界限自动机
  • 2 型: 上下文无关文法，非确定下推自动机
  • 3 型: 正规文法，有限自动机

词法分析器

• 词法分析器结构
• 状态转换图
• 正规式和正规集
• 正规式的性质
• 确定有限自动机
• 状态转换图的形式化
• NFA与DFA
• 将 NFA 确定化 — 子集法
• 正规式与有限自动机的等价性定理及其证明
• 确定有限自动机的化简
• 词法分析器的自动产生 — LEX

---