摘 要：在計(jì)算機(jī)編程領(lǐng)域中，語法分析是編譯程序的核心部分，它有著極其重要的地位，語法分析的作用是在詞法分析識(shí)別單詞符號(hào)串的基礎(chǔ)上，分析并判斷程序的語法結(jié)構(gòu)是否符合語法規(guī)則。目前語法分析包含為自頂向下的分析方法和自底向上的分析方法兩大類。明確文法分析的方法時(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ān)鍵詞：LL（1）分析法；自頂向下

1 原理概述

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

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

2 文法規(guī)則說明

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)前輸入來唯一確定選用某一條產(chǎn)生式來進(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）分析棧中存放的是分析過程中的文法符號(hào)。開始時(shí)棧底已經(jīng)存入了一個(gè)“#”作為標(biāo)示，然后再壓入文法的開始符號(hào)；當(dāng)分析棧中只剩下“#”標(biāo)示時(shí)，說明輸入串指針也指向了串尾的“#”標(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（α），換句話說α的所有可能推導(dǎo)的開頭終結(jié)符或可能的ε。

FOLLOW（A）={a|S->...Aa...，a∈Vt}，S->...Aa，說明邊界符#∈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）中，換句話說只需要把第一個(gè)非終結(jié)符的FIRST集傳過去。

對(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集來說，在上文中已經(jīng)求出了FIRST集合FOLLOW集，通過它們SELECT集就很好確定了，Select集的作用是將first集和follow集進(jìn)行合并，如果兩個(gè)文法的左端都是A，若他們的select集交集為空，表明他們是兩個(gè)無關(guān)的，不會(huì)產(chǎn)生不確定性的文法即該文法是LL（1）文法，反之，則表明文法不是LL（1）文法。

在SELECT集確定的過程中需要知道的是：

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

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

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

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

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

5 其他說明

本文中涉及的程序是由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īng)的這組函數(shù)（或子程序）必然以相互遞歸的方式進(jìn)行調(diào)用。在選用自頂向下分析技術(shù)時(shí)，首先必須判斷所給文法是否是LL（1）文法，然后編寫構(gòu)造LL（1）語法分析程序。因而對(duì)任給文法需計(jì)算FIRST、FOLLOW、SELECT集合，進(jìn)而判別文法是否為L(zhǎng)L（1）文法。

參考文獻(xiàn)：

[1]陳火旺.程序設(shè)計(jì)語言編譯原理.國(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)用。