第四章语法分析 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版
许畅 南京大学计算机系 2022年春季 第四章 语法分析 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅
概要 。 语法分析器 。上下文无关文法 语法分析技术 自顶向下 自底向上 译许畅 。 语法分析器生成工具 2
概要 • 语法分析器 • 上下文无关文法 • 语法分析技术 – 自顶向下 – 自底向上 • 语法分析器生成工具 2 南大编译许畅
语法分析器的作用 基本作用 从词法分析器获得词法单元的序列，确认该序列是否 可以由语言的文法生成 对于语法错误的程序，报告错误信息 对于语法正确的程序，生成语法分析树（简称语法树） 通常并不真的产生这棵语法分析树 源程序 词法单元 词法 语法 语法 前端的 中间表示 分析器 分析器 分析树 其余部分 获取下一 个词法单元 符号表 图4-1 编译器模型中语法分析器的位置 3
语法分析器的作用 • 基本作用 – 从词法分析器获得词法单元的序列，确认该序列是否 可以由语言的文法生成 – 对于语法错误的程序，报告错误信息 – 对于语法正确的程序，生成语法分析树 (简称语法树) • 通常并不真的产生这棵语法分析树 3 南大编译许畅
语法分析器的分类 通用语法分析器 可以对任意文法进行语法分析 效率很低，不适合用于编译器 自顶向下语法分析器（通常用于处理LL文法） 从语法分析树的根部开始构造语法分析树 自底向上语法分析器（通常用于处理LR文法） 从语法分析树的叶子开始构造语法分析树 。后两种方法 总是从左到右、逐个扫描词法单元 只能处理特定类型的文法，但足以描述程序设计语言 4
语法分析器的分类 • 通用语法分析器 – 可以对任意文法进行语法分析 – 效率很低，不适合用于编译器 • 自顶向下语法分析器 (通常用于处理LL文法) – 从语法分析树的根部开始构造语法分析树 • 自底向上语法分析器 (通常用于处理LR文法) – 从语法分析树的叶子开始构造语法分析树 • 后两种方法 – 总是从左到右、逐个扫描词法单元 – 只能处理特定类型的文法，但足以描述程序设计语言 4 南大编译许畅
程序设计语言构造的描述 程序设计语言构造的语法可使用上下文无关文法 (CFG)或BNF表示法来描述 文法可给出精确易懂的语法规则 可以自动构造出某些类型的文法的语法分析器 文法指出了语言的结构，有助于进一步的语义处理/代 码生成 支持语言的演化和迭代 5
程序设计语言构造的描述 • 程序设计语言构造的语法可使用上下文无关文法 (CFG) 或BNF表示法来描述 – 文法可给出精确易懂的语法规则 – 可以自动构造出某些类型的文法的语法分析器 – 文法指出了语言的结构，有助于进一步的语义处理/代 码生成 – 支持语言的演化和迭代 5 南大编译许畅