A. 计算机考研：数据结构常用算法解析(3)
第三章
例如：Exp=a*b+(c-d/e)*f
若 Exp=a*b+(c-d/e)*f 则它的
前缀式为： +*ab*-c/def
中缀式为： a*b+c-d/e*f
后缀式为： ab*cde/-fx+
综合比较它们之间的关系可得下列结论：
1.三式中的 “操作数之间的相对次序相同”;
(二叉树的三种访问次序中，叶子的相对访问次序是相同的)
2.三式中的 “运算符之间的的相对次序不同”;
3.中缀式丢失了括号信息，致使运算的次序不确定;
(而前缀和后缀运算只需要一个存储操作数的栈，而中缀求值需要两个栈，符号栈和操
作数栈)
4.前缀式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;
5.后缀式的运算规则为：
·运算符在式中出现的顺序恰为表达式的运算顺序;
·每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;
6.中缀求值的运算规则：
如果是操作数直接入栈。
如果是运算符。这与当前栈顶比较。个如果比当前栈顶高，则入栈，如果低则说明当前栈顶是最高的必须把他先运算完了。用编译原理的话就是说当前栈顶已经是最左素短语了)
其实中缀表达式直接求值和把中缀表达式转化成后缀表达式在求值的过程惊人的相似，只不过是直接求值是求出来，而转化成后缀是输出来。
中缀表达式直接求值算法：
OPNDType EvalueExpression()
{ //OPTR 和OPND分别为运算符栈和操作数栈
InitStack(OPTR);Push(OPTR,’#’);
InitStack(OPND);c=getchar();
While(c!=’#’|| GetTop(OPTR)!=’#’)
{
If(!IN(c,OP) ) //如果是操作数，直接入操作数栈
{ push(OPND,c);
c=getchar();
}
Else //如果是运算符，则与当前的栈顶比较
{
Switch(Precede(GetTop(OPTR),c))
{
Case ‘<’: push(OPTR,c);//比当前栈顶高，这入栈
c=getchar();
break;
Case ’= ’:Pop(OPTR,x); //在我们设计的优棚肆枯先级表中，
c=getchar(); //只有’(’和’)’存在相等的情况，
break; //而在规约中间只存在‘(’‘)’
//所以我们直接把’(’弹出就可以了
Case ‘>’: //比当前栈顶低，则要把栈顶先运算完(先规约)
pop(OPTR,theta); //把栈顶运算符弹出
Pop(OPND,b); //取出操作数，并且是前操作数雹搭
Pop(OPND,a); //在下面(栈的先进后出)
Push(OPND,Operate(a,theta,b)); //运算的结果入栈
//(他是其他运算符的操作数)
Break;
}//Switch
}//链洞else
}//whild
Return GetTop(OPND);//操作数栈中最后剩下的就是整个表达式的结果了。
}
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/
B. 编译原理-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(α) 包括空串ε，那么这个产生式是不是间接左递归。
C. 编译原理中的文法的产生式的括号有什么用
加上括号，是让编程渣谈磨语侍悄言机器 最先识别。
就不用 从 E 执行到 F——EIid
先执行 括号如斗里面的
D. 编译原理：真子串、前缀的问题
Let X be a set, and w∈X∗ be a word, i.e. an element of the free monoid on X. A word v∈X∗ is called prefix of w when a second word z∈X∗ exists such thatx=vz. A proper prefix of a word u is a prefix v of u not equal to u (sometimes v is required to be non-empty).
E. 编译原理 无法提取左公因子,都有公共前缀
就是有公共前缀才可以提取左公因子啊……
bool -> expr expr'
expr' -> e
| < expr
| <= expr
| > expr
| >= expr
后面几个比较操作符如果还算公因子的话，还可以继续提：
用expr1 代替 < expr 和 <= expr，删除这两个右部，添加右部 <expr1，添加产生式expr1-> expr|= expr
用expr2 代替 > expr 和 >= expr，删除这两个右部，添加右部 >expr2，添加产生式expr2-> expr|= expr
F. 编译原理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)就是假如两个产生式集相同则将它们合并为一个，几合并同心集。
G. 求助一个C语言的问题 int i=3； 则k=（i++）+（i++）+（i++）；执行过后k的
这个问题给你说了答案，以后你还会遇到很多次这样的问题。
不如直接告诉你原理来得实在。
关于++i，i++的问题看下面看完你再不会，打死我吧！)，请认真读完。然后再回来看你这道题。完全就是小儿科。
++是C++的自增运算符，作用是使变量自加1；——是自减运算符，作用是使变量自减1.++和——有两种用法，一种是前缀用法，一种是后缀用法。前缀用法如：++i、——i ，后缀用法如i++、i——，前缀用法跟后缀用法的差别在于前缀时++i的值为完成i加1后的值，——i为完成i减1后的值。例如：假设i的初值为3，执行cout<<++i<<endl；输出结果为4，而执行cout<<i++<<endl；输出结果为3.——运算符同理。这是世人皆知的常识，我们不再讨论，现在我们来讨论一点有趣的东西，看如下代码：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<(i++)+(i++)+(i++)<<endl;
cout<<i<<endl;
return 0;
}
问，第一次和第二次输出的结果分别是多少？
有人说，是12和6.理由是，表达式从左至右开始计算，因为第一个括号内++运算符是后缀用法，i的初值为3，所以，第一个括号的值是3，计算完第一个括号之后，i自加1，变成4，然后计算第二个括号，第二个括号里的++也是后缀用法，所以，值为4，执行完第二个括号后，i再加1，变成5，接下计算第三个括号，第三个括号里的++也是后缀用法，所以，第三个括号的值为5，然后计算第三个括号相加的和，即3+4+5=12.这个理由看起来不错，似乎应当是这样。然而，运行结果却让人大跌眼镜，竟然是9和6.这是怎么回事呢？说起来也很简单，和州这是因为很多编译系统规定，在遇源渣到一条计算表达式中同时出现若干i++、i——的情况时，在当前语句中并不执行i的自增和自减，i的初值是多少，i++和i——的值就是多少，当这条表达式执行完成之后，再将i连续自加或自减若干次。
再看如下代码：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<(++i)+(++i)+(++i)<<endl;
cout<<i<<endl;
return 0;
}
问，第一次和第二次输出的结果分别是多少？
有人说，结果应该是4+5+6=15和6.理由我想大家都想明白，我就不多说了。还有人总结了上例的雹棚悄经验，认为，输出结果应该是9和6.我们来运行一下这个程序，看看谁说得对……
好了，运行结果出来了，不过这不是什么好结果，可能很多人看完会抓狂，结果尽然是神鬼莫测的18和6.为什么呢？道理跟上例差不多，那就是很编译系统规定，连续多个前缀式++和——运算符出现在同一个运算表达式中时，先将变量连续自加或自减N次，然后判定++i的值为i+N.
为了验证上面的说法，请看下面的代码：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<(++i)+(i++)+(++i)<<endl;
cout<<i<<endl;
return 0;
}
按照我们上面的推测，第一个输出语句应当是这样执行的：首先，扫描整条运算表达式（++i）+（i++）+（++i），发现有两处++的前缀式用法，于是，将i连续自加两次，然后开始计算表达式，第一个括号是++i，判定为5，第二个括号是i++，判定值为5，第三个括号是++i判定值为5，最后，计算结果5+5+5=15.因为表达式中有一个i++，所以执行计算完之后将i的值再自加1，变为6.
运行程序，验证一下，果然，结果就是15和6.
下面在来讨论一下网上很多C++论坛里讨论得很多的int i=3；问++i+++i+i++的值是多少的问题。
我看到CSDN里也有人在讨论这个问题，很多人在回帖，答案似乎多种多样，有说是12的，有说是18的，更有说是9的，更有一条回帖十分搞笑——“答案是×××，这是很早以前我的一个很牛×的老师教我的解法得出的结果”。我很无语。学过编译原理的人都知道，“++i+++i”这一段根本就无法解析，编译系统从左至右扫描整条语句，先遇到++i，判断出来是一个i的前缀自加运算，然后接着扫描，遇到一个+，+是一个二目运算符，它的左边已经有一个运算数++i了，系统就向右搜索第二个运算数，又遇到一个+，++比+的运算级别要高，这时，编译系统就将两个+看成一个整体来处理，既然是++，编译系统就认定，肯定它的左边或右边有一个变量，编译系统先搜索左边，发现有一个 i，是个变量，于是它就将i和其后的++组合起来，这时问题就发生了，也就是说第一个i被编译系统绑架到它后面的++那里去了，那么i前面的++是个什么东西呢？编译系统是无法搞明白的，它会倒回去重新搜索++前面是否有左值，发现没有，因此它就认为++是一个缺少左值的自增运算符，于是提示提示用户：'++' needs l-value
我们写个程序验证一下上面的推测：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<++i+++i+i++<<i<<endl;
cout<<i<<endl;
return 0;
}
果然，编译时有一个错误，提示error C2105： '++' needs l-value ，证实了我们的推测。这个问题的讨论使我们得出一个结论：如果一个变量Ni的两侧都有++或——运算符并且Ni左边的表达式不能分解成X+或X-的形式，那么编译就会出错，X是有值变量。结论有点绕口，举例说明吧：
程序1
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<i+++i++<<endl;
cout<<i<<endl;
return 0;
}
程序1说明：表达式i+++i++中第二个i的左右两侧都有++，于是我们看第二个i的左侧，左侧是i+++，可以分解为（i++）+，其中“（i++）”是有值变量，符合X+的形式，因此i+++i++是合法表达式，可以通过编译。
程序2
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<++i+++i<<endl;
cout<<i<<endl;
return 0;
}
程序2说明：表达式++i+++i中第一个i的左右两侧都有++，于是我们看第一个i的左侧，左侧是++，不能分解成X+的形式，因此该表达式不合法。编译时会提示：error C2105： '++' needs l-value
下面，我们再来讨论一下关于i+++i的问题。曾经有人问，表达式i+++i在编译时，编译系统是怎么拆分的？究竟是拆分成（i++）+i呢，还是拆分成i+（++i）。
这个问题本身的答案很简单，是（i++）+i，不明白的自己去看编译原理。这个问题令人感兴趣之处并不在这里，不知道大家注意到i+（++i）这个表达式有什么奇特的地方没有？假设有如下程序：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<i+(++i)<<endl;
cout<<i<<endl;
return 0;
}
大家可以猜测一下程序的运行结果。
很多人可能会说是7和4，看起来的确像这样。但是，非常遗憾，实验再一次证明，你可能猜错了，结果是8和4.为什么是8和4呢？前面说过int i=3；cout<< （++i）+（++i） <<endl；的情况，编译系统会先将i连续自加1两次，然后将（++i）一律判定为5进行结算，输出10.这里同理，编译系统现将i自加1，然后再对i+（++i）做运算，（++i）的值判定为4，i的值也判定为4，因此计算结果是8.
下面我们来讨论int i=3；cout<<i++<<“ and ”<<i++<<endl；的问题。首先请看如下程序，猜测输出结果：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<i++<<" and "<<i++<<endl;
cout<<i<<endl;
return 0;
}
很多人认为输出结果应该是“3 and 4”和5.我们把代码复制到VC6.0或VC2005上编译运行一下，看看结果……
好了，运行结束，结果是“4 and 3”和5.Oh！My God！Can you tell me why？上帝不会告诉你，我可以告诉你。这是因为很多编译系统在处理输出流时，是从右至左的。在上面的例子中，两处i++处于同一个输出序列中，编译系统会先计算处于右侧的第二个i++，这时i的值为3，因此右侧i++的值为3，之后，i+1变成4，计算第一个i++的值为4，计算完之后将i的值再加1，最后才是输出结果，所以输出结果是4和3.
H. 将中序表达式转化成后序表达式
首先这里涉及到了编译原理的中间代码结构的相关知识。
简单的了解，如我们想要实现 A与B的相加，其有三种情况：
前缀表达式：运算符在前，则有 +AB
中缀表达式：运算符在中，则有 A+B
后缀表达式：运算符在后，则有 AB+
根据上述基本知识，后通过中缀表达式 a*b+c*(d-e)/f转为后缀表达式的过程如下：
(1)根据算术符号的优先级来进行操作即可，遇到括号则先运算括号中的式子，这与平时的运算过程其实是差不多的。
故转换如下：
ab* + c*(de-)/f
ab* + c(de-)*/f
ab* + cde-*f/
ab* cde-*f/＋
最终后缀表达式： ab* cde-*f/＋
第二种方法：即是利用数据结构正宏源中的栈来进行解决，其的规则有如下：
遇到 ”（ “则入栈
遇到其他的绝逗操作数即abc等则加入表达式
遇到运算符（如+ - * /）则入栈，且需要注意，当处理到运算符的时候，需要将比当前处理的运算符优先级高或同级的符号从栈中依次弹出，直到遇到比当前处理的举态运算符优先级低的或遇到 ”( "才停止弹出。即若当前扫描到了 ＋号且栈顶存在＊号，因为乘号的运算符优先级高于加号，则需要将＊号从栈中弹出加入表达式中，当然当加号遇到同优先级的减号时，也要将当前处于栈顶的减号从栈顶弹出并加入表达式中。
当遇到“）”时则将已在栈中的“（”即左括号之前的栈中符号依次弹出加入表达式中。
具体的流程可以查阅2014年计算机考研408真题的相关题型。
I. 编译原理写出表达式-a-(b*c/(c-d)+(-b)*a)的前缀式和后缀式。
abcde/+*+ 画一个运算树 先算的d/e根为"/"，子结点为d，e 然后算c+d/e，根为“+”，左右子结点为e和上面的子树 b*(c+d/e)根为"*"，作子树为b，右子树为(c+d/e)的树 最后a为右结点，"+"为根，左子树为刚才得到的树。 该树后序遍历即得。
J. 什么叫活前缀,用通俗的话解答下,或者简单的例子。 这个题是编译原理的。
活前缀：右句型的前缀，而且其右端不会超过该句型的最右边句柄的末端。
右句型：最右推导可得到的句型。
最右推导：每步推导都替代最右非终结符的推导。
推导：我们说αBγ推导出αβγ，是说存在产生式B->β。
产生式：左边为非终结符，右边为终结符与非终结符组合成的串。
非终结符：是字符串的集合。
终结符：组成语言的词。如c语言中的2，a，int，if等。
句型：开始符经过若干步推导后得到的串。
前缀：如abc的前缀为a、ab、abc。
开始符：开始符是整个语言的集合。
句柄：非形式的，句柄是和某个产生式右部匹配的字符串，把句柄归约成产生式左部的非终结符，可以得到最右推导的逆过程的一步。形式的定义为：开始符s经过若干步最右推导得到αBγ，αBγ经过一步最右推导得到αβγ，若γ为终结符的集合，则β为句柄。举例：
E->E+E|E*E|-E|(E)|id，对于id+id*id，其中一个最右推导为E->E+E->E+E*E->E+E*id->E+id*id->id+id*id。在id+id*id归约成E+id*id的过程中，最左边的id是句柄。E+id*id归约成E+E*id时，最左边的id是句柄，把E+E*id归约成E+E*E时，id是句柄。把E+E*E归约成E+E时E*E是句柄。E+E归约成E时，E+E是句柄。
归约：可理解为把产生式右边的串用产生式左边的非终结符代替。
注1：再说一下活前缀，举个例子，比如E+E*E归约成E+E，句柄是E*E，那么它的活前缀就是E、E+、E+E、E+E*、E+E*E。又比如id+id*id归约成E+id*id，句柄是最左边的id，那么它的活前缀是id，因为不能超过句柄。
注2：至于为什么要给出活前缀的定义和如何用归约的方法实现语法分析，还要进一步学习。