算法编译原理

计算的本质：深入剖析程序和计算机

字数统计: 1.7k字   |   阅读时长: 6分
, ,

摘要: 《计算的理论》

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

最近在 Leetcode 见到两类题目，一个是跟语法分析相关的，例如解析括号，解析表达式，等等各种解析，主要涉及编译原理中的语法分析的递归下降算法。语法分析问题分类汇总。

此外还有一类题目是根词法分析相关的，例如判断一个字符串是否表示一个数字(65. 有效数字)，字符串转数字(8. 字符串转换整数 (atoi))等，给定各种构词规则，判断给定字符串是否符合。主要涉及编译原理中词法分析的有限状态机(DFA)算法，参考文章 词法分析-有限自动机。

此外还有一些题目在主流解法之外也可以用 DFA 解，尤其是有些动态规划的问题，例如下面三道(好像还有很多的样子，比如股票系列)：

编译原理和可计算理论有经典的书，但是太大部头了，并没有耐心看下去，但是又觉得编译里面的词法，语法，语义的分析在业务上会很有用，于是找了一本比较薄，同时豆瓣风评还不错的书, 就是下面这本了。2015 年的，好像还比较新的样子。作者是英国人。

本书主要内容涉及编译原理中的形式语言，有限自动机，正则表达式，下推自动机，类型检查等；以及可计算理论中的图灵机、lambda演算、SKI 组合等。

这本书属于实战版本，对理论介绍的并不深，可惜代码是 Ruby，并不想花时间学习 Ruby。只能尝试理解了然后争取用 Python 复现了，顺便回忆下 Python，毕竟是业务语言。

形式语言与自动机、程序设计语言、编译原理、可计算理论，这在计算机系是三到四门课，企图用一本不到 300 页的书就了解，是贪心了点，不过先试试看呗，毕竟退出成本低，万一半路发现这书并不太行，还是可以弃坑的[/捂脸]。

编译原理中的阶段主要有词法分析，语法分析，语义分析。

(1) 词法分析

这是编译过程的第一个阶段，给定构词规则，然后逐个字符读入，按照给定的构词规则识别出字符流中的各个单词。

(2) 语法分析

这是编译过程的一个逻辑阶段，将词法分析产出的单词序列组合成各类语法短语，并且判断源程序在结构上是否正确，这里源程序的结构由上下文无关文法描述。

(3) 语义分析

这也是编译过程的一个逻辑阶段，对通过了语法分析，结构上正确的程序进行上下文有关性质的审查，以及进行类型审查。

第一部分 程序和机器

2 程序的含义

  • 2.1 “含义”的含义
  • 2.2 语法
  • 2.3 操作语义
    • 2.3.1 小步语义
    • 2.3.2 大步语义
  • 2.4 指称语义
    • 2.4.1 表达式
    • 2.4.2 语句
    • 2.4.3 应用
  • 2.5 形式化语义实践
    • 2.5.1 形式化
    • 2.5.2 找到含义
    • 2.5.3 备选方案
  • 2.6 实现语法解析器

3 最简单的计算机

  • 3.1 确定性有限自动机
    • 3.1.1 状态、规则和输入
    • 3.1.2 输出
    • 3.1.3 确定性
    • 3.1.4 模拟
  • 3.2 非确定性有限自动机
    • 3.2.1 非确定性
    • 3.2.2 自由移动（free move）
  • 3.3 正则表达式
    • 3.3.1 语法
    • 3.3.2 语义
    • 3.3.3 解析
  • 3.4 等价性

4 增加计算能力

  • 4.1 确定性下推自动机
    • 4.1.1 存储
    • 4.1.2 规则
    • 4.1.3 确定性
    • 4.1.4 模拟
  • 4.2 非确定性下推自动机
    • 4.2.1 模拟
    • 4.2.2 不等价
  • 4.3 使用下推自动机进行分析
    • 4.3.1 词法分析
    • 4.3.2 语法分析
    • 4.3.3 实践性
  • 4.4 有多少能力

5 终极机器

  • 5.1 确定型图灵机
    • 5.1.1 存储
    • 5.1.2 规则
    • 5.1.3 确定性
    • 5.1.4 模拟
  • 5.2 非确定型图灵机
  • 5.3 最大能力
    • 5.3.1 内部存储
    • 5.3.2 子例程
    • 5.3.3 多纸带
    • 5.3.4 多维纸带
  • 5.4 通用机器
    • 5.4.1 编码
    • 5.4.2 模拟

第二部分 计算与可计算性

6 从零开始编程

  • 6.1 模拟lambda演算
    • 6.1.1 使用proc工作
    • 6.1.2 问题
    • 6.1.3 数字
    • 6.1.4 布尔值
    • 6.1.5 谓词
    • 6.1.6 有序对
    • 6.1.7 数值运算
    • 6.1.8 列表
    • 6.1.9 字符串
    • 6.1.10 解决方案
    • 6.1.11 高级编程技术
  • 6.2 实现lambda演算
    • 6.2.1 语法
    • 6.2.2 语义
    • 6.2.3 语法分析

7 通用性无处不在

  • 7.1 lambda演算
  • 7.2 部分递归函数
  • 7.3 SKI组合子演算
  • 7.4 约塔（Iota）
  • 7.5 标签系统
  • 7.6 循环标签系统
  • 7.7 Conway的生命游戏
  • 7.8 rule 110
  • 7.9 Wolfram的2,3图灵机

8 不可能的程序

  • 8.1 基本事实
    • 8.1.1 能执行算法的通用系统
    • 8.1.2 能够替代图灵机的程序
    • 8.1.3 代码即数据
    • 8.1.4 可以永远循环的通用系统
    • 8.1.5 能引用自身的程序
  • 8.2 可判定性
  • 8.3 停机问题
    • 8.3.1 构建停机检查器
    • 8.3.2 永远不会有结果
  • 8.4 其他不可判定的问题
  • 8.5 令人沮丧的暗示
  • 8.6 发生上述情况的原因
  • 8.7 处理不可计算性

9 在“玩偶国”中编程

  • 9.1 抽象解释
    • 9.1.1 路线规划
    • 9.1.2 抽象：乘法的符号
    • 9.1.3 安全和近似：增加符号
  • 9.2 静态语义
    • 9.2.1 实现
    • 9.2.2 好处和限制
  • 9.3 应用
Share