堆栈在语法分析中的应用
2014-05-14张媛
张 媛
(天津市河东区职工大学 天津 300162)
计算机的应用中有多种高级语言，把这些高级语言翻译成对应的机器语言，这一过程就是编译。众所周知，编译原理在整个工作过程中通常分为词法分析、语法分析、语义分析和中间代码生成，代码优化以及目标代码生成这几个阶段，每一个阶段都会实现不同的功能。在整个编译过程中，堆栈都起着重要的作用，以下将就堆栈在语法分析中的应用进行说明。
所谓语法分析，就是在词法分析的基础上，通过分析输入串对高级语言的语法结构进行分析，分为自上而下的语法分析和自下而上的语法分析两种方法。
1 自上而下语法分析中堆栈的应用
在自上而下的语法分析中，从文法开始符号出发，利用所有的产生式，通过最左推导，为输入符号串自上而下地建立一棵语法树。在消除回溯和直接左递归后，即可利用栈来进行分析。自上而下语法分析中的一种有效方法是预测分析法，需要用到总控程序、预测分析表和一个先进后出栈，如图1所示。
图1 预测分析模型图Fig.1 Forecasting analysis model
在预测分析法中，栈底中最初存放“#”和文法开始符号，总控程序每次都要根据栈顶元素和新输入的符号来进行工作，若栈顶元素为终结符号，则：
①若栈顶元素＝输入终结符号≠“#”，则匹配成功，此时将栈顶元素弹出，将指针指向新的输入符号进行分析。②若栈顶元素＝输入终结符号＝“#”，说明整个输入符号串分析完成，结束分析过程。③若栈顶元素是非终结符号，则需要查看预测分析表，找到相应的产生式，将栈顶元素弹出后，产生式右部的所有符号按照反序依次压入堆栈中，形成新的栈顶元素。
假设有文法 G[S]：S→S＋S│S*S│a，该文法存在直接左递归，消除直接左递归得到新的文法：S→aS’，S’→＋SS’│*SS’│ε对输入符号串 a＋a*a 的优先分析过程如表1所示，其中栈存放分析过程中出现的文法符号序列。
表1 自上而下语法分析对符号串a＋a*a的分析过程表Tab.1 Table of analysis process for String a＋a*a via topdown syntax analysis
2 自下而上语法分析中堆栈的应用
自下而上的语法分析同样也是要建立一棵语法树，但它是从叶结点出发，利用所有产生式，逐步向上构造子树，直至得到根结点，也就是文法的开始符号。它的主导思想是“移进—规约”，是推导的逆过程，自上而下分析法是要为输入符号串找一个最左推导，而自下而上分析法则是要找到输入符号串的句柄，每次都对句柄进行规约，从而得到一个规范规约的过程。自下而上分析法中最常用的就是 LR分析法。在LR分析法中，需要用到LR分析程序、分析表和分析栈，如图2所示。
图2 LR分析模型图Fig.2 LR analysis model diagram
在该模型中，分析栈分为状态栈和符号栈两部分，状态栈中存放输入过程中的不同状态，栈顶元素为当前状态，而符号栈中存放的是现行输入符号，由当前状态栈的栈顶元素和现行输入符号来决定下一个动作。分析栈主要包括4种情况：
① 移进。在这种情况下，当前输入符号进入符号栈，而下一个输入符号则变为当前输入符号，查action表，将下一状态进入状态栈，作为新的栈顶元素。
② 规约。按照相应的产生式进行规约，若产生式右端共有n个字符，则同时将状态栈和符号栈两个栈顶弹出 n个元素，并将规约后的符号进入符号栈，作为新的栈顶元素，再查goto表，得到新的状态进入状态栈。
③ 接受。根据输入符号串进行移进和规约操作后，在符号栈中得到了开始符号及“#”号，则分析完成，整个字符串匹配成功。
④ 报错。除了以上动作外，其余都属于出错情况，此时应中止分析，调用出错处理程序，进行出错处理。
对于文法 G[E]：S→S＋L│L，L→L*M│M，M→(S)│a及输入符号串 a*a＋a，我们用 LR 分析法的分析过程，如表2所示。
3 结 论
栈在整个编译原理的各个过程中都起着重要的作用。进行语法分析时，在自上而下分析方法中用来存放分析过程中出现的字符串序列，在自下而上分析法中分为状态栈和符号栈，分别存放分析过程中的状态及即将输入的字符串序列。
［1］ 黄贤英，曹琼，王珂珂. 编译原理及实践教程(2版)[M]. 北京：清华大学出版社，2012.
［2］ 王晓斌，陈文宇. 程序设计语言与编译(3版)[M]. 北京：电子工业出版社，2009.
［3］ 何炎祥，伍春香，王汉飞. 编译原理[M]. 北京：机械工业出版社，2010.
［4］ 李文生. 编译原理与技术[M]. 北京：清华大学出版社，2009.
［5］ Alfred V Aho，Monica S，etc.Compilers：Principles，Techniques，and Tools(2,nd ed.)[M]. 北京：机械工业出版社，2011.
