免费智能真题库 > 历年试卷 > 软件设计师 > 2021年上半年 软件设计师 上午试卷 综合知识
  第52题      
  知识点:   语法分析   上下文无关文法   文法   有限自动机
  章/节:   计算机软件知识       

 
设有描述简单算术表达的上下文无关文法如下,其中id表示单字母。
E→E+T|T
T→F*T|F
F→id
与使用该文法描述的表达式a+b*c*d相符的语法树为(52),
下图所示有限自动机(DFA)是(53)。

 
 
  A. 
 
  B. 
 
  C. 
 
  D.  暂无
 
 
 

 
  第20题    2015年下半年  
   33%
编译器和解释器是两种基本的高级语言处理程序。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间..
  第20题    2018年下半年  
   16%
对布尔表达式进行短路求值是指:无须对表达式中所有操作数或运算符进行计算就可确定表达式的值。对于表达式"a or ((c< d..
  第48题    2014年下半年  
   39%
对高级语言源程序进行编译的过程可以分为多个阶段,分配寄存器的工作在()阶段进行。
   知识点讲解    
   · 语法分析    · 上下文无关文法    · 文法    · 有限自动机
 
       语法分析
        语法分析的任务是根据语言的语法规则,分析单词串是否构成短语和句子,同时检查和处理程序中的语法错误。根据产生语法树的方向,语法分析可分为自底向上和自顶向下两类。
        自顶向下的分析是对给定的符号串,试图自顶向下地为其构造一棵语法树,或者说从文法的开始符号出发,为其构造一个最佳推导。
        自底向上的分析是对给定的符号串,试图自底向上地为其构造一棵语法树,或者说从给定的符号串本身出发,试图将其归约为文法的开始符号。
        算符优先文法属于自底向上的分析法,它利用各个算符间的优先关系和结合规则来进行语法分析,特别是用于分析各种表达式。算符优先文法的任何产生式的右部都会出现两个非终结符相邻的情况,且任何一对终结符之间至多只有3种算符关系,即">""<"和"="之一成立。
 
       上下文无关文法
        上下文无关文法属于乔姆斯基定义的2型文法,被广泛地用于表示各种程序设计语言的语法。对于上下文无关文法GS]=(VNVTPS),其产生式的形式都是Aβ,其中AVNβ∈(VNVT*
        若不加特别说明,下面用大写英文字母ABC等表示非终结符,小写英文字母abc等表示终结符号,uvw等表示终结符号串,小写希腊字母αβγδ等表示终结符和非终结符构成的文法符号串。由于一个上下文无关文法的核心部分是其产生式集合,所以文法可以简写为其产生式集合的描述形式。
        (1)规范推导(最右推导)。如果在推导的任何一步其中αβ是句型),都是对α中最右边的非终结符进行替换,则称这种推导为最右推导。最右推导常称为规范推导。同理可定义最左推导。
        (2)短语、直接短语和句柄。设αδβ是文法G的一个句型,即,且满足,则称δ是句型αδβ相对于非终结符A的短语。特别地,如果有,则称δ是句型αδβ相对于产生式Aδ的直接短语。一个句型的最左直接短语称为该句型的句柄。
 
       文法
        描述语言语法结构的形式规则称为文法。文法G是一个四元组,可表示为G=(VNVTPS)。其中VT是一个非空有限集,其每个元素称为一个终结符;VN是一个非空有限集,其每个元素称为非终结符。VNVT=Φ,即VNVT不含公共元素。令V=VNVT,称V为文法G的词汇表,V中的符号称为文法符号,包括终结符和非终结符。SVN,称为开始符号,它至少要在一条产生式中作为左部出现。P是产生式的有限集合,每个产生式形如“αβ”。其中,α称为产生式的左部,αV+α中至少含有一个非终结符;β称为产生式的右部,且βV*。若干个产生式αβ1αβ2,…,αβn的左部相同时,可简写为αβ1β2|…|βn,称βi(1≤in)为α的一个候选式。
        (1)文法的分类。乔姆斯基(Chomsky)把文法分成4种类型,即0型、1型、2型和3型。这4类文法之间的差别在于对产生式要施加不同的限制。若文法G=(VNVTPS)的每个产生式αβ,均有α∈(VNVT*α至少含有一个非终结符,且β∈(VNVT*,则称G为0型文法。对0型文法的每条产生式分别施加以下限制,则可得以下文法:
        .1型文法:G的任何产生式αβSε除外)均满足|α|≤|β|(|x|表示x中文法符号的个数)。
        .2型文法:G的任何产生式形如Aβ,其中AVNβ∈(VNVT*
        .3型文法:G的任何产生式形如AaAaB(或者ABa),其中ABVNaVT
        0型文法也称为短语文法,其能力相当于图灵机,任何0型语言都是递归可枚举的;反之,递归可枚举集也必定是一个0型语言。1型文法也称为上下文有关文法,它意味着对非终结符的替换必须考虑上下文,并且一般不允许替换成ε串。例如,若αAβαγβ是1型文法的产生式,αβ不全为空,则非终结符A只有在左边是α,右边是β的上下文中才能替换成γ。2型文法就是上下文无关文法,其非终结符的替换无需考虑上下文。3型文法等价于正规式,因此也被称为正规文法或线性文法。
        若文法G1与文法G2产生的语言相同,即LG1)=LG2),则称这两个文法是等价的。
        (2)句子和语言。设有文法G=(VNVTPS)。
        .推导与直接推导:推导就是从文法的开始符号S出发,反复使用产生式,将产生式左部的非终结符替换为右部的文法符号序列(展开产生式用表示),直到产生一个终结符的序列时为止。若有产生式αβP,且γδV*,则称为文法G中的一个直接推导,并称γαδ可直接推导出γβδ。显然,对P中的每一个产生式αβ都有。若在文法中存在一个直接推导序列,即,则称α0可推导出αnαnα0的一个推导,并记为。用记号表示α0=αn或者
        .直接归约和归约:归约是推导的逆过程。若文法G中有一个直接推导,则称β可直接归约成α,或αβ的一个直接归约。若文法G中有一个推导,则称δ可归约成γ,或γδ的一个归约。
        .句型和句子:若文法G的开始符号为S,那么,从开始符号S能推导出的符号串称为文法的一个句型,即α是文法G的一个句型,当且仅当有如下推导,α∈V*。若X是文法G的一个句型,且,则称X是文法G的一个句子,即仅含终结符的句型是一个句子。
        .语言:从文法G的开始符号出发,能推导出的句子的全体称为文法G产生的语言,记为LG)。
 
       有限自动机
        有限自动机是一种识别装置的抽象概念,它能准确地识别正规集。有限自动机分为两类:确定的有限自动机和不确定的有限自动机。
        (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)。
        词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号,然后构造相应有限自动机的状态转换图,最后依据状态转换图编写词法分析器(程序)。
   题号导航      2021年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第52题    在手机中做本题