程序设计语言基础.ppt

1、2.1编程语言概述低级语言(面向机器语言)面向对象编程语言(c，Java，Smalltalk )编程语言逻辑编程语言(Prolog )高级语言函数语言(Lisp )指令性编程语言(c，Pascal 用于专家系统的开发、自然语言理解等。 函数表达式语言是基于运算的语言，其基本概念来自为人工智能而修订的Lisp语言。 这里所说的函数和数学中函数的概念相似。 指令型语言指令型语言也称为进程型语言，是基于动作的语言，所有修正算法都被视为工作序列。 例： _语言不是面向对象的编程语言。 A.Java B.C C.Smalltalk D.Fortran，2.2编译系统基本原理2.2.1编译原理基本知识语言

2、处理程序分为两类：翻译程序和解释程序。 翻译程序：把用某种编程语言编写的程序翻译成等价的机器语言。常考点1 :程序编译过程一般情况、编译程序的流程如下图所示：源程序、词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、目标程序、注意：所有编译程序示例(软件集2008年5月上午问题20 ) :编译器可以将高级语言源程序的处理过程分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段，而不需要各自的编译器。 a词法分析和语法分析b语义分析和中间代码生成c中间代码生成和代码优化d代码优化和目标代码生成，2.2编译系统基本原理2.2.2语法定义语法g定义为四组

3、(VN，VT，p，s )，其中(1)VN是非终结符(或语法实体) VT是结束符集合(3)P是产生式(也称为规则)的集合(4)S是被称为识别符号或者开始符号的非结束符。 一般来说，第一条生成式的左部是开始符号(识别符号)。 通常，大写字母表示非终结符，小写字母表示终结符。 例如语法G=(VN，VT，p，s )，其中VN=S，vt=0，1，P=S0S1，S01 .总结：在一个语法中定义的语言是终止符号串的集合。 2*: *集合的闭包。 其中，n表示的幂。 给定符号串，n表示通过将它自己连接n次而获得的符号串。 例如求出=AB、*。 其中，0=表示符号串，即，空符号串，其长度为0。 1=AB 2=A

4、BAB，定义：将GS作为语法，如果符号串x是从识别符号导出的，即如果S=x，则将x称为语法GS的句型。 在x仅由结尾符号构成的情况下，即在S=x，x属于VT*的情况下，x被称作GS的句子。 2.2.3语法分析1 .语法的类型(1)0型语法(2)1型语法或上下文相关语法(3)2型语法或上下文相关语法，(1)0型语法定义：对G=(VN，VT，p的0型语法生成式的形式有一些限制的是1型、2型、3型语法。 (2)1型语法或上下文相关语法定义：将G=(VN，VT，p，s )作为语法，p的各个生成式ab满足|b|a|，如果只除去s，则g是1型语法或上下文相关语法。(3)2型语法或上下文相关语法定义： G=

5、(VN，VT，p，s )为语法，如果p的各生成式ab为： a为非终结符，b为(VNVT)*，则该语法为2型语法例(2007年下半年上午第50 ) :程序语言的大部分语法现象可以用上下文相关语法记述。 对于一个上下文无关语法G=(N，t，p，s )，其中n是非终止符号的集合，t是终止符号的集合，p是生成式的集合，s是开始符号。 假设集合V=NT，则g描述的语言是的集合。 由字符串CN中的所有符号构成的字符串DT中的所有符号构成的字符串用上下文相关语法G=(N，t，p，s )来表示一种语言的语法规则(2009年前半部分第50 )，其中，所述字符串CN包括从as导出的v中的所有符号以及从字符串bs导

6、出的t中符号。 其中n是根据非终结符号a.s导出的、仅包含t中符号的符号串b.n中符号导出的、根据仅包含t中符号的符号串c.s导出的、包含v中符号的符号串d.n中符号导出的、包含v中符号的符号串从以下的例子说明语法树的构造。 示例： G=(S，a，a，b，p，s )，其中p是(1)saas(2)asba(3)ass(4)sa(5)。注意：如果在导出的任何步骤中要替换其中最左边(最右边)的非结尾符号，则该导出将是最左边(最右边)的非结尾符号。 另外，例子(软集2008年5月上午问题21 ) :某种语法GS:S0S0 S1是已知的，并且根据s导出的符号串可以用(n0)来描述。 A(010)n B0

7、n10n C1n D01n0，示例(2008年下半年上午第50 ) :如果某个上下文相关语法如下，则由该语法生成的所有二进制字符串所具有的特征能够被_ _ _ _ a.3除尽的b.0，1的出现次数相等的C. 0和1的出现次数例(2008年后半上午第48 ):给出的语法GS及其非终结符a，FIRST(A ) :对于被定义为从a的语法GS: SL|a LL，S|S，如果GS中包含的4个终结符分别是a的话， FIRST(S )的成员包括(48 ).aa ba，Ca，和Da，和，2.2.4词法分析测试点1 :词法分析的功能词法分析阶段的主要功能是： (1)识别源程序中含义独立的最小词法单位单词，并将其

8、类型(例如，演示、演示(3)报告分析时的错误。 经过字句分析，源程序被转换为单词列。例(软件集2005年11月上午问题27 ) :编译器进行词法分析时，将过滤_ _ _ _ _ _ _ _ _ _ _.a .源程序中的注释b，扫描源程序，识别句号c，指出错误的行号d，检测拼写错误的保留词， 测试点2 :正规式和正规集正规式和正规集正规式：能够用正规式(简称为正规式)表示程序语言的单词正规集：用正规式表示的集合称为正规集，例如：令=a，b，上面的正规式和与其对应的正规集的例子是正规式正规集aa|ba，即ab，ba，bb 由b组成的字符串(a|b)*，a，b，aa，bb，从正则语法到正则表达式的转

9、换规则，从表正则语法到正则表达式的转换规则，示例(2007年下半年上午第48 ) :正则表达式1*(0|01)*表示的集合元素的特点是： _.a .长度为奇数的0，1列b .开始和结束b * b * b.(b * a * a ) *，c.(a * b * b ) *。 1、确定的穷人机器人(DFA )一个确定的穷人机器人(DFA)M是五个组： M=(K，f，s， z )，(1)K有穷集，其中每个元素被称为一个(2)是穷字母，其中每个元素被称为输入字符，所以也被称为输入符号字母(3)f是转换函数，是KK上的映像，即f(ki，a )=kk (4)S属于k，s是唯一初始状态；(5)Z包含一组终端状态

10、，也称为容许状态或者终止状态。 例如，DFA M=(S、u、v、q、a、b、f、s、q )其中f对于定义为f(S，a)=U f(V，a)=的任意字符串t，存在从某初始状态节点到某最终状态节点的道路，该道路上的所有弧的符号依次连接当m个初始状态节点同时是最终状态节点时，空字符是m能够识别(接受)的。 2不确定的贫穷机器人(NFA )不确定的贫穷机器人(NFA)M是5个元组： M=(K，f，s，z )，(1)K是贫穷的集合，其各要素称为状态(2)是贫穷的字母，各要素称为输入文字(4)S属于k，s是一个非空的初始状态集合(5)Z包含和k，其中z是终端集合。 例2:nfam=(0、1、2、3、4、a、

11、b、f、0、2、4 )对于其中f定义为f(0，b)=4的任意字符串t，存在从某初始状态节点到某最终状态节点的道路，该道路上的所有弧的符号依次连接可以看到范例2的NFA M是包含两个连续的a或两个连续的b的串。 从自动机向正规式的变换过程，如图所示，相对于代理，为1、2、3、R1、R2、1、3、r1r2、1、2、1、2、3、1(1)A由符号a、b构成的包含偶数个a的列b由符号a、b构成，开头和末尾的符号都为a的列c由符号a、b构成的任意的列d由符号a、b构成，b的前后必须为a的列(2)a(a|b)*(aa)*的a .所识别的0、1列为0 一列中的1的数是偶数c .识别的0，一列中的0后面必定是1

12、 D .识别的0，一列中的1不连续出现的例子(2008年上半年上午第50 ) :某确定性有限自动机。 A3857 B1.2E 5 C-123.67 D0.576E10，例如(2008年上半年上午第48 ) :有限自动机(FA )可用于识别高级语言源程序中的符号(单词)，FA分为确定的有限自动机(DFA )和不确定的有限自动机ADFA D和NFA M的状态数一定相等BDFA D和NFA M能够识别的符号相同的CNFA M能够识别的正规集合是DFA D能够识别的正规集合的真子集DDFA D能够识别的正规集合是NFA M能够识别的正规集合的真子集，2.3 C语言基础常规测试点：关残奥词传递值调用：如果要使用传递值调用方法传递残奥仪表，请在执行调用函数之前将实际残奥仪表的值传递给形状残奥仪表。 调用的函数是在运行时不影响形状残奥仪表修改的值。 引用调用：如果要在引用调用中传递残奥仪表，请将实际残奥仪表地址传递给残奥仪表，然后执行所调用的函数。 在执行调用的函数时，对残奥仪表的修改将反映在相应的实际残奥仪表变