文档介绍：第三章语法分析
词法
分析器
记号
取下一个记号
源程序
分析树
前端的
其余部分
分析器
中间表示
符号表
本章内容
上下文无关文法
自上而下分析和自下而上分析
围绕分析器的自动生成展开
上下文无关文法
上下文无关文法的定义
正规式能定义一些简单的语言,能表示给定结构的固定次数的重复或者没有指定次数的重复
例:a (ba)5, a (ba)*
正规式不能用于描述配对或嵌套的结构
例1:配对括号串的集合
例2:{wcw | w是a和b的串}
上下文无关文法
上下文无关文法是四元组(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
上下文无关文法
例( {id, +, , , (, )}, {expr, op}, expr, P )
expr expr op expr expr (expr)
expr expr expr id
op + op
简化表示
E E A E | (E ) | E | id
A + |
上下文无关文法
推导
把产生式看成重写规则,把符号串中的非终结符用其产生式右部的串来代替
例 E E + E | E E | (E ) | E | id
E E (E) (E + E) (id + E)(id + id)
概念
上下文无关语言、等价的文法、句型
记号
S *、 S + w
上下文无关文法
E E + E | E E | (E ) | E | id
最左推导
E lm E lm (E) lm (E + E)
lm (id + E) lm (id + id)
最右推导(规范推导)
E rm E rm (E) rm (E + E)
rm (E + id) rm (id + id)
上下文无关文法
分析树
E
E
E
E
E
(
)
E
E
E
(
)
E
E
E
+
E
E
(
)
E
E
E
+
id
E
E
(
)
E
E
E
+
id
id
上下文无关文法
二义性
E E E E E + E
id E E E +E
id E + E id E + E
id id + E id id + E
id id + id id id + id
上下文无关文法
二义性
E E E E E + E
id E E E +E
id E + E id E + E
id id + E id id + E
id id + id id id + id
E
E
E
*
+
E
E
id
id
id
E
E
id
E
*
+
E
E
id
id
语言和文法
文法的优点
文法给出了精确的,易于理解的语法说明