多重定义的入口编译原理

A. 编译原理-LL1文法详细讲解

我们知道2型文法( CFG )，它的每个产生式类型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。

例如, 一个表达式的文法:

最终推导出 id + (id + id) 的句子，那么它的推导过程就会构成一颗树，即 CFG 分析树：

从分析树可以看出，我们从文法开始符号起，不断地利用产生式的右部替换产生式左部的非终结符，最终推导出我们想要的句子。这种方式我们称为自顶向下分析法。

从文法开始符号起，不断用非终结符的候选式(即产生式)替换当前句型中的非终结符，最终得到相应的句子。
在每一步推导过程中，我们需要做两个选择:

因为一个句型中，可能存在多个非终结符，我们就不确定选择那一个非终结符进行替换。
对于这种情况，我们就需要做强制规定，每次都选择句型中第一个非终结符进行替换(或者每次都选择句型中最后一个非终结符进行替换)。

自顶向下的语法分析采用最左推导方式，即总是选择每个句型的最左非终结符进行替换。

最终的结果是要推导出一个特定句子(例如 id + (id + id) )。
我们将特定句子看成一个输入字符串，而每一个非终结符对应一个处理方法，这个处理方法用来匹配输入字符串的部分，算法如下:

方法解析:

这种方式称为递归下降分析( Recursive-Descent Parsing )：

当选择的候选式不正确，就需要回溯( backtracking )，重新选择候选式，进行下一次尝试匹配。因为要不断的回溯，导致分析效率比较低。

这种方式叫做预测分析( Predictive Parsing )：

要实现预测分析，我们必须保证从文法开始符号起，每一个推导过程中，当前句型最左非终结符 A 对于当前输入字符 a ,只能得到唯一的 A 候选式。

根据上面的解决方法，我们首先想到，如果非终结符 A 的候选式只有一个以终结符 a 开头候选式不就行了么。
进而我们可以得出，如果一个非终结符 A ，它的候选式都是以终结符开头，并且这些终结符都各不相同，那么本身就符合预测分析了。

这就是S_文法，满足下面两个条件:

例子:

这就是一个典型的S_文法，它的每一个非终结符遇到任一终结符得到候选式是确定的。如 S -> aA | bAB , 只有遇到终结符 a 和 b 的时候，才能返回 S 的候选式，遇到其他终结符时，直接报错，匹配不成功。

虽然S_文法可以实现预测分析，但是从它的定义上看，S_文法不支持空产生式(ε产生式)，极大地限制了它的应用。

什么是空产生式(ε产生式)？

例子

这里 A 有了空产生式，那么 S 的产生式组 S -> aA | bAB ，就可以是 a | bB ,这样 a , bb , bc 就变成这个文法 G 的新句子了。

根据预测分析的定义，非终结符对于任一终结符得到的产生式是确定的，要么能获取唯一的产生式，要么不匹配直接报错。

那么空产生式何时被选择呢？

由此可以引入非终结符 A 的后继符号集的概念:
定义: 由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符 a 的集合，就是这个非终结符 A 的后继符号集，记为 FOLLOW(A) 。

因此对于 A -> ε 空产生式，只要遇到非终结符 A 的后继符号集中的字符，可以选择这个空产生式。
那么对于 A -> a 这样的产生式，只要遇到终结符 a 就可以选择了。

由此我们引入的产生式可选集概念:
定义: 在进行推导时，选用非终结符 A 一个产生式 A→β 对应的输入符号的集合，记为 SELECT(A→β)

因为预测分析要求非终结符 A 对于输入字符 a ,只能得到唯一的 A 候选式。
那么对于一个文法 G 的所有产生式组，要求有相同左部的产生式，它们的可选集不相交。

在 S_文法基础上，我们允许有空产生式，但是要做限制:

将上面例子中的文法改造:

但是q_文法的产生式不能是非终结符打头，这就限制了其应用，因此引入LL(1)文法。

LL(1)文法允许产生式的右部首字符是非终结符，那么怎么得到这个产生式可选集。
我们知道对于产生式:

