编译原理dfa需要什么条件

⑴ 编译原理NFA转DFA ，请问DFA的初始状态如何确定

NFA确定化的时候，包含NFA初态的那个DFA状态就是确定后的DFA的初态。

DFA的终态就是所有包含了NFA终态的DFA的状态。

对于DFA来说，他的初态就是包含了NFA唯一初态1的那个状态，就是左边的1，2右边的1了。

脱氧核糖-磷酸链在螺旋结构的外面，碱基朝向里面。两条多脱氧核苷酸链反向互补，通过碱基间的氢键形成的碱基配对相连，形成相当稳定的组合。

(1)编译原理dfa需要什么条件扩展阅读：

将DNA或RNA序列以三个核苷酸为一组的密码子转译为蛋白质的氨基酸序列，以用于蛋白质合成。密码子由mRNA上的三个核苷酸（例如ACU，CAG，UUU）的序列组成，每三个核苷酸与特定氨基酸相关。

例如，三个重复的胸腺嘧啶（UUU）编码苯丙氨酸。使用三个字母，可以拥有多达64种不同的组合。由于有64种可能的三联体和仅20种氨基酸，因此认为遗传密码是多余的（或简并的）：一些氨基酸确实可以由几种不同的三联体编码。

但每个三联体将对应于单个氨基酸。最后，有三个三联体不编码任何氨基酸，它们代表停止（或无意义）密码子，分别是UAA，UGA和UAG 。

⑵ 如题，编译原理中为什么要将NFA转化为DFA

对DFA来说，一个输入必然对应唯一的路径与结果，而这正是我们设计编译器所需要的。

如果从一个状态经过同样的一个输入可以通过两条或更多路径达到不同的状态，我们的编译器就会迷惑（不知道怎么办），只能通过穷举测试每个状态是否可行，而穷举算法的效率通常都很低下。
DFA的最简化是有固定算法的，NFA有没有我不知道，通常最简化之后的DFA要比NFA简单得多

⑶ 编译原理笔记17：自下而上语法分析（4）LR(0)、SLR(1) 分析表的构造

（移进项目就是指圆点右边是终结符的项目，规约项目指的就是圆点在右部最右端的项目）

LR(0) 文法可以直接通过识别活前缀的 DFA 来构造 LR 分析表

假定 C = {I ₀ , I ₁ , ... , I _n } （aka. LR(0) 项目规范族、DFA 状态集）

首先为文法产生式进行编号，拓广文法的产生式要标记为 0（这里就是后面分析表中 rj 的产生式编号 j 的由来）

然后令每个项目集 I _k 的下标 k 作为分析器的状态（行首），包含 S' → .S 的集合下标为分析器的初态（也就是 DFA 的初态，一般都是 0 ）。

下面用一个例子来说明 ACTION、GOTO 子表的构造：

SLR(1) 为解决冲突提出了一个简单的方法：通过识别活前缀的 DFA 和【简单向前看一个终结符】构造 SLR(1) 分析表。

如果我们的识别活前缀的 DFA 中存在移进-规约冲突、规约-规约冲突，都可以尝试使用这个方法来解决冲突。（这里说【尝试】，当然是因为 SLR 也只能解决一部分问题，并不是万能的灵丹妙药。。）

这里，我们拿前面那个 LR(0) 解决不了的文法来举例

该文法不是 LR(0) 文法，但是是 SLR(1) 文法。

观察上图 DFA 中的状态2，想象当我们的自动机正处于这个状态：次栈顶已经规约为 T 了，栈顶也是当前的状态 2 ，而当前剩余输入为 *。

如果这个自动机不会【往前多看一步】的话，那么对处于这个状态的自动机来说，看起来状态 2 中的移进项目和规约项目都是可选的。这就是移进-规约冲突。

想要解决这个冲突，就轮到【往前多看一步】上场了——把当前剩余输入考虑进来，辅助进行项目的选择：

对其他的冲突也使用同样的方法进行判断。

这种冲突性动作的解决办法叫做 SLR(1) 解决办法

准备工作部分，与 LR(0) 分析表的构造差不多：同样使用每个项目集的状态编号作为分析器的状态编号，也就同样用作行下标；同样使用拓广文法产生式作为 0 号产生式。

填表也和 LR(0) 类似，唯一的不同体现在对规约项的处理方法上：如果当前状态有项目 A → α.aβ 和 A → α. ，而次栈顶此时是 α 且读写头读到的是 a，那么当且仅当 a∈FOLLOW(A) 时，我们才会用 A → α 对 α 进行规约。

如果构造出来的表的每个入口都不含多重定义（也就是如上图中表格那样的，每个格子里面最多只有一个动作），那么该表就是该文法的 SLR(1) 表，这个文法就是 SLR(1) 文法。使用 SLR(1) 表的分析器叫做一个 SLR(1) 分析器。

