LL_1_预测分析器的构造(2)

“环”问题已经解决。

解决终结符的重复存在问题的算法

“起泡法”对ＦＩＲＳＴ集合里的终结符进行判断并将重①用复的终结符删除；

‘ε’字符加入可以推出空的非终结符ＦＩＲＳＴ集合中，②将

并将不能推出空的非终结符的ＦＩＲＳＴ集合中的‘ε’字符全部删除。

图１

预测分析程序的工作流程图

２．２类定义

ｃｌａｓｓＰｒｅｃｅｐｔ／／定义产生式类｛ｐｕｂｌｉｃ：

Ｐｒｅｃｅｐｔ（ｖｏｉｄ）；

Ｐｒｅｃｅｐｔ（ｓｔｒｉｎｇｌｅｆｔ，ｓｔｒｉｎｇｒｉｇｈｔ）；￣Ｐｒｅｃｅｐｔ（ｖｏｉｄ）；

“→”的左边字符ｓｔｒｉｎｇＧｅｔＬｅｆｔ（）；／／截取产生式中

“→”的右边字符ｓｔｒｉｎｇＧｅｔＲｉｇｈｔ（）；／／截取产生式中

１．２求解ＦＯＬＬＯＷ集合的算法

⑴逐一扫描代码中的产生式，将产生式右部赋给γ串，γ［ｊ］表示γ串中的第ｊ个字符。

⑵逐一扫描产生式的右部，若γ［ｊ］为非终结符Ｘ，找出γ［ｊ］后继的第一个字符γ［ｋ］。

①若γ［ｋ］为终结符，则将该终结符加入到ＦＯＬＬＯＷ集

合，结束，跳出⑵；

，执行⑶。②若γ［ｋ］为非终结符，则ＦＩＲＳＴ集合‘－ε’

ｐｒｉｖａｔｅ：

“→”的左边字符ｓｔｒｉｎｇｓｔｒＬｅｆｔ；／／存放

“→”的右边字符ｓｔｒｉｎｇｓｔｒＲｉｇｈｔ；／／存放

⑶逐一扫描Ｘ后的字符串，分为下面两种情况：

ａ．若非终结符γ［ｋ］能推出空字符串，则ｋ＋＋，继续执行①、②两步；

ｂ．若非终结符γ［ｋ］为产生式最后一个字符，则将该产生式

的左部非终结符的ＦＯＬＬＯＷ集合加入该非终结符的ＦＯＬ－

ｐｕｂｌｉｃ：

ｖｏｉｄＣｌｅａｒ（ｖｏｉｄ）；／／将所有产生式清空｝；

ｃｌａｓｓＳｅｔ／／定义集合类｛ｐｕｂｌｉｃ：Ｓｅｔ（ｖｏｉｄ）；￣Ｓｅｔ（ｖｏｉｄ）；

Ｓｅｔ（ｃｏｎｓｔＳｅｔ＆ｓｅｔ）；／／构造函数Ｓｅｔ（ｃｈａｒｃＣｈａｒ）；／／构造函数

ｂｏｏｌＩｎｓｅｒｔ（ｃｈａｒｃＩｎｓｅｒｔ）；／／在原来的集合中插入一个字符ｂｏｏｌＤｅｌｅｔｅ（ｃｈａｒｃＤｅｌｅｔｅ）；／／在原来的集合中删除一个字符ｂｏｏｌＦｉｎｄ（ｃｈａｒｃＦｉｎｄ）；／／在集合中查找字符ｃＦｉｎｄ

ｉｎｔＦｉｎｄＰｏｓ（ｃｈａｒｃＦｉｎｄ）；／／在集合中查找字符ｃＦｉｎｄ的位置ｉｎｔＡｄｄ（ｃｏｎｓｔＳｅｔ＆ｓｅｔ）；／／添加集合ｓｅｔｉｎｔＳｕｂ（ｃｏｎｓｔＳｅｔ＆ｓｅｔ）；／／删除集合ｓｅｔｉｎｔＳｉｚｅ（）ｃｏｎｓｔ；／／求集合的大小

Ｓｅｔｏｐｅｒａｔｏｒ＋（ｃｏｎｓｔＳｅｔ＆ｓｅｔ）；／／合并两个集合Ｓｅｔｏｐｅｒａｔｏｒ－（ｃｏｎｓｔＳｅｔ＆ｓｅｔ）；

ＬＯＷ集合。

⑷若扫描完全部的产生式，则求得所有非终结符的ＦＯＬＬＯＷ集合。

在计算ＦＯＬＬＯＷ集中也存在“环”和重复的终结符的问题，解决的办法与ＦＩＲＳＴ集的相同。

１．３求ＳＥＬＬＥＣＴ集合

对代码中的任意产生式Ａ→ａ，Ａ∈ＶＮ，ａ∈Ｖ＊，求ＳＥＬＥＣＴ集。可按下列算法：

ＩＦ（ａ不能推出ε）ＳＥＬＥＣＴ（Ａ→ａ）＝ＦＩＲＳＴ（ａ）ＥＬＳＥ