定义: 给定一个文法符号串 α ， α 的 串首终结符集 FIRST(α) 被定义为可以从 α 推导出的所有串首终结符构成的集合。

定义已经了解清楚了，那么该如何求呢？
例如一个文法符号串 BCDe , 其中 B C D 都是非终结符， e 是终结符。

因此对于一个文法符号串 X1X2 … Xn ，求解 串首终结符集 FIRST(X1X2 … Xn) 算法:

但是这里有一个关键点，如何求非终结符的串首终结符集？

因此对于一个非终结符 A , 求解 串首终结符集 FIRST(A) 算法:

这里大家可能有个疑惑，怎么能将 FIRST(Bβ) 添加到 FIRST(A) 中，如果问文法符号串 Bβ 中包含非终结符 A ，就产生了循环调用的情况，该怎么办?

对于 串首终结符集 ，我想大家疑惑的点就是，串首终结符集到底是针对 文法符号串 的，还是针对 非终结符 的，这个容易弄混。
其实我们应该知道， 非终结符 本身就属于一个特殊的 文法符号串 。
而求解 文法符号串 的串首终结符集，其实就是要知道文法符号串中每个字符的串首终结符集:

上面章节我们知道了，对于非终结符 A 的 后继符号集 :
就是由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符的集合，记为 FOLLOW(A) 。

仔细想一下，什么样的终结符可以出现在非终结符 A 后面，应该是在产生式中就位于 A 后面的终结符。例如 S -> Aa ，那么终结符 a 肯定属于 FOLLOW(A) 。

因此求非终结符 A 的 后继符号集 算法：

如果非终结符 A 是产生式结尾，那么说明这个产生式左部非终结符后面能出现的终结符，也都可以出现在非终结符 A 后面。

我们可以求出 LL(1) 文法中每个产生式可选集:

根据产生式可选集，我们可以构建一个预测分析表，表中的每一行都是一个非终结符，表中的每一列都是一个终结符，包括结束符号 $ ，而表中的值就是产生式。
这样进行语法推导的时候，非终结符遇到当前输入字符，就可以从预测分析表中获取对应的产生式了。

有了预测分析表，我们就可以进行预测分析了，具体流程:

可以这么理解：

我们知道要实现预测分析，要求相同左部的产生式，它们的可选集是不相交。
但是有的文法结构不符合这个要求，要进行改造。

如果相同左部的多个产生式有共同前缀，那么它们的可选集必然相交。
例如:

那么如何进行改造呢？
其实很简单，进行如下转换:

如此文法的相同左部的产生式，它们的可选集是不相交，符合现预测分析。

这种改造方法称为 提取公因子算法 。

当我们自顶向下的语法分析时，就需要采用最左推导方式。
而这个时候，如果产生式左部和产生式右部首字符一样(即A→Aα)，那么推导就可能陷入无限循环。
例如:

因此对于:

文法中不能包含这两种形式，不然最左推导就没办法进行。

例如:

它能够推导出如下:

你会惊奇的发现，它能推导出 b 和 (a)* (即由 0 个 a 或者无数个 a 生成的文法符号串)。其实就可以改造成:

因此消除 直接左递归 算法的一般形式：

例如:

消除间接左递归的方法就是直接带入消除，即

消除间接左递归算法：

这个算法看起来描述很多，其实理解起来很简单：

思考 : 我们通过 Ai -> Ajβ 来判断是不是间接左递归，那如果有产生式 Ai -> BAjβ 且 B -> ε ,那么它是不是间接左递归呢？
间接地我们可以推出如果一个产生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那么这个产生式是不是间接左递归。

B. C++中两个文件读取一个.h时多个多重定义错误

从昨晚到现在查了很多东西，但结果却超级简单：
首先#include在编译时会被预处理器将.h中的所有内容拷贝到当前文件中， 如果.h中还include了别的.h， 则递归拷贝；
如果.h文件中没有头文件保护，即#ifndef ... #define ... #endif则如果某文件include 1.h和 3.h, 而1.h也#include了3.h， 则会有完全相同的两份3.h中的代码， 这样就直接报错了； 但加入了头文件保护后就可以保证在单一文件中只会编译一遍3.h的代码；
所以到目前为止如果加入了头文件保护，在单一文件中不会有重声明(定义)，编译可以通过，生成各个.o文件了， 头文件中定义的变量都定义并分配了空间，就你的问题而言，tool.o中有Map， 同时main.o中也有Map；
然后就是链接了，此时会将各.o中的全局符号加入全局符号表中，如果.o中有相同的全局变量则会报重定义， 即tool.o和main.o中的Map冲突了。

