编译原理基础

编译原理基础

 

编译程序是现代计算机系统的基本组成部分。从功能上看，一个编译程序就是一个语言翻译程序，把一种语言书写的程序（源程序）翻译成另一种语言（目标程序）的等价的程序

 

软件，计算机系统中的程序及其文档

 

系统软件，居于计算机系统中最靠近硬件的一层，如编译系统和操作系统等

 

语言处理系统，把软件语言书写的各种程序处理成可在计算机上执行的程序。

 

软件语言：用于书写软件的语言，主要包括需求定义语言，功能性语言，设计性语言，程序

设计语言以及文档语言

 

编译逻辑过程：

  词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成

 

编译阶段的组合

  分析，综合：源程序分析（线性分析，层次分析，语义分析），目标程序的综合

  编译的前端（front end）

  编译的后端(back end)

  遍历一遍（pass）：从头到尾扫描源程序

 

什么是词法分析程序：逐个读入源程序字符并按照构词规则分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字，标识符，运算符，标点符号和常量

词法分析是编译过程中的一个阶段，在语法分析前进行，页可以和语法分析结合在一起作为一遍。由语法分析程序调用词法分析程序来获得当前单词供语法分析使用

词法分析程序的主要任务：读源程序，产生单词符号

词法分析程序的其他任务：滤掉空格，跳过注释，换行符；追踪换行表示，复制出错源程序；宏展开

 

符号串的运算：

符号串的头，尾，固有头和固有尾：z=xy，x是z的头，y是z的尾。若x非空，那么y是固有尾；同样y非空的话x是固有头  z=abc，那z的头是a,ab,abc，除abc外都是固有透；z的尾是c,bc,abc，除abc外均是固有尾。当对符号串z = xy头感兴趣对其余部分不感兴趣，可以简写z = x…;如果只是强调x在符号串z中某处出现，可以表示为z=…x…;符号t是符号串z的第一个符号，则表示为z=t…

符号串的连接：假设x,y是符号串，他们的连接xy是吧y的符号卸载x的符号后面得到的符号串

符号串的方幂：

符号串集合：集合A中所有元素都是某字母表∑上的符号串，则A为字母表上的符号串集合

两个符号串集合A和B的乘积定义为AB={xy|x∈A且y∈B}

 

正规表达式与正规集

程序设计语言中的单词是基本语法成分，单词符号的语法可以用有效的工具加以描述，并且基于这类描述，实现词法分析程序的自动构造

一些基本术语和概念：

符号：一个抽象实体，字母和数字都是符号

字母表；是元素的非空有穷集合，不同的语言可以有不同的字母表

符号串；由字母表中的符号组成的任何有穷序列陈伟符号串

符号串的长度：符号串中有多少个符号就是多长

空符号串；不包含任何符号的符号串 

正规式：也称正则表达式，是定义正规集的数学工具，我们用以描述单词符号。              

 

状态转换图：是设计词法分析器的一种好途径。转换图是一张有限方向图，结点代表状态，用圆圈表示；状态之间用箭弧连接。箭弧上标记代表在射出结点状态下可能出现的输入字符或者字符类

 

确定的有穷自动机DFA：一个确定的有穷自动机M是一个五元组M=(K,f,S,Z)其中K是一个有穷集，它的每个元素称为一个状态，∑是一个有穷字母表，它的每一个元素称为一个输入符号；f是转换函数，是在k×∑->K的映射，S∈K是唯一的一个初态；Z包含于K是一个终态集，终态页可称为接受状态或结束状态

一个DFA可以表示成一个状态图（或称状态转换图），整个图有唯一一个初态结点和若干个终态结点。

 

不确定的有穷自动机NFA

例题：写出一定条件的文法和正则表达式

 

文法和语言概述：当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了；但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。但是人们可以给出一些规则用来说明（或者定义）句子的组成结构

 

如果语言是无穷的，找出语言的有穷表示，语言的有穷表示有两个途径

生成方法（文法）：语言中的每个句子可以用严格定义的规则来构造

识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是“，若不属于，要么能停止并回答”不是“，要么永远继续下去