LL（1）文法分析器的研究与分析

摘 要：在计算机编程领域中，语法分析是编译程序的核心部分，它有着极其重要的地位，语法分析的作用是在词法分析识别单词符号串的基础上，分析并判断程序的语法结构是否符合语法规则。目前语法分析包含为自顶向下的分析方法和自底向上的分析方法两大类。明确文法分析的方法时，选用实用的方法对文法进行分析。本文主要采用自顶向下的分析方法，对LL（1）文法做出适当的分析与研究，LL（1）文法的功能是利用LL（1）控制程序和相关文法生成LL（1）分析表，对输入符号串进行自上而下的分析过程。

关键词：LL（1）分析法；自顶向下

1 原理概述

LL（1）文法使用的是确定的自顶向下的分析技术。其中LL（1）的代表的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将使用的是最左推导，1表明的是只需要向右看一个符号便可以决定如何推导，也就是说选择哪一个规则进行推导。

在对LL（1）文法的判别中，要铭记步骤即首先计算FIRST集，然后计算FOLLOW集和SELLECT集，最后判断是否为LL（1）文法，在此基础上再进行句子的分析。

2 文法规则说明

2.1 词法规则

在本文中，讨论的字符可以规定为终结符或非终结符，但“#”作为空串处理不可以作为终结符或非终结符去处理。

2.2 文法规则

（1）在产生式中，右边的字符不全是由终结符组成。

（2）如果在两个产生式中相同的左边字符，它们的右边一定是由不同的终结符或非终结符开始的。

3 算法设计

3.1 表驱动的LL（1）分析器

LL（1）分析法的基础思想是根据输入串的当前輸入来唯一确定选用某一条产生式来进行推导，当这个输入符号与推导的第一个符号相同时，再取出下一个输入串的符号，继续确定下一个推导应该选用的规则：如此下去直到推出被分析的输入串为止。

一个LL（1）分析器由一张LL（1）分析表、一个先进后出的分析栈以及一个控制程序组成，如图1所示：

（1）输入串是待分析的符号串，它以边界符“#”作为结束标志。

（2）分析栈中存放的是分析过程中的文法符号。开始时栈底已经存入了一个“#”作为标示，然后再压入文法的开始符号；当分析栈中只剩下“#”标示时，说明输入串指针也指向了串尾的“#”标示，这时表明分析成功。

（3）在本程序中概括了相应文法的全部信息。二维数组中的每一行与文法的一个终结符相关联，而每一列与文法的一个终结符或者是“#”标示相关联。

3.2 表驱动的LL（1）分析器

为了构造分析表N，要预先定义和构造文法的相关集合FIRST集合FOLLOW集，其中需要注意的是：

FIRST（α）={a|α->a...，a∈Vt}，在此其中需要注意的是ε∈FIRST（α），换句话说α的所有可能推导的开头终结符或可能的ε。

FOLLOW（A）={a|S->...Aa...，a∈Vt}，S->...Aa，说明边界符#∈FOLLOW（A）也就是所有句型中出现在紧随A之后的非终结符。

对于FIRST集合的确定：

FIRST集合最终是对产生式右部的字符串而言的，其关键是求出非终结符的FIRST集合，其中知道终结符的FIRST集合就是它自己，所以求出非终结符的FIRST集合后，就很直观地了解了每个字符串的FIRST集合。确定FIRST集主要有两种方法：

（1）直接收取：对形如S->a…的产生式（a是终结符），把a收入到FIRST（S）中。

（2）反复传送：对形入S->A…的产生式（其中A是非终结符），应把FIRST（A）中的全部内容传送到FIRST（S）中，换句话说只需要把第一个非终结符的FIRST集传过去。

对于FOLLOW集合的确定：

我们都知道FOLLOW集合是针对非终结符而言的，FOLLOW（A）所表达的是句型中非终结符A所有可能的后随终结符号的集合，特别地，“#”是识别符号的后随符。注意FOLLOW集合是从开始符号S开始推导。其求法主要有以下几种：

（1）直接收取：注意产生式右部的每一个形如“…Aa…”的组合，把a直接收入到FOLLOW（A）中。因a是紧跟在A后的终结符。

（2）直接收取：对形如“…SA…”（A是非终结符）的组合，把FIRST（A）直接收入到FOLLOW（S）中.

（3）直接收取：若S->…A，即以A结尾，则#∈Follow（A）

（4）反复传送：对形如S->…A的产生式（其中A是非终结符），应把Follow（S）中的全部内容传送到Follow（A）中。

总之：Follow集比First要复杂一点。

当确定好FIRST集和Follow集之后，就可以对LL（1）分析表进行构建了，具体如图2所示：

4 关于文法的判断

要想确定一个文法是不是LL（1）文法，需要对SELLECT集合进行确定，对于SELLECT集来说，在上文中已经求出了FIRST集合FOLLOW集，通过它们SELECT集就很好确定了，Select集的作用是将first集和follow集进行合并，如果两个文法的左端都是A，若他们的select集交集为空，表明他们是两个无关的，不会产生不确定性的文法即该文法是LL（1）文法，反之，则表明文法不是LL（1）文法。

在SELECT集确定的过程中需要知道的是：

（1）如果α是终结符，那么SELECT（A->α）={α}。

（2）如果α是“#”，那么SELECT（A->α）=FOLLOW（A）。

（3）如果α是非终结符，分为下列两种情况：

①如果a=>#，则SELECT（A->α）=（FIRST（α）-#）U FOLLOW（A）。

②如果！a=>#，则SELECT（A->α）=FIRST（α）。

5 其他说明

本文中涉及的程序是由JAVA所编写的，在程序中LL类表示的含有终态集和非终态集，其中所设计的方法全部都为静态方法，在程序中，当构建好LL（1）分析表后，输入需要分析的串就可以得到相关的分析表。程序流程图如图3所示：

6 总结

递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL（1）文法。它的基本思想是，对文法中的每个终结符编写一个函数（或子程序），每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用。在选用自顶向下分析技术时，首先必须判断所给文法是否是LL（1）文法，然后编写构造LL（1）语法分析程序。因而对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL（1）文法。

参考文献：

[1]陈火旺.程序设计语言编译原理.国防工业出版社，2006.

[2]胡元义.编译原理实践教程.西安电子科技大学出版社，2010.

[3]刘淼.LL（1）文法的研究[D].2011.

作者简介：邓丽慧（1988-），女，汉族，四川内江人，本科，初级工程师，现任职务：助理工程师，研究方向：计算机应用。