符号栈编译原理

A. 这个在编译原理中什么意思啊

大学课程为什么要开设编译原理呢？这门课程关注的是编译器方面的产生原理和技术问题，似乎和计算机的基础领域不沾边，可是编译原理却一直作为大学本科的必修课程，同时也成为了研究生入学考试的必考内容。编译原理及技术从本质上来讲就是一个算法问题而已，当然由于这个问题十分复杂，其解决算法也相对复杂。我们学的数据结构与算法分析也是讲算法的，不过讲的基础算法，换句话说讲的是算法导论，而编译原理这门课程讲的就是比较专注解决一种的算法了。在20世纪50年代，编译器的编写一直被认为是十分困难的事情，第一Fortran的编译器据说花了18年的时间才完成。在人们尝试编写编译器的同时，诞生了许多跟编译相关的理论和技术，而这些理论和技术比一个实际的编译器本身价值更大。就犹如数学家们在解决着名的哥德巴赫猜想一样，虽然没有最终解决问题，但是其间诞生不少名着的相关数论。推荐参考书虽然编译理论发展到今天，已经有了比较成熟的部分，但是作为一个大学生来说，要自己写出一个像TurbocC,Java那样的编译器来说还是太难了。不仅写编译器困难，学习编译原理这门课程也比较困难。第一本书的原名叫《CompilersPrinciples,Techniques,andTools》,另外一个响亮的名字就是龙书。原因是这本书的封面上有条红色的龙，也因为獗臼樵诒嘁朐?砘?嘴域确实?忻?所以很多国外的学者都直接取名为龙书。最近机械工业出版社已经出版了此书的中文版，名字就叫《编译原理》。该书出的比较早，大概是在85或86年编写完成的，作者之一还是着名的贝尔实验室的科学家。里面讲解的核心编译原理至今都没有变过，所以一直到今天，它的价值都非凡。这本书最大的特点就是一开始就通过一个实际的小例子，把编译原理的大致内容罗列出来，让很多编译原理的初学者很快心里有了个底,也知道为什么会有这些理论，怎么运用这些理论。而这一点是我感觉国内的教材缺乏的东西，所以国内的教材都不是写给愿意自学的读者，总之让人看了半天，却不知道里面的东西有什么用。第二本书的原名叫《ModernCompilerDesign》,中文名字叫做《现代编译程序设计》。该书由人民邮电出版社所出。此书比较关注的是编译原理的实践，书中给出了不少的实际程序代码，还有很多实际的编译技术问题等等。此书另外一个特点就是其现代而字。在传统的编译原理教材中，你是不可能看到如同Java中的垃圾回收等算法的。因为Java这样的解释执行语言是在近几年才流行起来的东西。如果你想深入学习编译原理的理论知识，那么你肯定得看前面那本龙书，如果你想自己动手做一个先进的编译器，那么你得看这本《现代编译程序设计》。第三本书就是很多国内的编译原理学者都推荐的那本《编译原理及实践》。或许是这本书引入国内比较早吧，我记得我是在高中就买了这本书，不过也是在前段时间才把整本书看完。此书作为入门教程也的确是个不错的选择。书中给出的编译原理讲解也相当细致，虽然不如前面的龙书那么深入，但是很多地方都是点到为止，作为大学本科教学已经是十分深入了。该书的特点就是注重实践，不过感觉还不如前面那本《现代编译程序设计》的实践味道更重。此书的重点还是在原理上的实践，而非前面那本那样的技术实践。《编译原理及实践》在讲解编译原理的各个部分的同时，也在逐步实践一个现代的编译器TinyC.等你把整本书看完，差不多自己也可以写一个TinyC了。作者还对Lex和Yacc这两个常用的编译相关的工具进行了很详细的说明，这一点也是很难在国内的教材中看到的。推荐了这三本教材，都有英文版和中文版的。很多英文好的同学只喜欢看原版的书，不我的感觉是这三本书的翻译都很不错，没有必要特别去买英文版的。理解理论的实质比理解表面的文字更为重要。编译原理的实质几乎每本编译原理的教材都是分成词法分析，语法分析（LL算法，递归下降算法，LR算法），语义分析，运行时环境，中间代码，代码生成，代码优化这些部分。其实现在很多编译原理的教材都是按照85,86出版的那本龙书来安排教学内容的，所以那本龙书的内容格式几乎成了现在编译原理教材的定式，包括国内的教材也是如此。一般来说，大学里面的本科教学是不可能把上面的所有部分都认真讲完的，而是比较偏重于前面几个部分。像代码优化那部分东西，就像个无底洞一样，如果要认真讲，就是单独开一个学期的课也不可能讲得清楚。所以，一般对于本科生，对词法分析和语法分析掌握要求就相对要高一点了。词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法，LL自顶向下算法和LR自底向上算法。LL算法还好说，到了LR算法的时候，困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了，又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器，一般都是用工具Yacc来生成，实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法，因为其实践十分简单，那么就应该要求每个学生都能自己写。当然，现在也有不少好的LL算法的语法分析器，不过要是换在非C平台，比如Java,Delphi,你不能运用YACC工具了，那么你就只有自己来写语法分析器。等学到词法分析和语法分析时候，你可能会出现这样的疑问：词法分析和语法分析到底有什么？就从编译器的角度来讲，编译器需要把程序员写的源程序转换成一种方便处理的数据结构（抽象语法树或语法树）,那么这个转换的过程就是通过词法分析和语法分析的。其实词法分析并非一开始就被列入编译器的必备部分，只是我们为了简化语法分析的过程，就把词法分析这种繁琐的工作单独提取出来，就成了现在的词法分析部分。除了编译器部分，在其它地方，词法分析和语法分析也是有用的。比如我们在DOS,Unix,Linux下输入命令的时候，程序如何分析你输入的命令形式，这也是简单的应用。总之，这两部分的工作就是把不规则的文本信息转换成一种比较好分析好处理的数据结构。那么为什么编译原理的教程都最终把要分析的源分析转换成树这种数据结构呢？数据结构中有Stack,Line,List这么多数据结构，各自都有各自的特点。但是Tree这种结构有很强的递归性，也就是说我们可以把Tree的任何结点Node提取出来后，它依旧是一颗完整的Tree。这一点符合我们现在编译原理分析的形式语言，比如我们在函数里面使用函树，循环中使用循环，条件中使用条件等等，那么就可以很直观地表示在Tree这种数据结构上。同样，我们在执行形式语言的程序的时候也是如此的递归性。在编译原理后面的代码生成的部分，就会介绍一种堆栈式的中间代码，我们可以根据分析出来的抽象语法树，很容易，很机械地运用递归遍历抽象语法树就可以生成这种指令代码。而这种代码其实也被广泛运用在其它的解释型语言中。像现在流行的Java,.NET，其底层的字节码bytecode,可以说就是这中基于堆栈的指令代码的。关于语义分析，语法制导翻译，类型检查等等部分，其实都是一种完善前面得到的抽象语法树的过程。比如说，我们写C语言程序的时候，都知道，如果把一个浮点数直接赋值给一个整数，就会出现类型不匹配，那么C语言的编译器是怎么知道的呢？就是通过这一步的类型检查。像C++语言这中支持多态函数的语言，这部分要处理的问题就更复杂了。大部编译原理的教材在这部分都是讲解一些比较好的处理策略而已。因为新的问题总是在发生，旧的法不见得足够解决。本来说，作为一个编译器，起作用的部分就是用户输入的源程序到最终的代码生成。但是在讲解最终代码生成的时候，又不得不讲解机器运行环境等内容。因为如果你不知道机器是怎么执行最终代码的，那么你当然无法知道如何生成合适的最终代码。这部分内容我自我感觉其意义甚至超过了编译原理本身。因为它会把一个计算机的程序的运行过程都通通排在你面前，你将来可能不会从事编译器的开发工作，但是只要是和计算机软件开发相关的领域,都会涉及到程序的执行过程。运行时环境的讲解会让你更清楚一个计算机程序是怎么存储，怎么装载，怎么执行的。关于部分的内容，我强烈建议大家看看龙书上的讲解，作者从最基本的存储组织，存储分配策略，非局部名字的访问，参数传递，符号表到动态存储分配(malloc,new)都作了十分详细的说明。这些东西都是我们编写平常程序的时候经常要做的事情，但是我们却少去探求其内部是如何完成。关于中间代码生成，代码生成,代码优化部分的内容就实在不好说了。国内很多教材到了这部分都会很简单地走马观花讲过去，学生听了也只是作为了解，不知道如何运用。不过这部分内容的东西如果要认真讲，单独开一学期的课程都讲不完。在《编译原理及实践》的书上，对于这部分的讲解就恰到好处。作者主要讲解的还是一种以堆栈为基础的指令代码，十分通俗易懂，让人看了后，很容易模仿，自己下来后就可以写自己的代码生成。当然，对于其它代码生成技术，代码优化技术的讲解就十分简单了。如果要仔细研究代码生成技术，其实另外还有本叫做《》,那本书现在由机械工业出版社引进的，十分厚重，而且是英文原版。不过这本书我没有把它列为推荐书给大家，毕竟能把龙书的内容搞清楚，在中国已经就算很不错的高手了，到那个时候再看这本《》也不迟。代码优化部分在大学本科教学中还是一个不太重要的部分，就是算是实践过程中，相信大家也不太运用得到。毕竟，自己做的编译器能正确生成执行代码已经很不错了，还谈什么优化呢？编译原理的课程毕竟还只是讲解原理的课程，不是专门的编译技术课程。这两门课程是有很大的区别的。编译技术更关注实际的编写编译器过程中运用到的技术，而原理的课

