实现移进归约分析的一种便利方法

❶ 分别解释软件的设计两种设计方法:自顶向下和自底向上

首先它们是两种程序设计的分析方法
自顶向下：这种方法的主旨是，对给定的输入符号串，从对应文法开始符号的根结点出发，自顶向下地为输入符号串建立一棵分析树。
自底向上：是一种“移进－归约”法。将这种过程看作为：归约一个输入符号串到文法开始的过程。换句话说，这样的分析法是从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。

❷ 使用自顶向下方法与自底向上方法分层有何差异，哪些类型的项目能最佳的匹配每种方法

自顶向下方法与自底向上方法分层是两种程序设计的分析方法：
自顶向下：这种方法的主旨是，对给定的输入符号串，从对应文法开始符号的根结点出发，自顶向下地为输入符号串建立一棵分析树。
自底向上：是一种“移进－归约”法。将这种过程看作为：归约一个输入符号串到文法开始的过程。换句话说，这样的分析法是从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。

项目的学习需要持续不断的自顶向下的学习与自底向上的学习。何谓自顶向下的学习，即先着手系统架构，然后逐层进入业务模块，最后进入细粒度功能模块的开发。所谓自底向上的学习，就是先从一行代码，一个Bug，一个模块做起，然后在做一个流程，一个业务模块，最后熟悉整个系统的架构。
自顶向下的学习与自底向上的学习是离不开的，没有自顶向下的学习，你就不能很好的理解业务，在开发过程中就会很被动。没有自底向上的学习，你就不能建立起自己的技术优势，无法去攻坚。在项目初期，通常系统架构师会讲解项目的架构，主要是业务架构。通过了解业务架构，熟悉整个系统的业务，便于在后续系统中根据业务进行开发，这就是所谓的自顶向下的学习。
有时候开发的新项目是自己之前未接触过的类型，在理解项目的业务时，就会有一定的难度，而每一个项目的开发时间又不是那么充裕，所以项目上不会给你那么多的时间来理解系统的业务架构（也包含其它的架构，如逻辑架构等），这时候就需要在项目开发中进行自底向上的学习。如果不是时间特别紧的话，通常会给你一定的时间去了解一个模块，熟悉系统框架之间各层次间的调用。以此为基础点，逐步深入，在开发过程中逐渐熟悉系统的架构。
当我们在开发中以模块为单位开发的乐此不疲时，一定要记得时不时的回头看看我们的系统架构，无论是业务架构，还是逻辑架构，甚至物理架构，这些都是我们深入理解一个项目的基本。如果我们不满足于当前的工作状况，更要记得时时学习系统架构，以整体为单位，进行全面的学习。
无论是作为一名现在的或未来的开发人员或者架构师，我们都不应该止步于当前的学习，时时刻刻切记自顶向下的学习与自底向上的学习是分不开的。自顶向下的学习需要自底向上的学习来完善，自底向上的学习需要自顶向下的学习来指导。

❸ LR分析法的LALR(1)分析表的构造

