算术表达式的 LL(1)语法分析器
张会霞
(辽宁师范大学 计算机与信息技术学院，辽宁 大连 116000)
摘要：语法分析是编译程序的核心部分，对其进行研究有着重要意义。本文介绍了编译过程语法分析阶段使用的LL(1)预测分析法的相关概念，并以算术表达式为例，对LL(1)语法分析器的构成及具体实现进行了详细的阐述。
关键词：语法分析；算术表达式；LL(1)文法；LL(1)语法分析器；
ArithmeticExpressions 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)分析器来判断某句子是否符合算术表达式文法的语法规则并输出语法分析过程。
1LL(1)文法
自顶向下的语法分析方法，就是从文法的开始符号出发，反复使用产生式向下推导出与输入符号串完全匹配的句子[2]。但由于同一产生式的左部可能会出现多个不同的右部，即多个候选式，这种情况下语法分析程序就不能根据当前输入符号来唯一确定产生式进行替换，因此会产生回溯现象，大大降低程序的效率。而且就算针对回溯现象进行逐一试探，含有左递归的文法也不能正常进行语法分析，会进入死循环状态。因此，为了避免左递归和回溯现象，需要对文法进行一定的限制，即通过构造LL(1)文法来进行确定的自顶向下的语法分析。
LL(1)中的第一个L表示将单词符号串从左到右进行扫描，第二个L表示最左推导，即每次都用产生式右部去替换符号串最左边的非终结符，1表示分析时每步只需向右查看一个符号。LL(1)文法的具体定义如下：若一个文法G不含左递归、对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交，且对文法中每个非终结符A若它存在某个候选首符集里包含ε而FIRST(A)∩FOLLOW(A)=Φ,则称该文法 G为LL(1)文法[3]。
2LL(1)语法分析器
LL(1)语法分析器是完成语法分析的核心部分。它由一张预测分析表table、一个先进后出的分析栈S、一个预测分析控制程序这3部分构成，如图1所示。分析表table是一个二维数组，其中算术表达式文法的非终结符为分析表的行标题，终结符号和输入结束符#组成了分析表的列标题，二维数组元素table[E][i]存放的是产生式或出错标志，表示当前分析栈的栈顶是E，当前输入字符为i，下一步需要用到的产生式为table[E][i]所存放的内容；分析栈S存放的是文法符号，当文法和符号串确定后，它随着分析过程不断变化；控制程序是根据分析表以及分析栈来控制整个语法分析的过程，即由分析栈、栈顶元素、符号串当前输入字符来确定下一步。
图
1 LL(1)分析器模型
3LL(1)语法分析器的具体实现——以算术表达式为例
3.1设计LL(1)文法
LL(1)语法分析器的实现是针对LL(1)文法而言的，因此在进行预测分析之前，需要先判断给定文法是不是LL(1)文法，若不是，则需要将给定文法进行提取左公共因子和消除左递归操作来将非LL(1)文法转化为等价的LL(1)文法。本文以简单算术表达式文法为例，在消除了左递归之后，得到的文法结果如下：
