免费智能真题库 > 历年试卷 > 嵌入式系统设计师 > 2015年下半年 嵌入式系统设计师 上午试卷 综合知识
  第19题      
  知识点:   编译器   词法分析   代码优化   目标代码生成   语法分析   语义分析   中间代码生成   高级语言   中间代码
  关键词:   编译器   词法分析   代码生成   代码优化   高级语言处理程序   解释器   语法分析   语义分析   源程序   中间代码   编译   高级语言   语言   语义        章/节:   嵌入式系统程序设计       

 
编译器和解释器是两种基本的高级语言处理程序。编译器高级语言源程序的处理过程可以划分为词法分析语法分析语义分析中间代码生成代码优化目标代码生成等阶段,其中,(19)并不是每个编译器都必需的。与编译器相比,解释器(20)。
 
 
  A.  词法分析和语法分析
 
  B.  语义分析和中间代码生成
 
  C.  中间代码生成和代码优化
 
  D.  代码优化和目标代码生成
 
 
 

 
  第50题    2015年下半年  
   44%
假设以下代码运行环境为32位系统,其中,_attribute_((packed))的作用是告诉编译器取消结构在编译过程中的优化对齐,按照实际占用..
  第41题    2013年下半年  
   54%
假定编译器规定int和short类型长度分别为32位和16位,执行下列C语言语句:

得到b的机器数为(41)。
  第33题    2015年下半年  
   44%
JTAG是用来进行嵌入式处理器调试的标准化接口,下列描述中,正确的是(33)。
 
  第18题    2019年下半年  
   62%
将编译器的工作过程划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成时,语法分析阶段的输入是(18)。..
  第18题    2019年下半年  
   62%
将编译器的工作过程划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成时,语法分析阶段的输入是(18)。..
  第22题    2017年下半年  
   64%
