免费智能真题库 > 历年试卷 > 软件评测师 > 2013年下半年 软件评测师 上午试卷 综合知识
  第12题      
  知识点:   文法
  关键词:   开始符号   文法        章/节:   程序设计语言知识       

 
己知文法G:S→A0|B1,A→S1|1,B→S0|0,其中S是开始符号。从S出发可以推导出(12)。
 
 
  A.  所有由0构成的字符串
 
  B.  所有由1构成的字符串
 
  C.  某些0和1个数相等的字符串
 
  D.  所有0和1个数不同的字符串
 
 
 

 
  第15题    2016年下半年  
   46%
线性表采用单循环链表存储的主要优点是(15)。
  第45题    2020年下半年  
   71%
下面给出的四种排序算法中,在输入序列基本有序时,最有效的算法是(44),空间复杂度最高的是(45)。
  第21题    2011年下半年  
   61%
若二维数组arr[1..M, 1..N]的首地址为base,数组元素按列存储且每个元素占用K个存储单元,则元素arr[i,j]在该数组空间的地址为(..
   知识点讲解    
   · 文法
 
       文法
        描述语言语法结构的形式规则称为文法。文法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)。
   题号导航      2013年下半年 软件评测师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第12题    在手机中做本题