编译原理基础知识汇总

前端: 词法分析 -> 语法分析 -> 语义分析
后端: 生成中间代码 -> 优化 -> 生产目标代码

词法分析：有限自动机
语法分析：构建抽象语法书（AST），递归下降算法
语义分析：

• 数据类型不匹配，是否做自动转换。
• 相同名称的变量，作用域的处理。
• 变量名重复检查

表达式：左递归、优先级、结合性
上下文无关文法：无论在任何情况下，文法的推到规则都是一样的。
递归下降算法：算法分为自顶向下、自底向上，显而易见递归下降算法就是自顶向下。
非终结符(non-terminal) 产生式(Production Rule) 推导(Derivation)

解决左递归产生的死循环问题:虽然解决了左递归产生的死循环，但是结合性出错了。

巴克斯范式、扩展巴克斯范式

add -> mul(+mul)*

上下文无关文法包含了正则文法。

• 保证运算符的优先级。
• 确保正确的结合性。
  注：阅读语法规则文件，熟悉语言的规则

消除左递归

add -> mul add'
add' -> + mul add'|ε

add -> mul(+mul)*

尾递归（函数的最后一句递归调用自身）。
尾递归 -> 循环调用（减少系统资源的开销）。

• 优先级越低越先尝试推导。
• 结合性由左递归和右递归产生（左递归 -> 左结合，右递归 -> 右结合）
• 改写语法规则避免左递归。
  回溯:尝试不成功后恢复原样
  REPL （read-eval-print loop）。