编译原理文法判别题目

① 编译原理，求文法的问题

l1:S->aS|bX
X->bX|cY
Y->cY|ε
l2:S->MbXcY
M->aM|ε
X->bX|ε
Y->cY|ε
例:bc,abc,abbc
l3:S->MX
M->aMb|ε
X->aXb|ε
例:ab,aabbab
l4:S->1S0|X|ε
X->0X1|ε
例:100110,10,1010

② 编译原理判断题

1. B 正确
2. A 错误，不一定存在
3. B 正确
4. B 正确
5. A 错误，是后缀式
6. A 错误，只是算符文法，不一定是算符优先文法
7. B 正确
8. B 正确
9. A 错误，语义动作是附加在产生式上的，不是附加在非终结符上
10. A 错误，有些文法不能改写为LL(1)文法
11. B 正确
12. B 正确
13. B 正确
14. B 正确
15. A 错误，SLR(1),LR(1)等都是冲突解决的办法
16. B 正确
17. B 正确
18. A 错误，不是编译程序工作效率高，而是生成的目标程序运行效率高
19. B 正确

③ 编译原理题目关于判断LL(1)文法的

A 不是，因为含有左公共引子a
B 和D不是，因为含有左递归
C是，因为SELECT(S→aS) 与SELECT(S→b)的交集为空，符合LL(1)文法的定义。

④ 编译原理考试问题:已知表达式文法G(Exp)

简单起见，用E代表Exp，用T代表Term，用F代表Factor。下面是所求属性文法

（1）E→ E1 + T E.val:=E1.val+T.val /* 为了区别→两侧的E, →右侧的E用E1表示 */

（2）E→
T E.val:=T.val

（3）T→ T1 * F T.val:=T1.val*F.val

（4）T→
F T.val:=F.val

（5）F→（E） F.val:=E.val

（6）F→num F.val:=num.val

⑤ 求解编译原理的一道题:设有文法如下

首先要做这题你要知道判别文法类型
包括四个层次：

0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。
1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
2-型文法生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。
正规语言类包含于上下文无关语言类，上下文无关语言类包含于上下文相关语言类，上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系，也就是说：存在递归可枚举语言不属于上下文相关语言类，存在上下文相关语言不属于上下文无关语言类，存在上下文无关语言不属于正规语言类。

1）本题应该是--上下文无关文法

句子是产生式在推导时“仅仅有终结符”的任何一步
2）%mm%nn 是一个句子

由于下面一题的图我等级不够 不能贴图 发你邮箱

⑥ 关于LL(1)文法的编译原理题目

判断是不是LL(1)，首先看候选式的首字符有没有相同的，第二判断首字符迭代进去是否会构成左递归。
如果首字符不相同，也没用左递归就说明此文法是LL(1)
M→MaH｜H
H→(M)｜b(M)｜b
第一个产生式中存在左递归:M->MaH
第二个产生式中存在首字符相同:H->b(M) ,
H->b
怎么改呢？
对第一个产生式，消除左递归就是要变成右递归，把右边剩下的符号提到前面:
M->aHM'

M'->aHM'
对第二个产生式，提出公共因子
H->b( (M)|ε)
=>
H->bH'

H'->(M)|ε

⑦ 编译原理中，形式语言里怎么区分2型文法与3型文法

二型文法如下:
S->Ac
S->Sc
A->ab
A->aAb
三型文法如下:
S->aS
A->bA
B->cB
B->c
A->Bb
A、2型文法是上下文无关文法，表现在产生式上就是产生式的左部只有一个非终结符；3型文法从广义上讲包括左线形文法、右线形文法和正规文法 。
B、左线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最左端。
C、右线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最右端 。
D、正规文法是右线形文法的一个子集，其产生式右部只有三种情况：
1）空串
2）只有一个终结符
3）只有一个终结符后接一个非终结符
E、所有的3型文法都是2型文法。

⑧ 编译原理 文法题目

首先扩展文法为：
1) S1->S
2) S->aS
3) S->bS
4) S->a
则：
I0 = Closure({S1->.S})={S1->.S,S->.aS,S->.bS,S->.a}
go(I0,S) = Closure({S1->S.})={S1->S.} = I1
go(I0,a) = Closure({S->a.S,S->a.})={S->a.S,S->.aS,S->.bS,S->.a,S->a.} = I2
go(I0,b) = Closure({S->b.S})={S->b.S,S->.aS,S->.bS,S->.a}=I3
go(I2,S) = closure({S->aS.})={S->aS.}=I4
go(I2,a) = Closure({S->a.S,S->a.}) = I2
go(I2,b) = Closure({S->b.S}) =I3
go(I3,S) = Closure({S->bS.}) = {S->bS.} = I5
go(I3,a) = Closure({S->a.S,S->a.}) = I2
go(I3,b) = Closure({S->b.S}) = I3

由图所示，状态I2,既有归约项目(S->a.)又有移近项目(S->.aS,S->.bS,S->.a)，产生冲突。当用SRL分析法时，需向前看一步，即求出：
Follow(S) = Follow(S1) = {#}
则，Follow(S)∩{a,b} =∮
故而Action(I2,a) = s2
Action(I2,b) = s3
Action(I2,#) = r4

则构造出srl分析表如下所示：
Action Goto
a b # S
I0 s2 s3 1
I1 acc
I2 s2 s3 r4 4
I3 s2 s3 5
I4 r2 r2 r2
I5 r3 r3 r3

请采纳。

⑨ 【编译原理】构造下述文法G[S]的确定有限自动机，并给出该文法的语言的正规表达式 S->Aa|ε A->Aa|Sb|a

通过联立方程组求正规表达式：
A = Aa|Sb|a = Aa|(Aa|ε)b|a= Aa+(Aa+ε)b+a=Aa+(Aab+b)+a=Aa+Aab+b+a=A(a+ab)+(b+a)
根据方程X=Xt+r 必有X=t*r解的论断，可得A=(a+ab)*(b+a)，进而可求得：
S = Aa|ε = Aa+ε = Aa = (a+ab)*(b+a)a = (a|ab)*(b|a)a
即文法的正规表达式为： (a|ab)*(b|a)a。
注意：以上求解的过程中“|”和“+”是等价的，都表示“或”的意思，它们的相互替换是为了描述的方便。

⑩ 编译原理中的文法设计这题该怎么做，能给一下思路和答案吗

文法的设计需要考虑文法的类型和表达能力。一种可能的思路是：

• 首先，确定值为非负的5的倍数或3的李腊消倍数的数字串有什么特征，例如结尾只能是0或5或3或6或9，不能有前导0等。

• 然后，选择合适的文法类型来描述这些特征，例如正规文法、上下文无关文法等。

• 最后，根据文法类哪知型的规则，给出局宽产生式和开始符号。

一种可能的答案是：

• 使用正规文法来描述这个语言。

• 产生式如下：

• S -> 0 | 3 | 5 | 6 | 9


• S -> A0 | A3 | A5 | A6 | A9


• A -> S


• A -> AA



• 开始符号为S。