熊鵬榮

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

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

熊鵬榮

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

對(duì)

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

文法；首符集；算法

編譯程序是將高級(jí)語(yǔ)言程序翻譯成機(jī)器語(yǔ)言的系統(tǒng)軟件，對(duì)編譯程序設(shè)計(jì)的基礎(chǔ)理論研究很有必要。求文法G的終極符和非終極符的首符集是編譯程序中自頂向下語(yǔ)法分析方法過(guò)程中的一個(gè)算法。求文法G的符號(hào)V的首符集的方法有根據(jù)定義求first集法和由關(guān)系圖求文法符號(hào)的first集［1－3］。本文對(duì)參考文獻(xiàn)［1］和［2］中對(duì)文法G的符號(hào)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為上下文無(wú)關(guān)文法，記VT∪VN＝V，稱V為文法G的字母表，且VT∩VN＝φ。

對(duì)于一個(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）是上下文無(wú)關(guān)文法，first（β）＝｛a｜β?＊aγ，a∈VT，β，γ∈V＊｝∪（ifβ?＊εthen｛ε｝elseφ），稱集合first（β）為β首符集。

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

2 算法的改進(jìn)

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

對(duì)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)ε的符號(hà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步中，對(duì)P1中的產(chǎn)生式形式為A→aβ，有

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

對(duì)每一個(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）對(duì)P1中的每個(gè)產(chǎn)生式A→aβ｜A→a，有first（A）＝first（A）∪｛a｝；

（4）Changes＝F；

對(duì)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)中對(duì)每個(gè)產(chǎn)生式都需要進(jìn)行計(jì)算①式的操作，共需要進(jìn)行（n1＋n2）＊m次計(jì)算①式的操作，改進(jìn)后的算法，由于將產(chǎn)生式P的子集P1移到循環(huán)外，在循環(huán)中只是需要對(duì)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ì)算①式的操作。這樣減少算法的工作量，從而提高算法的效率。

高級(jí)語(yǔ)言PASCAL用上下文無(wú)關(guān)文法G［4］定義的過(guò)程中，文法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］呂映芝.語(yǔ)法圖到產(chǎn)生式的自動(dòng)轉(zhuǎn)換［J］.清華大學(xué)學(xué)報(bào)（自然科學(xué)版），1996，36（5）：84－89.

［4］譚浩強(qiáng).PASCAL語(yǔ)言程序設(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