程序设计语言基础.ppt

1、2.1程序设计语言概述：低级语言(面向机器的语言)、面向对象的程序设计语言(c、Java、Smalltalk)、逻辑程序设计语言(Prolog)、高级语言、函数式语言(Lisp)、命令式程序设计语言(c、Pascal)、科学计算语言(Fortran)，逻辑语言是一种基于形式逻辑的语言，其代表是建立关系理论，一种逻辑语言具有很强的推理能力。用于开发专家系统和自然语言理解。函数语言是一种基于微积分的语言，它的基本概念来自为人工智能设计的Lisp语言。这里所谓的函数类似于数学中的函数概念。命令语言命令语言，也称为过程语言，是一种基于动作的语言，所有的计算都被视为工作序列。_ _ _ _语言不是面向对

2、象的编程语言。A.Java编译系统基础知识编译原理语言处理程序分为两类：翻译和口译。翻译程序：将用某种编程语言编写的程序翻译成等效的机器语言。常见测试点1:程序编译过程的概况，编译器的流程如下图所示：源程序，词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成，目标程序，注意：不是所有的编译器都分为这些处理阶段，有些编译器不需要生成中间代码，有些编译器不优化代码，还有一些是5月20号早上最考试， 2008:编译器对高级语言源程序的处理可分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成，其中并非每个编译器都是必需的。 a词法分析和语法分析b语义分析和中间代码生

3、成c中间代码生成和代码优化d代码优化和目标代码生成，2.2编译系统的基本原则2.2.2语法1语法定义语法g被定义为四元组(VN，VT，p，s)，其中：(1)VN是一组非终结符号(或语法实体，或变量)；(2)VT是最终的符号集；(3)P是一组生产公式(也称为规则)；(4)S被称为标识符或开始符号，它是非终止符。一般认为，第一个产品的左边部分是开始符号(识别符号)。一般来说，大写字母表示非终结符；小写字母代表终止符。例如：语法G=(VN，VT，P，S)，其中VN=S，vt=0，1，P=S0S1，S01。概要：语法定义的语言是一组终端符号串，它可以从语法的起始符号中派生出来。2 *: *称为集合的闭

4、包。*=012n.其中n是幂的幂。假设它是一个符号串，n代表一个符号串，通过n次连接得到。例如=AB，查找*。*=012n.其中：0=表示不包含任何符号的符号字符串，即长度为0的空符号字符串。1=AB 2=ABAB、定义：让GS成为一种语法。如果符号串X源自识别符号，即S=x，那么X是语法GS的句型。如果x只由最后一个符号组成，也就是说，S=x，x属于VT*，那么x就叫做gs的句子。语法分析1。语法类型(1)类型0语法(2)类型1语法或上下文相关语法(3)类型2语法或上下文无关语法，(1)类型0语法的定义：如果G=(VN，VT，p，s)的每个生成形式ab都是属于(VNVT)*的结构，则让G=(

5、VN，VT，p，s)成为一个语法。对类型0语法的生成形式有一些限制，即类型1、类型2和类型3语法。(2)类型1语法或语境相关语法的定义：让G=(VN，VT，P，S)成为一种语法。如果除了S，P中的每个生产ab都满足|b|a|，那么G就是类型1语法或上下文相关语法。(3)类型2语法或上下文无关语法的定义：让G=(VN，VT，P，S)成为一种语法。如果P中的每个生产ab满足A是非终止符，B属于(VNVT)*，则语法是类型2语法或上下文无关语法。例如：语法G=(E，* I，(，)，P，E)其中P是：Ei EE E EE * E E E(E(E)在将来，除非另有说明，“语法”一词是指上下文无关的语法。

6、编程语言中的大多数语法现象都可以用上下文无关的语法来描述。对于上下文无关的语法，G=(N，T，P，S)，其中N是一组非终结符号，T是一组终结符号，P是一个生产集，S是一个开始符号。设V=NT，那么g所描述的语言就是。从S派生的字符串，包含v b中的所有符号从S派生的字符串，仅包含T中的符号，由DT中的所有符号组成的字符串，例如(2009年上半年的第50个上午):让一种语言的语法规则用上下文无关语法G=(N，T，P，S)来表示，其中N是一组非终结符号，T是一组终结符号，P是一组生产符号。a .从s派生并仅包含t b中符号的符号串，从n派生并仅包含t c中符号的符号串，从s派生并包含v d中符号的

7、符号串，从n派生并包含v 2中符号的符号串。上下文无关语法及其语法树(派生树)语法树或派生树：描述上下文无关语法的句型派生是一种直观的方法。通过语法树，你可以得到语法g的句型。例如：G=(S，A，A，B，P，S)，其中P是：(1)SaAS (2)ASbA (3)ASS (4)Sa (5)Aba构造G的语法树。注意：如果在任何推导步骤中最左边(最右边)的非终止符被替换，这种推导称为最左边(最右边)的推导。示例(2008年5月21日上午的测试):语法GS:s0s 1是已知的，并且从S导出的符号串可以用(n0)来描述。A(010)n B0n10n C1n D01n0，例如(2008年下半年上午50时

8、):如果一个上下文无关的语法如下：S11 | 1001 | S0 |SS，那么由此语法生成的所有二进制字符串都具有_ _ _ _ _ _ _ _ _。可被3整除。B. 0和1出现的次数相同。C. 0和1出现的次数是偶数。d .可被2整除，例如(2008年下半年上午第48天):给定语法GS和它的非终结符A，FIRST(A)被定义为可以从A (s是语法的起始符号，它是非终结符)导出的一组终结符。关于语法GS: SL|a LL，S|S，其中包含在GS中的最后四个符号是：a，FIRST(S)的成员包括(48)。词汇分析测试站点1:词汇分析的功能词汇分析阶段的主要功能如下：(1)识别源程序中具有独立意义

9、的最小词汇单位词，并确定它们的类型(如符号、关键字、运算符或数字等)。)。(2)删除无用的空格、回车符、其他与输入媒体和程序注释相关的无用符号。(3)报告分析中的错误。经过词法分析，源程序被转换成字符串。示例(2005年11月27日上午的测试):编译器不能_ _ _ _ _ _ _ _ _ _ _ _ _ _。a .过滤源程序中的注释b .扫描源程序并识别句号c .指出错误的行号d .找出拼错的保留字，测试点2:正规表达式和正规集合正规表达式和正规集合正规表达式可以用来表示程序语言的词正规集合：正规表达式所表示的集合称为正规集合，例如，正规表达式和对应正规集合的例子有：任意一个的字符串。Ab，

10、ba，bb。由a和b (a | b) *、a、b、aa、bb、从正常语法到正常形式的转换规则，示例(2007年下半年上午第48期):用正则表达式1*(0|01)*表示的集合元素的特征为_ _ _ _ _ _ _ _。长度为奇数的0和1字符串；长度为偶数的0和1字符串；长度为偶数的0和1字符串；长度为奇数的0和1字符串；长度为奇数的0和1字符串；长度为偶数的1字符串；长度为奇数的0和1字符串；长度为偶数的1字符串；长度为偶数的1字符串；长度为奇数的0和1字符串；长度为奇数的1字符串；长度为奇数的1A .(A * A)* B * B .(B *(AB * A)*)* c .(A *(BA *)*

11、B)* d .(A | B)*(AA)*，测试点3:自动机有限自动机分为两类：1 .确定有限自动机(测试点1。确定性有限自动机确定性有限自动机M是一个五元组：M=(K，f，s，z)，其中(1)K是一个有限集合，其中的每个元素称为一个状态；(2)它是一个有限的字母表，每个元素被称为一个输入字符，所以它也被称为一个输入符号字母表；(3)f是一个转换函数，即KK上的图像，即如果f(ki，a)=kj(ki属于k，kj属于k)，则表示当前状态为ki，当输入字符处于A时，将转换到下一个状态kj；(4)硫属于钾，硫是唯一的初始状态；(5)Z包含K，Z是最终状态集，也称为可接受状态或结束状态。例如：DFA M

12、=(S，U，V，Q，A，B，F，S，Q)，其中F定义为：f(S，a)=U f(S，b)=V f(V，b)=Q f(U，A)，补充：对于任意字符串t in *，如果有一条从某个初始节点到某个最终节点的道路，并且该道路上所有弧线的标记所形成的字符串等于T， 如果M的初始节点也是最终节点，则空字可以被M识别(接受)。2不确定有限自动机(NFA)不确定有限自动机(NFA)M是一个五元组：M=(K，f，s，z)，其中(1)K是一个有限集合，其每个元素称为一个状态； (2)它是一个有限的字母表，每个元素被称为一个输入字符；(3)f是一个变换函数，它是K*K的一个子集的图像；(4)S属于K，S是非空初始状态

13、集；(5)Z包含K，Z是最终集合。例2:NFA M=(0，1，2，3，4，a，b，f，0，2，4)，其中f定义为：f(0，a)=0，3 f(2，b)=2 f(0，b)=0，1 f(3，补充：对于任意字符串T in *，如果有一条从某个初始节点到某个最终节点的道路，并且该道路上所有按顺序连接的弧的标记形成的字符串等于T， 据说T可以被NFA M识别(阅读或接受)。例2中的NFA M可以识别包含两个连续A或两个连续B的字符串。从自动机到范式的转换过程如图所示。被1、2、3、R1、R2、1、3、R1R2、1、2、1、2、3、1、2、1、3、R1 | R2、R1R2 * R3、取代。(1)由符号A和b

14、组成的串，由符号A和b组成的偶数个串b，由符号A和b在开始和结束处组成的串c，由符号A和b组成的任何串d，以及在b之前和之后的串必须是(2) a (a | b) * (aa) * ba (a | b) * a c (a | b) A。b .所识别的0和1字符串中的1的数量是偶数。0后面必须跟1 d。在识别的0和1字符串中，1不能连续出现。例如(2008年上半年的第50个上午):确定性有限自动机(Df a)的状态转移图如下图所示，让d=011 A 3857 B 1.2E 5 C-123.67D 0.576 E 10，例如(2008年上半年的第48个上午):有限自动机(FA)可用于识别高级语言源程

15、序中的标记(单词)，FA可分为确定性有限自动机(d FA)和不确定性有限自动机(NFA)如果DFA D相当于NFA M，那么_ _ _ _。ADFA和NFA拥有相同数量的州。BDFAD和NFAM可以认出相同的标记。CNFA M所识别的正规集是DFA D所识别的正规集的适当子集，DDFA D所识别的正规集是NFA M所识别的正规集的适当子集。参数传递有两种方式：值传递和引用传递。按值调用：当通过按值调用的方式传递参数时，实际参数的值被传递给形式参数，然后被调用的函数被执行。执行被调用函数时，形式参数的修改不影响实际参数的值。引用调用：当参数通过引用调用传递时，实际参数的地址被传递给参数，然后被调