任意的二义文法都不能构造出 SLR(1) 分析表

例：悬空 else

例：

这里的 L 可以理解为左值，R 可以理解为右值

经过计算可以确定其 DFA 如下图所示。

在 状态4 中，由于 "=" 同时存在于 FOLLOW(L) 与 FOLLOW(R) 中，因此该状态内存在移进-规约冲突，故该文法不是 SLR(1) 文法。

这样的非二义文法可以通过增加向前看终结符的个数来解决冲突（比如LL(2)、LR(2)）但这会让问题更加复杂，故一般不采用。而二义文法无论向前看多少个终结符都无法解决二义性。

⑷ 编译原理问题，高手进。

回答下列问题：(30分)
(6分)对于下面程序段
program test (input, output)
var i, j: integer;
procere CAL(x, y: integer);
begin
y:=y*y; x:=x-y; y:=y-x
end;
begin
i:=2; j:=3; CAL(i, j)
writeln(j)
end.
若参数传递的方法分别为(1)传值、(2)传地址，(3)传名，请写出程序执行的输出结果。
答： (1) 3 (2) 16 (3) 16 (每个值2分)

(6分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。
G(M)：
M → TB
T → Ba |
B → Db | eT |
D → d |

解答：
计算文法的FIRST和FOLLOW集合：(4分)
FIRST(M) = { a，b，e，d， } FIRST(T) = { a，b，e，d， }
FIRST(B) = {b，e，d， } FIRST(D) = {d，}
FOLLOW (M) = {#} FOLLOW (T) = { a，b，e，d，#}
FOLLOW (B) = {a，# } FOLLOW (D) = { b}

检查文法的所有产生式，我们可以得到：
1. 该文法不含左递归，
2. 该文法中每一个非终结符M，T，B，D的各个产生式的候选首符集两两不相交。
3. 该文法的非终结符T、B和D，它们都有候选式，而且
FIRST(T)∩FOLLOW(T)={ a，b，e，d }≠
所以该文法不是LL(1)文法。(2分)

(4分)考虑下面的属性文法
产 生 式 语 义 规 则
S→ABC

A→a
B→b
C→c B.u := S.u
A.u := B.v + C.v
S.v := A.v
A.v :=3*A.u
B.v := B.u
C.v := 1
画出字符串abc的语法树;
对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少。
答：(1) (2分)

(2) S.v的值为18 (2分)

(4分)运行时的DISPLAY表的内容是什么？它的作用是什么？
答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。

(5分)对下列四元式序列生成目标代码：
A:=B*C
D:=E+A
G:=B+C
H:=G*D
其中，H在基本块出口之后是活跃变量， R0和R1是可用寄存器。
答: 目标代码序列
LD R0 B
MUL R0 C
LD R1 E
ADD R1 R0
LD R0 B
ADD R0 C
MUL R0 R1
ST R0 H

(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。
答：
逆波兰式：(abcd-*+) (1分)
三元式序列: (2分)
OP ARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
抽象语法树：(2分)

(8分)构造一个DFA，它接受={a，b}上所有包含ab的字符串。
答：
(2分)构造相应的正规式：(a|b)*ab(a|b)*

(3分)
a a

a b
b b

(3分)确定化：
I
{0,1,2} {1,2,3} {1,2}
{1,2,3} {1,2,3} {1,2,4,5,6}
{1,2} {1,2,3} {1,2}
{1,2,4,5,6} {1,2,3,5,6} {1,2,5,6}
{1,2,3,5,6} {1,2,3,5,6} {1,2,4,5,6}
{1,2,5,6} {1,2,3,5,6} {1,2,5,6}
b b
b a
a a a a

a b b
b

最小化：
{0，1，2} {3，4，5}
{0， 2}，1， {3，4，5}

(6分)写一个文法使其语言为L(G)={anbncm| m,n≥1，n为奇数，m为偶数}。
答：
文法G(S):

(8分)对于文法G(S):

1. 写出句型b(Ma)b的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语和句柄。
答：
1. (4分)

2. (4分)
短语: Ma)， (Ma)， b(Ma)b
直接短语: Ma)
句柄: Ma)

(12分)对文法G(S)：
S → a | ^ | (T)
T → T，S | S
(1) 构造各非终结符的FIRSTVT和LASTVT集合;
(2) 构造算符优先表;
(3) 是算符优先文法吗?
(4) 构造优先函数。
答：
(1) (4分)

(2) (4分)
a ^ ( ) ,
a > >
^ > >
( < < < = <
) > >
, < < < > >

(3) 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。 (1分)

(4) 优先函数(3分)
a ^ ( ) ,
F 4 4 2 4 4
G 5 5 5 2 3

(8分)设某语言的do-while语句的语法形式为
S do S(1) While E
其语义解释为：

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式，将该语句翻译成四元式：
(1) 写出适合语法制导翻译的产生式；
(2) 写出每个产生式对应的语义动作。
答：(1). 适合语法制导翻译的文法(4分)
G(S):
R do
UR S(1) While
SU E
(2). (4分)
R do
{ R.QUAD:=NXQ }

UR S(1) While
{ U.QUAD:=R.QUAD;
BACKPATCH(S.CHAIN, NXQ) }

SU E
{ BACKPATCH(E.TC, U.QUAD);
S.CHAIN:=E.FC }

答案二：
(1) S do M1 S(1) While M2 E
M ε (4分)
(2) M ε { M.QUAD := NXQ } (4分)
S do M1 S(1) While M2 E
{
BACKPATCH(S(1).CHAIN, M2.QUAD);
BACKPATCH(E.TC, M1.QUAD);
S.CHAIN:=E. FC
}

(10分)将语句
while C>0 do if A B=0 then C:=C+D else C:=C*D
翻译成四元式。
答：
100 (j>， C， 0， 102)
101 (j， -， -， 112)
102 (jnz， A， -， 106)
103 (j， -， -， 104)
104 (j=， B， 0， 106)
105 (j， -， -， 109)
106 (+， C， D， T1)
107 (:=， T1， -， C)
108 (j， -， -， 100)
109 (*， C， D， T2)
110 (:=， T2， -， C)
111 (j， -， -， 100)
112

(10分)设有基本块如下：
T1:=3
T2:=A*B
T3:=9+T1
M:=A*B
T4:=C-D
L:=T3*T4
T2:=C+D
N:=T2
画出DAG图；
设L，M，N 是出基本块后的活跃变量，请给出优化后的四元式序列。
答：

1. (6分)
L

*
T2,M T4 T2,N

* - +

T1 T3
3 A B 12 C D

2. (4分)
M:=A*B
S1:=C-D
L:=12*S1
N:=C+D

(8分)文法G(S)及其LR分析表如下，请给出串baba#的分析过程。
(1) S → DbB (2) D → d (3) D → ε
(4) B → a (5) B → Bba (6) B → ε
LR分析表
ACTION GOTO
b D a # S B D
0 r3 s3 1 2
1 acc
2 s4
3 r2
4 r6 S5 r6 6
5 r4 r4
6 s7 r1
7 S8
8 r5 r5
解答：
步骤 状态 符号 输入串
0 0 # baba#
1 02 #D baba#
2 024 #Db aba#
3 0245 #Dba ba#
4 0246 #DbB ba#
5 02467 #DbBb a#
6 024678 #DbBba #
7 0246 #DbB #
8 01 #S # acc
哈哈，估计认识！！

⑸ 编译原理 有文法G（S）这道题怎么做

首先扩展文法为：

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分析表如下所示：

ActionGoto

ab# S

I0 s2s3 1

I1 acc

I2s2s3 r4 4

I3s2s3 5

I4 r2r2r2

I5 r3r3 r3

⑹ 编译原理由正规式构造DFA

先画出NFA，如图：（我就是传说当中的灵魂画师）

这个DFA本身就已经是最简的了，无法再简化，最简化过程我就直接省了

⑺ ！！编译原理DFA和NFA

DFA或NFA是对计算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1; 程序： if(a==1) b=1; 这个程序对应了一个自动机。
对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)
比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就是(1,1)。

画图出来就是 这4个状态作为顶点，并且有下面几条边
(0,0) --> (0,0)（自环）, (1,0)-->(1,1), (1,1)-->(1,1)（自环）, (0,1)-->(0,1)自环

存在的意义就是一种理论模型，也可以认为是一种编程思想。 词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。

最经典体现自动机思想的算法就是KMP算法，你肯定学过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。

⑻ 编译原理，子集法将NFA确定为DFA，求问，表格中的部分都是怎么来的

我也在看这个。
先以S开始，经过任意个ε得到的结点就是第一个I，这道题就是{X，1,2}，
然后将{X，1,2}中的每一个字符经过a（中间可以有ε）后得到的结点加起来，X的Ia={1,2}，
1的Ia={1,2}，2的Ia是空集，所以这一行的Ia={1,2}。
后面的Ib也是一样，只不过是经过b后得到的结点的集合。
然后分别将前面的Ia和Ib作为I计算新的Ia和Ib。
再将这些集合依次标号，这道题是{X，1,2}为X，{1,2}为1，{1,2,3}为2，{1,2，Y}为3，根据上面那个表就可以把图画出来了。