程序设计语言基础ppt课件

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

2、以演算为根底的言语，其根本概念来自为人工智能而设计的Lisp言语。这里所谓的函数跟数学中的函数概念是类似的。命令式言语 命令式言语又称过程式言语，它是一种基于动作的言语，一切的计算被看成任务序列。 例：_言语不是面向对象的程序设计言语。A.JavaB.C+C.SmalltalkD.Fortran2.2 编译系统根本原理2.2.1 编译原理根本知识 言语处置程序分为两个大类：翻译程序和解释程序。翻译程序：把用某种程序设计言语书写的程序翻译成等价的机器言语。 常考点常考点1：程序编译过程：程序编译过程普通情况，编译程序的流程如以下图所示：普通情况，编译程序的流程如以下图所示：源程序源程序词法分析词

3、法分析语法分析语法分析语义分析语义分析中间代码生成中间代码生成代码优化代码优化目的代码生成目的代码生成目的程序目的程序 留意： 并非一切的编译程序都分成这几个处置阶段，有些编译程序并不需求生成中间代码，有些编译程序不进展代码优化，有些最简单的编译程序在语法分析的同时产生目的指令代码。 例软设2019年5月上午试题20：编译器对高级言语源程序的处置过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目的代码生成等几个阶段，其中， 并不是每种编译器都必需的。 A词法分析和语法分析 B语义分析和中间代码生成 C中间代码生成和代码优化 D代码优化和目的代码生成2.2 编译系统根本原理2

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

5、例如=AB，求*。 *=012n. 其中： 0= ，表示不包含任何符号的符号串，即空 符号串，其长度为0。 1=AB 2=ABAB 定义：设GS是一文法，假设符号串x是从识别符号推导出来的，即有S=x，那么称x是文法GS的句型。假设x仅有终结符号组成，即S=x，x属于VT*，那么称x为GS的句子。2.2.3 文法分析文法分析1.文法的类型文法的类型10型文法型文法21型文法或上下文有关文法型文法或上下文有关文法32型文法或上下文无关文法型文法或上下文无关文法10型文法定义：设G=VN，VT，P，S为一文法，假设它的每个产生式ab是这样一种构造：a属于VNVT*且至少含有一个非终结符，而b属于V

6、NVT*，那么G是一个0型文法。 对0型文法产生式的方式作某些限制，就是1型、2型、3型文法。21型文法或上下文有关文法定义：设G=VN，VT，P，S为一文法，假设P中的每一个产生式ab均满足|b|a|,仅仅S除外，那么G是1型文法或上下文有关文法。32型文法或上下文无关文法定义：设G=VN，VT，P，S为一文法，假设P中的每一个产生式ab满足：a是一非终结符，b属于VNVT*，那么此文法为2型文法或上下文无关文法。例：文法G=E，+，*，i，(，)，P，E其中P为： Ei EE+E EE*E E(E)今后，对“文法一词假设无特别阐明，那么均指上下文无关文法。 例2019年下半年上午第50：程

7、序文语的大多数语法景象可用上下文无关文法描画。对于一个上下文无关文法 G=(N，T，P，S)，其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，S是开场符号。令集合V=NT，那么G所描画的言语是 的集合。 A从S出发推导出的包含V中一切符号的串 B从S出发推导出的仅包含T中符号的串 CN中一切符号组成的串 DT中一切符号组成的串 例2021年上半年上午第50：设某言语的语法规那么用上下文无关文法G=(N,T,P,S)表示，其中N是非终结符号的集合，T是终结符号的集合，P 是产生式集合，S是开场符号，令V=NT，那么符合该言语的句子是_。 A. 从S 出发推导的、仅包含T 中符号的符

