编译原理复习

引论

• 编译与解释：![[编译与解释型语言]]

• 编译原理重点 编译程序的工作：

  1. 词法分析
  2. 语法分析
  3. 中间代码产生
  4. 优化
  5. 目标代码产生

高级语言及其语法描述

• 语法：一组规则，用它可以形成和产生一个形式上正确的程序
  • 词法规则：单词符号的形成规则
    • 单词符号：语言中具有独立意义的最基本结构
    • 描述工具：有限自动机
  • 语法规则：语法单位的形成规则，规定了如何从单词符号形成语法单位
    • 一般包括表达式、语句、分程序、过程、函数、程序等
    • 描述工具：上下文无关文法
• 语义：赋予程序意义
  • 描述方法：基于属性文法的语法制导翻译方法

程序语言的语法描述

基本概念

![[高级语言及其语法描述#基本概念的介绍]]

上下文无关文法

[[高级语言及其语法描述#上下文无关文法]] - 文法：描述语言的语法结构的形式规则

• 描述程序设计语言时，对于上下文无关文法的限制：

  • 不包含\(P\rightarrow P\)形式的产生式
  • 每个非终结符\(P\)必须有用

• 编译原理重点 形式语言：

  • 0：短语文法、图灵机
  • 1：上下文有关文法、线性界限自动机
  • 2：上下文无关文法、非确定下推自动机
  • 3：正规文法、有限自动机
• 四种类型描述能力比较：

词法分析

语法分析——自上而下分析

• 自上而下分析：
  • 基本思想：从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导
  • 递归下降分析法
  • 预测分析程序

LL(1)

![[LL(1)分析法]]