编译原理课件.ppt
课时分配:6学时;本章知识点(内容);编译程序首先是在单词级别上来分析和翻译源程序的。
词法分析的任务是:从左至右逐个字符地对源程序进行扫描,产生一个个单词符号,把作为字符串的源程序改造成为单词符号串的中间程序。因此,词法分析是编译的根底。执行词法分析的程序称为词法分析器,词法分析程序亦称为扫描器。;一、词法分析器功能和输出形式
功能:输入源程序,输出单词符号。
程序语言的单词符号一般分为五种:
(1)关键字〔保存字或根本字〕
(2)标识符
(3)常数〔整型、实型、布尔型、文字型等〕
(4)运算符。
(5)界符(逗号、分号、括号、/*,*/等)。;单词种别通常用整数编码。
1、标识符一般统归为一种
2、常数那么宜按类型〔整、实、布尔等〕分种
3、关键字可视其全体为一种,也可以一字一种。
4、运算符可采用一符一种的分法,但也可以把具有一定共性的运算符视为一种。
5、界符一般一符一种的分法。;如果一个种别只含有一个单词符号,那么对于这个单词符号,种别编码就完全代表它自身了。假设一个种别含有多个单词符号,那麽,对于它的每个单词符号,除了给出种别编码之外,还应给出有关单词符号的属性信息。
单词符号的属性是指单词符号的特征或特性。属性值那么是反映特性或特征的值。
【例如】对于某个标识符,常将存放它有关信息的符号表项的指针作为其属性值;对于某个常数,那么将存放它的常数表项的指针作为其属性值。;作为例子考虑下述C++代码段:
while(i=j)i--;
经词法分析器处理后,它将转换为如下的单词符号序列:
while的编码,-
(的编码,-
标识符编码,指向i的符号表项的指针〉
=的编码,-
标识符编码,指向j的符号表项的指针
),-
标识符编码,指向i的符号表项的指针
--编码,-
;的编码,-;【例如】
单词符号类别编号
标识符 1
常数 2
if 3
then 4
else 5
program 6
begin 7
end 8
+ 9
- 10
* 11;可使整个编译程序的结构更简沽、清晰和条???化。
也可以把词法分析器安排成一个子程序,每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用,词法分析器就从输人串中识别出一个单词符号,把它交给语法分析器。;二、词法分析器的设计
1、输入、预处理
词法分析器工作的第一步是输入源程序文本。输入串一般放在一个缓冲区中,这个缓冲区称输入缓冲区。词法分析器的工作可以直接在这个缓冲区中进行。但在许多情况下,把输入串预处理一下,对单词符号的识别工作将是比较方便的。
预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理,及删除注解等。我们可以设想构造一个预处理子程序,他完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字符,并将其装入词法分析器所指定的缓冲区中〔称为扫描缓冲区〕。这样分析器就可以在此缓冲区中直接进行单词符号的识别工作。;扫描缓冲区进行扫描时一般用两个指示器,一个指向当前正在识别的单词的开始位置〔指向新单词的首字符〕,另一个用于向前搜索以寻找单词的终点。
;图1词法分析器;当词法分析器调用预处理子程序处理出一串输入字符串放进扫描缓冲区之后,分析器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后,它又调用预处理程序装入新串。
;单词的描述工具-正规表达式
单词的识别系统-有穷自动机;单词是程序设计语言中的根本语法符号,正规式给出了字符串的简洁结构表示,因此通常用正规式来描述字符串的词法结构,再利用正规式与有穷自动机之间的等价性,构造出能识别符合词法结构的字符串的有穷自动机,这便是词法分析器的形式化构造方法。;
3型文法,又称右线性文法或正规文法(RegularGrammars),其表达式形如:A→aB或A→a。绝大部份程序设计语言的单词都能用正规文法来描述。;;正规表达式与正规集;
;【例】设?={0,1},那么有;设r,s,t为正规式,那么正规式服从如下的代数规那么:
r|s=s|r(或满足交换律)
r|(s|t)=(r|s)|t(或满足结合律)
r(st)=(rs)t(连接满足结合律)
r(s|t)=rs|rt(分配律)
rε=εr=r(ε是连接的恒等元素)
注意:
rs?sr