8、号串 B. 从N 中符号出发推导的、仅包含T 中符号的符号串 C. 从S 出发推导的、包含V 中符号的符号串 D. 从N 中符号出发推导的、包含V 中符号的符号串 2.上下文无关文法及其语法树推导树语法树或推导树：是一种描画上下文无关文法的句型推导的直观方法。经过语法树，可以得到文法G的句型。 从下面的例子阐明语法树的构造。 例：G=S，A，a，b，P，S，其中P为： 1SaAS 2ASbA 3ASS 4Sa 5Aba 构造G的语法树。 留意：假设在推导的任何一步, 都是对其中的最左最右非终结符进展交换，那么称这种推导为最左最右推导。 例软设2019年5月上午试题21：知某文法GS：S0S0

9、S1，从S推导出的符号串可用 (n0)描画。 A(010)n B0n10n C1n D01n0 例2019年下半年上午第50：设某上下文无关文法如下：S11 | 1001 | S0 |SS，那么该文法所产生的一切二进制字符串都具有的特点是_。 A. 能被3整除 B. 0、1出现的次数相等 C. 0和1的出现次数都为偶数 D. 能被2整除 例2019年下半年上午第48：.给定文法GS及其非终结符A，FIRST(A)定义为：从A出发能推导出的终结符号的集合(S是文法的起始符号，为非终结符)。对于文法GS： SL|a LL，S|S 其中，GS包含的4个终结符号分别为： a ， 那么FIRST(S)的

10、成员包括 (48) 。 Aa Ba、 Ca、和 Da、和，2.2.4 词法分析词法分析考点考点1：词法分析的功能：词法分析的功能词法分析阶段的主要功能如下：词法分析阶段的主要功能如下：1识别出源程序中意义独立的最小词法识别出源程序中意义独立的最小词法单位单位单词，并且确定其类型例如表单词，并且确定其类型例如表示符、关键字、操作符还是数字等。示符、关键字、操作符还是数字等。2删除无用的空格、回车和其它与输入删除无用的空格、回车和其它与输入介质有关的无用符号以及程序注释。介质有关的无用符号以及程序注释。3报告分析时的错误。报告分析时的错误。 经过词法分析后，源程序就转换为单词串。经过词法分析后，源

11、程序就转换为单词串。 例软设2019年11月上午试题27：编译程序进展词法分析时不能_. A.过滤源程序中的注释 B.扫描源程序并识别句号 C.指出出错的行号 D.查出拼错的保管字考点考点2：正规式和正规集：正规式和正规集正规式和正规集正规式和正规集正规式：用正规表达式简称正规式可正规式：用正规表达式简称正规式可表示程序文语的单词表示程序文语的单词正规集：正规式表示的集合称为正规集正规集：正规式表示的集合称为正规集 例：令=a，b,上的正规式和相应的正规集的例子有： 正规式正规集 a a a|b a,b ab ab a* ,a,aa,.恣意个a的串 (a|b)(a|b) aa,ab,ba,bb

12、.一切a,b组成的串 (a|b)* ,a,b,aa,bb,. 正规文法到正规式的转换规那么 文法产生式 正规式 规则一AxB ByA=xy规则二AxA|yA=x*y规则三Ax AyA=x|y 表 正规文法到正规式的转换规那么 例2019年下半年上午第48：正那么表达式1*(0|01)*表示的集合元素的特点是_. A.长度为奇数的0、1串 B.开场和结尾字符必需为1的0、1串 C.串的长度为偶数的0、1串 D.不包含字串011的0、1串 例2021年上半年上午第49：由a、b构造且仅包含偶数个a的串的集合用正规式表示为_。 A. (a*a)*b* B. (b* (ab*a)*)* C. (a*

13、(ba*)*b)* D. (a|b)* (aa)*考点考点3：自动机：自动机有穷自动机分为两类：有穷自动机分为两类：1.确定的有穷自动机确定的有穷自动机Deterministic Finite Automata2.不确定的有穷自动机不确定的有穷自动机Nondeterministic Finite Automata。1.确定的有穷自动机DFA一个确定的有穷自动机DFAM是一个五元组：M=K，f，S，Z 其中1K是一个有穷集，它的每个元素称为一个形状；2是一个有穷字母表，它的每个元素称为一个输入字符，所以也称为输入符号字母表；3f是转换函数，是在KK上的映像，即，如f(ki，a)=kjki属于K，