总结下：头文件保护只是保证在 单一文件中不会重复include， 但不保证在不同文件中重复include。

解决办法为在.h中只声明变量： extern map Map； 而在tool.cpp中定义： map Map;

多谢问题哈，终于搞清楚了这个问题！

C. 编译C程序出现多重定义，怎么解决

应该是你在2个c文件中都定义了全局的MmiUtil_WaitKeyMenu，可以声明为static，或者改个名字

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

E. 关于编译原理

可以自己写一个JPanel或者JComponent的子类，然后在子类中重写paint方法，在里面绘制背景图片。下面的部分是从我的代码里截出来的，不保证这样能用，只是给你个大体的丝路。学会了这个后自己重写组件就方便多了 public class ChessBoard extends JComponent{ private Image screen = null; public void paint(Graphics g) { if (screen != null) { g.drawImage(screen, (width - BOARDWIDTH) / 2, (height - BOARDHEIGHT) / 2, this); } else { screen = ChessBoard.this.createImage(BOARDWIDTH,BOARDHEIGHT); } } }

F. 编译原理:考虑文法G[S]

考虑文法：
(1)消去左递归后:
S→a|∧|(T)
T→ST’
T’ →,ST’|ε
(2)计算每个非终结符的FIRST集合和FOLLOW集合:
FIRST(S)={a,∧,(}
FIRST(T)={ a,∧,(}
FIRST(T’)={,ε}
FOLLOW(S)={,#}
FOLLOW(T)={ )}
FOLLOW(T’)={ )}
预测分析表如下:
\x09a\x09∧\x09(\x09)\x09,\x09#
S\x09S→a\x09S→∧\x09S→(T)\x09\x09\x09
T\x09T→ST’\x09T→ST’\x09T→ST’\x09\x09\x09
T’\x09\x09\x09\x09T’ →ε\x09T’ →,ST’\x09
构造的预测分析表中没有多重入口,所以改造后的文法是LL(1)文法.

G. 关于multiple defination of (多重定义 )的错误

1.
不要在.h里面声明变量，而是在.c(.cpp)里面定义int mm=3;
然后在A.h里面用extern int mm;

2.
extern不要赋值。

ps：还没解决？
回楼上，没用的，那个能防止重复include，但是不能解决这里的问题。
头文件里面是不提倡也不应该定义一个变量的。
如果熟悉VC的win32程序，就知道那个theApp也是放在cpp文件里的，而不是头文件。

H. 关于vs2010运行多文件程序老是出现“fatal error LNK1169: 找到一个或多个多重定义的符号”的问题

头文件是要声明的，例如你的程序，在cpp结尾的程序的开头都要写#include"resource.h"就好了

I. 多重定义怎么解决

链接时多重定义怎么办？一般解决方案是：只保留一个定义的地方就好了，这对强迫症，很友好！但往往有时又嫌麻烦，或者杂七杂八的的原因导致了，两个定义都保留，但只让链接时，只链接第一个遇到的定义函数！


其实吧，如果这多重定义的函数是存在于不同的库，一般默认都只会找第一个遇到的库里面的函数就好了。

但是，因为，链接的最小单元一般是文件，.o。如果a.o和b.o同时存在test1()，但是a.o有test2()，b.o有test3()，结果这两个接口函数都会被系统使用，那么a.o和b.o就会被同时链接进去*。这就是为何会报多重定义的错误。

为了让这种情况下，链接器还是不报错，还是只会找第一个遇到的库里面的函数。可以使用以下参数：

-Wl,-z,multidefs或者Wl,'-z muldefs'，以及--allow-multiple-definition

让ld在遇到重复定义时候，只处理第一个定义。