免费智能真题库 > 历年试卷 > 软件设计师 > 2019年上半年 软件设计师 上午试卷 综合知识
  第48题      
  知识点:   词法分析   编译器
  关键词:   编译器   语言   编译        章/节:   计算机软件知识       

 
在以阶段划分的编译器中,( )阶段的主要作用是分析构成程序的字符及由字符按照构造规则构成的符号是否符合程序语言的规定。
 
 
  A.  词法分析
 
  B.  语法分析
 
  C.  语义分析
 
  D.  代码生成
 
 
 

 
  第21题    2010年下半年  
   23%
编译程序分析源程序的阶段依次是(21)。
  第49题    2016年下半年  
   45%
乔姆斯基(Chomsky)将文法分为4种类型,程序设计语言的大多数语法现象可用其中的(49)描述。
  第50题    2010年上半年  
   45%
对于正规式0*(10*1)*0*,其正规集中字符串的特点是(50) 。
   知识点讲解    
   · 词法分析    · 编译器
 
       词法分析
        1)正规表达式和正规集
        对于字母表∑,其上的正规表达式(也称正则表达式,简称正规式)及其表示的正规集可以递归定义如下。
        (1)ε是一个正规式,它表示集合L(ε)={ε}。
        (2)若a是∑上的字符,则a是一个正规式,它所表示的正规集为{a}。
        (3)若正规式rs分别表示正规集L(r)和L(s),则
        ①r|s是正规式,表示集合L(r)∪L(s)。
        ②r.s是正规式,表示集合L(r)L(s)。
        ③r*是正规式,表示集合(L(r))*
        ④(r)是正规式,表示集合L(r)。
        仅由有限次地使用上述3个步骤定义的表达式才是∑上的正规式,其中运算符"|"".""*"分别称为"或""连接"和"闭包"。若两个正规式表示的正规集相同,则认为两者等价。
        2)有限自动机
        有限自动机是一种识别装置的抽象概念,它能够正确地识别正规集。
        (1)确定的有限自动机。
        一个确定的有限自动机(DFA)是个五元组:(S,∑,fs0Z),其中:
        ①S是一个有限集,其每个元素称为一个状态。
        ②∑是一个有限字母表,其每个元素称为一个输入字符。
        ③f是从S×∑→S上的单值部分映像。
        ④s0S是唯一的一个开始状态。
        ⑤Z是非空的终止状态集合。
        一个DFA可以用两种直观的方式表示,即状态转换图和状态转换矩阵。状态转换图简称为转换图,它是一个有向图。DFA中的每个状态对应转换图中的一个节点,DFA中的每个转换函数对应图中的一条有向弧,若转换函数为f(A,a)=Q,则该有向弧从节点A出发,进入节点Q,字符a是弧上的标记。状态转换矩阵可以用一个二维数组M表示,矩阵元素的行下标表示状态,列下标表示输入字符,M[A,a]的值是当前状态为A、输入为a时应转换到的下一状态。在转换矩阵中,一般以第一行的行下标所对应的状态作为初态,而终态则需要特别指出。
        (2)不确定的有限自动机。
        一个不确定的有限自动机(NFA)也是一个五元组,它与确定的有限自动机的区别如下。
        ①f是从S×∑→2S上的映像。对于S中的一个给定状态及输入符号,返回一个状态的集合。
        ②有向弧上的标记可以是ε。
        显然,DFA是NFA的特例。
        实际上,对于每个NFAM,都存在一个DFAN,且L(M)=L(N)。
        对于任何两个有限自动机M1M2,如果L(M1)=L(M2),则称M1M2是等价的。
        3)NFA到DFA的转换
        设NFAN=(S,∑,f,s0Z),与之等价的DFAM=(S',∑,f',q0,Z'),用子集法将非确定的有限自动机确定化的算法步骤如下。
        (1)求出DFAM的初态q0,此时S'仅含初态q0,并且没有标记。
        (2)对于S'中尚未标记的状态qi={si1,si2,…,sim}和sij∈(j=1,2,…,m)进行下述处理。
        ①标记qi
        ②对于每个a∈∑,令T=f(si1,si2,…,sim,a),qj=ε_CLOSURE(T)。
        ③若qi尚不在S'中,则将qj作为一个未加标记的新状态添加到S',并把状态转换函数f'(qi,a)=qj添加到DFAM
        (3)重复步骤(2),直到S'中不再有未标记的状态时为止。
        (4)令Z'={q|qS'且qZ≠?}。
        注:I是NFAN的状态集合的一个子集,其中ε_CLOSURE(I)的定义如下。
        ①状态集I的ε_CLOSURE(I)是一个状态集。
        ②状态集I的所有状态属于ε_CLOSURE(I)。
        ③若sI中,那么从s出发经过任意条ε弧到达的状态s'都属于ε_CLOSURE(I)。
        从NFA转换得到的DFA不一定是最简化的,可以通过等价变换将DFA进行最小化处理。
        4)正规式与有限自动机之间的转换
        (1)对于∑上的NFAM,可以构造一个∑上的正规式R,使得L(R)=L(M)。
        构造过程分以下两步进行。
        ①在M的状态转换图中加两个节点xy
        ②按下图所示的方法逐步消去M中的除xy的所有节点。
        
        状态转换图(消去中间节点)
        (2)对于∑上的每一个正规式R,可以构造一个∑上的NFAM,使得L(M)=L(R)。
        (3)构造过程分两步进行。
        ①对于正规式R,可用如下图所示的拓广状态图表示。
        
        拓广状态图
        ②通过对正规式R进行分裂并加入新的节点,逐步把图转变成每条弧上的标记是∑上的一个字符或ε,转换规则如下图所示。
        
        状态转换图(加入新节点)
        5)词法分析器的构造
        词法分析器的构造过程如下。
        (1)用正规式描述语言中的单词构成规则。
        (2)为每个正规式构造一个NFA,用于识别正规式所表示的正规集。
        (3)将构造出的NFA转换成等价的DFA。
        (4)对DFA进行最小化处理,使其最简。
        (5)根据DFA构造词法分析器。
 
       编译器
        编译阶段要做的工作是用交叉编译或汇编工具处理源代码,产生目标文件。在嵌入式系统中,宿主机和目标机所采用的处理器芯片通常是不一样的。例如,目标机采用的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”参数可以对执行程序进行调试。
   题号导航      2019年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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题    在手机中做本题