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