编译原理简明教程(第2版)[冯秀芳,崔冬华,段富][电子教案]第2章.ppt

《编译原理简明教程》
普通高等教育“十二五”规划计算机教材
---太原理工大学
---计算机科学与技术学院
---冯秀芳、崔冬华、段富等
第一章引言
第二章形式语言理论基础
第三章自动机理论基础
第四章词法分析
第五章语法分析—自顶向下分析方法
第六章语法分析—自底向上分析方法
第七章语义分析及中间代码的生成
第八章代码优化
第九章目标代码的生成
第十章符号表
第十一章目标程序运行时的存储组织与分配
第十二章出错处理
第十三章编译程序自动生成工具简介
第十四章面向对象语言的编译
第十五章并行编译技术
目录
第二章  形式语言理论基础
学****目标
学****形式语言理论中的一些基本概念和基础知识
掌握程序设计语言的语法描述方法
需要着重掌握的内容为
字母表
产生式、上下文无关文法
推导、句型、句子、语言
语法树
二义性
Chomsky文法分类
语法: 程序的结构形式
语义: 语言所代表的含义
语用: 语言的实际应用
例如:x:=a*b+c
语法: 变量:=表达式 v:= e
语义: 对e求值,再赋给变量
语用: 计算和保存e的值
以上形式化的描述不够清晰明确。
程序设计语言
探讨形式化方法: 用一套带有严格规定的符号体系来描
述问题的理论和方法。
形式语言:是一种不考虑含义的符号语言(只谈语法
不谈语义)。
形式语言理论:主要研究组成这组符号串的集合,它
们的表示法、结构及特性,只能用于
程序语言的语法描述和语法分析。
1956年著名语言学家Noam Chomsky 首先描述形式
语言,已成为计算机科学的一个重要组成部分,是编译
理论重要基础。
形式语言的基本概念
文法和形式语言的定义
语法树和二义性
文法的实用限制
文法和语言的Chomsky分类
目录
形式语言的基本概念
符号和符号串

形式语言和编译技术中两个主要概念
任何一种语言都是由该语言的基本符号组成的基本符
号串集合。
英文:26个字母、数字、标点符号等
PASCAL:字母、数字、关键字、专用符号等
中文:汉字、数字、标点符号等
:是一个非空的有限集合。用Σ表示。
例Σ={a,b,c} (a,b,c均为字符或符号,
是字母表中的元素)
:符号的有序序列。用小写希腊字母表示如:
ω,φ,λ
a,b,ab, abc等。
ε表示空字符串,不包含任何符号的符号串。
ε≠空格另外ab≠ba
3. 符号串集合:字母表上若干符号串的组成集合。用
大写字母表示。
例:A={a,ab,bc}
(形式语言):字母表上所有符号串组成的集合的子集,用 L表示。
L Σ*,L可抽象地看成所有句子的集合。
句子又可抽象看成是某个有限字母表Σ的符号串。
字母表上的符号串不可能都是句子。
例:Σ={a},L={a2k|k≥0}
Σ={0,1}, L1={(01)n|n≥0}={ε,01,0101,……}
L2={0n1n| n≥0}={ε,01,0011,……}
ф空集或者空语言,不含任何符号串的语言。ф≠{ε}
符号串的运算
1. 符号串相等:同一字母表的两个符号串所有
符号依次相等。
如Σ={a,b,c}
ω=abc, ψ=abc,则ω=φ;
若ω=abc, ψ=cba,则ω≠φ
2. 字符串长度:符号串中包含的字符的个数。
记|ω|
例|abc|=3,|ε|=0, |aω|=|ωa|=1+|ω|,
a∈Σ。