上述每个LR(1)项目均由两部分组成： 第一部分是一个LR(0)项目，称为LR(1)项目的核；第二部分则是一个向前搜索符号集。对于移进项目而言，搜索符号对分析表的构造无影响；但对归约项目而言，则仅在当前输入符号属于该搜索符号集时，才能用相应的产生式进行归约。LR(1)分析表的这种机理，较圆满地解决了SLR(1)分析所难以解决的某些“移进归约”或“归约归约”冲突，从而使LR(1)的分析能力比SLR(1)分析有明显的提高。然而，LR(1)分析的主要缺点在于，对同一个文法而言，LR(1)分析表的规模将远远大于相应的SLR(1)或LR(0)分析表。例如，为一个C语言构造LR(0)分析表，一般大约设置300个状态即可，而构造LR(1)分析表则需上千个状态，即后者将导致时间和内存空间开销的急剧上升。因此，就有必要寻求一种其分析表的规模与SLR(1)相当，但其分析能力又不比LR(1)相差太大的LR分析方法，这就是下面我们要介绍的LALR(1)分析技术。
下面，我们首先对造成LR(1)项目集族规模大幅度上升的原因进行分析，然后再设法从中找出构造高效LR分析表 (即LALR(1)分析表)的方法。为此，试看下面的例子。
再考察文法G[E]：
0?S→E4?T→F
1?E→E+T5?F→(E)
2?E→T6?F→ID
3?T→T*F
利用上面所给算法，为G[E]构造的LR(1)项目集族和识别活前缀的DFA如图420(a)，(b)所示 (请注意，由于图幅较大，这里将其划分为(a)，(b)两部分)。对比这两幅图我们立即就会发现，除其中的状态0和状态3之外，对于(a)中的每一状态 (LR(1)项目集)，在(b)中都有一个状态 (LR(1)项目集)与其相似。例如，比较状态7和16：在这两个项目集中，除搜索符号集不同外，各个LR(1)项目的核都彼此相同 (即产生式相同，且产生式中圆点的位置也相同)，我们把具有这种特点的两个LR(1)项目集称为同心集。所以，在图420(a)和(b)中，7/16，5/12，10/17，4/13，8/18，2/14，11/19，6/20，1/15和9/21都是同心集。显然，在LR(0)分析器中，每个“心”仅对应一个LR(0)项目集；但在LR(1)分析器中，由于向前搜索符号的不同，同一个“心”将会派生出多个同心集。这就是对同一文法而言，LR(1)项目集族远大于LR(0)项目集规范族的原因。
7E→E+·T[]#+T→·T*F
T→·F
F→·(E)
F→·ID〖〗#+*
#+*
#+*
#+*[][]16E→E+·T[]+)T→·T*F
T→·F
F→·(E)
F→·ID〖〗+)*
+)*
+)*
+)*
为解决上述问题，F?DeRemer提出了LALR(1)分析法。这种方法的基本思想是将LR(1)项目集族中的同心项目集加以合并，以削减项目集的个数。所谓合并同心集，实际上也就是将其中的每个LR(1)项目的向前搜索符集对应地合并在一起。例如，对于文法G[E]的同心项目集4和13，设合并后的新项目集为4/13，则有
4E→T·
T→T·*F〖〗#+
#+*[][]13E→T·
T→T·*F〖〗+)
+)*[][]4/13E→T·
T→T·*F〖〗#+)
#+)*
由于同心集的合并，对原来识别活前缀的DFA也须作相应的修改。
对于LALR(1)项目集族，我们须着重指出如下几点：
(1) 合并同心集也就是将同心集中每个LR(1)项目的两个组成部分 (核及向前搜索符号集)分别、对应地合并在一起。设I1,I2,…,Im为同心项目集，J是合并之后的新的项目集，显然J与Ii同心；再设X∈V∪{#}，则GO(I1,X),GO(I2,X)，…，GO(Im,X)也必然同心，若把这m个同心项目集合并后的新项目集记为K，则有GOTO(J，X)=K。可见前面定义的GOTO函数在这里仍然适用。
(2) 尽管原来各LR(1)项目集均不存在冲突，但合并同心集后就有可能出现冲突。换言之，即LR(1)文法未必总是LALR(1)文法。不过，由此引入的冲突只能是“归约归约”冲突，而决不会是“移进归约”冲突。事实上，设原LR(1)项目集族中有如下两个项目集
Ik：
[A→α·，W1]
[B→β·aγ,b]Ij:
[A→α·,W2]
[B→β·aγ，c]
并设Ik与Ij均无冲突，故有
W1∩{a}=?W2∩{a}=?
从而
(W1∪W2)∩{a}=?
现将Ik与Ij合并，有
Ik/j:
[A→α·,W1∪W2]
[B→β·aγ，{b}∪{c}]
若此时Ik/j有“移进归约”冲突，则必有
(W1∪W2)∩{a}≠?
这就与Ik与Ij无冲突的假设相矛盾。因此，合并同心集不会引入新的“移进归约”冲突。
(3) 对同一个语法上正确的输入符号串而言，不论用LALR(1)分析表还是用LR(1)分析表进行分析，所经历的移进、归约序列总是相同的 (仅状态名可能不同)。然而，当输入符号串有错时，LALR分析器可能会比LR(1)分析器多进行几步归约才能报错，但决不会比LR分析器多移进输入符号。也就是说，LALR分析器虽然可能延迟了发现出错的时间，但对错误的准确定位不产生影响。
(4) LALR(1)项目集族总是与同一文法的SLR(1)项目集族有同样个数的项目集。但是构造LALR项目集族的开销比SLR大。实现LALR分析对文法的要求比LR(1)严、比SLR(1)宽，但开销远小于LR(1)。权衡利弊的结果，LALR堪称为当前实现自底向上语法分析，特别是构造分析器自动生成工具的最为适用的技术。
综上所述，可给出构造LALR(1)分析表的算法如下。
1? 对已给的拓广文法G′，构造相应的LR(1)项目集族C={I0,I1,…,In}。
2? 对于C，将各LR(1)项目集按同心关系进行分组，并将同组的同心集加以合并，设所得的新项目集族为C′={J0,J1,…,Jm}，其中含有项目[S′→·S,#]的项目集对应于初态。
3? 若C′中的项目集含有冲突项目，则G′不是LALR(1)文法。否则，可按如下法则构造LALR(1)分析表：
(1) 用构造LR(1)分析表类似的方法构造ACTION表；
(2) 对于某个X∈VN，若有GO(Jk,X)=Jt，则置GOTO(k,X)=t。
上述通过构造LR(1)项目集族和合并同心集来构造LALR分析表的方式仅有理论意义而无实用价值。因为构造完整的LR(1)项目集族的时间和空间开销都很大，故应首先设法予以解决。
迄今已有多种高效构造LALR分析表的算法，其共同的特点都是不从直接构造完整的LR(1)项目集入手，而是通过构造LR(0)项目集并添加相应的向前搜索符号来形成LALR(1)项目集 (请注意，对同一个文法而言，LALR(1)项目集与同心的LR(0)项目集一一对应)。例如，OCCS/YACC构造LALR(1)项目集所采用的策略是，每当创建一新的项目集时，就检查目前是否已存在与之同心的项目集，若有这样的项目集，则只需将向前搜索符号加入其中，而不再建立新的项目集。一种更为有效的方法甚至无需构造完整的LALR(1)项目集，而仅通过各个项目集中的“核心项目”便能构造相应的LALR(1)分析表。这里所说的核心项目是指形如[S′→·S，#]的项目 (其中，S′→S是拓广文法的第1个产生式)，或者是形如[A→α·Xβ,a]的项目 (其中，α≠ε，即圆点不出现在产生式右部的最左位置)，亦即那些用于构造本项目集闭包的“基本项目”。例如，对于文法G[E]，各项目集的核心项目如图422所示。
下面，我们对利用项目集的核心项目构造LALR分析表的原理进行说明。 构造ACTION表的关键在于确定“归约”和“移进”两种动作。
(1) 归约动作的确定
由核心项目的定义可知，任何归约项目都必然会出现在某个项目集的核心项目之中，现设项目集I的核心为K，若[A→α·,a]∈K (其中α≠ε，搜索符号如何配置下面再介绍)，我们立即可以确定： 在当前状态下所面临的输入符号为a时，应按产生式A→α进行归约，即有
ACTION[I,a]=rj
若α=ε，则当且仅当
[B→γ·Cδ， b]∈KC?*[]rAη
且a∈FIRST(ηδb)时，才能确定面临输入符号a时用产生式A→ε进行归约。由于对任何C∈VN，满足C?*[]rAη的所有非终结符号A预先能完全确定，故项目集I所引发的归约动作，仅由其核心K即能完全确定。
(2) 移进动作的确定
若
[A→α·Xβ,b]∈KX?*[]raη(a∈VT)
且上述推导的最后一步未使用ε产生式，则可确定： 状态I面临输入符号a时的动作为“移进”。其中，终结符号a可通过预先计算FIRST(X)加以确定。 对于任何项目[B→γ·Xδ,b]∈K，相应的项目[B→γX·δ,b]显然必属于某个项目集J=GO(I，X)的核心L。另外，若
[B→γ·Cδ,b]∈KC?*[]rAη
且A→Xβ是文法中的一个产生式，则对于任何
a∈FIRST(ηδb)[A→X·β,a]∈L
由于对每一对非终结符号(C，A)，是否存在关系C?*[]rAη，可采用类似于计算FIRST集的方法预先求出，故仅从I的核心同样可构造出GOTO表。 上面的讨论，是在假定每个核心项目都已配置了搜索符号的情况下进行的。现在，再回头讨论： 如何为每个LR(0)项目集的核心项目配置搜索符号，使之成为LALR项目集的核心项目。为此，我们首先考察搜索符号从项目集I传播到项目集GO(I，X)的规律。
再设项目集I的核心为K，若有
[B→γ·Cδ,b]∈KC?*[]rAη
且A→Xβ是文法中的一个产生式，则根据上面的讨论有
[A→X·β,a]∈La∈FIRST(ηδb)
其中L是项目集J的核心，且J=GO(I,X)。现分如下两种情况讨论搜索符号a和b间的关系。
(1) 当ηδ?*ε时，显然也有[A→X·β,b]∈L。此时，我们就说项目[A→X·β,b]中的搜索符号b是从项目[B→γ·Cδ,b]中传递过来的 (propagate)。
(2) 当ηδ不能推导出ε时，a仅取决于η或δ，而与b无关，此时我们就说搜索符号a是自生的 (spotaneous)。
无论a是传递的还是自生的，它总能根据项目[B→γ·Cδ,b]中的有关信息，通过上述计算获得，这便是搜索符号从项目集I传播到项目集J的规律。
其次，在同一项目集中，核心项目中的搜索符号向非核心项目传播的规律与上述规律极为相似。事实上，设[B→γ·Cδ,b]∈K，而C→α是文法中的一个产生式，则[C→·α，c]是I的一个非核心项目。其中，搜索符c∈FIRST(δb)，且按如下方法确定： 若δ不能推出ε，则c是自生的；否则，c=b，即c是从上面的项目传递下来的。
类似地，也可讨论搜索符号在非核心项目间的传播规律。例如，对于文法G[E]，从核心项目[S→·E，#]开始，向前搜索符号在I0中的传递和自生的情况如图423所示。
设K是LR(0)项目集I的核心，X是某个文法符号，则对GO(I，X)的核心中的每一项目A→αX·β，通过程序47描述的操作 (请注意，这里使用了一个虚拟搜索符号lookahead)，可由I中的项目确定其全部自生的搜索符号，并能确定K中的哪些项目将其搜索符号传递给GO(I，X)中的项目A→αX·β。
程序47确定自生搜索符号和传递搜索符号的项目
for (K中的每个项目B→γ·δ)
{
J′=CLOSURE ([B→γ·δ,lookahead]);
/*计算GO函数之值 */
for (J′中的每一项目[A→α·Xβ,a])
{
if(a!=lookahead)
确定GO(I，X)核心项目[A→αX·β,a]
之搜索符号a是自生的
if(a==lookahead)
确定GO(I，X)核心项目[A→αX·β，a]之搜索符号a是从K中项目
B→γ·δ传递过来的；
}
}
最后，我们再考虑如何给每个LR(0)项目集的核心中的各个项目都配置一个搜索符号集，以获得各个LALR(1)项目集的核心。完成此项任务的大致过程如下。
(1) 为拓广文法G′构造全部LR(0)项目集的核心。
(2) 首先从初始项目集I0惟一的核心项目S′→·S (其搜索符号显然为#)开始，对每个LR(0)项目集的核心和每个文法符号X，利用上面的算法，确定GO(I，X)各核心项目的自生搜索符号集，并确定从I的哪些项目将搜索符号传递到GO(I，X)的核心项目。
(3) 按某种便于操作的结构，建立一张核心项目表，此项目表记录了每个项目集的各个核心项目及其相应的搜索符号集。开始时，这些搜索符号集仅是由第(2)步所确定的自生搜索符号集 (若该核心项目无自生向前搜索符号则为空)。
(4) 传递每个核心项目中的自生搜索符号，直到无法再进行传递为止。即反复扫视各项目集的每个核心项目，每当访问一个核心项目i时，便根据第(2)步所获的信息，将i当前要传递的搜索符号添加到承接它的那个核心项目之中，直至没有新的搜索符号要传递为止。
对一个给定的文法G而言，当它的各个LALR(1)项目集的核心构造出来之后，就能根据上面所描述的原理，为G构造相应的LALR(1)分析表。不过，尽管上述构造LALR分析表的方法效率较高，但对于常见的程序设计语言，企图用手工的方式来建立LALR分析表仍几乎是不可能的。所幸的是，目前已有一些自动生成LALR分析表的工具可资使用(如YACC)。
还应当指出，在构造LR语法分析器时，尚有若干技术问题需予以考虑，如二义性文法的处理，避免按单产生式的归约，等等。前者我们将在第5章介绍语法分析器自动生成工具时再进行讨论；至于后者，由于需涉及一些语义处理及其信息传递的细节，故就不再讨论了。
在结束本章时，我们还要给出如下的结论，这些结论的证明读者可参阅有关的文献(1，2，8，15)。
(1) 任何LR(K)，LL(K)及简单优先文法类都是无二义性的；对于算符优先文法，如果不考虑归约所得非终结符号的名字，也可认为是无二义性的。
(2) 任何二义性的文法都不可能是LR(1)(或LL(1))文法，但可借助于其它因素，如算符的优先级和结合规则以及某些语义解释等等，来构造无冲突的分析表。
(3) 每个SLR(K)文法都是LR(K)文法，但却存在这样的LR(1)文法，它对任何K而言均不是SLR(K)文法。

❹ 提示Target not created.

提示Target not created代表编译没有成功；

编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。编译程序的语法规则可用上下文无关文法来刻画。

语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。

(4)实现移进归约分析的一种便利方法扩展阅读：

如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误的发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动纠正错误，这些工作由错误处理程序完成。

需要注意的是，一般上编译器只做语法检查和最简单的语义检查，而不检查程序的逻辑。

❺ 编译原理 - 移进归约分析中如何确定句柄的开始处与结束处

当然是根据文法来写的呀 没有文法无法确定 句柄的开始处和结束处 的 当然 还要看看匹配不匹配呀 ，要最后 这个句型和文法都匹配起来都行呀 总之 句柄肯定都是在产生式右端的 你可以一个个匹配过来

❻ LR分析法的LR(1)分析表的构造

前面所介绍的SLR(1)分析法是一种较实用的方法。其优点是状态数目少，造表算法简单，大多数程序设计语言基本上都可用SLR(1)文法来描述。然而，也的确存在这样的文法，其项目集的“移进归约”冲突不可能通过SLR(1)规则得到解决。试看下面的例子。
例4?8考察文法G[S′]=({S′,S,A,B,C,D}, {a,b},,P,S′)其中，P由如下的产生式组成：
0? S′→S4?B→C
1?S→CbBA5?B→Db
2?A→Aab6?C→a
3?A→ab7?D→a
识别此文法的全部活前缀的DFA见图418。其中项目集I10={S→CbBA·,A→A·ab}存在“移进归约”冲突，但因FOLLOW(S)={#}，故上述冲突可通过SLR(1)规则得到解决。然而，在项目集I8={C→a·,D→a·}中，由于FOLLOW(C)={a,b}，FOLLOW(D)={b}，即FOLLOW(C)∩FOLLOW(D)≠?，故用SLR(1)规则解决上述“归约归约”冲突无效。而且还可验证，对于任何K>0，上述文法也是非SLR(k)的，故不能通过任何SLR(k)规则使项目集I8中的“归约归约”冲突得到解决 [2]。因此，我们需要更强的LR分析法，即LR(1)分析方法来解决这一问题。
对SLR(1)规则稍作分析即可发现，它对某些文法失效的原因，在于当所给的文法出现冲突的分析动作时，SLR(1)规则仅孤立地考察输入符号是否属于与归约项目A→α·相关联的集合FOLLOW(A)，以确定是否应按产生式A→α进行归约，而没有考察符号串α所在规范句型的“环境”，即没有考察α在规范句型中的“上下文”，这就具有一定的片面性。因为一旦α出现在分析栈的顶部 (设分析栈当前所存放的符号串为#δα)，且当前的输入符号a也属于FOLLOW(A)，就贸然将α归约为A，此时分析栈中的符号串将变成#δA，但若文法中并不存在以δAa为前缀的规范句型，那么，这种归约无效。例如，对于上述文法中的规范句型Cbabab，当分析达到格局
I0I2I4I8[]#Cbabab(4?50)
时，如果仅根据当前输入符号b∈FOLLOW(C)，就将栈顶符号a按产生式C→a归约为C，则有如下的格局：
I0I2I4I6[]#CbCbab
但在该文法中，根本不存在以CbCb为前缀的规范句型，因此在执行下一动作将b移进之前，分析器将报告“出错”。由此可见，在分析过程中，当试图用某一产生式A→α归约栈顶符号串α时，不仅应查看栈中符号串δα，还应向前扫视一输入符号a (我们将a称为向前搜索符号)，只有当δAa的确构成文法某一规范句型的前缀时，才能用此产生式进行归约。为了指明上述事实，应当在原来的每一LR(0)项目[A→α·β]中放置一个向前搜索符号a，使之成为[A→α·β,a]的形式，我们将此种项目称为一个LR(1)项目。同时，为了使分析的每一步都能在栈中得到一个规范句型的活前缀，还应要求每一个LR(1)项目对相应的活前缀都是有效的 (其定义在下面给出)。此外，为了克服分析动作的冲突，在必要时，我们还可将某些项目集进行分解，以便使每一个状态都能确切地指明： 当α已出现在栈顶，且面临哪些输入符号时，才能按产生式A→α将α归约为A。
所谓一个LR(1)项目[A→α·β，a]对活前缀γ=δα有效，是指存在规范推导
S?*δAy?δαβyy∈V*T
且满足下列条件：
(1) 当y≠ε时，a是y的首符号；
(2) 当y=ε时，a=#。
例如，对于例4?8所给文法，因有
S?CbBA?CbBab?CbDbab
其中，δ=Cb,α=D,β=b,y=ab,A=B，故LR(1)项目[B→D·b,a]对活前缀γ=CbD有效。又因
S?*CbDbab?Cbabab
其中，δ=Cb,A=D,α=a,β=ε,y=bab,故LR(1)项目[D→a·,b]对活前缀γ=Cba有效。由此也可看出，当分析器所处的格局为式(4?50)时，应当将栈顶符号a归为D，而不应将它归约为C。
与LR(0)文法的情况相类似，识别文法全部活前缀的DFA的每一个状态也是用一个LR(1)项目集来表示，而每一个项目集又是由若干个对相应活前缀有效的LR(1)项目组成。为了构造LR(1)项目集族，我们同样需要用到两个函数，即CLOSURE(I)及GO(I，X)。
对每一LR(1)项目集I，相应的CLOSURE(I)的定义如下：
(1) I中的任何LR(1)项目都属于CLOSURE(I)。
(2) 设项目[A→α·Bβ，a]∈CLOSURE(I)，并假设它对活前缀γ=δα有效，则对文法中所有形如B→η的产生式和每一个b∈FIRST(βa)，形如[B→·η,b]的全部项目也都对γ有效，故若[B→·η,b]原不在CLOSURE(I)中，则应将其放入。事实上，因为[A→α·Bβ，a]对γ=δα有效，则由定义我们有：
s?*δAy?δαBβyy∈V*T
且a∈FIRST(y)∪{#}，故可将上面的推导写成
S?*δAy?δαBβaωω∈V*T∪{#}
现设文法已经过化简，故不论β是否为ε，从βaω总能推出终结符号串，于是可假定
βaω?*bω′
又因a≠ε，有FIRST(βaω)=FIRST(βa)，从而就得到推导
S?*δαBbω′
由此可见，一切形如[B→·η,b]的项目也对活前缀γ=δα有效。
(3) 重复步骤(2)直到没有新的项目加入为止。
至于函数GO(I，X)，其中I为一LR(1)项目集，X为某一文法符号，与LR(0)文法类似，我们也将它定义为：
GO(I,X)=CLOSURE(J)
其中J是由这样的一些LR(1)项目组成： 对I中所有圆点在X左边形如[A→α·Xβ,a]的项目，其后继项目[A→αX·β,a]∈J。注意，每一LR(1)项目与其后继项目有相同的向前搜索符号。
有了上述CLOSURE(I)和GO(I，X)的定义之后，采用与LR(0)类似的方法，可构造出所给文法G的LR(1)项目集族C及状态转换图。例如，对于上述文法，其LR(1)项目集及状态转换图如图419所示。
对于给定的文法G，当相应的LR(1)项目集族C及GO函数构造出来之后，便可按如下的算法构造它的LR(1)分析表：
(1) 对于每个项目集Ii中形如[A→α·Xβ,b]的项目，若GO(Ii,X)=Ij，且当X为一终结符号a时，置ACTION[i,a]=sj。但若X为一非终结符号时，则置GOTO[i,X]=j。
(2) 若归约项目[A→α·,a]∈Ii，A→α为文法的第j个产生式，则置ACTION[i,a]=rj。
(3) 若项目[S′→S·,#]∈Ii，则置ACTION[i,#]=acc。
(4) 在分析表中，凡不能照上述规则填入信息的元素，均置为“出错”。
对于一个文法G来说，若按上述算法所构造的分析表不含有多重定义的元素，则称此分析表为G的LR(1)分析表。凡具有LR(1)分析表的文法称为LR(1)文法。例如，上述文法的LR(1)分析表见表416，所以它是一个LR(1)文法。

❼ LR分析法的SLR(1)分析表的构造

在前面讨论LR(0)分析表的构造算法时，我们曾经指出，仅当一个文法G是LR(0)文法时，才能对它构造出无冲突动作的LR(0)分析表。然而，对于通常的程序设计语言来说，它们一般都不能用LR(0)文法来描述。例如，考虑如下“简单分程序”的文法G[B′]：
0? B′→B3? D→d
1? B→bD;Se4? S→s;S
2? D→D;d5? S→s
相应识别其全部活前缀的DFA及LR(0)分析表如图417及表414所示。由于在项目集I8中，既含有移进项目[S→s·;S]，又含有归约项目[S→s·]，因而反映到分析表中就出现了具有多重定义的元素ACTION[8,′；′]={s10,r5}，前者指明当输入符号为“；”时应将它移进栈中，而后者则要求按第5个产生式S→s进行归约。于是就出现了有“移进归约”冲突的分析动作。又如，对于通常用来描述简单表达式的文法G[E]，当构造它的项目集规范族时，也会出现类似的情况。这就表明，这两个文法都不是LR(0)文法。然而，尽管如此，对大多数程序设计语言来说，这种具有冲突项目的项目集，在整个项目集规范族中所占的比例毕竟是很小的。因此，如果我们能设法解决出现在一个项目集中的“移进归约”或“归约归约”冲突，那么，只要对前述构造LR(0)分析表的算法稍加修改，它仍能适用于我们现在讨论的情况。
表414G[B′]的LR(0)分析表
b[]d[]；[]s[]e[]#[]B[]D[]S0[]s2[8]11[7]acc2[3]s4[9]33[4]s54[]r3[]r3[]r3[]r3[]r3[]r35[][]s7[][]s8[10]66[6]s97[]r2[]r2[]r2[]r2[]r2[]r28[]r5[]r5[]r5,s10[]r5[]r5[]r59[]r1[]r1[]r1[]r1[]r1[]r110[5]s8[10]1111[]r4[]r4[]r4[]r4[]r4[]r4
仔细分析上述构造LR(0)分析表的算法容易看出，使分析表中出现多重定义分析动作的原因在于其中的规则(2)，即对于每一项目集Ii中的归约项目A→α·，不管当前的输入符号是什么，都把ACTION子表相应于Ii那一行 (即第i行)的各个元素指定为rj，其中j是产生式A→α的编号。因此，如果该项目集Ii中同时还含有形如B→α·bβ或C→α·的项目，则在分析表的第i行中，必然会出现多重定义的元素。
由此可见，对于含有冲突的项目集
Ii={B→α·bβ，A→α·，C→α·}
在构造分析表时，如果能根据不同的向前符号a，将Ii中各项目所对应的分析动作加以区分，那么就有可能使冲突得到解决。为此，对于文法中的非终结符号U，我们定义集合
FOLLOW(U)={a|S′#?*…Ua…, a∈VT∪{#}}
即FOLLOW(U)是由所有含U的句型中，直接跟在U后的终结符号或#组成的集合。现对上述项目集Ii，考察FOLLOW(A)，FOLLOW(C)及{b}，若它们两两不相交，则可采用下面的方法，对Ii中各个项目所对应的分析动作加以区分。
对任何输入符号a：
(1) 当a=b时，置ACTION[i,b]=“移进”；
(2) 当a∈FOLLOW(A)时，置ACTION[i,a]={按产生式A→α归约}；
(3) 当a∈FOLLOW(C)时，置ACTION[i,a]={按产生式C→α归约}；
(4) 当a不属于上述三种情况之一时，置ACTION[i,a]=“ERROR”。
一般地，若一个项目集I含有多个移进项目和归约项目，例如
I={A1→α·a1β1, A2→α·a2β2，…，Am→α·amβm, B1→α·, B2→α·, …, Bn→α·}
则当集合{a1,a2,…,am}，FOLLOW(B1),FOLLOW(B2)，…,FOLLOW(Bn)两两不相交时，可类似地根据不同的向前符号，对状态为i时的冲突动作进行区分。
上述用来解决分析动作冲突的方法称为SLR(1)规则。此规则是由F?DeRemer于1971年提出的。
有了SLR(1)规则之后，只须对前述构造LR(0)分析表的算法中的规则(2)作如下的修改：“(2)′若归约项目A→α·属于Ii，设A→α为文法的第j个产生式，则对于任何属于FOLLOW(A)的输入符号a，置ACTION[i,a]=rj”，且其余的规则仍保持不变，就得到了构造SLR(1)分析表的算法。
对于给定的文法G，若按上述算法构造的分析表不含多重定义的元素，则称文法G为SLR(1)文法。例如，对于上面的文法G[B′]，它的项目集
I8={S→s·; S,S→s·}
含有冲突的项目，但由于FOLLOW(S)={e}≠{;}，故冲突可用SLR(1)规则解决，与上述项目相应的分析动作分别是：
ACTION[8,;]=s10ACTION[8,e]=r5
此外，再注意到FOLLOW(B′)=FOLLOW(B)={#}和FOLLOW(D)={;}，则按上述算法为G[B′]所构造的SLR(1)分析表b[]d[];[]s[]e[]#[]B[]D[]S0[]s2[8]11[7]acc2[3]s4[9]33[4]s54[4]r35[3]s7[][]s8[10]66[6]s97[4]r28[4]s10[][]r59[7]r110[5]s8[10]1111[6]r4

❽ lr是什么

lr是一款专业调色的软件。

LR是lightroom的简称，是Adobe旗下一款后期处理工具。最被我们所熟悉的是另一款软件是photoshop，相比于PS，LR在调色方面更加的方便，好用。使我们的工作效率大大的提高，这是一款专业的调色工具。

ir的基础使用方法

一般我们在用Lightroom调修照片时，最先或最常用到的工具就是基本面板，它内建了一张照片所有的基调调整，包括白平衡（色温／色调）、曝光度、对比、亮部、阴影、白色／黑色剪载、清晰度、鲜艳度和饱和度。运用“基本面板”，我们就可以对照片进行初步的调整了。

❾ 编译原理，算符优先文法采用"移进-规约"技术,其规约过程是规范的. 这句话错在哪了谢谢

算符优先文法确实使用了移入归约技术，但其归约过程不满足规范归约（最左归约），算符优先文法每次归约的是最左素短语，而规范归约每次归约的是最左直接短语（句柄）

❿ 编译原理试题

习题一、单项选择题
1、将编译程序分成若干个“遍”是为了 。
a．提高程序的执行效率
b．使程序的结构更加清晰
c．利用有限的机器内存并提高机器的执行效率
d．利用有限的机器内存但降低了机器的执行效率
2、构造编译程序应掌握 。
a．源程序 b．目标语言
c．编译方法 d．以上三项都是
3、变量应当 。
a．持有左值 b．持有右值
c．既持有左值又持有右值 d．既不持有左值也不持有右值
4、编译程序绝大多数时间花在 上。
a．出错处理 b．词法分析
c．目标代码生成 d．管理表格
5、 不可能是目标代码。
a．汇编指令代码 b．可重定位指令代码
c．绝对指令代码 d．中间代码
6、使用 可以定义一个程序的意义。
a．语义规则 b．词法规则
c．产生规则 d．词法规则
7、词法分析器的输入是 。
a．单词符号串 b．源程序
c．语法单位 d．目标程序
8、中间代码生成时所遵循的是- 。
a．语法规则 b．词法规则
c．语义规则 d．等价变换规则
9、编译程序是对 。
a．汇编程序的翻译 b．高级语言程序的解释执行
c．机器语言的执行 d．高级语言的翻译
10、语法分析应遵循 。
a．语义规则 b．语法规则
c．构词规则 d．等价变换规则
解答
1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。
2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。
3、对编译而言，变量既持有左值又持有右值，故选c。
4、编译程序打交道最多的就是各种表格，因此选d。
5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。
6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。
7、b 8、c 9、d 10、c
二、多项选择题
1、编译程序各阶段的工作都涉及到 。
a．语法分析 b．表格管理 c．出错处理
d．语义分析 e．词法分析
2、编译程序工作时，通常有 阶段。
a．词法分析 b．语法分析 c．中间代码生成
d．语义检查 e．目标代码生成
解答
1．b、c 2. a、b、c、e
三、填空题
1、解释程序和编译程序的区别在于 。
2、编译过程通常可分为5个阶段，分别是 、语法分析 、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是 ，最后阶段的输出为 程序。
4、编译程序是指将 程序翻译成 程序的程序。 解答
是否生成目标程序 2、词法分析 中间代码生成 3、源程序 目标代码生成 4、源程序 目标语言
一、单项选择题
1、文法G：S→xSx|y所识别的语言是 。
a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx*
2、文法G描述的语言L(G)是指 。
a. L(G)={α|S+ ⇒α , α∈VT*} b. L(G)={α|S*⇒α, α∈VT*}
c. L(G)={α|S*⇒α,α∈(VT∪VN*)} d. L(G)={α|S+ ⇒α, α∈(VT∪VN*)}
3、有限状态自动机能识别 。
a. 上下文无关文法 b. 上下文有关文法
c.正规文法 d. 短语文法
4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立 。
a. 若f(a)>g(b)，则a>b b.若f(a)<g(b)，则a<b
c. a~b都不一定成立 d. a~b一定成立
5、如果文法G是无二义的，则它的任何句子α 。
a. 最左推导和最右推导对应的语法树必定相同
b. 最左推导和最右推导对应的语法树可能不同
c. 最左推导和最右推导必定相同
d. 可能存在两个不同的最左推导，但它们对应的语法树相同
6、由文法的开始符经0步或多步推导产生的文法符号序列是 。
a. 短语 b.句柄 c. 句型 d. 句子
7、文法G：E→E+T|T
T→T*P|P
P→(E)|I
则句型P+T+i的句柄和最左素短语为 。
a.P+T和i b. P和P+T c. i和P+T+i d.P和T
8、设文法为：S→SA|A
A→a|b
则对句子aba，下面 是规范推导。
a. SÞSAÞSAAÞAAAÞaAAÞabAÞaba
b. SÞSAÞSAAÞAAAÞAAaÞAbaÞaba
c. SÞSAÞSAAÞSAaÞSbaÞAbaÞaba
d. SÞSAÞSaÞSAaÞSbaÞAbaÞaba
9、文法G：S→b|∧(T)
T→T,S|S
则FIRSTVT(T) 。
a. {b,∧,(} b. {b,∧,)} c.{b,∧,(,，} d.{b,∧,),，}
10、产生正规语言的文法为 。
a. 0型 b. 1型 c. 2型 d. 3型
11、采用自上而下分析，必须 。
a. 消除左递归 b. 消除右递归 c. 消除回溯 d. 提取公共左因子
12、在规范归约中，用 来刻画可归约串。
a. 直接短语 b. 句柄 c. 最左素短语 d. 素短语
13、有文法G：E→E*T|T
T→T+i|i
句子1+2*8+6按该文法G归约，其值为 。
a. 23 B. 42 c. 30 d. 17
14、规范归约指 。
a. 最左推导的逆过程 b. 最右推导的逆过程
c. 规范推导 d. 最左归约的逆过程
[解答]
1、选c。
2、选a。
3、选c。
4、虽然a与b没有优先关系，但构造优先函数后，a与b就一定存在优先关系了。所以，由f(a)>g)(b)或f(a)<g(b)并不能判定原来的a与b之间是否存在优先关系：故选c。
5、如果文法G无二义性，则最左推导是先生长右边的枝叶：对于d，如果有两个不同的是了左推导，则必然有二义性。故选a。
6、选c。
7、由图2-8-1的语法树和优先关系可以看出应选b。

8、规范推导是最左推导，故选d。
9、由T→T,…和T→(… 得FIRSTVT(T))={(,，)}；
由T→S得FIRSTVT(S)⊂FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即
FIRSTVT(T)={b,∧,(,，}； 因此选c。
10、d 11、c 12、b 13、b 14、b
二、多项选择题
1、下面哪些说法是错误的 。
a. 有向图是一个状态转换图 b. 状态转换图是一个有向图
c.有向图是一个DFA d.DFA可以用状态转换图表示
2、对无二义性文法来说，一棵语法树往往代表了 。
a. 多种推导过程 b. 多种最左推导过程 c.一种最左推导过程
d.仅一种推导过程 e.一种最左推导过程
3、如果文法G存在一个句子，满足下列条件 之一时，则称该文法是二义文法。
a. 该句子的最左推导与最右推导相同
b. 该句子有两个不同的最左推导
c. 该句子有两棵不同的最右推导
d. 该句子有两棵不同的语法树
e.该句子的语法树只有一个
4、有一文法G：S→AB
A→aAb|ε
B→cBd|ε
它不产生下面 集合。
a. {anbmcndm|n,m≥0} b. {anbncmdm|n,m>0}
c. {anbmcmdn|n,m≥0} d. {anbncmdm|n,m≥0}
e. {anbncndn|n≥0}
5、自下而上的语法分析中，应从 开始分析。
a. 句型 b. 句子 c. 以单词为单位的程序
d. 文法的开始符 e. 句柄
6、对正规文法描述的语言，以下 有能力描述它。
a.0型文法 b.1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法
解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e
三、填空题
1、文法中的终结符和非终结符的交集是 。词法分析器交给语法分析器的文法符号一定是 ，它一定只出现在产生式的 部。
2、最左推导是指每次都对句型中的 非终结符进行扩展。
3、在语法分析中，最常见的两种方法一定是 分析法，另一是 分析法。
4、采用 语法分析时，必须消除文法的左递归。
5、 树代表推导过程， 树代表归约过程。
6、自下而上分析法采用 、归约、错误处理、 等四种操作。
7、Chomsky把文法分为 种类型，编译器构造中采用 和 文法，它们分别产生 和 语言，并分别用 和 自动机识别所产生的语言。
解答 1、空集 终结符 右
2、最左
3、自上而上 自下而上
4、自上而上
5、语法 分析
6、移进 接受
7、4 2 型 3型 上下文无关语言 正规语言 下推自动机 有限
四、判断题
1、文法 S→aS|bR|ε描述的语言是(a|bc)* ( )
R→cS
2、在自下而上的语法分析中，语法树与分析树一定相同。 （ ）
3、二义文法不是上下文无关文法。 （ ）
4、语法分析时必须先消除文法中的左递归。 （ ）
5、规范归约和规范推导是互逆的两个过程。 （ ）
6、一个文法所有句型的集合形成该文法所能接受的语言。 （ ）
解答 1、对 2、错 3、错 4、错 5、错 6、错
五、简答题
1、句柄 2、素短语 3、语法树 4、归约 5、推导
[解答]
1、句柄：一个句型的最左直接短语称为该句型的句柄。
2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。
3、语法树：满足下面4个条件的树称之为文法G[S]的一棵语法树。
①每一终结均有一标记，此标记为VN∪VT中的一个符号；
②树的根结点以文法G[S]的开始符S标记；
③若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；
④若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,…,XK，则A→X1,X2,…,XK，必然是G的一个产生式。
4、归约：我们称αγβ直接归约出αAβ，仅当A→γ 是一个产生式，且α、β∈(VN∪VT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。
5、推导：我们称αAβ直接推出αγβ，即αAβÞαγβ，仅当A→ γ 是一个产生式，且α、β∈(VN∪VT)*。如果α1Þα2Þ…Þαn，则我们称这个序列是从α1至α2的一个推导。若存在一个从α1αn的推导，则称α1可推导出αn。推导是归约的逆过程。
六、问答题
1、给出上下文无关文法的定义。
[解答]
一个上下文无关文法G是一个四元式（VT,VN,S, P），其中：
●VT是一个非空有限集，它的每个元素称为终结符号；
●VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=Φ；
●S是一个非终结符号，称为开始符号；
●P是一个产生式集合（有限），每个产生式的形式是P→α，其中，P∈VN，
α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。
2、文法G[S]：
S→aSPQ|abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
（1）它是Chomsky哪一型文法？
（2）它生成的语言是什么？
[解答]
（1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法G[S]是Chomsky1型文法，即上下文有关文法。
（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到：
SÞabQÞabc
SÞaSPQÞaabQPQÞaabPQQÞaabbQQÞaabbcQÞaabbcc
SÞaSPQÞaaSPQPQÞaaabQPQPQÞaaabPQQPQÞaaabPQPQQÞaaaPPQQQÞ
aaabbPqqqÞaaabbQQQÞaaabbbcQQÞaaabbbccQÞaaabbbccc
……
于是得到文法G[S]生成的语言L={anbncn|n≥1}
3、按指定类型，给出语言的文法。
L={aibj|j＞i≥1}的上下文无关文法。
【解答】
（1）由L={aibj|j＞i≥1}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→bS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法G[S]为：
G[S]：S→aSb|Sb|b
4、有文法G：S→aAcB|Bd
A→AaB|c
B→bScA|b
（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；
（2）写出句子acabcbbdcc的最左推导过程。
【解答】（1）分别画出对应两句型的语法树，如图2-8-2所示
句柄:AaB Bd

图2-8-2 语法树
（2）句子acabcbbdcc的最左推导如下：
SÞaAcBÞaAaBcBÞacaBcBÞacabcBÞacabcbScAÞacabcbBdcA
ÞacabcbbdcAÞacabcbbdcc
5、对于文法G[S]：
S→（L）|aS|a L→L, S|S
（1）画出句型（S,（a））的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。
【解答】
（1）句型（S,（a））的语法树如图2-8-3所示

（2）由图2-8-3可知：
①短语：S、a、(a)、S,(a)、(S,(a))；
②直接短语：a、S；
③句柄：S；
④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；

因此素短语为a。
6、考虑文法G[T]：
T→T*F|F
F→F↑P|P
P→（T）|i
证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。
【解答】
首先构造T*P↑（T*F）的语法树如图2-8-4所示。

由图2-8-4可知，T*P↑（T*F）是文法G[T]的一个句型。
直接短语有两个，即P和T*F；句柄为P。

一、单项选择题
1、词法分析所依据的是 。
a. 语义规则 b. 构词规则 c. 语法规则 d. 等价变换规则
2、词法分析器的输出结果是 。
a. 单词的种别编码 b. 单词在符号表中的位置
c. 单词的种别编码和自身值 d. 单词自身值
3、正规式M1和M2等价是指 。
a. M1和M2的状态数相等 b. M1和M2的有向弧条数相等
c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向弧条数相等
4、状态转换图（见图3-6-1）接受的字集为 。

a. 以 0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合
c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合
5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此， 。
a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好
c. 词法分析器分解为多个过程，由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段
解答 1、b 2、c 3、c 4、d 5、b
二、多项选择题
1、在词法分析中，能识别出 。
a. 基本字 b. 四元式 c. 运算符
d. 逆波兰式 e. 常数
2、令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为 。
a. b(ab)* b. b(ab)+ c.(ba)*b
d. (ba)+b e. b(a|b)
解答 1、a、c、e 2、a、b、d
三、填空题
1、确定有限自动机DFA是 的一个特例。
2、若二个正规式所表示的 相同，则认为二者是等价的。
3、一个字集是正规的，当且仅当它可由 所 。
解答 1、NFA 2、正规集 3、DFA（NFA）所识别
四、判断题
1、一个有限状态自动机中，有且仅有一个唯一终态。 （ ）
2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。 （ ）
3、自动机M和M′的状态数不同，则二者必不等价。 （ ）
4、确定的自动机以及不确定的自动机都能正确地识别正规集。 （ ）
5、对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。 （ ）
6、对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。 （ ）
7、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。 （ ）
8、对任何正规表达式e，都存在一个DFA M，满足L(G)=L(e)。 （ ）
解答 1 、2、3、错 4、5、6、7、8、正确
五、基本题
1、设M＝（{x,y}, {a,b}, f,x,{y}）为一非确定的有限自动机，其中f定义如下：
f（x,a）＝{x,y} f（x,b）＝{y}
f（y,a）＝φ f（y,b）＝{x,y}
试构造相应的确定有限自动机M′。
解答：对照自动机的定义M=(S,Σ,f,S0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFA M相应的状态图，如图3-6-2所示。

用子集法构造状态转换矩阵表3-6-3所示。
I Ia Ib
{x} {x,y} {y}
{y} — {x,y}
{x,y} {x,y} {x,y}
将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。
表3-6-4 状态转换矩阵
a b
0 2 1
1 — 2
2 2 2
即得到M′=（{0,1,2}, {a,b}, f,0, {1,2}），其状态转换图如图3-6-5所示。

将图3-6-5的DFA M′最小化。首先，将M′的状态分成终态组{1，2}与非终态组{0}；其次，考察{1,2}。由于{1,2}a={1,2}b={2}⊂{1,2}，所以不再将其划分了，也即整个划分只有两组{0}，{1,2}：令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图3-6-6所示化简DFA M′。

2、对给定正规式b*（d|ad）（b|ab）+，构造其NFA M；
解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的NFA M，如图3-6-7所示。