程序设计语言基础PPT培训资料

《程序设计语言基础PPT培训资料》由会员分享，可在线阅读，更多相关《程序设计语言基础PPT培训资料（49页珍藏版）》请在金锄头文库上搜索。

1、1,第2章 程序语言基础知识 2.1 程序设计语言基础知识 2.2 编译系统基本原理 2.2.1 文法 2.2.2 文法分析 2.2.3 词法分析 2.3 C语言基础,2,2.1 程序设计语言概述 低级语言(面向机器的语言) 面向对象程序设计语言 (C+，Java， Smalltalk) 程序设计语言 逻辑程序设计语言（ Prolog ） 高级语言 函数式的语言（Lisp） 命令式程序设计语言(C，Pascal) 科学计算语言（Fortran）,3,逻辑式语言 是一类以形式逻辑为基础的语言，其代表就是建立关系理论和一阶谓词理论基础上的Prolog 。逻辑式语言有很强的推理能力。用于开发专家系统

2、、自然语言理解等。,4,函数式语言 是一类以演算为基础的语言，其基本概念来自为人工智能而设计的Lisp语言。这里所谓的函数跟数学中的函数概念是类似的。 命令式语言 命令式语言又称过程式语言，它是一种基于动作的语言，所有的计算被看成工作序列。,5,例：_语言不是面向对象的程序设计语言。 A.Java B.C+ C.Smalltalk D.Fortran,6,2.2 编译系统基本原理 2.2.1 编译原理基本知识 语言处理程序分为两个大类：翻译程序和解释程序。 翻译程序：把用某种程序设计语言书写的程序翻译成等价的机器语言。,7,常考点1：程序编译过程 一般情况，编译程序的流程如下图所示：,源程序,

3、词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成,目标程序,8,注意： 并非所有的编译程序都分成这几个处理阶段，有些编译程序并不需要生成中间代码，有些编译程序不进行代码优化，有些最简单的编译程序在语法分析的同时产生目标指令代码。,9,例（软设2008年5月上午试题20）：编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段，其中， 并不是每种编译器都必需的。 A词法分析和语法分析 B语义分析和中间代码生成 C中间代码生成和代码优化 D代码优化和目标代码生成,10,2.2 编译系统基本原理 2.2.2 文法 1文

4、法定义 文法G定义为四元组（VN，VT，P，S），其中： （1）VN为非终结符号（或语法实体，或变量）集； （2）VT为终结符号集； （3）P为产生式（也称规则）的集合； （4）S称为识别符号或开始符号，它是一个非终结符。一般约定，第一条产生式的左部是开始符号（识别符号）。 一般情况，大写字母表示非终结符； 小写字母表示终结符。,11,例：文法G=（VN，VT，P，S），其中VN=S，VT=0，1，P=S0S1，S01. 总结： 一个文法定义的语言是终结符号串的集合，这些终结符号串应能从文法的起始符号出发推导出来。,12,2*： *称为集合的闭包。*=012n. 其中，n表示 的方幂。假设是个

5、符号串，n表示把自身连接n次得到的符号串。 例如=AB，求*。 *=012n. 其中： 0= ，表示不包含任何符号的符号串，即空 符号串，其长度为0。 1=AB 2=ABAB ,13,定义：设GS是一文法，如果符号串x是从识别符号推导出来的，即有S=x，则称x是文法GS的句型。若x仅有终结符号组成，即S=x，x属于VT*，则称x为GS的句子。,14,2.2.3 文法分析 1.文法的类型 （1）0型文法 （2）1型文法或上下文有关文法 （3）2型文法或上下文无关文法,15,（1）0型文法 定义：设G=（VN，VT，P，S）为一文法，如果它的每个产生式ab是这样一种结构：a属于（VNVT）*且至少

6、含有一个非终结符，而b属于（VNVT）*，则G是一个0型文法。 对0型文法产生式的形式作某些限制，就是1型、2型、3型文法。,16,（2）1型文法或上下文有关文法 定义：设G=（VN，VT，P，S）为一文法，若P中的每一个产生式ab均满足|b|a|,仅仅S除外，则G是1型文法或上下文有关文法。,17,（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) 今后，对“文法”一词若

7、无特别说明，则均指上下文无关文法。,18,例（2007年下半年上午第50）：程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法 G=(N，T，P，S)，其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，S是开始符号。令集合V=NT，那么G所描述的语言是 的集合。 A从S出发推导出的包含V中所有符号的串 B从S出发推导出的仅包含T中符号的串 CN中所有符号组成的串 DT中所有符号组成的串,19,例（2009年上半年上午第50）：设某语言的语法规则用上下文无关文法G=(N,T,P,S)表示，其中N是非终结符号的集合，T是终结符号的集合，P 是产生式集合，S是开始符号

8、，令V=NT，那么符合该语言的句子是_。 A. 从S 出发推导的、仅包含T 中符号的符号串 B. 从N 中符号出发推导的、仅包含T 中符号的符号串 C. 从S 出发推导的、包含V 中符号的符号串 D. 从N 中符号出发推导的、包含V 中符号的符号串,20,2.上下文无关文法及其语法树（推导树） 语法树或推导树：是一种描述上下文无关文法的句型推导的直观方法。 通过语法树，可以得到文法G的句型。,21,从下面的例子说明语法树的构造。 例：G=（S，A，a，b，P，S），其中P为： （1）SaAS （2）ASbA （3）ASS （4）Sa （5）Aba 构造G的语法树。 注意：如果在推导的任何一步,

