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-），女，漢族，四川內江人，本科，初級工程師，現任職務：助理工程師，研究方向：計算機應用。