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

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

 
 
  A. 
 
  B. 
 
  C. 
 
  D.  暂无
 
 
 



   知识点讲解    
   · 有限自动机    · 文法    · 上下文无关文法
 
       有限自动机
        有限自动机是一种识别装置的抽象概念,它能准确地识别正规集。有限自动机分为两类:确定的有限自动机和不确定的有限自动机。
        (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)。
        词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号,然后构造相应有限自动机的状态转换图,最后依据状态转换图编写词法分析器(程序)。
 
       文法
        描述语言语法结构的形式规则称为文法。文法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)。
 
       上下文无关文法
        上下文无关文法属于乔姆斯基定义的2型文法,被广泛地用于表示各种程序设计语言的语法。对于上下文无关文法GS]=(VNVTPS),其产生式的形式都是Aβ,其中AVNβ∈(VNVT*
        若不加特别说明,下面用大写英文字母ABC等表示非终结符,小写英文字母abc等表示终结符号,uvw等表示终结符号串,小写希腊字母αβγδ等表示终结符和非终结符构成的文法符号串。由于一个上下文无关文法的核心部分是其产生式集合,所以文法可以简写为其产生式集合的描述形式。
        (1)规范推导(最右推导)。如果在推导的任何一步其中αβ是句型),都是对α中最右边的非终结符进行替换,则称这种推导为最右推导。最右推导常称为规范推导。同理可定义最左推导。
        (2)短语、直接短语和句柄。设αδβ是文法G的一个句型,即,且满足,则称δ是句型αδβ相对于非终结符A的短语。特别地,如果有,则称δ是句型αδβ相对于产生式Aδ的直接短语。一个句型的最左直接短语称为该句型的句柄。


 题号导航      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题