将高级语言源程序通过编译或解释方式进行翻译时,可以先生成与源程序等价的某种中间代码。以下关于中间代码的叙述中,正确的是(..
 
  第21题    2010年下半年  
   69%
编译程序分析源程序的阶段依次是(21)。
  第18题    2019年下半年  
   62%
将编译器的工作过程划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成时,语法分析阶段的输入是(18)。..
  第19题    2019年下半年  
   51%
将编译器的工作过程划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成时,语法分析阶段的输入是(18)。..
   知识点讲解    
   · 编译器    · 词法分析    · 代码优化    · 目标代码生成    · 语法分析    · 语义分析    · 中间代码生成    · 高级语言    · 中间代码
 
       编译器
        编译阶段要做的工作是用交叉编译或汇编工具处理源代码,产生目标文件。在嵌入式系统中,宿主机和目标机所采用的处理器芯片通常是不一样的。例如,目标机采用的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)。
               词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号,然后构造相应有限自动机的状态转换图,最后依据状态转换图编写词法分析器(程序)。
 
       代码优化
        由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的,因此,生成的中间代码往往在计算时间上和存储空间上有很大的浪费。当需要生成高效的目标代码时,就必须进行优化。优化过程可以在中间代码生成阶段进行,也可以在目标代码生成阶段进行。由于中间代码是不依赖于具体机器的,此时所作的优化一般建立在对程序的控制流和数据流分析的基础之上,与具体的机器无关。优化所依据的原则是程序的等价变换规则。例如,在生成语句X:=Y+Z*60的四元式后,60是编译时已知的常数,把它转换为60.0的工作可以在编译时完成,没有必要生成一个四元式,同时t3仅仅用来将其值传递给id1,也可以化简掉,因此上述的中间代码可优化成下面的等价代码:
        ①(*,id3,60.0,t1)
        ②(+,id2,t1,id1)
        这只是优化工作中的一个简单示例,真正的优化工作还要涉及公共子表达式的提取、循环优化等更多的内容和技术。
 
       目标代码生成
        目标代码生成是编译器工作的最后一个阶段。这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码,这个阶段的工作与具体的机器密切相关。例如,使用两个寄存器R1和R2,可对上述的四元式生成下面的目标代码:
        ①MOVFid3,R2
        ②MULF#60.0,R2
        ③MOVFid2,R1
        ④ADDFR2,R1
        ⑤MOVR1,id1
        这里用#表明60.0为常数。
 
       语法分析
        程序设计语言的语法常采用上下文无关文法描述。文法不仅规定了单词如何组成句子,而且刻画了句子的组成结构。形式文法是一个规则(或称产生式)系统,它规定了单词在句子中的位置和顺序,也描述了句子的层次结构。
        下面以一个简单算术表达式的文法为例进行说明,其中,E代表算术表达式。
        E→E+T|T(1)
        T→T*F|F(2)
        F→(E)|N(3)
        D→0|1|2|3|4|5|6|7|3|4|5|6(4)
        N→DN|D(5)
        “→”读作“定义为”,上述产生式规定简单算术表达式的运算符号为“加(+)”“乘(*)”,运算符号写在运算对象的中间,运算对象是非负整数,“乘”运算的优先级高于“加”运算,表达式或运算对象可加括号。
        有了以上文法,对于算术表达式2+3*4,其结构可从上面的文法推导得出,如下图(a)所示(分析树),简化的语法树如下图(b)所示。
        
        分析树和语法树示意图
        有关语法分析以及编译过程后续阶段的工作较为复杂,兹不赘述。
 
       语义分析
        语义分析阶段主要分析程序中各种语法结构的语义信息,包括检查源程序是否包含静态语义错误,并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能被翻译成正确的目标代码。
        语义分析的一个主要工作是进行类型分析和检查。程序设计语言中的一个数据类型一般包含两个方面的内容:类型的载体及其上的运算。例如,整除取余运算符只能对整型数据进行运算,若其运算对象中有浮点数就认为是一种类型不匹配的错误。
        在确认源程序的语法和语义之后,就可对其进行翻译,同时改变源程序的内部表示。对于声明语句,需要记录所遇到的符号的信息,因此应进行符号表的填查工作。在下图(a)所示的符号表中,每行存放一个符号的信息。第一行存放标识符X的信息,其类型为real,为它分配的逻辑地址是0;第二行存放Y的信息,其类型为real,为它分配的逻辑地址是4。对于可执行语句,则检查结构合理的语句是否有意义。对语句id1:=id2+id3*60进行语义分析后的语法树如下图(b)所示,其中增加了一个语义处理结点inttoreal,用于将一个整型数转换为浮点数。
        
        语义分析后的符号表和语法树示意图
 
       中间代码生成
        中间代码生成阶段的工作是根据语义分析的输出生成中间代码。“中间代码”是一种简单且含义明确的记号系统,可以有若干种形式,它们的共同特征是与具体的机器无关。中间代码的设计原则主要有两点:一是容易生成,二是容易被翻译成目标代码。最常用的一种中间代码是与汇编语言的指令非常相似的三地址码,其实现方式常采用四元式。四元式的形式为:
        
        例如,对语句X:=Y+Z*60,可生成以下四元式序列:
        ①(inttoreal,60,-,t1)
        ②(*,id3,t1,t2)
        ③(+,id2,t2,t3)
        ④(:=,t3,-,id1)
        其中,t1、t2、t3是编译过程中形成的临时变量,用于存放中间运算结果。
        语义分析和中间代码生成所依据的是语言的语义规则。
 
       高级语言
        不论是机器语言还是汇编语言都是面向硬件的具体操作的,语言对机器的过分依赖,要求使用者必须对硬件结构及其工作原理都十分熟悉,非计算机专业人员是难以做到的,对于计算机的推广应用是不利的。计算机事业的发展,促使人们去寻求一些与人类自然语言相接近且能为计算机所接受的语意确定、规则明确、自然直观和通用易学的计算机语言。这种与自然语言相近并为计算机所接受和执行的计算机语言称高级语言。高级语言是面向用户的语言,每一种高级(程序设计)语言,都有自己人为规定的专用符号、英文单词、语法规则和语句结构(书写格式)。高级语言与自然语言(英语)更接近,而与硬件功能相分离(彻底脱离了具体的指令系统),便于广大用户掌握和使用。高级语言的通用性强,兼容性好,便于移植。
        高级语言主要是相对于汇编语言而言,它并不是特指某一种具体的语言,而是包括了很多编程语言。它又可分为面向过程的语言和面向问题的语言,前者在编程时不仅要告诉计算机“做什么”,而且要告诉计算机“怎么做”,如Basic,Pascal, Fortran, C等高级语言。后者只要告诉计算机做什么,如Lisp,Prolog等高级语言,也常称为人工智能语言。
 
       中间代码
        从原理上讲,对源程序进行语义分析之后就可以直接生成目标代码,但由于源程序与目标代码的逻辑结构往往差别很大,特别是考虑到具体机器指令系统的特点,要使翻译一次到位很困难,而且用语法制导方式机械生成的目标代码往往是烦琐和低效的,因此有必要设计一种中间代码,将源程序首先翻译成中间代码表示形式,以利于进行与机器无关的优化处理。由于中间代码实际上也起着编译器前端和后端的分水岭作用,所以使用中间代码也有助于提高编译程序的可移植性。常用的中间代码有后缀式、四元式和树等形式。
        (1)后缀式(逆波兰式)。逆波兰式是波兰逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面,例如,把a+b写成ab+,所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算,不需要使用括号,也便于用栈实现求值。对于表达式x:=(a+b)*(c+d),其后缀式为xab+cd+*:=。
        (2)树形表示。例如,表达式x:=(a+b)*(c+d)的树形表示如下图所示。
        
        表达式的树形表示
        (3)四元式表示。四元式是一种普遍采用的中间代码形式,其组成成分为运算符OP、第一运算对象ARG1、第二运算对象ARG2和运算结果RESULT。其中,运算对象和运算结果有时指用户自定义的变量,有时指编译程序引入的临时变量,RESULT总是一个新引进的临时变量,用来存放运算结果。例如,表达式x:=(a+b)*(c+d)的四元式表示为:
        ①(+,a,b,t1)②(+,c,d,t2)③(*,t1,t2,t3)④(:=,t3,_,x)
   题号导航      2015年下半年 嵌入式系统设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第19题    在手机中做本题