ＳＥＬＥＣＴ（Ａ→ａ）＝ＦＩＲＳＴ（ａ）∪ＦＯＬＬＯＷ（Ａ）

２ＬＬ（１）预测分析器的构造

２．１预测分析器的工作流程

ＬＬ（１）预测分析器的总控程序利用栈顶元素和当前输入符

预测分析器的构造

计算机时代２００８年第３期

／／在集合中删掉集合ｓｅｔ中的字符

ｃｏｎｓｔＳｅｔｏｐｅｒａｔｏｒ＝（ｃｏｎｓｔＳｅｔ＆ｓｅｔ）；／／对集合进行赋值ｃｈａｒＧｅｔＡｔ（ｉｎｔｉＰｏｓ）；／／取集合中第ｉＰｏｓ个字符ｂｏｏｌＩｓＥｍｐｔｙ（）；／／判断集合是否为空ｐｒｉｖａｔｅ：

ｖｅｃｔｏｒ＜ｃｈａｒ＞ＳｅｔＣｏｎｔｅｎｔ；

／／变量ＳｅｔＣｏｎｔｅｎｔ存放集合的具体内容｝；

ｃｌａｓｓＧｒａｍｍａｒ／／定义ＬＬ（１）代码类｛ｐｕｂｌｉｃ：

Ｇｒａｍｍａｒ（ｖｏｉｄ）；￣Ｇｒａｍｍａｒ（ｖｏｉｄ）；

Ｇｒａｍｍａｒ（ｃｏｎｓｔＧｒａｍｍａｒ＆ｇ）；／／构造函数ｃｏｎｓｔＧｒａｍｍａｒｏｐｅｒａｔｏｒ＝（ｃｏｎｓｔＧｒａｍｍａｒ＆ｇ）；／／对代码进行赋值

ｖｏｉｄＳｅｔＶｔ（ｓｔｒｉｎｇｖｔ）；／／设置终结符集合的值为ｖｔｖｏｉｄＳｅｔＶｎ（ｓｔｒｉｎｇｖｎ）；／／设置非终结符集合的值为ｖｎｖｏｉｄＳｅｔＳｔａｒｔ（ｃｈａｒｓｔａｒｔ）；／／设置代码的开始符号为ｓｔａｒｔｖｏｉｄＡｄｄＰｒｅｃｅｐｔ（ｓｔｒｉｎｇｐ）；／／添加产生式ｐｖｏｉｄＧｅｎｅｒａｔｅＰｒｅｄｉｃｔＴａｂｌｅ（）；／／构造预测分析表ｂｏｏｌＩｓＧｒａｍｍａｒＬｅｇａｌ（）；／／判断代码是否合法ｓｔｒｉｎｇＯｕｔｐｕｔＨＴＭＬ（）；／／将结果输在窗体中

ｖｏｉｄＯｕｔｐｕｔ（ｃｈａｒ＊ｐＦｉｌｅｎａｍｅ）；／／将结果写入文件ｐＦｉｌｅｎａｍｅ中ｂｏｏｌＩｓＩｎＶｎ（ｃｈａｒｃＣｈａｒ）；／／判断ｃＣｈａｒ是否在非终结符集合中

６５

ｖｏｉｄＭａｋｅＰｒｅｄｉｃｔＴａｂｌｅ（）；／／构造预测分析表ｂｏｏｌＣａｎＲｅａｃｈＥｍｐｔｙ（ｓｔｒｉｎｇｓｔｒ）；／／判断字符串ｓｔｒ是否可以推出空字符ｂｏｏｌＣａｎＲｅａｃｈＥｍｐｔｙ（ｃｈａｒｃＣｈａｒ）；／／判断字符ｃＣｈａｒ是否可以推出空字符

ＳｅｔＧｅｔＦｉｒｓｔＳｅｔ（ｃｈａｒｃＣｈａｒ）；／／求字符ｃＣｈａｒ的Ｆｉｒｓｔ集ＳｅｔＧｅｔＦｉｒｓｔＳｅｔ（ｓｔｒｉｎｇｓｔｒ）；／／求字符串ｃＣｈａｒ的Ｆｉｒｓｔ集ＳｅｔＧｅｔＦｏｌｌｏｗＳｅｔ（ｃｈａｒｃＣｈａｒ）；／／求字符ｃＣｈａｒ的Ｆｏｌｌｏｗ集｝；

２．３构造预测分析表的算法设计

对于给定的代码，首先需要判断它是否为合法的代码，然后判断是否为ＬＬ（１）代码，这需要求出代码中每个产生式的

ＳＥＬＬＥＣＴ集合，然后进行判断。而对于已经判定是ＬＬ（１）代码

的代码，就可以构造预测分析表，首先将表清空，然后取一个产生式，求得该产生式的ＳＥＬＬＥＣＴ集合。假设ａ∈ＳＥＬＥＣＴ（Ａ→

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说公务员考试LL_1_预测分析器的构造(2)在线全文阅读。