免费智能真题库 > 历年试卷 > 程序员 > 2009年上半年 程序员 上午试卷 综合知识
  第31题      
  知识点:   编译程序基本原理   有限自动机
  关键词:   有限自动机   自动机        章/节:   软件基础知识       

 
下图所示的有限自动机中,SO是初始状态,S3为终止状态,该自动机不能识别(31)。


 
 
  A.  abab
 
  B.  aaaa
 
  C.  babb
 
  D.  abba
 
 
 

 
  第31题    2011年上半年  
   42%
对C/C++程序进行处理时,可先将(31),然后进行链接以形成可执行程序。
  第29题    2017年下半年  
   38%
编译和解释是实现高级程序设计语言的两种方式,其区别主要在于( )。
  第30题    2014年下半年  
   46%
以下叙述中,正确的是(30)。
   知识点讲解    
   · 编译程序基本原理    · 有限自动机
 
       编译程序基本原理
        编译程序的功能就是把用某种高级语言书写的源程序翻译成与之等价的低级语言的目标程序,如下图所示。
        
        编译程序的功能
        编译程序一般可划分为前后衔接的6个阶段:词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成,如下图所示。
        
        编译程序的结构
               词法分析阶段的主要任务
               词法分析阶段是编译过程的第一个阶段。词法分析的任务是:从左到右一个个字符地输入源程序,对构成源程序的字符串进行扫描和分解,识别出一个个的单词符号(简称单词或符号)。单词是程序设计语言的基本语法符号,如保留字(begin、end、if、for和while等)、标识符、常数、算符及界符(标点符号和左右括号等)。
               在词法分析这一阶段的工作中,所依循的是语言的构词规则。
               语法分析阶段的主要任务
               语法分析的任务是:在词法分析的基础上,根据语言的语法规则(文法规则),把单词符号串分解成各类语法单位,如"短语""子句""句子"("语句")、"程序段"和"程序"。通过语法分解,确定整个输入串是否构成一个语法上正确的"程序"。在语法分析这一阶段的工作中,所依循的是语言的语法规则。
               语义分析阶段的主要任务
               语义分析阶段主要检查源程序是否包含语义错误,并收集类型信息供后面的代码生成阶段使用,只有语法和语义都正确的源程序才能被翻译成正确的目标代码。语义分析的一个主要工作是进行类型分析和检查。程序语言中的一个数据类型一般包含两个方面的内容:类型的载体及其上的运算。
               中间代码生成阶段的主要任务
               中间代码产生的任务是根据语义分析的输出生成中间代码。中间代码是一种简单且含义明确的记号系统。中间代码设计原则有两点:一是容易生成;二是容易将它翻译成目标代码。
               代码优化阶段的主要任务
               代码优化的任务是:对前阶段产生的中间代码进行加工变换,以期在最后阶段能产生更为高效(省时间和省空间)的目标代码。优化的主要方面有:公共子表达式的提取、循环优化和算符归约等。在代码优化这一阶段的工作中,所依循的原则是程序的等价变换规则。
               目标代码生成阶段的主要任务
               目标代码生成的任务是:把中间代码(或者经优化处理之后)变换成特定机器上的绝对指令代码、可重新定位的指令代码或者汇编指令代码。这一阶段实现了最后的翻译,它的工作有赖于硬件系统结构和机器指令含义。这一阶段的工作也是最复杂的,涉及计算机硬件系统功能部件的运用,机器指令的选择,各种数据类型变量的存储空间分配,以及寄存器和后缓寄存器的调度等。
               在编译过程中,汇编源程序的各种信息被保留在各种不同的表格里,编译各阶段的工作都涉及构造、查找,或者更新有关的表格。因此,编译程序中必须含有一组管理各种表格的程序。
               如果汇编源程序有错误,编译程序应该设法发现错误,把有关信息报告给用户。这部分工作是由专门的一组出错处理程序完成的,它与编译各阶段都有联系。因此,编译程序中必须含有一组出错处理程序。
 
       有限自动机
        有限自动机是一种识别装置的抽象概念,它能准确地识别正规集。有限自动机分为两类:确定的有限自动机和不确定的有限自动机。
        (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)。
        词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号,然后构造相应有限自动机的状态转换图,最后依据状态转换图编写词法分析器(程序)。
   题号导航      2009年上半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第31题    在手机中做本题