编译原理lr0状态转换图

1. 编译原理中，LR(0)文法的项目集规范族的I0,I1,I2,I3…………是怎么求的～

先举个例子：

}

将其命名为I1。

其他可类似推出。

2. LR分析法的LR(0)分析表的构造

顾名思义，LR(0)分析就是LR(K)分析当K=0的情况，亦即在分析的每一步，只要根据当前的栈顶状态 (或者说根据当前分析栈中已移进或归约出的全部文法符号)就能确定应采取何种分析动作，而无须向前查看输入符号。
为了给出构造LR分析表的算法，我们首先需要引入一些非常重要的概念和术语。 由例4?6对输入串“a,b,a”的分析过程容易看出，如果所分析的输入串没有语法错误，则在分析的每一步，若将分析栈中已移进和归约出的全部文法符号与余留的输入符号串拼接起来，就形成了所给文法的一个规范句型。换言之，也就是在分析的每一步，如输入串已被扫视的部分无语法错误，则当前分析栈中的全部文法符号应当是某一规范句型的前缀。而且还不难看出，此种规范句型的前缀决不会含有句柄右边的任何符号，这是因为一旦句型的句柄在栈的顶部形成，将会立即被归约之故。以后，我们将把规范句型具有上述性质 (即不含句柄之右的任何符号)的前缀称为它的活前缀。例如，对于文法G[L]的规范句型“E,b,a” (见表412分析过程第5步)，其句柄为“b”，栈中的符号串为“E，b”，此句型的活前缀为ε，“E”，“E，”，“E,b”等。
由此可见，一个LR分析器的工作过程，实质上也就是一个逐步产生 (或识别)所给文法的规范句型之活前缀的过程。同时，在分析的每一步，分析栈中的全部文法符号 (如果输入串无语法错误)应是当前规范句型的活前缀，并且与此时的栈顶状态相关联。因此，我们自然会想到，如果能构造一个识别所给文法的所有活前缀的有限自动机，那么就能很方便地构造出相应的LR分析表来。稍后我们将讨论这一问题。 上面我们已经说过，在一个规范句型的活前缀中决不含有句柄右边的任何符号。因此，活前缀与句柄的关系不外下述三种情况：
(1) 其中已含有句柄的全部符号 (句柄的最右符号即为活前缀的最右符号)；
(2) 其中只含句柄的一部分符号 (句柄开头的若干符号与活前缀最右的若干个符号一致)；
(3) 其中全然不含有句柄的任何符号。
第一种情况表明，此时某一产生式A→β的右部符号串β已出现在栈顶，因此相应的分析动作应是用此产生式进行归约。第二种情况意味着形如A→β1β2的产生式的右部子串β1已出现于栈顶，正期待着从余留输入串中看到能由β2推出的符号串。而第三种情况则意味着期望从余留输入串中能看到由某一产生式A→α的右部，即α所推出的符号串。为了刻画在分析过程中，文法的一个产生式右部符号串已有多大一部分被识别，我们可在该产生式的右部的某处加上一个圆点“·”来指示位置。例如，对于上述三种情况，标有圆点的产生式分别为A→β·，A→β1·β2以及A→·α。我们把右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。特别，对形如A→ε的产生式，相应的LR(0)项目为A→·。显然，不同的LR(0)项目反映了分析过程中栈顶的不同情况。下面我们就会看到，文法的全部LR(0)项目，将是构造识别其全部活前缀的有限自动机的基础。 在作出文法的全部LR(0)项目之后，现在用它们来构造识别全部活前缀的DFA。这种DFA的每一个状态由若干个LK(0)项目所组成的集合 (称为项目集)来表示。下面以例4?7所给出的文法为例来说明构造此种DFA的方法。
首先，我们用I0表示这个DFA的初态，它预示着分析过程的开始，并且期待着将给定的输入符号串逐步归约为文法的开始符号S′。或者反过来说，我们所期待的是，从使用产生式S′→S开始，能够逐步推导出所给的输入符号串。因此，我们应将项目S′→·S列入状态I0中。换言之，也就是我们期待着将要扫视的输入串正好就是能由S推出的任何终结符号串。然而，由于不能从输入串中直接读出非终结符号S，因此我们也应当把项目S→·A以及S→·B列入到I0中。由于A和B同样是非终结符号，所以又应当将A→·aAb，A→·c和B→·aBb，B→·d列入I0中。由于最后列入I0的项目中，圆点之后都是终结符号，故I0已经“封闭”，构造项目集I0宣告结束。这样，表示初态的项目集I0由如下的项目组成：
I0: S′→·SS→·AA→·aAb
S→·BB→·aBbB→·d
A→·c
我们将项目S′→·S称为项目集I0的基本项目。上述从项目S′→·S出发构造项目集I0的过程，可用一个对其基本项目集{S′→·S}的闭包运算，即CLOSURE({S′→·S})来表示。一般地，设I为一项目集，则构造I的闭包CLOSURE(I)的算法如下：
(1) I中每一项目都属于CLOSURE(I)；
(2) 若形如A→α·Xβ的项目属于CLOSURE(I)，且X为非终结符号，则文法中任何X产生式的一切圆点在最左边的项目X→·γ也都属于CLOSURE(I)；
(3) 重复上述过程，直至不再有新的项目加入CLOSURE(I)为止。
有了初态I0之后，我们来说明如何确定从I0可能转移到的下一个状态。设X为一个文法符号 (终结符号或非终结符号)，若I0中有圆点位于X左边的项目A→α·Xβ (其中α可以为ε)，则当分析器从输入串识别出 (即移进或归约出)文法符号X后，分析器将进入它的下一个状态。设此状态为Ii，显然Ii中必含有全部形如A→αX·β的项目，我们将这样的项目称为A→α·Xβ的后继项目。对于每一文法符号X，如果存在这样的后继项目，则可能不止一个，设其组成的集合为J,J中的每个项目也就是项目集Ii的基本项目。因此，按照与上面构造项目集I0相类似的讨论，我们就有
Ii=CLOSURE(J)
为了指明Ii是“I0关于文法符号X的后继状态”这一事实，我们可定义一个状态转移函数
GO(I,X)=CLOSURE(J)
其中，I为当前状态，X为文法符号，J为I中所有形如A→α·Xβ的项目的后继项目所组成的集合，而CLOSURE(J)就是项目集I (即状态I)关于X的后继项目集 (即后继状态)。例如，对于上例，我们有：
I1=GO(I0,S)=CLOSURE({S′→S·})={S′→S·}
I2=GO(I0,A)=CLOSURE({S→A·})={S→A·}
I3=GO(I0,B)=CLOSURE({S→B·})={S→B·}
I4=GO(I0,a)=CLOSURE({A→a·Ab,B→a·Bb})=
{A→a·Ab, B→a·Bb, A→·aAb, B→·aBb, A→·c, B→·d}
I5=GO(I0,c)=CLOSURE({A→c·})={A→c·}
I6=GO(I0,d)=CLOSURE({B→d·})={B→d·}
请注意，由于I0中无圆点在b之前的项目，故GO(I0,b)无定义。这样，我们求出了I0的全部后继项目集I1,I2,I3,I4,I5,I6。容易看出，由于I1,I2,I3,I5,I6诸项目集中的项目均无后继项目，因此它们都没有后继状态。对于项目集I4，我们再仿此求出它的后继状态，这些后继状态是：
I7=GO(I4,A)=CLOSURE({A→aA·b})={A→aA·b}
I9=GO(I4,B)=CLOSURE({B→aB·b})={B→aB·b}
此外，由于
GO(I4,a)=I4GO(I4,c)=I5GO(I4,d)=I6
故它们均不产生新的项目集。最后，再求出I7,I9的后继项目集。它们分别是
I8=GO(I7,b)=CLOSURE({A→aAb·})={A→aAb·}
I10=GO(I9,b)=CLOSURE({B→aBb·})={B→aBb·}
由于I8和I10已无后继项目集，所以至此我们已求出所给文法G[S]的全部项目集I0~I10，通常，我们将这些项目集的全体称为文法G[S]的LR(0)项目集规范族，并记为
C={I0,I1,I2,I3,…,I10}
于是，我们所要构造的识别文法G[S]全部活前缀的DFA为
M=(C,V,GO,I0,C)
其中： M的状态集也就是文法的LR(0)项目集规范族C={I0,I1,…,I10}；
M的字母表也就是文法的字汇表V={S′，S，A，B，a,b,c,d}；
M的映像也就是如上定义的状态转换函数GO；
M的终态集也是C，这表明M的每一状态都是它的终态。
对于上述文法G[S]，如上构造的识别其全部活前缀的DFA的状态转换图如图416所示。
由于状态转换图416中的每一个状态都是终态，因此在上述DFA工作的过程中，从初态I0出发，沿着有向边所指示的方向前进，可以使DFA在所经历的任何状态上中止它的工作。当DFA到达某一状态时，我们把从初态I0出发，到达该状态所经过的全部有向边上的标记符号依次连接起来，就得到了DFA在到达该状态时，所识别出的某规范句型的一个活前缀。例如：当上述DFA处于初态I0时，它所识别的活前缀为ε；当M处于状态I3时，它所识别的活前缀为B；当M处于I4时，它所识别的活前缀为aa*；而达到I9时，它所识别的活前缀为aa*B等等。需要注意的是，对那些只含有归约项目的项目集，即M的I1,I2,I3,I5,I6,I8和I10，当M到达这些状态时，表明活前缀中已含有相应句柄的全部符号 (即句柄已在栈顶形成)，因此，我们将这些状态称为句柄识别状态。特别是当M处于状态I1时，M所识别的活前缀为S，这意味着已将所给的输入串归约为S，如果再按产生式S′→S归约一步，就得到了拓广文法G′的开始符号S′。因此，我们将状态I1称为“接受状态”，它预示着对输入串的分析已成功地完成。
对于一个给定文法G的拓广文法G′，当识别它的全部活前缀的DFA作出之后，我们就可据此构造相应的LR(0)分析表了。然而，应当首先注意的是，用前述方法所构造的每一个LR(0)项目集，实质上表征了在分析过程中可能出现的一种分析状态；再根据前面对LR(0)项目的分类，项目集中的每一个项目又与某一种分析动作相关联，因此，我们自然会提出这样的要求，即每一项目集中的诸项目应当是相容的。所谓相容，是指在一个项目集中，不出现这样的情况：
(1) 移进项目和归约项目并存；
(2) 多个归约项目并存。
如果一个文法G满足上述条件，也就是它的每个LR(0)项目集中都不含冲突项目，则称G为LR(0)文法。显然，只有当一个文法是LR(0)文法时，才能构造出不含冲突动作的LR(0)分析表来。
从前面的讨论和分析，我们将不难得出构造LR(0)分析表的算法。为方便起见，我们用整数0，1，2，…表示状态I0,I1,…，而且如表411那样，也将GOTO子表中有关终结符号的各列并入ACTION子表相应的各列中去，此外，算法中形如sj和rj等记号的含义同前，此算法如下：
(1) 对于每个项目集Ii中形如A→α·Xβ的项目，若GO(Ii,X)=Ij，且X为一终结符号a时，置ACTION[i,a]=sj。但若X为非终结符号时，则仅置GOTO[i,X]=j。
(2) 若归约项目A→α·属于Ii，设A→α为文法的第j个产生式，则对文法的任何终结符号或句子的右界符# (将它们统一地记为a)，置ACTION[i,a]=rj。
(3) 若接受项目S′→S·属于Ii，则置ACTION[i,#]=acc。
(4) 在分析表中，凡不能按上述规则填入信息的元素，均置为“出错”。

3. 编译原理偶数个0和偶数个1转换图

嘛，差不多就是这样了。思路是分析所有0和1的组合画出存在的状态，然后判断转移条件，找出可接受的状态。

4. 编译原理lr0和slr1的区别

语法分析有自上而下和自下而上两种分析方法其中自上而下：递归下降，LL(1)自下而上：LR(0),SLR(1),LR(1),LALR(1)

LR需要构造一张LR分析表，此表用于当面临输入字符时，将它移进，规约（即自下而上分析思想），接受还是出错。
LR(0)找出句柄前缀，构造分析表，然后根据输入符号进行规约。 SLR(1)使用LR(0)时若有冲突，不知道规约，移进，活移进哪一个，所以需要向前搜索，则只把有问题的地方向前搜索一次。 LR(1)1.在每个项目中增加搜索符。2.举个列子如有A->α.Bβ，则还需将B的规则也加入。 LALR(1)就是假如两个产生式集相同则将它们合并为一个，几合并同心集。

5. 编译原理 语法

编译原理不同教材用的表示不太一样，翻译也五花八门，我不是很确定你这个活前缀是什么意思。我按我知道的告诉你，我用“。”表示状态的位置，你的书上可能通常是一个黑点表示，先要建立文法的状态集合：
S1：S->。a
S2：S->a。
S3：S->。^
S4：S->^。
S5：S->。(T)
S6：S->(。T)
S7：S->(T。)
S8：S->(T)。
S9：T->。T,S
S10：T->T。,S
S11：T->T,。S
S12：T->T,S。
S13：T->。S
S14：T->S。
归集状态，和状态转换关系（这应该是要画成图的，这里没法画。。。）用I表示
I0：S1 S3 S5 S9 S13
输入a，I0->I1
I1：S2
输入^，I0->I2
I2：S4
输入(，I0->I3
I3：S6 S9 S13 S1 S3 S5
归约S，I0->I4
I4：S14
归约T，I0->I5
I5：S10
归约T，I3->I6
I6：S7
输入)，I6->I7
I7：S8
输入,，I5->I8
I8：S11 S1 S3 S5
归约S，I8->I9
I9：S12
输入a，I8->I1
输入^，I8->I2
输入(，I8->I3
输入a，I3->I1
输入^，I3->I2
输入(，I3->I3
然后你要建立状态转换表，网络不能画表格。。。，你将就看看( $是结束符啊.还有你的文法没有开始，即S')
先把题目中的规则编个号：
(1) S->a
(2) S->^
(3) S->(T)
(4) T->T,S
(5) T->S
action goto
状态集 a ^ ( ) , $ S T
0 s1 s2 s3 14 10
1 acc
2 acc
3 s1
因为没有S'不知道最终怎么规约

6. 程序设计语言编译原理试题，有会做的吗

要求1、写一个顺序控制程序，要求输出一个控制字，就必须查询相应的一种输入最好又每一步骤的说明，十分感谢！ DLX语言?

7. 编译原理 LR(0) 项目集规范族怎么构建。 书上的实在是看不懂那些I0、I1、I2的步骤。求一个

LR分析法是一种自下而上进行规范归约的语法分析法，L指从左到右扫描输入符号串，R是指构造最右推导的逆过程。对大多数无二义性上下文无关文法描述的语言都可用它进行有效的分析。主要分析器有LR（0），SLR（1），LR（1），LALR（1）：
LR（0）：在分析的每一步，只需根据当前栈顶状态而不必向前查看输入符号就能确定应采取的分析动作。所能分析的LR（0）文法要求文法的每一个LR（0）项目集中都不含冲突项目。
示例文法：
0 S’ -> S
1 S -> A
2 S -> B
3 A -> aAb
4 A -> c
5 B -> aBb
6 B -> d

8. 编译原理——LR分析表

自底向上的语法分析

LR分析表的结构如上，其分为两个部分 Action Goto

两个参数状态i，终结符号a（s(i)代表第i个状态，r(i)代表第i条表达式）

Goto[i,A]=j

文法

容易得知这个文法可以推出 0 1 00 01 等的字符串。因为它是 左递归 。不适用于 LL 文法分析，只能使用 LR 分析。

因为本题入口有两个—— S → L·L S → L ，所以需要构造额外的产生式 S'->S

2.1 第一次遍历

我们从 [S -> . L·L] 开始，构造这个状态的闭包，也就是加上所有能从这个产生式推出的表项。

首先，判断 . 后面是否为 非终结符号A 。如果是，那我们就得找所有由 A-> 推出的产生式，并将它们添加进入 闭包 里(也就是State包里)。循环做即可。

因此我们可以得到 State 0 有

下一步，就是我的 . 往下一位移动。对每个符号X后有个 . 的项，都可以从 State 0 过渡到其他状态。

由以上6条式子可以得知下一位符号可以是 S L B 0 1 。所以自然可以得到5个状态。

State 1 是由 State 0 通过 S 转移到这里的，所以我们找出所有 State 0 中在 S 前有 . 的项。

此状态作为结束状态 Accept ，不需要继续状态转移了。

State 2 是由 State 0 通过 L 转移到这里的，所以我们找出所有 State 0 中在 L 前有 . 的项。

S -> . L·L S -> . L L -> . LB

有3条式子，现在我们将 . 向后推一格，就得到 State 1 的项了。

但是 . 之后的符号分别是 · $ B ， B 为非终结符号，我们得包含 B -> 的项

State 3 是由 State 0 通过 B 转移到这里的，所以我们找出所有 State 0 中在 B 前有 . 的项。

因为 . 后没有其他符号了，因此这个状态不需要继续转移了。

State 4 是由 State 0 通过 0 转移到这里的，所以我们找出所有 State 0 中在 0 前有 . 的项。

因为 . 后没有其他符号了，因此这个状态不需要继续转移了。

很简单，同样的道理找 State 5

State 5 是由 State 0 通过 1 转移到这里的，所以我们找出所有 State 0 中在 1 前有 . 的项。

因为 . 后没有其他符号了，因此这个状态不需要继续转移了。

好的，现在我们第一次遍历完成。

2.2 第二次遍历

第二次遍历自然从 State 2 开始。

我们回到 State2 ，可以看出 . 之后的符号有 · B 0 1 。

State 6 是由 State 2 通过 · 转移到这里的，所以我们找出所有 State 2 中在 · 前有 . 的项。

S -> L. ·L 只有1条，我们往后移发现 L 又为非终结符号，参考 State 0 做的操作，我们得找出所有的式子。

共有5条式子，共同组成 State 6 ，由上面的式子可以看出我们还得继续下一次遍历。先不管着，我们进行下一次状态查找。

State 7 是由 State 2 通过 B 转移到这里的，所以我们找出所有 State 2 中在 B 前有 . 的项。

L -> L. B 也是只有1条，我们往后移发现没有非终结符号了，那就不需要再继续添加其他式子了。

这个状态也不需要继续进行转移了。

接下来很关键，因为我们通过 State2 的 . 后的符号找出了 State 6 State 7 ，接下来还差符号 0 1 ，那么是否像之前一样按例添加状态呢， 答案是不是的 ，因为我们发现通过 0 1 找到的闭包集分别是 B -> 0 B -> 1 ，这与我们的之前的 State 4 State 5 相同。所以我们得将其整合起来，相当于 State 2 通过 0 1 符号找到了 State 4 State 5 状态。

2.3 第三次遍历

回头看第二次遍历，可以看出只有 State 6 可以进行状态转移了。

那么就将 State 6 作为第三次遍历的源头，可以看出 . 之后的符号有 L B 0 1 。

State 8 是由 State 6 通过 L 转移到这里的，所以我们找出所有 State 6 在 L 前有 . 的项。

S -> L· .L L -> . LB 有两条式子，往后移发现有非终结符号 B ，所以经过整合可以得到

可以看出 . 的后面还有一个符号，所以这里我们还得再进行一次遍历。

接下来，又是遇到重复的包的情况，可以看出我们由 State 6 通过 B 0 1 得到的闭包分别是 L->B B->0 B->1 ，很明显，这分别对应于 State 3 State 4 State 5 。

第三次遍历也就结束了。

2.4 第四次遍历

回看第三次遍历，可以看出只有 State 8 可以进行状态转移，其 . 之后的符号分别是 B 0 1 。

诶，感觉很熟悉，就是上面几行刚说的情况，也就是说通过这三个符号找到的闭包是我们之前遇到的状态，分别是 State 3 State 4 State 5 。

做到这里，我们发现我们已经全部遍历完毕！

总共有8个状态，通过以上流程做成个图是什么样子的？来看看！

这么一看就很清晰明了了，我们就可以通过这个图做出我们的 LR分析表

其实就是我们之前呈现的表

在状态 I2 和 I8 中，既有 移入 项目，也有 规约 项目，存在 移入 - 规约的冲突 ，所以不是 LR(0) 文法，但是因为 FOLLOW(S) ∩ {0, 1} = ∅，所以可以用 FOLLOW 集解决冲突，所以该文法是 SLR(1) 文法。

上表我们发现还有 r1，r2，r3 等。这个其实就是代表状态停止转移时为 第几条表达式 ，r3代表第三条表达式 L -> LB 。

当我们构建了表之后，我们如何运用起来呢？

下面我们通过一个例子来说明

以上字符串是如何被SLR分析器识别的呢？

9. 求大神指导编译原理的状态转换图怎么画

这里你要弄清子集法中，每一行，指的是变迁。比如第一行，代表状态0，画一根线到状态1，因此第1个0是指这个变迁的起点状态0，第3个1是指变迁的终点状态1。

同理，第2行是指从状态1出发，有2个变迁，即第一个是状态1指向状态1（自己），第2个变迁是从状态1到状态1和2。

这样第3行就表示如果从状态{1，2}开始，输入是0和1时的变迁分别是什么，依此类推。
你红的圈出来的就是NFA所有可能的状态和状态组合。