第四章语法分析 赵建华 南京大学计算机系 2010.3
第四章 语法分析 赵建华 南京大学计算机系 2010.3
程序设计语言构造的描述 程序设计语言构造的语法可使用上下文无 关文法或BNF表示法来描述 文法可给出精确易懂的语法规则 可以自动构造出某些类型的文法的语法分析器 文法指出了语言的结构,有助于进一步的语义 处理代码生成。 支持语言的演化和迭代
程序设计语言构造的描述 • 程序设计语言构造的语法可使用上下文无 关文法或BNF表示法来描述 – 文法可给出精确易懂的语法规则 – 可以自动构造出某些类型的文法的语法分析器 – 文法指出了语言的结构，有助于进一步的语义 处理/代码生成。 – 支持语言的演化和迭代
语法分析器的作用 基本作用 从词法分析器得词法单元的序列,确认该序列是 否可以由语言的文法生成。 对于语法错误的程序,报告错误信息 对于语法正确的程序,生成语法分析树。 通常并不真的生产这棵语法分析树 源程序 词法词法单元 语法 语法 前端的L中间表示 分析器 获取下 分析器分析树“其余部分 个词法单元 符号表 图4-1编译器模型中语法分析器的位置
语法分析器的作用 • 基本作用 – 从词法分析器获得词法单元的序列，确认该序列是 否可以由语言的文法生成。 – 对于语法错误的程序，报告错误信息 – 对于语法正确的程序，生成语法分析树。 • 通常并不真的生产这棵语法分析树
语法分析器的分类 通用语法分析器 可以对任意文法进行语法分析 效率很低,不适合用于编译器 自顶向下语法分析器 从语法分析树的根部开始构造语法分析树 ·自底向上语法分析器 从语法分析树的叶子开始构造语法分析树 ·后两种方法 总是从左到右、逐个扫描词法单完 只能处理特定类型的文法但是这些大法足以用来 描述程序设计语言
语法分析器的分类 • 通用语法分析器 – 可以对任意文法进行语法分析 – 效率很低，不适合用于编译器 • 自顶向下语法分析器 – 从语法分析树的根部开始构造语法分析树 • 自底向上语法分析器 – 从语法分析树的叶子开始构造语法分析树 • 后两种方法 – 总是从左到右、逐个扫描词法单元。 – 只能处理特定类型的文法，但是这些文法足以用来 描述程序设计语言
上下文无关文法 ·定义:一个上下文无关文法包含四个部分 终结待号:组成串的基本待号(词法单元名字) 非终结符号:表示串的集合的语法变量 给出了语言的层次结构。 ·在程序设计语言中通常对应于某个程序构造,比如stmt(语旬) 开始符号:某个被指定的非终结符号。 ·它对应的串的集合就是大法的语言 产生式集合:描述将终结号和非终结♂号组成串的 方法 产生式的形式:头/左部→体/右部 头部是一个非终结符号,右部是一个符号串; ·例子: expression+ expression+term
上下文无关文法 • 定义：一个上下文无关文法包含四个部分 – 终结符号：组成串的基本符号（词法单元名字） – 非终结符号：表示串的集合的语法变量。 • 给出了语言的层次结构。 • 在程序设计语言中通常对应于某个程序构造，比如stmt（语句） – 开始符号：某个被指定的非终结符号。 • 它对应的串的集合就是文法的语言 – 产生式集合：描述将终结符号和非终结符号组成串的 方法 • 产生式的形式：头/左部 → 体/右部 • 头部是一个非终结符号，右部是一个符号串； • 例子：expression → expression + term