编译原理项目集的冲突

㈠ 编译原理笔记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)）但这会让问题更加复杂，故一般不采用。而二义文法无论向前看多少个终结符都无法解决二义性。

㈡ 计算机科学与技术中编译原理简答题

时间有点久记得不太真切，用通俗语言说，希望题主尽量查阅书籍参考资料自行验证理解。

1、什么是移进项目，什么是规约项目

这个是自顶向下和自下向上分析时候用到的。所谓移进就是不处理，所谓规约就是处理，合并，替换。比如当前符合某个正规式左部，就用这个正规式右部替换左部，称为规约。两种操作的目的都是为了分析整体是否符合语法树。

2、请给出生成C语言语句序列的文法（假定s表示任意一个语句，它为终结符）

关于这个，我感觉你描述的不是很清楚，因为C语言文法包含的正规式还是挺多的，如果单指statement的话，
statement_listà
statement
| statement_list statement

Statementà
| compound_statement
| expression_statement
| selection_statement
| iteration_statement
| jump_statement
再配合上相应的终结符。

3、能用上下文无关文法生成正规集吗？为什么？

可以。不过无法保证不含冲突。

4、计算first集和follow集对于构造自顶向下的语法分析器有什么作用？

可以用来排除冲突。例如移进-移进冲突，移进-规约冲突。

5、是否可能存在这样一个DFA，它的所有状态都是接受状态，包括其实状态，为什么？

这个爱莫能助，据我的构想是可以的，但是这样的DFA最终都会成为单一状态DFA。

㈢ 编译原理 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

㈣ 编译原理作业求助

单选
1. C
2. C
3. D
4. A

判断
5. 对
6. 错
7. 错
8. 错
9. 对
10. 错

㈤ 编译原理 A产生空和B的规约在一个项目集里是规约冲突吗

如果我们把同心的项目集合合并为一,就可能导致冲突,但是这种冲突不会是移进-规约冲突.因为如果存在这种冲突,则意味着对当前输入符号a,有一个项目[A→α.,a]要求以A→α进行规约,同时又有另一个项目[B→β.aγ,b]要求把a移进.这两个项目既然同处于合并之后的项目集中,则意味着在合并前,必有某个c使得[A→α.,a]和[B→β.aγ,c]同处于合并前的某一集合中.然而,这又意味着原来的LR(1)项目集就已经存在移进-规约冲突.从而文法不是LR(1)的,这与假设不符.事实上移进-规约冲突不依赖于搜索符号而只依赖于其心,因此,同心集合的合并不会引起新的移进-规约冲突

㈥ 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)文法。

㈦ 编译原理 文法题目

首先扩展文法为：
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

请采纳。

㈧ 同一依赖程序集的不同版本之间出现冲突 .net的怎么解决

会显示此警告，如果您的项目依赖项关系图包含对同一程序集的不同版本。
如果具有 app.config 文件，则 Visual Studio 可以添加绑定重定向到它。 绑定重定向所有程序集引用重定向到程序集的最高编号版本的强制说明。 Visual Studio 保存在 app.config 的重定向信息。 如果使用绑定重定向，则不会再出现此警告。
如果您决定不添加绑定重定向，项目将象以前一样继续引用程序集的同一版本。 但是，仍出现此警告。
更正此错误
双击该警告并选择 “是”，若收到提示， “希望通过添加绑定这些冲突重于 app.config 文件的记录定向?”

㈨ 编译原理文法题 求解

一看就是计科的 …………
我们都是 LL1 SLR1文法没怎么用过
进来问候下
有空加个好友 讨论下

㈩ 有关编译原理

⑴拓广文法 1 分
G[S ′ ]: S ′→ S ⑴
S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸
该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA ：

⑵ 该文法的 LR(0) 分析表：
状态 ACTION GOTO
a b # S A
0 S 2 1
1 S 3 acc
2 r 3 r 3 r 3
3 S 5 4
4 r 2 r 2 /S 6 r 2
5 r 5 r 5 r 5
6 S 2 7
7 r 4 /S 3 r 4 r 4
⑶ LR(0) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突状态。
该文法不是 LR(0) 文法
因为存在冲突状态： I 4 和 I 7
⑷ SLR(1) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突状态，冲突可用 FOLLOW 集解决。
该文法不是 SLR(1) 文法。
因为 FOLLOW(S)={a,b,#} ，所以无法解决冲突