内容发布更新时间 : 2024/12/23 9:48:38星期一 下面是文章的全部内容请认真阅读。
64. 有限状态自动机能识别(C)
A.上下文无关语言
B.上下文有关语言
C.正规语言
D.0型文法定义的语言
65. 已知文法G是无二义的,则对G的任意句型α(A)
A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能相同 C.最左推导和最右推导必定相同
D.可能存在两个不同的最左推导,但他们对应的语法树相同 66. (B)不是DFA的成分
A.有穷字母表
B.多个初始状态的集合
C.多个终态的集合
D.转换函数
67. 与逆波兰式(后缀表达式)ab+c*d+对应的中缀表达式是(B)
A. a+b+c*d
B. (a+b)* c+d
C. (a+b)* (c+d)
D. a+b*c+d
68. 后缀式abc?+?d+可用表达式(B)来表示。
A.(? (a+b)?c)+d
B.?(a+(b?c))+d
C.? (a?(b+c))+d
D.(a?(?b+c))+d
69. 表达式A*(B-C*(C/D))的后缀式为(B)。
A.ABC-CD/**
B.ABCCD/*-*
C.ABC-*CD/*
D.以上都不对
70. (D)不是NFA的成分。
A. 有穷字母表 二、 问答
1. 将文法G[S] 改写为等价的G′[S],使G′[S]不含左递归和左公共因子。 G[S]: S→bSAe | bA A→Ab | d 答:
文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为: S→bB B→SAe | A
B. 初始状态集合
C. 终止状态集合
D. 有限状态集合
A→d A'
A' →bA' | ε
2. 将文法G[S] 改写为等价的G'[S],使G'[S]不含左递归和左公共因子。 G[S]: S→SAe|Ae A→dAbA|dA|d 答:
文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为: S →AeS' S' →AeS'|ε A →dA' A' →AB|ε B →bA |ε
3. 将文法G[S] 改写为等价的G'[S],使G'[S]不含左递归和左公共因子。 G[S]: S→[A A→B]|AS B→aB|a 答:
文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为: S →[A A →B]A′ A′→SA′|ε B →aB′
B′→B|ε
4. 判断下面文法是否为LL(1)文法,若是,请构造相应的LL(1)分析表。 S→aH H→aMd | d M→Ab | ε A→aM | e 答:
首先计算文法的 FIRST集和FOLLOW集如下表。
文法的 FIRST集和FOLLOW集
非终结符 S H M A FIRST集 {a}......... {a ,d}..... {a ,e ,ε} {a ,e}..... FOLLOW集 {# }... {# }... {d ,b} {b}.... 由于predict(H→aMd)∩predict(H→d)={a}∩{d }= predict(M→Ab)∩predict(M→ε)={a ,e}∩{d ,b }= predict(A→aM)∩predict(A→e)={ a }∩{ e }= 所以该文法是LL(1)文法,LL(1)分析表如下表。
S H M A a →aH. →aMd →Ab. →aM. d →d. →ε b →ε e →Ab →e. # 5. 判断下面文法是否为LL(1)文法,若是,请构造相应的LL(1)分析表。 S→aD D→STe|ε T→bH|H H→d|ε 答:
首先计算文法的 FIRST集和FOLLOW集如下表。
非终结符 S D T H {a} {a,ε} {b,d,ε} {d,ε} FIRST集 FOLLOW集 {#,b,d,e}. {#,b,d,e } {e} {e} 由于predict(D→STe)∩predict(D→ε)={a}∩{# ,b ,d ,e }= predict(T→bH)∩predict(T→H)={b}∩{e }= predict(H→d)∩predict(H→ε)={ d }∩{ e }= 所以该文法是LL(1)文法,LL(1)分析表如下表:
S D T H a →aD. →STe e →ε →H. →ε b →ε →bH d →ε →H. →d. # →ε 6. 判断下面文法是否为LL(1)文法,若是,请构造相应的LL(1)分析表。 S→aD D→STe|ε T→bM M→bH H→M|ε 答:
文法的 FIRST集和FOLLOW集
非终结符 S D T M H FIRST集 {a}..... {a ,ε} {b}..... {b}..... {b ,ε} FOLLOW集 {# ,b} {# ,b} {e}.... {e}.... {e}.... 由于predict(D→STe)∩predict(D→ε)={a}∩{# ,b}= predict(H→M)∩predict(H→ε)={ b }∩{ e }= 所以该文法是LL(1)文法,LL(1)分析表如下表:
a e b # S D T M H →aD. →STe →ε →ε →bM →bH →M. →ε 7. 某语言的拓广文法G′为: (0) S′→S (1) S → Db|B (2) D → d|ε (3) B → Ba|ε
证明G不是LR(0)文法而是SLR(1)文法,请给出SLR(1)分析表。 答:
拓广文法G',增加产生式S'→S 在项目集I0中: 有移进项目D →·d 归约项目D →·和B →·
存在移进-归约和归约-归约冲突,所以G不是LR(0)文法。
若产生式排序为: (0) S'→S (1) S → Db (2) S → B (3) D → d (4) D →ε (5) B → Ba (6) B →ε
G′的LR(0)项目集族及识别活前缀的DFA如下图: