编译原理学习记录
学习资料：中科大视频https://www.bilibili.com/video/av32233569/?p=1
教材《编译原理与实践》
正则表达式
- 定义：选择、连接、闭包
有限状态自动机
- 分类
- 不确定有限状态自动机（NFA）：下一个状态可能有多个
- 确定有限状态自动机（DFA）：下一个状态只有一个
- 信息
- 两个圈：接收状态
- 目的：
- 从RE→NFA（汤普森算法，递归、子结构）
- e1e2
- e1|e2
-
- e1e2
- NFA→DFA（子集构造法）
- 算法描述：从起始状态出发，读入任意一个字符所能到达的所有状态，类似宽度优先搜索算法
- 算法性质
- 可终结性
- 最坏时间复杂度：
上下文无关文法
- 非终结符：大写字母
- 终结符：小写字母
- 最左推导、最右推导
- 分析树(parsing tree)
- 特点：分析树的形状和推导的顺序无关
- 后序遍历
语法分析
- 自顶向下分析
- LL（1）