第四章语法分析 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版
许畅 南京大学计算机系 2022年春季 第四章 语法分析 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅
概要 。 语法分析器 。上下文无关文法 语法分析技术 自顶向下 自底向上 译许畅 。 语法分析器生成工具 2
概要 • 语法分析器 • 上下文无关文法 • 语法分析技术 – 自顶向下 – 自底向上 • 语法分析器生成工具 2 南大编译许畅
语法分析器的作用 基本作用 从词法分析器获得词法单元的序列，确认该序列是否 可以由语言的文法生成 对于语法错误的程序，报告错误信息 对于语法正确的程序，生成语法分析树（简称语法树） 通常并不真的产生这棵语法分析树 源程序 词法单元 词法 语法 语法 前端的 中间表示 分析器 分析器 分析树 其余部分 获取下一 个词法单元 符号表 图4-1 编译器模型中语法分析器的位置 3
语法分析器的作用 • 基本作用 – 从词法分析器获得词法单元的序列，确认该序列是否 可以由语言的文法生成 – 对于语法错误的程序，报告错误信息 – 对于语法正确的程序，生成语法分析树 (简称语法树) • 通常并不真的产生这棵语法分析树 3 南大编译许畅
语法分析器的分类 通用语法分析器 可以对任意文法进行语法分析 效率很低，不适合用于编译器 自顶向下语法分析器（通常用于处理LL文法） 从语法分析树的根部开始构造语法分析树 自底向上语法分析器（通常用于处理LR文法） 从语法分析树的叶子开始构造语法分析树 。后两种方法 总是从左到右、逐个扫描词法单元 只能处理特定类型的文法，但足以描述程序设计语言 4
语法分析器的分类 • 通用语法分析器 – 可以对任意文法进行语法分析 – 效率很低，不适合用于编译器 • 自顶向下语法分析器 (通常用于处理LL文法) – 从语法分析树的根部开始构造语法分析树 • 自底向上语法分析器 (通常用于处理LR文法) – 从语法分析树的叶子开始构造语法分析树 • 后两种方法 – 总是从左到右、逐个扫描词法单元 – 只能处理特定类型的文法，但足以描述程序设计语言 4 南大编译许畅
程序设计语言构造的描述 程序设计语言构造的语法可使用上下文无关文法 (CFG)或BNF表示法来描述 文法可给出精确易懂的语法规则 可以自动构造出某些类型的文法的语法分析器 文法指出了语言的结构，有助于进一步的语义处理/代 码生成 支持语言的演化和迭代 5
程序设计语言构造的描述 • 程序设计语言构造的语法可使用上下文无关文法 (CFG) 或BNF表示法来描述 – 文法可给出精确易懂的语法规则 – 可以自动构造出某些类型的文法的语法分析器 – 文法指出了语言的结构，有助于进一步的语义处理/代 码生成 – 支持语言的演化和迭代 5 南大编译许畅
上下文无关文法 ·一个上下文无关文法 (CFG)包含四个部分 终结符号：组成串的基本符号（词法单元名字） 非终结符号：表示串的集合的语法变量 。 在程序设计语言中通常对应于某个程序构造，比如stmt(语句) 开始符号：某个被指定的非终结符号 它对应的串的集合就是文法的语言 产生式：描述将终结符号和非终结符号组成串的方法 形式：头（左）部今体（右）部 头部是一个非终结符号，右部是一个符号串 例子：expression→expression+term 6
上下文无关文法 • 一个上下文无关文法 (CFG) 包含四个部分 – 终结符号：组成串的基本符号 (词法单元名字) – 非终结符号：表示串的集合的语法变量 • 在程序设计语言中通常对应于某个程序构造，比如stmt (语句) – 开始符号：某个被指定的非终结符号 • 它对应的串的集合就是文法的语言 – 产生式：描述将终结符号和非终结符号组成串的方法 • 形式：头 (左) 部 → 体 (右) 部 • 头部是一个非终结符号，右部是一个符号串 • 例子：expression → expression + term 6 南大编译许畅
上下文无关文法的例子 ·简单算术表达式的文法 终结符号：id,+,-,*,/,() 非终结符号：expressic0n,term,factor 开始符号：expression 产生式集合 expression>expression +term expression expression-term expression→term term→term*factor term→term/factor term→factor factor→(expression) factor→id 7
上下文无关文法的例子 • 简单算术表达式的文法 – 终结符号：id, +, –, *, /, (, ) – 非终结符号：expression, term, factor – 开始符号：expression – 产生式集合 expression → expression + term expression → expression – term expression → term term → term * factor term → term / factor term → factor factor → ( expression ) factor → id 7 南大编译许畅
文法简单形式的例子 E→E+TIE-TIT T→T*FIT/FIF F→(E)Iid 译许 ·注意 是元符号（即文法描述中的符号，而不是文法符号） 这里的（和）不是元符号 9
文法简单形式的例子 E → E + T | E – T | T T → T * F | T / F | F F → ( E ) | id • 注意 – |是元符号 (即文法描述中的符号，而不是文法符号) – 这里的 ( 和 ) 不是元符号 9 南大编译许畅
推导(1) ·推导 将待处理的串中的某个非终结符号替换为这个非终结 符号的某个产生式的体 从开始符号出发，不断进行上面的替换，就可以得到 文法的不同句型 例子 文法：E→-EIE+EIE*EI(E)Iid 推导序列：E=>-E=>-（E)=>-（id) 10
推导 (1) • 推导 – 将待处理的串中的某个非终结符号替换为这个非终结 符号的某个产生式的体 – 从开始符号出发，不断进行上面的替换，就可以得到 文法的不同句型 • 例子 – 文法：E → – E | E + E | E * E | ( E ) | id – 推导序列：E => – E => – ( E ) => – ( id ) 10 南大编译许畅
推导(2) ·推导的正式定义 如果A→Y是一个产生式，那么xAB=>yB 最左（右）推导：（β）中不包含非终结符号 。 符号：言>盖> rm 经过零步或者多步推导出：> 对于任何串x±x 如果x±>阝且阝=>Y,那么x>y 。经过一步或者多步推导出：〧 -xB即x>B且不等于B(不严格) 11
推导 (2) • 推导的正式定义 – 如果A → γ是一个产生式，那么αAβ => αγβ – 最左 (右) 推导：α(β) 中不包含非终结符号 • 符号： • 经过零步或者多步推导出： – 对于任何串α α – 如果α β且β => γ，那么α γ • 经过一步或者多步推导出： – α β即α β且α不等于β (不严格) 11 南大编译许畅
