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

摘 要：在計(jì)算機(jī)編程領(lǐng)域中，語(yǔ)法分析是編譯程序的核心部分，它有著極其重要的地位，語(yǔ)法分析的作用是在詞法分析識(shí)別單詞符號(hào)串的基礎(chǔ)上，分析并判斷程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。目前語(yǔ)法分析包含為自頂向下的分析方法和自底向上的分析方法兩大類。明確文法分析的方法時(shí)，選用實(shí)用的方法對(duì)文法進(jìn)行分析。本文主要采用自頂向下的分析方法，對(duì)LL（1）文法做出適當(dāng)?shù)姆治雠c研究，LL（1）文法的功能是利用LL（1）控制程序和相關(guān)文法生成LL（1）分析表，對(duì)輸入符號(hào)串進(jìn)行自上而下的分析過(guò)程。

關(guān)鍵詞：LL（1）分析法；自頂向下

1 原理概述

LL（1）文法使用的是確定的自頂向下的分析技術(shù)。其中LL（1）的代表的含義是：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第二個(gè)L表明分析過(guò)程中將使用的是最左推導(dǎo)，1表明的是只需要向右看一個(gè)符號(hào)便可以決定如何推導(dǎo)，也就是說(shuō)選擇哪一個(gè)規(guī)則進(jìn)行推導(dǎo)。

在對(duì)LL（1）文法的判別中，要銘記步驟即首先計(jì)算FIRST集，然后計(jì)算FOLLOW集和SELLECT集，最后判斷是否為L(zhǎng)L（1）文法，在此基礎(chǔ)上再進(jìn)行句子的分析。

2 文法規(guī)則說(shuō)明

2.1 詞法規(guī)則

在本文中，討論的字符可以規(guī)定為終結(jié)符或非終結(jié)符，但“#”作為空串處理不可以作為終結(jié)符或非終結(jié)符去處理。

2.2 文法規(guī)則

（1）在產(chǎn)生式中，右邊的字符不全是由終結(jié)符組成。

（2）如果在兩個(gè)產(chǎn)生式中相同的左邊字符，它們的右邊一定是由不同的終結(jié)符或非終結(jié)符開始的。

3 算法設(shè)計(jì)

3.1 表驅(qū)動(dòng)的LL（1）分析器

LL（1）分析法的基礎(chǔ)思想是根據(jù)輸入串的當(dāng)前輸入來(lái)唯一確定選用某一條產(chǎn)生式來(lái)進(jìn)行推導(dǎo)，當(dāng)這個(gè)輸入符號(hào)與推導(dǎo)的第一個(gè)符號(hào)相同時(shí)，再取出下一個(gè)輸入串的符號(hào)，繼續(xù)確定下一個(gè)推導(dǎo)應(yīng)該選用的規(guī)則：如此下去直到推出被分析的輸入串為止。

一個(gè)LL（1）分析器由一張LL（1）分析表、一個(gè)先進(jìn)后出的分析棧以及一個(gè)控制程序組成，如圖1所示：

（1）輸入串是待分析的符號(hào)串，它以邊界符“#”作為結(jié)束標(biāo)志。

（2）分析棧中存放的是分析過(guò)程中的文法符號(hào)。開始時(shí)棧底已經(jīng)存入了一個(gè)“#”作為標(biāo)示，然后再壓入文法的開始符號(hào)；當(dāng)分析棧中只剩下“#”標(biāo)示時(shí)，說(shuō)明輸入串指針也指向了串尾的“#”標(biāo)示，這時(shí)表明分析成功。

（3）在本程序中概括了相應(yīng)文法的全部信息。二維數(shù)組中的每一行與文法的一個(gè)終結(jié)符相關(guān)聯(lián)，而每一列與文法的一個(gè)終結(jié)符或者是“#”標(biāo)示相關(guān)聯(lián)。

3.2 表驅(qū)動(dòng)的LL（1）分析器

為了構(gòu)造分析表N，要預(yù)先定義和構(gòu)造文法的相關(guān)集合FIRST集合FOLLOW集，其中需要注意的是：

FIRST（α）={a|α->a...，a∈Vt}，在此其中需要注意的是ε∈FIRST（α），換句話說(shuō)α的所有可能推導(dǎo)的開頭終結(jié)符或可能的ε。

FOLLOW（A）={a|S->...Aa...，a∈Vt}，S->...Aa，說(shuō)明邊界符#∈FOLLOW（A）也就是所有句型中出現(xiàn)在緊隨A之后的非終結(jié)符。

對(duì)于FIRST集合的確定：

FIRST集合最終是對(duì)產(chǎn)生式右部的字符串而言的，其關(guān)鍵是求出非終結(jié)符的FIRST集合，其中知道終結(jié)符的FIRST集合就是它自己，所以求出非終結(jié)符的FIRST集合后，就很直觀地了解了每個(gè)字符串的FIRST集合。確定FIRST集主要有兩種方法：

