免费智能真题库 > 历年试卷 > 软件评测师 > 2017年下半年 软件评测师 上午试卷 综合知识
  第48题      
  知识点:   编译器   词法分析   软件体系结构   体系结构   语法分析
  关键词:   编译器   词法分析   代码生成   软件体系结构风格   语法分析   编译   软件体系结构        章/节:   软件开发方法及过程       

 
传统编译器进行词法分析语法分析、代码生成等步骤的处理时,前一阶段处理的输出是后一阶段处理的输入,则采用的软件体系结构风格是(48)。该体系结构的优点不包括(49)。
 
 
  A.  管道过滤器
 
  B.  分层
 
  C.  信息库
 
  D.  发布订阅
 
 
 

 
  第38题    2013年下半年  
   57%
在结构化分析方法中,数据流图描述数据在系统中如何被传送或变换,反映系统必须完成的逻辑功能,用于(38)建模。在绘制数据流图时..
  第38题    2016年下半年  
   43%
模块A的功能为:从数据库中读出产品信息,修改后存回数据库,然后将修改记录写到维护文件中。该模块内聚类型为(38)内聚。以下关..
  第37题    2016年下半年  
   57%
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)描述算法时,(37)不是理想的表..
   知识点讲解    
   · 编译器    · 词法分析    · 软件体系结构    · 体系结构    · 语法分析
 
       编译器
        编译阶段要做的工作是用交叉编译或汇编工具处理源代码,产生目标文件。在嵌入式系统中,宿主机和目标机所采用的处理器芯片通常是不一样的。例如,目标机采用的CPU是DragonBall M68x系列或ARM系列,而宿主机采用的是x86系列。因此,为了把宿主机上编写的高级语言程序编译成可以在目标机上运行的二进制代码,就需要用到交叉编译器。
        与普通PC中的C语言编译器不同,嵌入式系统中的C语言编译器要进行专门的优化,以提高编译效率。一般来说,优秀的嵌入式C编译器所生成的代码,其长度和执行时间仅比用汇编语言编写的代码长5%~20%。编译质量的不同,是区别嵌入式C编译器工具的重要指标。因此,硬件厂商往往会针对自己开发的处理器的特性来定制编译器,既提供对高级语言的支持,又能很好地对目标代码进行优化。
        GNU C/C++(gcc)是目前比较常用的一种交叉编译器,它支持非常多的宿主机/目标机组合。宿主机可以是Unix、AIX、Solaris、Windows、Linux等操作系统,目标机可以是x86、Power PC、MIPS、SPARC、Motorola 68K等各种类型的处理器。
        gcc是一个功能强大的工具集合,包含了预处理器、编译器、汇编器、连接器等组件。它在需要时会去调用这些组件来完成编译任务,而输入文件的类型和传递给gcc的参数决定了它将调用哪些组件。对于一般或初级的开发者,它可以提供简单的使用方式,即只给它提供C源码文件,它将完成预处理、编译、汇编、连接等所有工作,最后生成一个可执行文件。而对于中高级开发者,它提供了足够多的参数,可以让开发者全面控制代码的生成,这对于嵌入式系统软件开发来说是非常重要的。
        gcc识别的文件类型主要包括:C语言文件、C++语言文件、预处理后的C文件、预处理后的C++文件、汇编语言文件、目标文件、静态链接库、动态链接库等。以C程序为例,gcc的编译过程主要分为4个阶段:
        (1)预处理阶段,即完成宏定义和include文件展开等工作;
        (2)根据编译参数进行不同程度的优化,编译成汇编代码;
        (3)用汇编器把上一阶段生成的汇编码进一步生成目标代码;
        (4)用连接器把上一阶段生成的目标代码、其他一些相关的系统目标代码以及系统的库函数连接起来,生成最终的可执行代码。
        用户可以通过设定不同的编译参数,让gcc在编译的不同阶段停止下来,这样可以检查编译器在不同阶段的输出结果。
        在gcc的高级用法上,一般希望通过使用编译器达到两个目的:检查出源程序的错误;生成速度快、代码量小的执行程序。这可以通过设置不同的参数来实现,例如,“-Wall”参数可以发现源程序中隐藏的错误;“-O2”参数可以优化程序的执行速度和代码大小;“-g”参数可以对执行程序进行调试。
 
       词法分析
        词法分析过程的本质是对构成源程序的字符串进行分析,是一种对象为字符串的运算。语言中具有独立含义的最小语法单位是符号(单词),如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。
               字母表、字符串、字符串集合及运算
               (1)字母表∑:元素的非空有穷集合。例如,∑={ab}。
               (2)字符:字母表∑中的一个元素。例如,∑上的ab
               (3)字符串:字母表∑中字符组成的有穷序列。例如,a、ab、aaa都是∑上的字符串。
               (4)字符串的长度:字符串中的字符个数。例如,|aba|=3。
               (5)空串ε:由0个字符组成的序列。例如,|ε|=0。
               (6)连接:字符串ST的连接是指将串T接续在串S之后,表示为S·T,连接符号“·”可省略。显然,对于字母表∑上的任意字符串SS·ε=ε·S=S。
               (7)空集:用符号Φ表示。
               (8)∑*:指包括空串ε在内的∑上所有字符串的集合。例如,设∑={ab},∑*={ε,ab,aa,bb,ab,ba,aaa,…}。
               (9)字符串的方幂:把字符串α自身连接n次得到的串,称为字符串αn次方幂,记为αnα0=ε,αn=ααn-1=αn-1αn>0)。
               (10)字符串集合的运算:设AB代表字母表∑上的两个字符串集合。
               .或(合并):AB={α|αAαB}。
               .积(连接):AB={αβ|αAβB}。
               .幂:An=A·An-1=An-1·An>0),并规定A0={ε}。
               .正则闭包+:A+=A1A2A3∪…
               .闭包*:A*=A0A+。显然,∑*=∑0∪∑1∪∑2∪…
               正规表达式和正规集
               词法规则可用3型文法(正规文法)或正规表达式描述,它产生的集合是语言基本字符集∑(字母表)上的字符串的一个子集,称为正规集。
               对于字母表∑,其上的正规式(正则表达式)及其表示的正规集可以递归定义如下。
               (1)ε是一个正规式,它表示集合Lε)={ε}。
               (2)若a是∑上的字符,则a是一个正规式,它所表示的正规集为La)={a}。
               (3)若正规式rs分别表示正规集Lr)和L(s),则:
               ①r|s是正规式,表示集合Lr)∪L(s)。
               ②r·s是正规式,表示集合LrLs)。
               ③r*是正规式,表示集合(Lr))*。
               ④(r)是正规式,表示集合Lr)。
               仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。
               运算符“|”“·”“*”分别称为“或”“连接”和“闭包”。在正规式的书写中,连接运算符“·”可省略。运算符的优先级从高到低顺序排列为“*”“·”“|”。
               设∑={ab},在下表中列出了∑上的一些正规式和相应的正规集。
               
               正规式和相应的正规集
               若两个正规式表示的正规集相同,则认为二者等价。两个等价的正规式UV记为U=V。例如,b(ab)*=(ba)*b,(a|b)*=(a*b*)*。
               有限自动机
               有限自动机是一种识别装置的抽象概念,它能准确地识别正规集。有限自动机分为两类:确定的有限自动机和不确定的有限自动机。
               (1)确定的有限自动机(Deterministic Finite Automata,DFA)。一个确定的有限自动机是个五元组:(S,∑,fs0Z),其中:
               ①S是一个有限集合,它的每个元素称为一个状态。
               ②∑是一个有穷字母表,它的每个元素称为一个输入字符。
               ③fS×∑→S上的单值部分映像。fAa=Q表示当前状态为A、输入为a时,将转换到下一状态Q。称QA的一个后继状态。
               ④s0S,是唯一的一个开始状态。
               ⑤Z是非空的终止状态集合,
               一个DFA可以用两种直观的方式表示:状态转换图和状态转换矩阵。状态转换图是一个有向图,简称为转换图。DFA中的每个状态对应转换图中的一个结点;DFA中的每个转换函数对应图中的一条有向弧,若转换函数为fAa)=Q,则该有向弧从结点A出发,进入结点Q,字符a是弧上的标记。
               例如,DFAM1=({s0s1s2s3},{ab},fs0,{s3}),其中f为:
               fs0a)=s1fs0b)=s2fs1a)=s3fs1b)=s2fs2a)=s1fs2b)=s3fs3a)=s3
               与DFAM1对应的状态转换图如下图(a)所示,其中,状态s3表示的结点是终态结点。状态转换矩阵可以用一个二维数组M表示,矩阵元素M[A,a]的行下标表示状态,列下标表示输入字符,M[Aa]的值是当前状态为A、输入字符为a时,应转换到的下一状态。与DFAM1对应的状态转换矩阵如下图(b)所示。在转换矩阵中,一般以第一行的行下标对应的状态作为初态,而终态则需要特别指出。
               
               确定的有限自动机示意图
               对于∑中的任何字符串ω,若存在一条从初态结点到某一终止状态结点的路径,且这条路径上所有弧的标记符连接成的字符串等于ω,则称ω可由DFAM识别(接受或读出)。若一个DFAM的初态结点同时又是终态结点,则空字ε可由该DFA识别(或接受)。DFAM所能识别的语言LM)={ω|ω是从M的初态到终态的路径上的弧上标记所形成的串}。
               例如,对于字符串"ababaa",在上图(a)所示的状态转换图中,识别"ababaa"的路径是s0s1s2s1s2s1s3。由于从初态结点s0出发,存在到达终态结点s3的路径,因此该DFA可识别串"ababaa"。而"abab"和"baab"都不能被该DFA接受。对于字符串“abab“,从初态结点s0出发,经过路径s0s1s2s1s2,当串结束时还没有到达终态结点s3;而对于串"baab",经过路径s0s2s1s3,虽然能到达终态结点s3,但串尚未结束又不存在与下一字符"b"相匹配的状态转换。
               (2)不确定的有限自动机(Nondeterministic Finite Automata,NFA)。一个不确定的有限自动机也是一个五元组,它与确定有限自动机的区别如下。
               ①fS×∑→2s上的映像。对于S中的一个给定状态及输入符号,返回一个状态的集合。即当前状态的后继状态不一定是唯一确定的。
               ②有向弧上的标记可以是ε
               例如,已知有NFAN=({s0s1s2s3},{ab},fs0,{s3}),其中f为:
               fs0a)=s0fs0a)=s1fs0b)=s0fs1b)=s2fs2b)=s3
               与NFAM2对应的状态转换图和状态转换矩阵如下图所示。
               
               NFA的状态转换图和转换矩阵
               显然,DFA是NFA的特例。实际上,对于每个NFAM,都存在一个DFAN,L(M)=L(N)。
               词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号,然后构造相应有限自动机的状态转换图,最后依据状态转换图编写词法分析器(程序)。
 
       软件体系结构
        随着嵌入式技术的发展,特别是在后PC时代,嵌入式软件系统得到了极大的丰富和发展,形成了一个完整的软件体系。如下图所示,这个体系自底向上由3部分组成,分别是嵌入式操作系统、支撑软件和应用软件。
        
        嵌入式系统的软件体系结构
        嵌入式操作系统(Embedded Operating System, EOS)由操作系统内核、应用程序接口、设备驱动程序接口等几部分组成。嵌入式操作一般采用微内核结构。操作系统只负责进程的调度、进程间的通信、内存分配及异常与中断管理最基本的任务,其他大部分的功能则由支撑软件完成。
        嵌入式系统中的支撑软件由窗口系统、网络系统、数据库管理系统及Java虚拟机等几部分组成。对于嵌入式系统来讲,软件的开发环境大部分在通用台式计算机和工作站上运行,但从逻辑上讲,它仍然被认为是嵌入式系统支撑软件的一部分。支撑软件一般用于一些浅度嵌入的系统中,如智能手机、个人数字助理等。
        嵌入式系统中的应用软件是系统整体功能的集中体现。系统的能力总是通过应用软件表现出来的。
 
       体系结构
        RPR的体系结构如下图所示。RPR采用了双环结构,由内层的环1和外层的环0组成,每个环都是单方向传送。相邻工作站之间的跨距包含传送方向相反的两条链路。RPR支持多达255个工作站,最大环周长为2000km。
        
        RPR体系结构
 
       语法分析
        语法分析的任务是根据语言的语法规则,分析单词串是否构成短语和句子,即是否为合法的表达式、语句和程序等基本语言结构,同时检查和处理程序中的语法错误。程序设计语言的绝大多数语法规则可以采用上下文无关文法进行描述。语法分析方法有多种,根据产生语法树的方向,可分为自底向上(或自下而上)和自顶向下(或自上而下)两类。
               上下文无关文法
               上下文无关文法属于乔姆斯基定义的2型文法,被广泛地用于表示各种程序设计语言的语法。对于上下文无关文法GS]=(VNVTPS),其产生式的形式都是Aβ,其中AVNβ∈(VNVT*
               若不加特别说明,下面用大写英文字母ABC等表示非终结符,小写英文字母abc等表示终结符号,uvw等表示终结符号串,小写希腊字母αβγδ等表示终结符和非终结符构成的文法符号串。由于一个上下文无关文法的核心部分是其产生式集合,所以文法可以简写为其产生式集合的描述形式。
               (1)规范推导(最右推导)。如果在推导的任何一步其中αβ是句型),都是对α中最右边的非终结符进行替换,则称这种推导为最右推导。最右推导常称为规范推导。同理可定义最左推导。
               (2)短语、直接短语和句柄。设αδβ是文法G的一个句型,即,且满足,则称δ是句型αδβ相对于非终结符A的短语。特别地,如果有,则称δ是句型αδβ相对于产生式Aδ的直接短语。一个句型的最左直接短语称为该句型的句柄。
               自顶向下语法分析方法
               自顶向下分析法的基本思想是:对于给定的输入串ω,从文法的开始符号S出发进行最左推导,直到得到一个合法的句子或者发现一个非法结构。在推导的过程中试图用一切可能的方法,自上而下、从左到右地为输入串ω建立语法树。整个分析过程是一个试探的过程,是反复使用不同产生式谋求与输入序列匹配的过程。若输入串是给定文法的句子,则必能成功,反之必然出错。
               文法中存在下述产生式时,自顶向下分析过程中会出现下面的问题:
               (1)若文法中存在形如Aαβαδ的产生式,即A产生式中有多于一个候选项的前缀相同(称为公共左因子,简称左因子),则可能导致分析过程中的回溯处理。
               (2)若文法中存在形如A的产生式,由于采取了最左推导,可能会造成分析过程陷入死循环的情况,产生式的这种形式被称为左递归。
               因此,需要对文法进行改造,消除其中的左递归,以避免分析陷入死循环;提取左因子,以避免回溯。
               (3)递归下降分析法。递归下降分析法直接以子程序调用的方法模拟产生式产生语言的过程,其基本思想是:为每一个非终结符构造一个子程序,每个子程序的过程体按该产生式候选项分情况展开,遇到终结符即进行匹配,而遇到非终结符则调用相应的子程序。该分析法从调用文法开始符号的子程序开始,直到所有非终结符都展开为终结符并得到匹配为止。若分析过程可以达到这一步,则表明分析成功,否则表明输入串中有语法错误。递归下降分析法的优点是简单且易于构造,缺点是程序与文法直接相关,对文法的任何改变都需要在程序中进行相应的修改。
               (4)预测分析法。预测分析法是另一种自顶向下的语法分析方法,其基本模型如下图所示。
               
               预测分析模型示意图
               预测分析法的核心是预测分析表,可以用一个二维数组M表示,其元素MAa](AVNaVT∪#)存放关于A的产生式,表明当遇到输入符号为a且用A进行推导时,所应采用的产生式;若MAa]为error,则表明推导时遇到了不该出现的符号,应进行出错处理。
               例如,根据文法GE]={ETE',E'→+TE'|εTFT',T'→*FT'|εF→(E)|id|}的构造的预测分析表如下表所示。
               
               预测分析表
               预测分析法的工作过程是:初始时,将“#”和文法的开始符号依次压入栈中;在分析过程中,根据输入串中的当前输入符号a和当前的栈顶符号X进行处理。
               若X=a='#',则分析成功;若X='#'且a≠'#',则出错。
               若XVTX=a,则X退栈,并读入下一个符号a;若XVTXa,则出错。
               若XVNMXa]='Aα',则X退栈,α中的符号从右到左依次进栈(ε无须进栈);若MXa]='error',则调用出错程序进行处理。
               自底向上语法分析方法
               常用的自底向上分析方法也称移进-归约分析法,工作模型是下推自动机,如下图所示。其基本思想是对输入序列ω自左向右进行扫描,并将输入符号逐个移进一个栈中,边移进边分析,一旦栈顶符号串形成某个句型的可归约串(即句柄)时,就用某个产生式的左部非终结符来替代,这称为一步归约。重复这一过程,直至栈中只剩下文法的开始符号且输入串也被扫描完时为止,确认输入串ω是文法的句子,表明分析成功;否则,进行出错处理。
               
               移进-归约分析模型
               LR分析法是一种规范归约分析法。规范归约是规范推导(最右推导)的逆过程,下面举例说明规范归约的过程。
               LR分析法根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的k个(k≥0)符号,就可唯一确定分析器的动作是移进还是归约,以及用哪条产生式进行归约,因而也就能唯一地确定句柄。当k=1时,已能满足当前绝大多数高级语言编译程序的需求。常用的LR分析器有LR(0)、SLR(1)、LALR(1)和LR(1)。
               一个LR分析器由如下三个部分组成:
               (1)驱动器。或称驱动程序。对所有LR分析器,驱动程序都是相同的。
               (2)分析表。不同的文法具有不同的分析表。同一文法采用不同的LR分析器时,分析表也不同。分析表又可分为动作表(ACTION)和状态转换表(GOTO)两个部分,它们都可用二维数组表示。
               (3)分析栈。其包括文法符号栈和相应的状态栈。
               分析器的动作由栈顶状态和当前输入符号决定(LR(0)分析器不需向前查看输入符号),LR分析器的模型如下图所示。
               
               LR分析器模型示意图
               其中SP为栈顶指针,Si为状态,Xi为文法符号。ACTION[Sia]=Sj规定了栈顶状态为Si且遇到输入符号a时应执行的动作。状态转换表GOTO[SiX]=Sj表示当状态栈顶为Si且文法符号栈顶为X时应转向状态Sj
               LR分析器的工作过程以格局的变化来反映。格局的形式为(栈,剩余输入,动作)。分析是从某个初始格局开始的,经过一系列的格局变化,最终达到接受格局,表明分析成功;或者达到出错格局,表明发现一个语法错误。因此,开始格局的剩余输入应该是全部的输入序列,而接受格局中的剩余输入应该为空,任何其他格局或者出错格局中的剩余输入应该是全部输入序列的一个后缀。
               在LR分析过程中,改变格局的动作有以下4种:
               (1)移进(shift)。当ACTION[Sia]=Sj时,把a移进文法符号栈并转向状态Sj
               (2)归约(reduce)。当在文法符号栈顶形成句柄β时,把β归约为相应产生式Aβ的非终结符A。若β的长度为r(即|β|=r),则弹出文法符号栈顶的r个符号,然后将A压入文法符号栈中。
               (3)接受(accept)。当文法符号栈中只剩下文法的开始符号S,并且输入符号串已经结束时(当前输入符是“#”),分析成功。
               (4)报错(error)。当输入串中出现不该有的文法符号时,就报错。
               LR分析器的核心部分是分析表的构造,这里不再详述。
   题号导航      2017年下半年 软件评测师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第48题    在手机中做本题