第四章语法分析 赵建华 南京大学计算机系 2010.3
第四章 语法分析 赵建华 南京大学计算机系 2010.3
程序设计语言构造的描述 程序设计语言构造的语法可使用上下文无 关文法或BNF表示法来描述 文法可给出精确易懂的语法规则 可以自动构造出某些类型的文法的语法分析器 文法指出了语言的结构,有助于进一步的语义 处理代码生成。 支持语言的演化和迭代
程序设计语言构造的描述 • 程序设计语言构造的语法可使用上下文无 关文法或BNF表示法来描述 – 文法可给出精确易懂的语法规则 – 可以自动构造出某些类型的文法的语法分析器 – 文法指出了语言的结构，有助于进一步的语义 处理/代码生成。 – 支持语言的演化和迭代
语法分析器的作用 基本作用 从词法分析器得词法单元的序列,确认该序列是 否可以由语言的文法生成。 对于语法错误的程序,报告错误信息 对于语法正确的程序,生成语法分析树。 通常并不真的生产这棵语法分析树 源程序 词法词法单元 语法 语法 前端的L中间表示 分析器 获取下 分析器分析树“其余部分 个词法单元 符号表 图4-1编译器模型中语法分析器的位置
语法分析器的作用 • 基本作用 – 从词法分析器获得词法单元的序列，确认该序列是 否可以由语言的文法生成。 – 对于语法错误的程序，报告错误信息 – 对于语法正确的程序，生成语法分析树。 • 通常并不真的生产这棵语法分析树
语法分析器的分类 通用语法分析器 可以对任意文法进行语法分析 效率很低,不适合用于编译器 自顶向下语法分析器 从语法分析树的根部开始构造语法分析树 ·自底向上语法分析器 从语法分析树的叶子开始构造语法分析树 ·后两种方法 总是从左到右、逐个扫描词法单完 只能处理特定类型的文法但是这些大法足以用来 描述程序设计语言
语法分析器的分类 • 通用语法分析器 – 可以对任意文法进行语法分析 – 效率很低，不适合用于编译器 • 自顶向下语法分析器 – 从语法分析树的根部开始构造语法分析树 • 自底向上语法分析器 – 从语法分析树的叶子开始构造语法分析树 • 后两种方法 – 总是从左到右、逐个扫描词法单元。 – 只能处理特定类型的文法，但是这些文法足以用来 描述程序设计语言
上下文无关文法 ·定义:一个上下文无关文法包含四个部分 终结待号:组成串的基本待号(词法单元名字) 非终结符号:表示串的集合的语法变量 给出了语言的层次结构。 ·在程序设计语言中通常对应于某个程序构造,比如stmt(语旬) 开始符号:某个被指定的非终结符号。 ·它对应的串的集合就是大法的语言 产生式集合:描述将终结号和非终结♂号组成串的 方法 产生式的形式:头/左部→体/右部 头部是一个非终结符号,右部是一个符号串; ·例子: expression+ expression+term
上下文无关文法 • 定义：一个上下文无关文法包含四个部分 – 终结符号：组成串的基本符号（词法单元名字） – 非终结符号：表示串的集合的语法变量。 • 给出了语言的层次结构。 • 在程序设计语言中通常对应于某个程序构造，比如stmt（语句） – 开始符号：某个被指定的非终结符号。 • 它对应的串的集合就是文法的语言 – 产生式集合：描述将终结符号和非终结符号组成串的 方法 • 产生式的形式：头/左部 → 体/右部 • 头部是一个非终结符号，右部是一个符号串； • 例子：expression → expression + term
上下文无关文法的例子 简单算术表达式的文法: 终结诗号:id+-*/() 非终结符号: expression,term, factor 开始符号: expression 生式集合 expression expression term expression expression -term expression term tem→term* factor term→term/ factor tem→ factor factor >(expression) factor→id
上下文无关文法的例子 • 简单算术表达式的文法： – 终结符号：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
文法书写的约定 终结符号 靠前的小写字母(a2b,);运算符号(+*);标点符号;数 位;黑体字符串(id,if, while ·非终结符号 靠前的大小字母(AB,C);字母S(通常是开始符号); 小写斜体字母;表示程序枃造的大写字母 X,Y,Z文法符号(终结苻号或非终结符号) 小写希腊字母表示文法符号串(,B,y) ·靠后的小写字母表示终结符号串 具有相同头的产生式可以合并成A→a1|02….an的 形式 通常第一个产生式的左部就是开始苻号
文法书写的约定 • 终结符号 – 靠前的小写字母(a,b,c)；运算符号(+ *)；标点符号；数 位；黑体字符串(id, if, while) • 非终结符号 – 靠前的大小字母(A,B,C)；字母S（通常是开始符号）； 小写斜体字母；表示程序构造的大写字母 • X,Y,Z文法符号（终结符号或非终结符号） • 小写希腊字母表示文法符号串(α, β, γ) • 靠后的小写字母表示终结符号串 • 具有相同头的产生式可以合并成A→ α1 | α2 | … | αn的 形式 • 通常第一个产生式的左部就是开始符号
文法简单形式的例子 E→E+T|E-T|T T>T*FIT/FF F→(E)id 注意 是元符号(即文法描述方式中的符号,而不是 文法符号) 这里()不是元符号;在有些地方会把(看作元 子号
文法简单形式的例子 E → E + T | E – T | T T → T * F | T / F | F F → ( E ) | id • 注意: – | 是元符号（即文法描述方式中的符号，而不是 文法符号） – 这里(,)不是元符号；在有些地方会把( )看作元 符号
推导(1) 推导 一将待处理的串中的某个非终结脊号替换为这个 非终结符号的某个产生式的体 从开始号出发,不断进行上面的替换.就可 以得到文法的不同句型 ·例子 文法:E→|E+E|E*E|(E)|id 推导序列:E→>→>(E)=>-(id)
推导（1） • 推导： – 将待处理的串中的某个非终结符号替换为这个 非终结符号的某个产生式的体。 – 从开始符号出发，不断进行上面的替换，就可 以得到文法的不同句型 • 例子 – 文法: E → -E | E+E | E*E | (E) | id – 推导序列：E => -E => -(E) => -(id)
推导(2) 推导的正式定义 如果A+y是一个产生式,那么AB=>YB 最左(右)推导:0(β)中不包含非终结符号 符号:需 经过零步或者多步推导出: 对于任何串Q=Q 如果β且β 那么0=y 经过一步或者多步推导出: 0→>β等价于>阝且不等于β
推导（2） • 推导的正式定义 – 如果A→γ是一个产生式，那么αAβ => αγβ – 最左(右)推导：α(β)中不包含非终结符号 • 符号： • 经过零步或者多步推导出： – 对于任何串α α – 如果α β且β=>γ，那么α γ • 经过一步或者多步推导出： – α β等价于α β且α不等于β