第四章 语法分析【荐】.pdf

第四章语法分析 许畅 南京大学计算机系 2013年春季 概要  语法分析器  上下文无关文法  语法分析技术  自顶向下  自底向上  语法分析器生成工具 2 程序设计语言构造的描述  程序设计语言构造的语法可使用上下文无关文法 或BNF表示法来描述  文法可给出精确易懂的语法规则  可以自动构造出某些类型的文法的语法分析器  文法指出了语言的结构，有助于进一步的语义处理/代 码生成  支持语言的演化和迭代 3 语法分析器的作用 • 基本作用 – 从词法分析器获得词法单元的序列，确认该序列是否 可以由语言的文法生成 – 对于语法错误的程序，报告错误信息 – 对于语法正确的程序，生成语法分析树 • 通常并不真的生产这棵语法分析树 4 语法分析器的分类 • 通用语法分析器 – 可以对任意文法进行语法分析 – 效率很低，不适合用于编译器 • 自顶向下语法分析器(通常用于处理LL文法) – 从语法分析树的根部开始构造语法分析树 • 自底向上语法分析器(通常用于处理LR文法) – 从语法分析树的叶子开始构造语法分析树 • 后两种方法 – 总是从左到右、逐个扫描词法单元 – 只能处理特定类型的文法，但是这些文法足以用来描 述程序设计语言 5 上下文无关文法 • 定义：一个上下文无关文法(CFG) 包含四个部分 – 终结符号：组成串的基本符号(词法单元名字) – 非终结符号：表示串的集合的语法变量 • 给出了语言的层次结构 • 在程序设计语言中通常对应于某个程序构造，比如stmt (语句) – 开始符号：某个被指定的非终结符号 • 它对应的串的集合就是文法的语言 – 产生式集合：描述将终结符号和非终结符号组成串的 方法 • 产生式的形式：头(左) 部 体(右) 部 • 头部是一个非终结符号，右部是一个符号串 • 例子：expression  expression + term 6 上下文无关文法的例子 • 简单算术表达式的文法 – 终结符号：id, +, –, *, /, (, ) – 非终结符号：expression, term,factor – 开始符号：expression – 产生式集合 expression  expression + term expression  expression – term expression  term term  term *factor term  term /factor term factor factor  ( expression