资源描述：
《【精品】程序分析技术.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第一讲：程序语言的发展过程任务：以程序为对象，分析其属性，如：值的获収与传播，活跃性应用：程序转换程序理解程序演化程序逆向工程程序验证与测试程序优化重构自动并行化发展：机器语言：指令：二进制纽•成具有基本操作，左移、右移、加1缺点：可读性差（可理解性差）写程序困难（不方便）问题：程序的维护比较困难扩展纠错预防适应汇编语言：符号化了的机器语言功能没有扩充可读性强高级程序设计语言：（1）过程（PASCAL,C,FORTRAN,PL1）特点：命令为基础，程序由一系列语句组成,语句的执行引起存储单元值的变化。程序的止确型（归纳断言指导…）数学性质弱（副作用，变
2、量值变化）数据类型不够丰富程序的动静态结构差异大Goto语言的争议（难以理解，难以查错,动静态差异大修改引起的副作用小，全局优化简单概念简单，效率高）（2）函数式语言（LISP,ML,HOPE,FP）程序山一如函数组成，通过调用执行程序。特点：数学性质好数据类型可自定义支持并行计算抽象级别高数据以表为基础⑶逻辑式语言（PROLOG）以谓词为基础，具有推理能力特定的应用领域抽象的问题求解公式处理专家系统人工智能等（4）对象式语言SmallTalkSO特点：封装性继承性多态性代语言：特定领域的特殊类语言高级语言的抽象如：Oracle应用开发环境、Power
3、Builder••程序分析方法：静态分析方法：（词法分析语法分析所需要的分析）动态分析方法第二讲：编译原理基础基本概念：•字母表：E,元素的非空有穷集合。•符号串：山字母农中的符号纽成的任何有穷序列。或者如下定义：1.空符号串£是》上的符号串2.若x是工上的符号串,a是》的元素，则xa是力上的符号串3.y是工上的符号串，当且仅当它可以山1和2导出•符号串的连接：设x和y均是字母表工上的符号串，它们的连接是把y的所有符号顺序接在x的符号之后所得到的符号串。•符号串的方幕：设x是字母表工上的符号串，把x自身连接n次得到的符号串z,称作符号串x的n次幕,记作
4、z=（幕形式），特别地：x0=8•前缀和后缀：设X是字母表上的符号串，x=yz,则y是X的询缀，Z是x的后缀，特别是当zHe时，y是x的真询缀；yH£时，Z是x的真后缀。•子字符串：非空字符串x,删去它的前缀和后缀后所得到的字符串称为x的子字符串，简称子串。如果删去的前缀和后缀不同吋为£，则称该子串为真子串。•符号串集合：若集合A中的所有元素都是某字母农上的符号串，则称A为该字母表上的符号串集合。•符号串集合的乘积：设A、B是两个符号串集合，AB表示A与B的乘积，则定义AB={xyl(xeA)A(yeB)}•符号串集合的方幕：设A是符号串集合，则称A，
5、是符号串集合A的方幕，其中i是非负整数。A°={e},A1=A,A2=AA,…,A11=AA…A・符号串集合的正闭包：A+=A1UA2UA3…・符号串集合的星闭包：A*=AOUA1UA2UA3…2正则表达式・定义：RE为定义在工上的止则表达式则-A,£ere-若aFE,则aWRE一若el,e2eRE,则el・e2,elle2,eP£RE•语义函数(解释函数)LL(A)=^,L(£)={e}一若aE则L(a)={a}一若el,e2ERE则L(el・e2)=L(e1)•L(e2)L(e1Ie2)=L(e1)UL(e2)L(el+)=L+(el)Eg:ab*
6、表示所有以字母a开头的后而跟了n个(包括)0个b的字符串a(alb)^示所有以a开头的字符串3自动机定义：一个DFA是一个5元纽(S,=6S°,F),其中S是状态集合，刀是字符集,§是转换函数(转移函数)SxE-S,So为初始状态SoeS,F为终止状态集合，FCSo两种表示形式(转换图转换矩阵)Eg:确定有限状态自动机M=({a,b),{S,U,V,Q},f,S,{Q}),其中f定义为:f(S,a)=Uf(S,b)=Vf(U,a)=Qf(U,b)=V词法分析:SuVQaUQUQbVVQQf(V,a)=Uf(V,b)=Qf(Q,a)=Qf(Q,b)=Q功
7、能：读源程序的字符序列，逐个拼出讥词,并构造相应的内部表示，同吋检查源程序中的词法错误。单词：所谓单词是指语言中具有独立含义的最小的语义单位。Token：单词的内部表示。''程序语言的操作对彖(只能)是该语言规定的务种数据。”编译程序是用某种程序语言书写的程序，其操作对象是-•般程序中的各种语法单位。单词的一种分类：识别常数的自动机文法概述定义文法G定义为四元组(VtMSP)Vt是有限的终极符集合Vn是有限的非终极符集合S是开始符，SgVnP是产生式的集合，且具有下面的形式：aOp,英中a,Pg(VTUVn)*分类・O型文法：也称为短语文法，其产生式具
8、有形式：a—卩，其中a,Pg(VTuVN)*,并且a至少含一个非终极符。•1型文法：也称为上下
