摘要：语法分析是编译程序的核心部分，对其进行研究有着重要意义。本文介绍了编译过程语法分析阶段使用的LL(1)预测分析法的相关概念，并以算术表达式为例，对LL(1)语法分析器的构成及具体实现进行了详细的阐述。
关键词：语法分析；算术表达式；LL(1)文法；LL(1)语法分析器；
Arithmetic Expressions of LL(1) Parser
Zhang Huixia
（College of Computer and Information Technology, Liaoning Normal University, Dalian Liaoning 116000, China）
Abstract:Syntax analysis is the core part of compiler.It is of great significance to study it .This paper introduces the relevant concepts of LL(1) predictive analysis method used in the parsing stage of compilation process,and takes arithmetic expressions for example to elaborate the structure and concrete implementation of LL(1) parser.
Key words：syntax analysis; arithmetic expressions; LL(1) grammar; LL(1) parser
前言
编译程序极大地推动了计算机的发展，现已成为计算机系统的重要组成部分。语法分析(Syntax Analysis)是编译程序的第二阶段，也是核心功能之一，其主要任务是根据语法规则检查词法分析器输出的单词序列是否是该语言文法的正确句子[1]。在语法分析阶段，比较常见的方法主要分为自顶向下和自底向上两大类，其中LL(1)预测分析法是一种自顶向下的语法分析方法，它因直观易判定，执行效率高而被广泛应用。本文详细讲述了LL(1)文法的特点，以及LL(1)预测分析表构造的方法，进而设计LL(1)分析器来判断某句子是否符合算数表达式文法的语法规则并输出语法分析过程。
1 LL(1)文法
自顶向下的语法分析方法，就是从文法的开始符号出发，反复使用产生式向下推导出与输入符号串完全匹配的句子[2]。但由于同一产生式的左部可能会出现多个不同的右部，即多个候选式，这种情况下语法分析程序就不能根据当前输入符号来唯一确定产生式进行替换，因此会产生回溯现象，大大降低程序的效率。而且就算针对回溯现象进行逐一试探，含有左递归的文法也不能正常进行语法分析，会进入死循环状态。因此，为了避免左递归和回溯现象，需要对文法进行一定的限制，即通过构造LL(1)文法来进行确定的自顶向下的语法分析。
LL(1)中的第一个L表示将单词符号串从左到右进行扫描，第二个L表示最左推导，即每次都用产生式右部去替换符号串最左边的非终结符，1表示分析时每步只需向右查看一个符号。LL(1)文法的具体定义如下：若一个文法G不含左递归、对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交，且对文法中每个非终结符A若它存在某个候选首符集里包含ε而FIRST(A)∩FOLLOW(A)=Φ,则称该文法 G为LL(1)文法[3]。
2 LL(1)语法分析器
LL(1)语法分析器是完成语法分析的核心部分。它由一张预测分析表table、一个先进后出的分析栈S、一个预测分析控制程序这3部分构成，如图1所示。分析表table是一个二维数组，其中算术表达式文法的非终结符为分析表的行标题，终结符号和输入结束符#组成了分析表的列标题，二维数组元素table[E][i]存放的是产生式或出错标志，表示当前分析栈的栈顶是E，当前输入字符为i，下一步需要用到的产生式为table[E][i]所存放的内容；分析栈S存放的是文法符号，当文法和符号串确定后，它随着分析过程不断变化；控制程序是根据分析表以及分析栈来控制整个语法分析的过程，即由分析栈、栈顶元素、符号串当前输入字符来确定下一步。
图1 LL(1)分析器模型
3 LL(1)语法分析器的具体实现——以算术表达式为例
3.1 设计LL(1)文法
LL(1)语法分析器的实现是针对LL(1)文法而言的，因此在进行预测分析之前，需要先判断给定文法是不是LL(1)文法，若不是，则需要将给定文法进行提取左公共因子和消除左递归操作来将非LL(1)文法转化为等价的LL(1)文法。本文以简单算术表达式文法为例，在消除了左递归之后，得到的文法结果如下：
.png)
在进行了初步的消除左递归操作之后，需要求解给定文法的非终结符的FIRST集合和FOLLOW集合，从而求解所有产生式的SELECT集合来判定该文法是否是LL(1)文法。只有同一非终结符的各个产生式的SELECT集合互不相交，才能说明该文法是LL(1)文法，可进行确定的自顶向下的语法分析。笔者求解上述改进后的算术表达式文法G[E]的SELECT集合的结果如下：
.png)
由此可见，文法G[E]为LL(1)文法。
3.2 构造LL(1)预测分析表
在确定给定文法是LL(1)文法后，需要构造文法G[E]的LL(1)预测分析表。对每个终结符用a表示,若a∈在SELECT(A→a)中，则需要把产生式A→a写入预测分析表table[A][a]中[4]。结果如表1所示：
.png)
3.3 LL(1)语法分析程序算法
（1） 创建预测分析表table、分析栈s、终结符集VT、非终结符集VN 等数据结构，并对其进行初始化；
（2）输入：经过词法分析产生的符号串，以简单算术表达式i+i#为例；
（3）#入栈，开始符号E入栈；
（4）重复比较分析栈栈顶符号X和剩余字符串的最左字符（当前分析字符）a,对于任何X和a,每次都执行下述可能的动作之一：
若X∈VN , ①当X=a=‘#’时,则语法匹配成功；②当X=a≠‘#’时，则X出栈，输入字符后移一位。
若X∈VT，查看分析表，①表中元素非空时，X出栈，产生式右部逆序入栈，输入字符后移一位；②表中元素为ε时，则X出栈，输入字符a保持不变；③表中元素为错误标志时，语法分析错误，调用出错程序。
（5）输出：若语法匹配成功，则输出该表达式的语法分析过程；否则输出错误标志。根据上述的LL(1)语法分析程序，符号串i+i#的语法分析过程如表2所示：
.png)
4 结语
语法分析是编译过程中不可或缺的阶段，对其研究有利于深入了解编译原理的相关知识。本文主要采用表驱动的LL(1)预测分析法，用C语言完成了算术表达式的LL(1)语法分析器设计。但是本程序不仅仅局限于算术表达式文法，还可进一步扩充，只要给定文法，即可判断该文法是否是LL(1)文法，紧接着通过LL(1)语法分析器进行语法分析，进而判断某一输入串是否是该文法的正确句子。
参考文献：
[1] 王生原，董渊，张素琴，等. 编译原理[ M] . 北京：清华大学出版社, 2015.
[2] 尹大力. 编译原理计算机辅助教学系统的研制[J]. 长春理工大学学报，2002，25(03):44-46.
[3] 王一宾，陈文莉，陈义仁. 语法分析方法研究评述及其应用[J]. 计算机工程与设计，2007，28（13）.
[4] 杨奎河，李宝树. 语法分析中的LL预测分析器改进设计研究[J]. 系统工程与电子技术，2002，24（12）.