B. 寻求pascal计算四则混合运算的原理

在编译原理里有讲,利用堆栈.
我来简单的说下.
程序中有2个栈,一个放数值,一个放操作符

A 程序开始后,第一次的操作符和数值先入栈
B 获取下一个操作符NextOP
C 把NextOP和栈顶操作符进行优先级比较

情况1.NextOP优先级比栈顶操作符要高的话,把NextOP压入操作符栈.继续步骤B
情况2.NextOP优先级比栈顶操作符要低的话,用栈顶运行符,数值栈拿顶的2个值做运算,运算结果压入数值栈.重复步骤C 如果操作符栈为空,运算结束,步骤D

D 运算结果在数值栈
回答者： cpplyy - 千总 四级 10-8 09:12
1.分治搜索法 每次找到最后运算的符号,对其左右分别深搜到出结果为止
2.堆栈处理法 分数栈与符号栈 先定义常量数组(判断运算\入栈\错误),然后从左到右依次运算 数进数栈 符号与符号栈内比较运算\入栈\错误操作 运算从数栈里拿数与后面的计算 然后结果入数栈 最后结果在数栈里
回答者： LXYXYNT - 举人 四级 10-8 12:50
堆栈就行了
回答者： sd542927172 - 见习魔法师 二级 10-9 20:09
堆栈

