程序设计语言基础

第2章程序语言基础知识2.1程序设计语言基础知识2.2编译系统基本原理2.2.1文法2.2.2文法分析2.2.3词法分析2.3C语言基础2.1程序设计语言概述低级语言(面向机器的语言)面向对象程序设计语言(C++，Java，Smalltalk)程序设计语言逻辑程序设计语言（Prolog）高级语言函数式的语言（Lisp）命令式程序设计语言(C，Pascal)科学计算语言（Fortran）•逻辑式语言是一类以形式逻辑为基础的语言，其代表就是建立关系理论和一阶谓词理论基础上的Prolog。逻辑式语言有很强的推理能力。用于开发专家系统、自然语言理解等。•函数式语言是一类以演算为基础的语言，其基本概念来自为人工智能而设计的Lisp语言。这里所谓的函数跟数学中的函数概念是类似的。•命令式语言命令式语言又称过程式语言，它是一种基于动作的语言，所有的计算被看成工作序列。例：____语言不是面向对象的程序设计语言。A.JavaB.C++C.SmalltalkD.Fortran2.2编译系统基本原理2.2.1编译原理基本知识•语言处理程序分为两个大类：翻译程序和解释程序。•翻译程序：把用某种程序设计语言书写的程序翻译成等价的机器语言。常考点1：程序编译过程一般情况，编译程序的流程如下图所示：源程序词法分析语法分析语义分析中间代码生成代码优化目标代码生成目标程序•注意：并非所有的编译程序都分成这几个处理阶段，有些编译程序并不需要生成中间代码，有些编译程序不进行代码优化，有些最简单的编译程序在语法分析的同时产生目标指令代码。•例（软设2008年5月上午试题20）：编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段，其中，并不是每种编译器都必需的。A．词法分析和语法分析B．语义分析和中间代码生成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={S—0S1，S—01}.总结：一个文法定义的语言是终结符号串的集合，这些终结符号串应能从文法的起始符号出发推导出来。2．∑*：•∑*称为集合∑的闭包。∑*=∑0∪∑1∪∑2∪…∑n∪...其中，∑n表示∑的方幂。假设∑是个符号串，∑n表示把∑自身连接n次得到的符号串。•例如∑=AB，求∑*。∑*=∑0∪∑1∪∑2∪…∑n∪...其中：∑0=，表示不包含任何符号的符号串，即空符号串，其长度为0。∑1=AB∑2=ABAB……•定义：设G[S]是一文法，如果符号串x是从识别符号推导出来的，即有S=x，则称x是文法G[S]的句型。若x仅有终结符号组成，即S=x，x属于VT*，则称x为G[S]的句子。2.2.3文法分析1.文法的类型（1）0型文法（2）1型文法或上下文有关文法（3）2型文法或上下文无关文法（1）0型文法•定义：设G=（VN，VT，P，S）为一文法，如果它的每个产生式a—b是这样一种结构：a属于（VN∪VT）*且至少含有一个非终结符，而b属于（VN∪VT）*，则G是一个0型文法。•对0型文法产生式的形式作某些限制，就是1型、2型、3型文法。（2）1型文法或上下文有关文法•定义：设G=（VN，VT，P，S）为一文法，若P中的每一个产生式a—b均满足|b|≥|a|,仅仅S—除外，则G是1型文法或上下文有关文法。（3）2型文法或上下文无关文法•定义：设G=（VN，VT，P，S）为一文法，若P中的每一个产生式a—b满足：a是一非终结符，b属于（VN∪VT）*，则此文法为2型文法或上下文无关文法。•例：文法G=（{E}，{+，*，i，(，)}，P，E）其中P为：E—iE—E+EE—E*EE—(E)•今后，对“文法”一词若无特别说明，则均指上下文无关文法。•例（2007年下半年上午第50）：程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法G=(N，T，P，S)，其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，S是开始符号。令集合V=N∪T，那么G所描述的语言是的集合。A．从S出发推导出的包含V中所有符号的串B．从S出发推导出的仅包含T中符号的串C．N中所有符号组成的串D．T中所有符号组成的串•例（2009年上半年上午第50）：设某语言的语法规则用上下文无关文法G=(N,T,P,S)表示，其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，S是开始符号，令V=N∪T，那么符合该语言的句子是________。A.从S出发推导的、仅包含T中符号的符号串B.从N中符号出发推导的、仅包含T中符号的符号串C.从S出发推导的、包含V中符号的符号串D.从N中符号出发推导的、包含V中符号的符号串2.上下文无关文法及其语法树（推导树）•语法树或推导树：是一种描述上下文无关文法的句型推导的直观方法。•通过语法树，可以得到文法G的句型。•从下面的例子说明语法树的构造。例：G=（{S，A}，{a，b，}，P，S），其中P为：（1）S—aAS（2）A—SbA（3）A—SS（4）S—a（5）A—ba构造G的语法树。注意：如果在推导的任何一步,都是对其中的最左（最右）非终结符进行替换，则称这种推导为最左（最右）推导。•例（软设2008年5月上午试题21）：已知某文法G[S]：S→0S0S→1，从S推导出的符号串可用(n≥0)描述。A．(010)nB．0n10nC．1nD．01n0•例（2008年下半年上午第50）：设某上下文无关文法如下：S→11|1001|S0|SS，则该文法所产生的所有二进制字符串都具有的特点是_______。A.能被3整除B.0、1出现的次数相等C.0和1的出现次数都为偶数D.能被2整除•例（2008年下半年上午第48）：.给定文法G[S]及其非终结符A，FIRST(A)定义为：从A出发能推导出的终结符号的集合(S是文法的起始符号，为非终结符)。对于文法G[S]：S→[L]|aL→L，S|S其中，G[S]包含的4个终结符号分别为：a，[]则FIRST(S)的成员包括(48)。A．aB．a、[C．a、[和]D．a、[、]和，2.2.4词法分析考点1：词法分析的功能词法分析阶段的主要功能如下：（1）识别出源程序中意义独立的最小词法单位——单词，并且确定其类型（例如表示符、关键字、操作符还是数字等）。（2）删除无用的空格、回车和其它与输入介质有关的无用符号以及程序注释。（3）报告分析时的错误。经过词法分析后，源程序就转换为单词串。•例（软设2005年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….所有a,b组成的串}(a|b)*｛,a,b,aa,bb,…..｝②正规文法到正规式的转换规则文法产生式正规式规则一A—xBB—yA=xy规则二A—xA|yA=x*y规则三A—xA—yA=x|y表正规文法到正规式的转换规则•例（2007年下半年上午第48）：正则表达式1*(0|01)*表示的集合元素的特点是________.A.长度为奇数的0、1串B.开始和结尾字符必须为1的0、1串C.串的长度为偶数的0、1串D.不包含字串011的0、1串•例（2009年上半年上午第49）：由a、b构造且仅包含偶数个a的串的集合用正规式表示为__________。A.(a*a)*b*B.(b*(ab*a)*)*C.(a*(ba*)*b)*D.(a|b)*(aa)*考点3：自动机有穷自动机分为两类：1.确定的有穷自动机（DeterministicFiniteAutomata）2.不确定的有穷自动机（NondeterministicFiniteAutomata）。1.确定的有穷自动机（DFA）•一个确定的有穷自动机（DFA）M是一个五元组：M=（K，∑，f，S，Z）其中（1）K是一个有穷集，它的每个元素称为一个状态；（2）∑是一个有穷字母表，它的每个元素称为一个输入字符，所以也称∑为输入符号字母表；（3）f是转换函数，是在K×∑—K上的映像，即，如f(ki，a)=kj（ki属于K，kj属于K）表示当前状态为ki,输入字符在a时，将转换为下一个状态kj；（4）S属于K，S是唯一的一个初态；（5）Z包含与K，Z是一个终态集，终态也称为可接受状态或结束状态。•例：DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q•请画出该DFA的状态转换图。补充：对于∑*中的任何一个串t，若存在一条从某一初态结点到某一个终态结点的道路，且这条道路上所有弧的标记符依序连接成的串等于t，则称t可为DFAM所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字可为M所识别（接受）。2．不确定的有穷自动机（NFA）•一个不确定的有穷自动机（NFA）M是一个五元组：M=（K，∑，f，S，Z）其中（1）K是一个有穷集，它的每个元素称为一个状态；（2）∑是一个有穷字母表，它的每个元素称为一个输入字符；（3）f是转换函数，是从K×∑*—K上子集的映像；（4）S属于K，S是一个非空的初态集；（5）Z包含与K，Z是一个终态集。•例2：一个NFAM=（{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的状态转换图。补充：对于∑*中的任何一个串t，若存在一条从某一初态结点到某一个终态结点的道路，且这条道路上所有弧的标记符依序连接成的串等于t，则称t可为NFAM所识别（读出或接受）。•例2中的NFAM所能识别的是那些含有相继两个a或相继两个b的串。•自动机到正规式的转换过程如图所示:对于代之对于代之对于代之123R1R213R1R2121231213R1|R2R1R2*R3R1R2R1R3R2•例（2006年下半年上午第45-46）：下图是一有限自动机的状态转换图，该自动机所识别语言的特点是（1），等价的正规式为（2）。（1）A．由符号a、b构成且包含偶数个a的串B．由符号a、b构成且开头和结尾符号都为a的串C．由符号a、b构成的任意串D．由符号a、b构成且b的前后必须为a的串（2）A．(a|b)*(aa)*B．a(a|b)*aC．(a|b)*D．a(ba)*a•例（2009年上半年上午第48）：下图所示有限自动机的特点是________。A.识别的0、1串是以0开头且以1结尾B.识别的0、1串中1的数目为偶数C.识别的0、1串中0后面必须是1D.识别的0、1串中1不能连续出现•例（2008年上半年上午第50）：某确定性有限自动机(DFA)的状态转换图如下图所示，令d=0｜1｜2｜…｜9，则以下字符串中，能被该DFA接受的是________。A．3857B．1.2E+5C．-123.67D．0.576E10例（2008