9、 都是对其中的最左（最右）非终结符进行替换，则称这种推导为最左（最右）推导。,22,例（软设2008年5月上午试题21）：已知某文法GS：S0S0 S1，从S推导出的符号串可用 (n0)描述。 A(010)n B0n10n C1n D01n0,23,例（2008年下半年上午第50）：设某上下文无关文法如下：S11 | 1001 | S0 |SS，则该文法所产生的所有二进制字符串都具有的特点是_。 A. 能被3整除 B. 0、1出现的次数相等 C. 0和1的出现次数都为偶数 D. 能被2整除,24,例（2008年下半年上午第48）：.给定文法GS及其非终结符A，FIRST(A)定义为：从A出发能

10、推导出的终结符号的集合(S是文法的起始符号，为非终结符)。对于文法GS： SL|a LL，S|S 其中，GS包含的4个终结符号分别为： a ， 则FIRST(S)的成员包括 (48) 。 Aa Ba、 Ca、和 Da、和，,25,2.2.4 词法分析 考点1：词法分析的功能 词法分析阶段的主要功能如下： （1）识别出源程序中意义独立的最小词法单位单词，并且确定其类型（例如表示符、关键字、操作符还是数字等）。 （2）删除无用的空格、回车和其它与输入介质有关的无用符号以及程序注释。 （3）报告分析时的错误。 经过词法分析后，源程序就转换为单词串。,26,例（软设2005年11月上午试题27）：编译

11、程序进行词法分析时不能_. A.过滤源程序中的注释 B.扫描源程序并识别句号 C.指出出错的行号 D.查出拼错的保留字,27,考点2：正规式和正规集 正规式和正规集 正规式：用正规表达式（简称正规式）可表示程序语言的单词 正规集：正规式表示的集合称为正规集,28,例：令=a，b,上的正规式和相应的正规集的例子有： 正规式正规集 a a a|b a,b ab ab a* ,a,aa,.任意个a的串 (a|b)(a|b) aa,ab,ba,bb.所有a,b组成的串 (a|b)* ,a,b,aa,bb,. ,29,正规文法到正规式的转换规则,表 正规文法到正规式的转换规则,30,例（2007年下半年

12、上午第48）：正则表达式1*(0|01)*表示的集合元素的特点是_. A.长度为奇数的0、1串 B.开始和结尾字符必须为1的0、1串 C.串的长度为偶数的0、1串 D.不包含字串011的0、1串,31,例（2009年上半年上午第49）：由a、b构造且仅包含偶数个a的串的集合用正规式表示为_。 A. (a*a)*b* B. (b* (ab*a)*)* C. (a* (ba*)*b)* D. (a|b)* (aa)*,32,考点3：自动机 有穷自动机分为两类： 1.确定的有穷自动机（Deterministic Finite Automata） 2.不确定的有穷自动机（Nondeterministi

13、c Finite Automata）。,33,1.确定的有穷自动机（DFA） 一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z） 其中 （1）K是一个有穷集，它的每个元素称为一个状态； （2）是一个有穷字母表，它的每个元素称为一个输入字符，所以也称为输入符号字母表； （3）f是转换函数，是在KK上的映像，即，如f(ki，a)=kj（ki属于K，kj属于K）表示当前状态为ki,输入字符在a时，将转换为下一个状态kj； （4）S属于K，S是唯一的一个初态； （5）Z包含与K，Z是一个终态集，终态也称为可接受状态或结束状态。,34,例：DFA M=（S，U，V，Q，a，b，f，S，

14、Q）其中f定义为： f（S，a）=U f（V，a）=U f（S，b）=V f（V，b）=Q f（U，a）=Q f（Q，a）=Q f（U，b）=V f（Q，b）=Q 请画出该DFA的状态转换图。,35,补充： 对于*中的任何一个串t，若存在一条从某一初态结点到某一个终态结点的道路，且这条道路上所有弧的标记符依序连接成的串等于t，则称t可为DFA M所识别（读出或接受）。 若M的初态结点同时又是终态结点，则空字可为M所识别（接受）。,36,2不确定的有穷自动机（NFA） 一个不确定的有穷自动机（NFA）M是一个五元组：M=（K，f，S，Z）其中 （1）K是一个有穷集，它的每个元素称为一个状态； （

15、2）是一个有穷字母表，它的每个元素称为一个输入字符； （3）f是转换函数，是从K*K上子集的映像； （4）S属于K，S是一个非空的初态集； （5）Z包含与K，Z是一个终态集。,37,例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，a）=4 f（1，b）=2 f（4，a）=4 f（2，a）=2 f（4，b）=4 请画出该NFA的状态转换图。,38,补充： 对于*中的任何一个串t，若存在一条从某一初态结点到某一个终态结点的道路，且这条道路上所有弧的标记符依序连接成的串等于t，则称t可为NFA M所识别（读出或接受）。,39,例2中的NFA M所能识别的是那些含有相继两个a或相继两个b的串。,40,自动机到正规式的转换过程如图所示: 对于 代之 对于 代之 对于 代之,1,2,3,R1,R2,1,3,R1 R2,1,2,1,2,3,1,2,1,3,R1| R2,R1 R2* R3,R1,R2,R1,R3,R2,41,例（2006年下半年上午第45-46）：下图是一有限自动机的状态转换图，