字母表中后面的大写字母，如，，，可以是 终结符或非终结符
字母表中后面的小写字母，如， … 可代表 终结符号串
小写希腊字母，如，，可代表文法的符号串
对于 ， ，... 可以写成

…
上下文无关文法
推导（自顶向下）
把产生式看成重写规则，把符号串中的非终结 符用其产生式右部的串来代替
例
()
正则式不能用于描述配对或嵌套的结构 例：配对括号串的集合
上下文无关文法
上下文无关文法是四元组（ , , , ）
: 终结符集合
: 非终结符集合
: 开始符号，非终结符中的一个
: 产生式集合， 产生式形式 :
例 ( {, , , , (, )}, {, }, , )

()


简化表示
注解和空白由自己来处理的分析器，比注解 和空格已由词法分析器删除的分析器要复杂 得多
语言和文法
验证文法产生的语言
: ()
() 配对的括号串的集合
语言和文法
验证文法产生的语言
: ()
() 配对的括号串的集合
按推导步数进行归纳：推出的是配对括号串 归纳基础： 归纳假设：少于步的推导都产生配对的括号串 归纳步骤：步的最左推导如下：
文法的问题 文法只能描述编程语言的大部分语法，不能
描述语言中上下文有关的语法特征
语言和文法
正则式和上下文无关文法的比较
正则式 ()*
a 开始 0 a 1 b 2
文法
b
语言和文法
分离词法分析器理由
为什么要用正则式定义词法 词法规则非常简单，不必用上下文无关文法 对于词法记号，正则式描述简洁且易于理解 从正则式构造出的词法分析器效率高
() ( ) ( ) ( )
概念
* 、 ，于是
*
* ， 且 γ, 则
*γ
上下文无关文法
推导 概念 上下文无关语言 →γ, 且、是任意符号串，则 γ 由上下文无关文法生成的语言是上下文无关语
言 等价的文法 如果两个文法产生同样的语言，则两个文法等
价
上下文无关文法
例
()
最左推导

最右推导

再消除左递归

语言和文法 提左因子 有左因子的文法
提左因子
语言和文法
例 悬空的文法

提左因子

形式语言
⑴ 型语言 由 型文法定义
又称 无限制文法！
• 产生式形式为： > ⑵ 型语言 由 型文法定义
• 产生式形式为： >
⑶ 型语言 由 型文法定义 • 产生式形式为： >
() () 文法
()
语言和文法
()
expr
term
term * factor term * factor id
factor id
id 分析树
expr
expr + term
term term * factor
factor factor
id
id
id
分析树
Байду номын сангаас
消除二义性
语言和文法
句型： 两个最左推导：
语言和文法
章语法分析
第四章 语法分析
源程序
词法 分析器
记号
取下一个 记号
分析器
分析 树
前端的 中间 其余部分 表示
符号表
本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开
上下文无关文法
上下文无关文法
上下文无关文法的定义
正则式能定义一些简单的语言，能表示给定结 构的固定次数的重复或者没有指定次数的重 复 例： (), ()*

()
()
()
()
()
()
()
()
分析树 例
上下文无关文法 ()
()
二义性
上下文无关文法
两个不同的最左推导
二义性
上下文无关文法
E
E* id E
id
E 两棵不同的语法树E
+E
E*
id
id
E
+E E
id id
语言和文法
文法的优点 文法给出了精确的，易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改
⑷ 型语言 由 型文法定义
又称 上下文有关文法！
又称 上下文无关文法！
又称 正规文法！
• 产生式形式为：> , > , >
【注】 四类语言为 包含关系，且有 ⊃ ⊃ ⊃ ； 编译处理中，主要应用后两种文法！
乔姆斯基
艾弗拉姆·诺姆·乔姆斯基（英语 ： ，年月日－）
美国哲学家、语言学家、认知学 家、逻辑学家、政治评论家。乔 姆斯基是麻省理工学院语言学的 荣誉退休教授，他的生成语法被 认为是世纪理论语言学研究上的 重要贡献。

上下文无关文法 ()
简化表示

()

上下文无关文法
文法书写上的约定 终结符 字母表中的小写字母，如 ，， 黑体串，如 , 数字 , , … , 标点符号，如括号，逗号等 运算符号，如, 等 非终结符 字母表中的大写字母，如, ,
上下文无关文法
文法书写上的约定
() * () * ()
语言和文法
验证文法产生的语言
: ()
() 配对的括号串的集合
按串长进行归纳：配对括号串可由推出 归纳基础： 归纳假设：长度小于的都可以从推导出来 归纳步骤：考虑长度为( )的 ()
() * () * ()
语言和文法
适当的表达式文法 用一种层次观点看待表达式
()
语言和文法 适当的表达式文法 用一种层次观点看待表达式
无二义的文法



消除左递归 消除左递归
αβ
语言和文法
β αε
语言和文法
消除左递归
文法左递归
直接左递归
串的特点
...
消除直接左递归
语言和文法
例 算术表达文法



()
消除左递归后文法





()
（ ... ） （ ... ）
语言和文法
非直接左递归

先变换成直接左递归
句法结构
《句法结构》是乔姆斯基介绍转换生成语 法的《语言学理论的逻辑结构》一书的精 华版。这一理论认为说话的方式（词序） 遵循一定的句法，这种句法是以形式的语 法为特征的，具体而言就是一种不受语境 影响并带有转换生成规则的语法。
儿童被假定为天生具有适用于所有人类语 言的基本语法结构的知识。这种与生俱来 的知识通常被称作普遍语法。
语言和文法
从软件工程角度看，词法分析和语法分析的 分离有如下好处
简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分
语言和文法
能否把词法分析并入到语法分析中，直接从 字符流进行语法分析
若把词法分析和语法分析合在一起，则必须 将语言的注解和空白的规则反映在文法中， 文法将大大复杂