表达式的计算应用相当广泛，比如电力调度系统中的计算遥测、车站票务系统中的票价类型计算公式等。
本文讲述中置表达式转换为后置表达式和后置表达式的求值算法，并给出实现的C++源代码，同时给出一个相当简洁的堆栈C++模板类。

中缀表达式到后缀表达式的转换
要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。 如果所有操作符优先级一样，那么求值顺序就取决于它们的结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。
转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：
1. 初始化一个空堆栈，将结果字符串变量置空。
2. 从左到右读入中缀表达式，每次一个字符。
3. 如果字符是操作数，将它添加到结果字符串。
4. 如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆栈。
5. 如果字符是个开括号，把它压入堆栈。
6. 如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。
7. 如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。

后缀表达式求值
对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作符的优先级也不再起作用了。您可以用如下算法对后缀表达式求值：
1. 初始化一个空堆栈
2. 从左到右读入后缀表达式
3. 如果字符是一个操作数，把它压入堆栈。
4. 如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。如果您不能够弹出两个操作数，后缀表达式的语法就不正确。
5. 到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。

写在这里不方便，讲解的话+Q244957727
给分拉给分啦~
回答者： wind_teller - 魔法师 四级 10-10 21:57
表达式的计算应用相当广泛，比如电力调度系统中的计算遥测、车站票务系统中的票价类型计算公式等。
本文讲述中置表达式转换为后置表达式和后置表达式的求值算法，并给出实现的C++源代码，同时给出一个相当简洁的堆栈C++模板类。

中缀表达式到后缀表达式的转换
要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。 如果所有操作符优先级一样，那么求值顺序就取决于它们的结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。
转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：
1. 初始化一个空堆栈，将结果字符串变量置空。
2. 从左到右读入中缀表达式，每次一个字符。
3. 如果字符是操作数，将它添加到结果字符串。
4. 如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆栈。
5. 如果字符是个开括号，把它压入堆栈。
6. 如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。
7. 如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。

后缀表达式求值
对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作符的优先级也不再起作用了。您可以用如下算法对后缀表达式求值：
1. 初始化一个空堆栈
2. 从左到右读入后缀表达式
3. 如果字符是一个操作数，把它压入堆栈。
4. 如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。如果您不能够弹出两个操作数，后缀表达式的语法就不正确。
5. 到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空
在编译原理里有讲,利用堆栈.
我来简单的说下.
程序中有2个栈,一个放数值,一个放操作符