14、kj属于K表示当前形状为ki,输入字符在a时，将转换为下一个形状kj；4S属于K，S是独一的一个初态；5Z包含与K，Z是一个终态集，终态也称为可接受形状或终了形状。 例：DFA M=S，U，V，Q，a，b，f，S，Q其中f定义为： fS，a=U fV，a=U fS，b=V fV，b=Q fU，a=Q fQ，a=Q fU，b=V fQ，b=Q 请画出该DFA的形状转换图。补充： 对于*中的任何一个串t，假设存在一条从某一初态结点到某一个终态结点的道路，且这条道路上一切弧的标志符依序衔接成的串等于t，那么称t可为DFA M所识别读出或接受。 假设M的初态结点同时又是终态结点，那么空字可为M所识别接

15、受。2不确定的有穷自动机NFA一个不确定的有穷自动机NFAM是一个五元组：M=K，f，S，Z其中1K是一个有穷集，它的每个元素称为一个形状；2是一个有穷字母表，它的每个元素称为一个输入字符；3f是转换函数，是从K*K上子集的映像； 4S属于K，S是一个非空的初态集；5Z包含与K，Z是一个终态集。 例2：一个NFA M=0，1，2，3，4，a，b，f，0，2，4其中f定义为： f0，a=0，3 f2，b=2 f0，b=0，1 f3，a=4 f1，b=2 f4，a=4 f2，a=2 f4，b=4 请画出该NFA的形状转换图。补充： 对于*中的任何一个串t，假设存在一条从某一初态结点到某一个终态结点

16、的道路，且这条道路上一切弧的标志符依序衔接成的串等于t，那么称t可为NFA M所识别读出或接受。 例2中的NFA M所能识别的是那些含有相继两个a或相继两个b的串。 自动机到正规式的转换过程如下图: 对于 代之 对于 代之 对于 代之123R1R213R1 R2121231213R1| R2R 1 R 2 * R3R1R2R1R3R2 例2019年下半年上午第45-46：以下图是一有限自动机的形状转换图，该自动机所识别言语的特点是 1 ，等价的正规式为 2 。 1A由符号a、b构成且包含偶数个a的串 B由符号a、b构成且开头和结尾符号都为a的串 C由符号a、b构成的恣意串 D由符号a、b构成且

17、b的前后必需为a的串 2A(a|b)*(aa)* Ba(a|b)*a C(a|b)* Da(ba)*a 例2021年上半年上午第48：以下图所示有限自动机的特点是_ 。 A. 识别的0、1串是以0开头且以1结尾 B. 识别的0、1串中1的数目为偶数 C. 识别的0、1串中0后面必需是1 D. 识别的0、1串中1不能延续出现 例2019年上半年上午第50：某确定性有限自动机(DFA)的形状转换图如以下图所示，令d=0129，那么以下字符串中，能被该DFA接受的是_。 A3857 B1.2E+5 C-123.67 D0.576E10 例2019年上半年上午第48：有限自动机(FA)可用于识别高级言

18、语源程序中的记号(单词)，FA可分为确定的有限自动机(DFA)和不确定的有限自动机(NFA)。假设某DFA D与某NFA M等价，那么_。 ADFA D与NFA M的形状数一定相等 BDFA D与NFA M可识别的记号一样 CNFA M能识别的正规集是DFA D所识别正规集的真子集 DDFA D能识别的正规集是NFA M所识别正规集的真子集2.3 C言语根底常考点：参数传送方式参数传送有两种方式：传值方式和传援用方式。 传值调用： 以传值调用方式进展参数传送时，是将实参的值传送给形参，然后执行被调用的函数，被调用的函数执行时对形参的修正不影响实参的值。 援用调用： 以援用调用方式进展参数传送时，是将实参的地址传送给形参，然后执行被调用的函数，被调用的函数执行时对形参的修正将反映在对应实参变量中。 例：函数f()、g()的定义如下所示，调用函数f时传送给形参a的值为1。假设采用传值call by value的方式调用g(c)，那么函数f的前往值为_(1)_；假设采用传援用call by reference