第三章语法分析 源程序一词法记号 分析器「取下一个 分析器分析「前端的|中间 树其余部分表示 记号 符号表 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开
第三章 语法分析 • 本章内容 – 上下文无关文法 – 自上而下分析和自下而上分析 – 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个 记号 源程序 分析 树 前端的 其余部分 分析器 中间 表示 符号表
31上下文无关文法 311上下文无关文法的定义 正规式能定义一些简单的语言,能表示给定结构 的固定次数的重复或者没有指定次数的重复 例 a (ba.a(ba 正规式不能用于描述配对或嵌套的结构 例1:配对括号串的集合 例2:{ww|v是a和b的串
3.1 上下文无关文法 3.1.1 上下文无关文法的定义 –正规式能定义一些简单的语言，能表示给定结构 的固定次数的重复或者没有指定次数的重复 例：a (ba) 5 , a (ba)* –正规式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcw | w是a和b的串}
31上下文无关文法 上下文无关文法是四元组(Vr,V,S,P T 终结符集合 V:非终结符集合 S 开始符号,非终结符中的一个 P:产生式集合,产生式形式:A→>a B(id,t, *,,()B, expr, op), expr, P) expr→ ecpr op ecpl expr→(expr) eupr→>-exDr evpr→id 0p→>+ 0p→>*
3.1 上下文无关文法 • 上下文无关文法是四元组（VT , VN , S, P） VT : 终结符集合 VN : 非终结符集合 S : 开始符号，非终结符中的一个 P : 产生式集合， 产生式形式 : A → • 例 ( {id, +, , −, (, )}, {expr, op}, expr, P ) expr → expr op expr expr → (expr) expr → − expr expr → id op → + op →
31上下文无关文法 简化表示 expr>expr op expr (expr) -expr id 0p→+|* 简化表示 E→EAE|(E)-Eid A→+|*
3.1 上下文无关文法 • 简化表示 expr → expr op expr | (expr) | − expr | id op → + | • 简化表示 E → E A E | (E ) | −E | id A → + |
31上下文无关文法 312推导 把产生式看成重写规则,把符号串中的非终结符 用其产生式右部的串来代替 例E→E+E|E*E|(E)|-E|id E→-E→-(E)→-(E+B→-id+E)→-(id+id) 概念 上下文无关语言、等价的文法、句型 记号 S→*a、S→+w
3.1 上下文无关文法 3.1.2 推导 –把产生式看成重写规则，把符号串中的非终结符 用其产生式右部的串来代替 • 例 E → E + E | E E | (E ) | − E | id E −E −(E) −(E + E) −(id + E) −(id + id) • 概念 – 上下文无关语言、等价的文法、句型 • 记号 S *、 S + w