A 程序开始后,第一次的操作符和数值先入栈
B 获取下一个操作符NextOP
C 把NextOP和栈顶操作符进行优先级比较

情况1.NextOP优先级比栈顶操作符要高的话,把NextOP压入操作符栈.继续步骤B
情况2.NextOP优先级比栈顶操作符要低的话,用栈顶运行符,数值栈拿顶的2个值做运算,运算结果压入数值栈.重复步骤C 如果操作符栈为空,运算结束,步骤D

D 运算结果在数值栈
.分治搜索法 每次找到最后运算的符号,对其左右分别深搜到出结果为止
2.堆栈处理法 分数栈与符号栈 先定义常量数组(判断运算\入栈\错误),然后从左到右依次运算 数进数栈 符号与符号栈内比较运算\入栈\错误操作 运算从数栈里拿数与后面的计算 然后结果入数栈 最后结果在数栈里

C. 栈的应用举例：数制转换，表达式求值

关于表达式的分析与求值是计算机软件专业中“编译原理”课程极其重要的部分，主要用于最初的词法分析。其表示方式有：前缀、中缀、后缀表示法。其数据结构可以使用一个堆栈来表示。具体的实现代码，我以前使用的书籍是《C语言大全》，那上面就有完整的、现成的代码，可以供你参考运行。同时你还可以参考《编译原理》相关的教材。
但是由于我已经很久没有编写编译原理方面的程序了，况且编写并亲自调试通过该程序，难度还是比较大的。所以我也无法亲自给你编写一个完整表达式分析与求值的程序。只能够给你提供一些思路和线索。
另外，关于不同数制之间的转换问题，这个倒是不难解决，可以采用通常的算法就是短除法，然后将每一次的余数采取“倒排”即可。例如：将十进制的 15 转换为二进制。
2|15(1
--
2|7(1
-
2|3(1
-
2|1(1

-
0
则十进制的 15 为二进制的：1111。

D. 编译原理什么是素短语

编译原理中，素短语是至少含义一个终结符，并且自身不包含任何更小素短语的一种短语。

素短语是一种特殊的短语，它是一个递归的定义，至少含有一个终结符，并且除它自身之外不再含任何更小的素短语，所谓最左素短语就是处于句型最左边的素短语的短语。

一个算符优先文法G的任何句型的最左素短语是满足以下条件的最左子串NaNb…NcNdN(N是非终结符，a,b,c,d是终结符)。例如：句型T+T*F+id，T*F是最左素短语，id是素短语。

(4)符号栈编译原理扩展阅读：

通过语法树可以得知素短语：

1、每个句型对应一棵语法树

2、每棵语法树的叶子结点从左到右排列构成一个句型

3、每棵语法树的子树的叶子结点从左到右排列构成一个短语

4、每棵语法树的简单子树（只有父子两层结点）的叶子结点从左到右排列构成一个简单(直接)短语。

5、素短语是至少包含一个终结符的短语，但它不能包含其它素短语。

E. 谁能够解释下编译原理中什么是FIRSTVT,和LASTVT，尽量浅显易懂点谢谢

Firstvt和Lastvt是为了画算符优先关系表的（就是表里面填优先大于小于等于的那个）。
然后要注意他们可都是终结符的集合。
Firstvt
找Firstvt的三条规则：如果要找A的Firstvt，A的候选式中出现：
A->a.......，即以终结符开头，该终结符入Firstvt
A->B.......，即以非终结符开头，该非终结符的Firstvt入A的Firstvt
A->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入Firstvt

Lastvt
找Lastvt的三条规则：如果要找A的Lastvt，A的候选式中出现：
A->.......a，即以终结符结尾，该终结符入Lastvt
A->.......B，即以非终结符结尾，该非终结符的Lastvt入A的Lastvt
A->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Firstvt

F. 编译原理

编译原理)：利用编译程序从源语言编写的源程序产生目标程序的过程； 用编译程序产生目标程序的动作。 编译就是把高级语言变成计算机可以识别的2进制语言，计算机只认识1和0，编译程序把人们熟悉的语言换成2进制的。

编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段：词法分析；语法分析；语义检查和中间代码生成

(6)符号栈编译原理扩展阅读：

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

编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。

而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。