熊鹏荣

（上饶师范学院数学与计算机科学学院，江西上饶334001）

求first集的改进算法

熊鹏荣

（上饶师范学院数学与计算机科学学院，江西上饶334001）

对

［1］和［2］，给出的求文法G的终极符和非终极符的首符集算法进行改进，改进的算法使原算法循环需要进行（n1＋n2）m次，减少为循环只需要进行n1＋n2＊m次。

文法；首符集；算法

编译程序是将高级语言程序翻译成机器语言的系统软件，对编译程序设计的基础理论研究很有必要。求文法G的终极符和非终极符的首符集是编译程序中自顶向下语法分析方法过程中的一个算法。求文法G的符号V的首符集的方法有根据定义求first集法和由关系图求文法符号的first集［1－3］。本文对参考文献［1］和［2］中对文法G的符号V的求first集算法做出优化改进，使得算法的效率更高。

1 文法的基础知识

定义1 设G＝（VT，VN，S，P）是一个四元组，

其中VT是有限的终极符集；

VN是有限的非终极符集；

S是初始符，S∈VN；

P是产生式的有限集且形式：A→X1X2…Xn，其中A∈VN，Xi∈（VT∪VN）＊（i＝1，2，…，n），称四元组G为上下文无关文法，记VT∪VN＝V，称V为文法G的字母表，且VT∩VN＝φ。

对于一个可用的文法应满足的条件是其一，∀A∈VN都至少出现于一个产生式的左部，且∀a∈VT至少出现于一个产生式的右部中；其二，∀A∈VN都能推导出VT中的元素终极符。

定义2 设G＝（VT，VN，S，P）是上下文无关文法，first（β）＝｛a｜β⇒＊aγ，a∈VT，β，γ∈V＊｝∪（ifβ⇒＊εthen｛ε｝elseφ），称集合first（β）为β首符集。

由定义可得，若X∈VT，则first（X）＝｛X｝，对于空串ε有first（ε）＝｛ε｝。

2 算法的改进

［1］和［2］中给出了对每个X∈VT∪VN，求首符集的算法。在该算法的第3步为：Changes＝F；

对P中的每个产生式A→X1…Xi…Xn，do｛

Oldfirst＝first（A）；

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

其中A→X1…Xi…Xn（表示Xi是产生式右部中第一个不可推导ε的符号）。

但该步骤是可以改进优化的，使该算法的效率更高。……