PPT《编译原理》

编译原理

第一章 编译程序概述

第二章 PL/0编译程序的实现

第三章 文法和语言

第四章 词法分析

第五章 自顶向下语法分析方法

第六章 自底向上优先分析方法

第七章 LR分析方法

第八章 语法制导翻译和中间代码生成

第九章 符号表

第一章 代码优化第一一章 代码生成 词法分析 主要任务:从左到右逐个字符地对源程序进行扫描,产生一个个单词序列,用以语法分析.

词法分析的基本思路:将单词符号的语法用有效的工具描述;

基于该描述建立单词的识别机制;

设计和实现词法分析程序 词法分析是编译过程的第一个阶段. 单词的描述技术正规文法正规式单词的识别机制确定有穷自动机不确定有穷自动机词法分析程序的自动构造原理正规式和有穷自动机的等价性词法分析程序的自动构造工具 单词的描述工具 某种程序设计语言中的所有单词构成一种语言.该语言的语法都能用正规文法表示.正规文法是描述单词的一种工具.

1、正规文法(回顾) 文法G=(VN,VT,P,S),P中每一规则有A→aB或A→a ,A,B?VN,a?VT*,称G(S)是正规文法. →l|l → l|d|l| d → d|dl表示a-z中的任何英文字母,d表示0-9中的任何数字由正规文法产生的语言称为正规集

2、正规式(正则表达式)是表示正规集的工具,也是用以描述单词符号的方便工具. 正规式与正规集的定义: 设字母表为Σ,辅助字母表Σ'

={?,?,?和?都是Σ上的正规式,表示的正规集分别为{?}和?;

任何a?Σ,a是Σ上的一个正规式,表示的正规集为{a};

假定e1和e2都是Σ上的正规式,它们所表示的正规集分别为L(e1)和L(e2),则(e1),e1|e2,e1・e2和e1*也都是正规式,所表示的正规集分别为L(e1),L(e1)∪L(e2), L(e1)L(e2)和(L(e1))*. 仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式,仅由这些正规式所表示的集合才是Σ上的正规集. 例: ?={a,b}, ?上的正规式和相应的正规集为: ??ab-a)一个正规式可以表示若干个符号串,(b)其正规集就是这些符号串的集合a|baba*b*a|b)*a*|b*aba*(a|b)*(aa|bb) (a|b)* ? {?}? ?a {a}b {b}a) {a}一个正规式可以表示若干个符号串,(b) {b}其正规集就是这些符号串的集合a|b {a,b}ab {ab}a* {?,a,aa,aaa,aaaa,….}b* {?,b,bb,bbb,bbbb,a|b)* a和b组成的所有串a*|b* {?,a,aa,aaa,aaaa,….,b,bb,bbb,bbbb,….}aba* 以ab开头后接若干个(包括0个)a组成的串(a|b)*(aa|bb) (a|b)* ?*上所有含有两个相继的a或两个相继的b组成的串 例:令?={d,? ,e,+,-},则?上的正规式d*(.dd*| ?)(e(+|-|?)dd*|?)表示的是所有无符号数. 其中d为0~9中的数字. 比如:2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的元素. 设r,s,t为正规式,正规式服从代数规律有:

1、r|s=s|r 交换律

2、r|(s|t)=(r|s)|t 结合律

3、(rs)t=r(st) 结合律 4. r(s|t) = rs|rt 分配律 (s|t)r = sr|tr 分配律5. ?r=r 零一律 r?=r 零一律 程序设计语言中的单词既能用正规文法表示,又能用正规式来表示. 正规文法: →l|l → l|d|l| d → d|dl表示a-z中的任何英文字母,d表示0-9中的任何数字 正规式? 4. r(s|t) = rs|rt 分配律 (s|t)r = sr|tr 分配律5. ?r=r 零一律 r?=r 零一律 程序设计语言中的单词既能用正规文法表示,又能用正规式来表示. 正规文法: →l|l → l|d|l| d → d|dl表示a-z中的任何英文字母,d表示0-9中的任何数字 正规式:标识符:e1=字母(字母|数字)* 无符号整数:e2=dd*