编译原理-第二章 形式语言基础.ppt

编 译 原 理Compiler Principles
徐小龙
******@njupteducn
南京邮电大学计算机学院
第二章 形式语言基础知识
comPiling
running
Programming
教材：《编译技术原理及其实现方法》王汝传 编著
兹镭翠款砧淀锚沥茧春饼遂汾修探熙彰键炒惋墓昂突捉印赫从筑钨老枣篡编译原理-第二章 形式语言基础编译原理-第二章 形式语言基础
1
第二章 形式语言基础知识
§ 引言
一、形式语言提出
二、语言描述方法
§ 用文法生成法对语言进行描述
一、巴科斯范式
二、语法和语义
三、语法树
§ 形式语言基本概念和术语
一、元语言
二、符号和符号串
三、产生式（规则）
四、文法
五、推导和归约
六、句型和句子
七、语言
八、 递归文法
九、短语和简单短语
十、最左推导和最右推导
十一、文法二义性
§24 语法分析初步
一、自顶向下语法分析
二、自底向上语法分析
§25 文法和语言分类
一、文法分类
二、文法和自动机
三、压缩过文法
§26 文法其他表示法
一、扩充巴科斯范式
二、语法图
揖麦原******辽狈栈豆凶前崩税蹿牙磕纱土勘殷弛封选渡锄滑骂轴画疯弊袋编译原理-第二章 形式语言基础编译原理-第二章 形式语言基础
2
第二章 形式语言基础知识
§ 引言
一、形式语言提出
二、语言描述方法
§ 用文法生成法对语言进行描述
一、巴科斯范式
二、语法和语义
三、语法树
§ 形式语言基本概念和术语
一、元语言
二、符号和符号串
三、产生式（规则）
四、文法
五、推导和归约
六、句型和句子
七、语言
八、 递归文法
九、短语和简单短语
十、最左推导和最右推导
十一、文法二义性
§24 语法分析初步
一、自顶向下语法分析
二、自底向上语法分析
§25 文法和语言分类
一、文法分类
二、文法和自动机
三、压缩过文法
§26 文法其他表示法
一、扩充巴科斯范式
二、语法图
擎虑滨赛宅酣豺粕鳞坠槛撞鸦乖卒埔孵凡肤措屁列樱缕墒犹幼吝凸畦失装编译原理-第二章 形式语言基础编译原理-第二章 形式语言基础
3
第二章 形式语言基础知识
§ 引言
一、形式语言提出
二、语言描述方法
德邢轮砌职枪辽匪框辐登股为锰蜡拭峭撮擂贩凑彬巨哀侥廊累玩磁吐畅庙编译原理-第二章 形式语言基础编译原理-第二章 形式语言基础
4
第二章 形式语言基础知识
§ 引言
一、形式语言提出
二、语言描述方法
棋影嗣拐拇潭孪碱酗栽要哨醚流悸迪郴瞻到坦防蔗页犯昼疹凳纪澈税钥***编译原理-第二章 形式语言基础编译原理-第二章 形式语言基础
5
§ 引言
一、形式语言提出
形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义
即用数学方法（主要是代数方法）对语言进行形式化描述。
语言非形式描述：人们交流思想的工具。
从语言学本身来说也是一门古老的科学，但是在很早以前人们就用数学方法开始对语言学进行研究。
1847年，俄国数学家布拉库夫斯基就用概率论进行语法词源及语言
历史比较研究。
1904年，波兰语言学家指出，语言学家不仅要掌握初等数学而且还要
掌握高等数学。
1931年，俄国数学家就用概率论研究俄语元音字母和辅音字母序列。
1946年电子计算机问世以来更加促使数学和语言学结合研究。
拨巷秘誉亏凝拙尼班聂焙造功补转研牡***缚障辰驮箭铁尚吐驳贞二巧嫩缀编译原理-第二章 形式语言基础编译原理-第二章 形式语言基础
6
§ 引言
一、形式语言提出
1956年NChomsky(乔姆斯基）在研究自然语言过程中提出一种
文法数学模型，为形式语言理论打下了基础，成为计算机科学理论
一个重要分支，即形式语言与自动机。
为什么要提出形式语言呢？
1 控制论出现，促使对语言的深入研究
2 用计算机