论文部分内容阅读
摘要：栈在计算机科学领域具有广泛的应用，正确理解语法分析中栈的原理对数据结构中线性结构的应用以及编译程序的教学具有重要意义。
关键词：栈；后进先出；语法分析；编译器
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）17-0067-02
1概述
在计算机算法与数据结构课程的教学中，栈（stack）是一种非常重要的线性结构，而栈是限定仅在表尾进行插人和删除操作的一种线性表。在栈中，允许进行插人和删除的一端称为栈顶，不允许插入和删除的一端称为栈底，栈的修改是按后进先出的原则进行的，因此栈又称为后进先出的线性表，简称LIFO线性表。
栈在计算机科学领域具有广泛的应用，如求表达式的值及递归到非递归，只要问题满足后进先出原则，均可使用栈作为其数据结构。在计算机系统软件中，各种高级语言的编译系统也离不开栈的使用，比如利用栈进行语法检查、函数的调用等，本文以栈在编译程序语法分析的应用为主线，对栈进行剖析，希望对计算机相关课程的教学与应用有所启示。
2编译程序的语法分析方法
编译程序是现代计算机系统的基本组成部分，其基本任务是将源语言程序翻译成等价的目标语言程序。其中语法分析（syntax analysic）是编译程序的核心部分，其功能是以词法分析器生成的单词符号序列作为输入，根据语言的语法规则，识别出各种语法成分，并在分析过程中进行语法检查，检查所给单词符号序列是否是该语言文法的正确句子。在编译程序中，常用的语法分析方法有：预测分析法、递归子程序法、算符优先分析法、LR分析法。而各种语法分析方法中都使用了相应的分析算法结合栈进行语法分析。
2.1预测分析法
预测分析法是一种高效的自顶向下的语法分析方法，预测分析程序采用表驱动的方式来实现，具有一个输入缓冲区、一个先进后出栈、一张预测分析表和一个输出流。
预测分析程序的总体结构如下图：
从以上算法可知，预测分析程序是根据栈顶符号X和当前输入符号a来决定语法分析器的动作，从而进一步进行语法分析。其中分析栈用来存放句型分析过程中动态产生的文法符号序列，开始时，把识别符号置于分析栈顶，每当分析栈顶是非终结符号，展开时把它出栈，然后按逆序下推入展开的规则的右部各个符号，因而，分析栈记录了分析活动经历。编译程序的预测分析语法分析法的优点是效率高、便于维护而且可以自动生成。
2.2递归子程序法
递归子程序法是比较简单直观易于构造的一种语法分析方法，是一种无回溯的自顶向下分析技术，其实现思想是让相应的识别程序由一组子程序组成，每个子程序的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按LL（1）形式唯一地确定选择某个产生式进行推导。由于遞归子程序法对每个过程可能存在直接或间接递归调用，所以对某个过程在退出之前可能又被调用，通常在入口时需保留某些信息，出口时恢复。递归过程遵循先进后出规律，所以通常开辟先进后出栈来处理。
采用递归下降子程序法构造语法分析器的算法步骤如下：
1）构造文法G；
2）改造文法G：包括消除文法二义性、消除左递归、提取左因子。
3）求每个产生式的FIRST集和语法变量的FOLLOW集；
4）检查文法G是不是LL（1）文法，若是按照LL（1）文法绘制语法图；如果不是LL（1）文法，需要进行文法等价变换，附加新的“信息”。
5）化简语法图；按照语法图为每个语法变量设置一个子程序。
递归子程序法实现思想简单清晰明了，各子程序的流程图几乎就是文法规则的图解描述，并且能灵活在各子程序中添加语义处理工作。递归子程序法易于手工实现，许多高级程序设计语言，如C、PASCAL等语言都采用递归子程序法。但缺点是对文法的要求较高，必须是LL（1）文法，且递归调用较多，运行速度较慢。
2.2算符优先分析法
算符优先分析法是仿照算术表达式的四则运算而提出的一种语法分析文法，其基本思想是将句型中的终结符当作“算符”，通过比较相邻算符的优先次序来确定句型的可归约串并进行归约。
令S为分析栈，用于存放以寄存归约或待形成最左素短语的符号串，k为栈S的深度，工作单元a存放当前读入的终结符号，文法G算符优先分析法的算法可描述为：
在算符优先识别算法的实现中，须同时考虑分析栈的实现和优先关系的确定，其实现思想简单直观，所需存储容量小，且速度快被广泛应用于识别各类表达式。算符优先文法并不适合所有的文法，要求文法必须是满足算符优先文法才能用此方法进行语法分析。
2.3 LR分析法
LR分析法是一种自下而上进行规范归约的语法分析文法。LR分析器的基本原理是将句柄（产生式右部）的识别过程划分为若干状态，分析器根据当前的状态确定是否找到了句柄。
一个LR分析器由3个部分组成：总控程序、分析表、分析栈（包括文法符号栈和相应的状态栈），分析器的动作由栈顶状态和当前输入符号决定是否需向前查看输入符号。LR分析器的工作过程如下图所示：
关键词：栈；后进先出；语法分析；编译器
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）17-0067-02
1概述
在计算机算法与数据结构课程的教学中，栈（stack）是一种非常重要的线性结构，而栈是限定仅在表尾进行插人和删除操作的一种线性表。在栈中，允许进行插人和删除的一端称为栈顶，不允许插入和删除的一端称为栈底，栈的修改是按后进先出的原则进行的，因此栈又称为后进先出的线性表，简称LIFO线性表。
栈在计算机科学领域具有广泛的应用，如求表达式的值及递归到非递归，只要问题满足后进先出原则，均可使用栈作为其数据结构。在计算机系统软件中，各种高级语言的编译系统也离不开栈的使用，比如利用栈进行语法检查、函数的调用等，本文以栈在编译程序语法分析的应用为主线，对栈进行剖析，希望对计算机相关课程的教学与应用有所启示。
2编译程序的语法分析方法
编译程序是现代计算机系统的基本组成部分，其基本任务是将源语言程序翻译成等价的目标语言程序。其中语法分析（syntax analysic）是编译程序的核心部分，其功能是以词法分析器生成的单词符号序列作为输入，根据语言的语法规则，识别出各种语法成分，并在分析过程中进行语法检查，检查所给单词符号序列是否是该语言文法的正确句子。在编译程序中，常用的语法分析方法有：预测分析法、递归子程序法、算符优先分析法、LR分析法。而各种语法分析方法中都使用了相应的分析算法结合栈进行语法分析。
2.1预测分析法
预测分析法是一种高效的自顶向下的语法分析方法，预测分析程序采用表驱动的方式来实现，具有一个输入缓冲区、一个先进后出栈、一张预测分析表和一个输出流。
预测分析程序的总体结构如下图：
从以上算法可知，预测分析程序是根据栈顶符号X和当前输入符号a来决定语法分析器的动作，从而进一步进行语法分析。其中分析栈用来存放句型分析过程中动态产生的文法符号序列，开始时，把识别符号置于分析栈顶，每当分析栈顶是非终结符号，展开时把它出栈，然后按逆序下推入展开的规则的右部各个符号，因而，分析栈记录了分析活动经历。编译程序的预测分析语法分析法的优点是效率高、便于维护而且可以自动生成。
2.2递归子程序法
递归子程序法是比较简单直观易于构造的一种语法分析方法，是一种无回溯的自顶向下分析技术，其实现思想是让相应的识别程序由一组子程序组成，每个子程序的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按LL（1）形式唯一地确定选择某个产生式进行推导。由于遞归子程序法对每个过程可能存在直接或间接递归调用，所以对某个过程在退出之前可能又被调用，通常在入口时需保留某些信息，出口时恢复。递归过程遵循先进后出规律，所以通常开辟先进后出栈来处理。
采用递归下降子程序法构造语法分析器的算法步骤如下：
1）构造文法G；
2）改造文法G：包括消除文法二义性、消除左递归、提取左因子。
3）求每个产生式的FIRST集和语法变量的FOLLOW集；
4）检查文法G是不是LL（1）文法，若是按照LL（1）文法绘制语法图；如果不是LL（1）文法，需要进行文法等价变换，附加新的“信息”。
5）化简语法图；按照语法图为每个语法变量设置一个子程序。
递归子程序法实现思想简单清晰明了，各子程序的流程图几乎就是文法规则的图解描述，并且能灵活在各子程序中添加语义处理工作。递归子程序法易于手工实现，许多高级程序设计语言，如C、PASCAL等语言都采用递归子程序法。但缺点是对文法的要求较高，必须是LL（1）文法，且递归调用较多，运行速度较慢。
2.2算符优先分析法
算符优先分析法是仿照算术表达式的四则运算而提出的一种语法分析文法，其基本思想是将句型中的终结符当作“算符”，通过比较相邻算符的优先次序来确定句型的可归约串并进行归约。
令S为分析栈，用于存放以寄存归约或待形成最左素短语的符号串，k为栈S的深度，工作单元a存放当前读入的终结符号，文法G算符优先分析法的算法可描述为：
在算符优先识别算法的实现中，须同时考虑分析栈的实现和优先关系的确定，其实现思想简单直观，所需存储容量小，且速度快被广泛应用于识别各类表达式。算符优先文法并不适合所有的文法，要求文法必须是满足算符优先文法才能用此方法进行语法分析。
2.3 LR分析法
LR分析法是一种自下而上进行规范归约的语法分析文法。LR分析器的基本原理是将句柄（产生式右部）的识别过程划分为若干状态，分析器根据当前的状态确定是否找到了句柄。
一个LR分析器由3个部分组成：总控程序、分析表、分析栈（包括文法符号栈和相应的状态栈），分析器的动作由栈顶状态和当前输入符号决定是否需向前查看输入符号。LR分析器的工作过程如下图所示：