求first集的改進(jìn)算法

熊鵬榮

（上饒師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西上饒334001）

求first集的改進(jìn)算法

熊鵬榮

（上饒師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西上饒334001）

對

［1］和［2］，給出的求文法G的終極符和非終極符的首符集算法進(jìn)行改進(jìn)，改進(jìn)的算法使原算法循環(huán)需要進(jìn)行（n1＋n2）m次，減少為循環(huán)只需要進(jìn)行n1＋n2＊m次。

文法；首符集；算法

編譯程序是將高級語言程序翻譯成機(jī)器語言的系統(tǒng)軟件，對編譯程序設(shè)計(jì)的基礎(chǔ)理論研究很有必要。求文法G的終極符和非終極符的首符集是編譯程序中自頂向下語法分析方法過程中的一個(gè)算法。求文法G的符號V的首符集的方法有根據(jù)定義求first集法和由關(guān)系圖求文法符號的first集［1－3］。本文對參考文獻(xiàn)［1］和［2］中對文法G的符號V的求first集算法做出優(yōu)化改進(jìn)，使得算法的效率更高。

1 文法的基礎(chǔ)知識(shí)

定義1 設(shè)G＝（VT，VN，S，P）是一個(gè)四元組，

其中VT是有限的終極符集；

VN是有限的非終極符集；

S是初始符，S∈VN；

P是產(chǎn)生式的有限集且形式：A→X1X2…Xn，其中A∈VN，Xi∈（VT∪VN）＊（i＝1，2，…，n），稱四元組G為上下文無關(guān)文法，記VT∪VN＝V，稱V為文法G的字母表，且VT∩VN＝φ。

對于一個(gè)可用的文法應(yīng)滿足的條件是其一，?A∈VN都至少出現(xiàn)于一個(gè)產(chǎn)生式的左部，且?a∈VT至少出現(xiàn)于一個(gè)產(chǎn)生式的右部中；其二，?A∈VN都能推導(dǎo)出VT中的元素終極符。

定義2 設(shè)G＝（VT，VN，S，P）是上下文無關(guān)文法，first（β）＝｛a｜β?＊aγ，a∈VT，β，γ∈V＊｝∪（ifβ?＊εthen｛ε｝elseφ），稱集合first（β）為β首符集。

由定義可得，若X∈VT，則first（X）＝｛X｝，對于空串ε有first（ε）＝｛ε｝。

2 算法的改進(jìn)

［1］和［2］中給出了對每個(gè)X∈VT∪VN，求首符集的算法。在該算法的第3步為：Changes＝F；

對P中的每個(gè)產(chǎn)生式A→X1…Xi…Xn，do｛

Oldfirst＝first（A）；

若Oldfirst≠first（A），則Changes＝T｝

其中A→X1…Xi…Xn（表示Xi是產(chǎn)生式右部中第一個(gè)不可推導(dǎo)ε的符號）。

但該步驟是可以改進(jìn)優(yōu)化的，使該算法的效率更高。

將產(chǎn)生式集P分為兩個(gè)子集：

第一個(gè)子集是P1＝｛A→aβ｜A∈VN，a∈VT，β∈V＊｝；

第二個(gè)子集是P2＝P－P1。

由此可得P＝P1∪P2。

原算法中第3步中，對P1中的產(chǎn)生式形式為A→aβ，有

該式子說明只要first（A）含有終極符a，無論該產(chǎn)生式以后使用多少次計(jì)算①式操作，再也不能為first（A）增加一個(gè)終極符元素。這樣可以將P1中產(chǎn)生式在循環(huán)中計(jì)算①式操作，移到循環(huán)外計(jì)算①式操作，而不會(huì)改變求first（A）集的結(jié)果。故可以將算法進(jìn)行改進(jìn)，使算法的效率更高。

對每一個(gè)X∈V，求first（X）的改進(jìn)優(yōu)化算法如下：

（1）當(dāng)X∈VT，有first（X）＝｛X｝；

（2）當(dāng)X∈VN，有若X?＊ε，則first（X）＝｛ε｝，否則first（X）＝φ；

（3）對P1中的每個(gè)產(chǎn)生式A→aβ｜A→a，有first（A）＝first（A）∪｛a｝；

（4）Changes＝F；

對P2中的每個(gè)產(chǎn)生式A→X1…Xi…Xn，do｛

Oldfirst＝first（A）；

若Oldfirst≠first（A），則Changes＝T｝

（5）若Changes＝T，則轉(zhuǎn)（4）；

（6）算法結(jié)束。

該改進(jìn)算法由于將產(chǎn)生式P的子集P1移到循環(huán)外計(jì)算①式操作，這樣在循環(huán)中可以減少循環(huán)中的運(yùn)算量。

設(shè)｜P1｜＝n1，｜P2｜＝n2，步驟4的循環(huán)次數(shù)為m，則原算法中，在循環(huán)中對每個(gè)產(chǎn)生式都需要進(jìn)行計(jì)算①式的操作，共需要進(jìn)行（n1＋n2）＊m次計(jì)算①式的操作，改進(jìn)后的算法，由于將產(chǎn)生式P的子集P1移到循環(huán)外，在循環(huán)中只是需要對P2中產(chǎn)生式的進(jìn)行計(jì)算①式的操作，再加上P1中產(chǎn)生式在循環(huán)外進(jìn)行一次計(jì)算（1）式的操作，故改進(jìn)算法只需要進(jìn)行n1＋n2＊m次計(jì)算①式的操作，比原算法減少了n1（m－1）計(jì)算①式的操作。這樣減少算法的工作量，從而提高算法的效率。

高級語言PASCAL用上下文無關(guān)文法G［4］定義的過程中，文法G的產(chǎn)生式集P共有318條產(chǎn)生式，其中產(chǎn)生式集P1的產(chǎn)生式為152條，占總數(shù)47.78%，故該算法的改進(jìn)在實(shí)際上是可以提高算法的效率，有一定的實(shí)際應(yīng)用價(jià)值。

參考文獻(xiàn)：

［1］金成植.編譯程序設(shè)計(jì)原理［M］.北京：高等教育出版社，2000：70.

［2］呂映芝.編譯原理［M］.北京：清華大學(xué)出版社，1998：75－76.

［3］呂映芝.語法圖到產(chǎn)生式的自動(dòng)轉(zhuǎn)換［J］.清華大學(xué)學(xué)報(bào)（自然科學(xué)版），1996，36（5）：84－89.

［4］譚浩強(qiáng).PASCAL語言程序設(shè)計(jì)［M］.北京：高等教育出版社，1999：330－335.

An Improved Algorithm for First Set

XlONG Pong－rong

（School of Mathematics and Computer Science，Shangrao Normal University，Shangrao Jiangxi 334001，China）

On the［1］and［2］，the and the non ultimate symbol of G are improved.The improved algorithm makes the original algorithm（n1＋n2）m times，and reduces the need for n1＋n2＊m times.

grammar；first set；algorithm

O142

A

1004－2237（2016）03－0010－02

10.3969／j.issn.1004－2237.2016.03.003

2015－10－20

熊鵬榮（1961－），男，江西上饒人，副教授，學(xué)士，主要從事算法設(shè)計(jì)和分析研究。E－mail：xpr7810＠163.com