[toc]
递归向量分析
参考上下文无关文法orzzz
- 子串$\ne$子序列。后者可能不相邻
- 重写规则左部不能是空串。右部可以是。
- 直接推导/直接规约
- 句型：从开始符号推导出的符号串
- 句子：仅由终结符构成的句型
- 语言层面上，句子是给定字母表上一个符号串
- C语言语句不是句子。完整程序才是。
- 语言：L(G)
- 语言等价$\Rightarrow$文法等价，即$L(G)=L(G^\prime) \Rightarrow G=G^\prime$
- 乔姆斯基语言族
- 0型文法（PSG）
- 定义：每个产生式的左部都含有至少一个非终结符
- 等价于图灵机
- 通过对产生式形式做限制得到其他三类文法
- 1型文法（CSG）
- 上下文有关文法。要求左部长度小于右部；右部包含上下文
- 计算比较3项关系
- 等价于线性边界自动机
- 对程序语义太复杂
- 2型文法（CFG）
- 上下文无关文法
- 计算比较2项关系
- 等价于下推自动机（PDA）
- 可以用来自动形成语法分析树
- 语法树的构建过程对应一个推导过程
- 3型文法（RG）
- 正则文法
- 右部只有一个终结符或一个终结符和一个非终结符（同侧）
- 左线性文法和右线性文法等价（非终结符在左/右）
- 识别有限长度任何模型
- 模式识别、符号匹配、词法分析
- 语言类上自上到下包含。但具体语言可能是自下而上包含（上部语言可能是下部语言的真子集）。
- 各型语言类对并、积、闭包运算封闭
- 2型语言对交、补运算不封闭
- 3型语言对交、补运算封闭
- 语法制导定义不明确说明语义规则的计算次序
- 0型文法（PSG）
- 结点自身是自身的祖先/后代结点
- 一个父节点的各个子节点从左到右有序
- 从左向右将语法树的所有叶节点依次连接，得到符合文法的一个句子
- 语法树不能反映构建过程（最右/最左推导结果可能相同），可能存在多个合法推导序列
- 如果文法对同一个终结符号串存在两个以上对应语法树，则称之具有二义性
- 只要一个句子对应多个语法树，即为二义性文法
- 同一个语法树也可以有多种推导
- 如果文法没有二义性，那么每个句子只存在一种最左推导和最右推导
- 在有n层算符优先级的文法中，引入n+1个非终结符，可以解决运算优先性的问题
将语义动作与产生式关联的方式
- 语法制导翻译输出的代码格式为后缀表示
- 根据语义规则计算与产生式中符号关联的属性值，得到带注释的语法树
- 综合属性
- 由子节点和自身属性值确定
- 对语法树的后根遍历完成
- 继承属性
- 属性计算需要用到父节点或兄弟节点的属性值
- 语法制导翻译未明确说明计算顺序
- 翻译方案
- 在文法产生式中附加程序片段描述翻译结果，以显式给出语义动作计算顺序
- 扩充了语义动作结点的语法树，用虚线连接
- 分类
- 自顶向下
- 递归下降、LL分析等
- 构造简单，但需要
- 避免回溯
- 消除左递归、左因子
- 自底向上
- 叶结点开始选择语法子树
- 算符优先、LR分析等
- LR分析能力强，可分析更多文法
- 自顶向下
- 不是所有文法都适合
- 以开始符号作为树根，开始构建语法分析树，匹配产生式
- 产生式关注第一个尚未处理的终结符
- 使用一组递归过程
- 每个非终结符对应一个过程
- 隐式定义了语法分析树
- 简单形式是预测分析
- 可以根据向前看的符号无二义地决定语法分析过程
- 判断当前结点是否与向前看的符号匹配
- 非终结符作为多个产生式左部时
- 根据向前看的符号区分，避免回溯（所以应当令first集合互不相交）
-
$\epsilon$ 产生式最后考虑
- 如果加入相关语义动作，则成为翻译器
- 消除左递归的方法：变为右递归
- 语法树的两种形式
- 语法分析树
- 内部节点是非终结符，叶结点是终结符
- 抽象语法树（AST）
- 节点数目少，编译更常用
- 内部节点对应算符，子结点对应运算对象
- 没有单产生式和$\epsilon$产生式对应节点
- 编译器的简化：把递归变为迭代
- 输出语法分析的输入终结符
- 附加行号等信息
- 处理空格、制表符、换行符、注释等
- 预读（对于多符号情况）
- 可以多读若干位或引入缓冲区
- 常量表示为<num, val>
- 关键字被多数语言作为保留字
- 标识符用id标识，用于变量、函数、常数的明明，写入符号表，用hash表优化
- 入表前先查询；可以初始化将关键字入表
- 第六章
- 保存源程序构造各种信息的数据结构
- 语法分析会在词法分析上进一步完善符号表
- 符号表受作用域规则影响（最近嵌套原则）
- 局部符号表构成树
- 两个栈表示符号表层次结构
- 符号表栈
- 符号表表项栈（hash索引）
- 函数处理完后函数本身入表项栈
- 声明时把条目入表
- 两种中间表示形式
- （抽象语法）树
- 前端采用树形式
- 线性表示（如三地址代码）
- 一般用于后端输出
- （抽象语法）树
- 静态检查
- 前端的重要工作
- 在编译时完成的一致性检查，大多在语法分析阶段发现
- 发现语法格式、语法约束条件（如break只能在特定结构）、类型匹配等错误
- 语句的抽象语法树
- 为每种语句构造定义相应算符（如关键字）
- 表示语句块和语句序列
- 类似的算符归为一组以减少子类，相应在树节点增加域来划分
- 左值和右值
- 左值指存储位置，右值指存放的值
- 赋值号两侧都可以是表达式，但结果应对应
- 常量只有右值
- 静态检查的一项要求
- 语句翻译
- 控制流优化
- 表达式翻译
- 为每个运算符结点生成一个三地址代码（可能引入临时变量）
- 指令优化
- 减少拷贝指令
- 合并变量
- 回填技术
- 左值和右值分析
- 减少拷贝指令