编译原理与实践 学习笔记

学习资料：中科大视频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）的改进
• 

抽象语法树

语义分析

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