学习资料：中科大视频https://www.bilibili.com/video/av32233569/?p=1

教材《编译原理与实践》

正则表达式

  • 定义：选择、连接、闭包

有限状态自动机

  • 分类
    • 不确定有限状态自动机（NFA）：下一个状态可能有多个
    • 确定有限状态自动机（DFA）：下一个状态只有一个
  • 信息
    • 两个圈：接收状态
  • 目的：
  • 从RE→NFA（汤普森算法，递归、子结构）
    • e1e2
    • e1|e2
  • NFA→DFA（子集构造法）
    • 算法描述：从起始状态出发，读入任意一个字符所能到达的所有状态，类似宽度优先搜索算法
    • 算法性质
      • 可终结性

上下文无关文法

  • 非终结符：大写字母
  • 终结符：小写字母
  • 最左推导、最右推导
  • 分析树(parsing tree)
    • 特点：分析树的形状和推导的顺序无关
    • 后序遍历

语法分析

  • 自顶向下分析
  • LL（1）：从左到右，最左推导，用1个辅助
  • LL（1）分析表：指导当前栈顶元素应该如何转换
  • First（N） = 从非终结符N开始推得出的所有句子开头可能的所有终结符
  • First（N）的不动点算法，先求得所有的NULLABLE集合，然后枚举，直到某个β∉NULLABLE，那么First（N）并就到β为止
  • follow（N）的不动点算法
    • 逆序来求，如果当前可为空，那么累计并，否则清空
  • 判断是不是LL（1） ， 一个非终结符到终结符，表格只能有一个内容。即一个非终结符的某个follow终结符，只能通过一条式子得到
  • 优点：算法时间复杂度线性
  • 缺点：分析文法类型受限，可能需要文法改写
  • NULLBALE：通过推导能得到空的所有非终结符集合

LR（0）自底向上分析

  • 归约：从产生式右边 → 左边 
  • 本质：是最右推导的逆过程，利用了有记忆能力的DFA
  • 点记号：点的左边都被读入，点的右边还没读入
  • 实现关键
    • 何时规约？何时移进？
  • 算法画图思想：
    • 有点记号的都是项目，每个状态由若干个项目集组成。
    • 如果点记号后面是一个非终结符，那么多一条项目
    • 图对应LR（0）分析表
  • SLR算法：LR（0）的改进

抽象语法树

语义分析

  • 目标：检查抽象语法树语义上是否合法的？？