（1）直接收取：對(duì)形如S->a…的產(chǎn)生式（a是終結(jié)符），把a(bǔ)收入到FIRST（S）中。

（2）反復(fù)傳送：對(duì)形入S->A…的產(chǎn)生式（其中A是非終結(jié)符），應(yīng)把FIRST（A）中的全部?jī)?nèi)容傳送到FIRST（S）中，換句話說(shuō)只需要把第一個(gè)非終結(jié)符的FIRST集傳過(guò)去。

對(duì)于FOLLOW集合的確定：

我們都知道FOLLOW集合是針對(duì)非終結(jié)符而言的，F(xiàn)OLLOW（A）所表達(dá)的是句型中非終結(jié)符A所有可能的后隨終結(jié)符號(hào)的集合，特別地，“#”是識(shí)別符號(hào)的后隨符。注意FOLLOW集合是從開始符號(hào)S開始推導(dǎo)。其求法主要有以下幾種：

（1）直接收?。鹤⒁猱a(chǎn)生式右部的每一個(gè)形如“…Aa…”的組合，把a(bǔ)直接收入到FOLLOW（A）中。因a是緊跟在A后的終結(jié)符。

（2）直接收取：對(duì)形如“…SA…”（A是非終結(jié)符）的組合，把FIRST（A）直接收入到FOLLOW（S）中.

（3）直接收?。喝鬝->…A，即以A結(jié)尾，則#∈Follow（A）

（4）反復(fù)傳送：對(duì)形如S->…A的產(chǎn)生式（其中A是非終結(jié)符），應(yīng)把Follow（S）中的全部?jī)?nèi)容傳送到Follow（A）中。

總之：Follow集比First要復(fù)雜一點(diǎn)。

當(dāng)確定好FIRST集和Follow集之后，就可以對(duì)LL（1）分析表進(jìn)行構(gòu)建了，具體如圖2所示：

4 關(guān)于文法的判斷

要想確定一個(gè)文法是不是LL（1）文法，需要對(duì)SELLECT集合進(jìn)行確定，對(duì)于SELLECT集來(lái)說(shuō)，在上文中已經(jīng)求出了FIRST集合FOLLOW集，通過(guò)它們SELECT集就很好確定了，Select集的作用是將first集和follow集進(jìn)行合并，如果兩個(gè)文法的左端都是A，若他們的select集交集為空，表明他們是兩個(gè)無(wú)關(guān)的，不會(huì)產(chǎn)生不確定性的文法即該文法是LL（1）文法，反之，則表明文法不是LL（1）文法。

在SELECT集確定的過(guò)程中需要知道的是：

（1）如果α是終結(jié)符，那么SELECT（A->α）={α}。

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

（3）如果α是非終結(jié)符，分為下列兩種情況：

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

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

5 其他說(shuō)明

本文中涉及的程序是由JAVA所編寫的，在程序中LL類表示的含有終態(tài)集和非終態(tài)集，其中所設(shè)計(jì)的方法全部都為靜態(tài)方法，在程序中，當(dāng)構(gòu)建好LL（1）分析表后，輸入需要分析的串就可以得到相關(guān)的分析表。程序流程圖如圖3所示：

6 總結(jié)

遞歸下降分析法是確定的自上而下分析法，這種分析法要求文法是LL（1）文法。它的基本思想是，對(duì)文法中的每個(gè)終結(jié)符編寫一個(gè)函數(shù)（或子程序），每個(gè)函數(shù)（或子程序）的功能是識(shí)別由該非終結(jié)符所表示的語(yǔ)法成分。由于描述語(yǔ)言的文法常常是遞歸定義的，因此相應(yīng)的這組函數(shù)（或子程序）必然以相互遞歸的方式進(jìn)行調(diào)用。在選用自頂向下分析技術(shù)時(shí)，首先必須判斷所給文法是否是LL（1）文法，然后編寫構(gòu)造LL（1）語(yǔ)法分析程序。因而對(duì)任給文法需計(jì)算FIRST、FOLLOW、SELECT集合，進(jìn)而判別文法是否為L(zhǎng)L（1）文法。

參考文獻(xiàn)：

[1]陳火旺.程序設(shè)計(jì)語(yǔ)言編譯原理.國(guó)防工業(yè)出版社，2006.

[2]胡元義.編譯原理實(shí)踐教程.西安電子科技大學(xué)出版社，2010.

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

作者簡(jiǎn)介：鄧麗慧（1988-），女，漢族，四川內(nèi)江人，本科，初級(jí)工程師，現(xiàn)任職務(wù)：助理工程師，研究方向：計(jì)算機(jī)應(yīng)用。