LL_1_预测分析器的构造

预测分析器的构造

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

６３

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

褚亚飞

（浙江海洋学院高职杭州分院，浙江杭州３１１２５８）

摘

要：着重分析了编译原理课程中的ＬＬ（１）预测分析器的设计算法。对于给定的代码，求出ＦＩＲＳＴ、ＦＯＬＬＯＷ和

ＳＥＬＥＣＴ集，构造相应的ＬＬ（１）预测分析器，给出预测分析表，并对求解ＦＩＲＳＴ集和ＦＯＬＬＯＷ集中存在的环问题提出了

解决算法。

关键词：ＦＩＲＳＴ；ＦＯＬＬＯＷ；ＳＥＬＥＣＴ；ＬＬ（１）；算法

０引言

学好编译原理对计算机专业的学生至关重要。随着计算机科学的迅速发展，程序设计语言也有了飞速的发展，语言的功能、结构均有了本质的改变。相对而言，编译原理课程的教学却大大落后于实际需要，仍然停留在以理论教学为主的状态。编译原理作为计算机专业学生的必修课，较其他专业课程而言，显得过于枯燥、抽象和难于理解，由此出现学生学习积极性不高、兴趣不浓、掌握不透等现象。本分析器以给出解答过程和答案为主要内容，以简单清晰的界面给出问题的具体解答过程，给学习者一个直观的认识，使他们了解编译原理工作的过程，进而提高对编译原理的兴趣。

给γ，γ［ｊ］是指γ串中第ｊ个字符。

⑵逐一扫描产生式右部，要处理如下两种情况：

①若产生式的右部为空字符串或第一个字符为非终结符，

则将‘ε’和终结符加入此非终结符的ＦＩＲＳＴ集合，跳出⑵；

②若产生式右部为非终结符，则将γ［ｊ］的ＦＩＲＳＴ集合加

入该非终结符的ＦＩＲＳＴ集合。

ａ．若γ［ｊ］不能推出空字符串，则结束，跳出⑵；

ｂ．若ｊ＜＝γ串的长度（即该非终结符γ［ｊ］不是产生式最后

一个字符），则继续执行②；否则，结束，跳出⑵。

⑶扫描完所有的产生式，求得所有的非终结符的ＦＩＲＳＴ

集合，跳出⑴。

所求得的ＦＩＲＳＴ集合中还可能存在环的问题（形如产生式

１ＦＩＲＳＴ，ＦＯＬＬＯＷ，ＳＥＬＥＣＴ集的算法设计

１．１求解ＦＩＲＳＴ集合的算法

Ｘ→Ｘ…（Ｘ∈Ｖｎ）或者求非终结符的ＦＩＲＳＴ集合需要先求代码

中其他非终结符的ＦＩＲＳＴ集合的两种情况）和存在重复终结符的问题。下面就这两个问题提出解决的算法。

⑴逐一扫描代码中的产生式，将产生式右部的字符串赋

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

编辑软件，如ＡｄｏｂｅＰｒｅｍｉｅｒｅ对屏幕录像和摄像机的录像进行合成，形成画中画功能，再做流化处理。如电子科技大学网络教育学院的《网页设计教程》课件就是一种有“动态电脑屏幕画面”和（合成为画中画）及“讲课音频”的流媒体课件。“教师讲课画面”

过程录制成上述课件则可以“以不变应万变”。当然日常课堂教学中用的屏幕录像课件可以直接生成ＥＸＥ文件，若不在网上传输可不必进行流化处理。此外，还可以对电脑上播放的一些现成的视频（音频）进行屏幕录像（要注意保护版权）制成课件，但要设置“录像模式／基本设置”中的参数：去掉“帧数过大，自要录动停止录制”和“自动”选项，把录制频率设置成２５帧／秒。制播放中的声音，还需设置好录音来源，可选“ｓｔｅｒｅｏｍｉｘ”，但这时录制的文件数据量将会大增。

“动态屏幕捕获型”流媒体课件的应用３

“动态屏幕捕获型”流媒体课件的应用非常广泛，可用于网上教学、课堂教学。

３．１用于网上教学

流媒体课件的最大优势是实时传输，能实现网上边下载边播放。“动态屏幕捕获型”流媒体课件在现代远程教育（如电大、网络教育学院开办的远程教育）或校园网教学中大有用武之地。若将一些应用软件的教学制成流媒体课件，学习者可以在家里直观自主地学习，定能收到好的学习效果。没有上网的学习者，可以购买配套光盘进行学习。

４结束语

通过所述屏幕录像方式可以将电脑屏幕的动态变化信息以文件的形式记录保存下来，编制成流媒体课件，特别适宜于网上进行应用软件教学。它建构出直观生动的学习情境，避免了教学中出现“只可意会不可言传”的尴尬局面，丰富了教学信息资源，增大了教学信息容量，减轻了教师的劳动强度，取得了良好的教学效果，具有广阔的应用前景。

参考文献：

３．２用于课堂教学

在课堂教学中，公用的多媒体教室讲台上的电脑只安装了一些常用的软件，而且由于大家共用电脑，出现软件故障是常事，再加之教师上课地点的不固定性，给一些上应用软件课的教师带来了诸多不便，经常要装机。教师如果将应用软件教学

［１］陈代武．流媒体课件制作中关键技术研究［Ｊ］．计算机与现代化，

２００７．１０：９￣１１

［２］李志河．多媒体课件制作技术［Ｍ］．清华大学出版社，２００５．

ＣＥ

预测分析器的构造

６４

解决“环”的算法

ＣｏｍｐｕｔｅｒＥｒａＮｏ．３２００８

号对输入串进行预测分析，而预测的信息则存放在分析表的相矩阵的元素Ｍ［Ａ，ａ］中应入口里。分析表可用一个矩阵Ｍ表示。“＃”。矩阵元素的下标Ａ表示非终结符，ａ为终结符或句子括号

⑴将代码中的所有非终结符按预处理的结果顺序处理。⑵三种扫描方式：

①按顺序扫描ＦＩＲＳＴ集合（Ｘ１，Ｘ２，…，Ｘｎ），若该非终结符Ｘｊ需由另一个非终结符的Ｘｉ求得，那么若Ｘｉ排在Ｘｊ前面，则

将Ｘｉ代入Ｘｊ中；

Ｍ［Ａ，ａ］中存放着一条关于Ａ的产生式，即当用非终结符Ａ向

下推导，遇到输入符ａ时所应采取的候选产生式，当元素内容无产生式时，则表明用Ａ为左部向下推导时遇到了不该出现的符号，此时应转向出错处理。分析程序的工作流程如图１所示。

②逐一扫描按顺序排列的ＦＩＲＳＴ集合（Ｘ１，Ｘ２，…，Ｘｎ），若非终

结符的ＦＩＲＳＴ集合中含有它本身，则删除等式右部的该非终结符；

③从序号最大的非终结符的ＦＩＲＳＴ集开始，逐一扫描按顺

序排列的ＦＩＲＳＴ集合（Ｘ１，Ｘ２，…，Ｘｎ），若该非终结符Ｘｊ需由另一个非终结符的Ｘｉ求得，那么若Ｘｉ排在Ｘｊ后面，则将该Ｘｉ回代入Ｘｊ中，调用第②步。

⑶若所有非终结符的ＦＩＲＳＴ集中都已经为终结符，则

“环”问题已经解决。

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

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

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

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

图１

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

２．２类定义

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

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

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

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

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

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

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

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

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

合，结束，跳出⑵；

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

ｐｒｉｖａｔｅ：

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

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

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

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

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

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

ｐｕｂｌｉｃ：

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

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

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

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

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

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

ＬＯＷ集合。

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

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

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

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

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

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

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

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

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

预测分析器的构造

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

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

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

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

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

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

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

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

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

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

６５

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

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

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

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

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

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

α），则把α放入以Ａ所在行为行号，以ＳＥＬＥＣＴ（Ａ→α）为列

号的分析表ｐＰｒｅｄｉｃｔＴａｂｌｅ［］中。重复以上操作，直到所有产生式的ＳＥＬＥＣＴ集合都分析完为止。

２．４利用预测分析表进行分析的算法设计

分析中需要用到分析栈、剩余输入串及有关产生式。为了显示整个分析过程，程序中分别用栈ｓ，ｉｎｐｕｔ，ｓｔ来实现。分析时，首先将开始符压人分析栈ｓ，用户输入的字符串与‘＃’的连接串放入剩余压入栈ｉｎｐｕｔ的第一个单元中，然后去掉ｓ栈栈顶元素的最后一个字符，在预测分析表中查找该非终结符所在的行、ｉｎｐｕｔ栈栈顶元素的第一个字符所在列的值。如果表中元素为空，则出错；否则将表中的产生式放入产生式栈ｓｔ栈顶，并用该产生式的右部替换ｓ的栈顶元素的字符串的最后一个非终结符，然后将替换后的非终结符串压入ｓ栈栈顶。如果栈ｓ的栈顶元素的最后一个字符是终结符，ｉｎｐｕｔ栈的栈顶元素的第一个字符是终结符，若两个字符不相等，则出错；否则匹配，分别将两个栈的栈顶元素的匹配字符去掉，并将更新后的元素压入栈顶。ｓｔ栈栈顶压入“匹配”字符串。如此一直进行到最后ｓ及ｉｎｐｕｔ栈栈时，分析完毕，表示可以接受此字符串。顶元素都为‘＃’

ｂｏｏｌＩｓＩｎＶｔ（ｃｈａｒｃＣｈａｒ）；／／判断ｃＣｈａｒ是否在终结符集合中ｃｈａｒＧｅｔＳｔａｒｔ（）；／／取代码的开始符号

ｂｏｏｌＩｓＬｅｇａｌＬＬ１Ｇｒａｍｍａｒ（）；／／判断是否为ＬＬ（１）代码ｐｒｉｖａｔｅ：

ｅｎｕｍＣａｎＥｍｐｔｙ｛ＣＡＮＴＲＵＥ，ＣＡＮＦＡＬＳＥ，ＵＮＤＥＦＩＮＥＤ｝；／／定义枚举型变量

／／用来标明一个分析表是否为空，还是未定义ＳｅｔＶｔ；／／终结符集合ＳｅｔＶｎ；／／非终结符集合ｃｈａｒｃＳｔａｒｔ；／／代码开始符号ｖｅｃｔｏｒ＜Ｐｒｅｃｅｐｔ＞Ｐ；／／产生式

ＣａｎＥｍｐｔｙ＊ｐＣａｎＥｍｐｔｙＴａｂｌｅ；／／定义分析表所处状态的变量ｉｎｔ＊ｐＰｒｅｄｉｃｔＴａｂｌｅ；／／定义存放分析表的指针变量ｖｅｃｔｏｒ＜Ｓｅｔ＞ＦｉｒｓｔＳｅｔ；／／产生Ｆｉｒｓｔ集ｖｅｃｔｏｒ＜Ｓｅｔ＞ＦｏｌｌｏｗＳｅｔ；／／产生Ｆｏｌｌｏｗ集ｖｅｃｔｏｒ＜Ｓｅｔ＞ＳｅｌｅｃｔＳｅｔ；／／产生Ｓｅｌｅｃｔ集ｉｎｔｎＶｔ；／／终结符的个数ｉｎｔｎＶｎ；／／非终结符的个数ｉｎｔｎＰ；／／产生式的个数ｉｎｔｉＩｓＬＬ１；／／标记是ＬＬ（１）代码ｖｏｉｄＭａｋｅＣａｎＲｅａｃｈＥｍｐｔｙＴａｂｌｅ（）；／／清空原来分析表中的内容，进行新的构造

ｖｏｉｄＣａｌｃｕｌａｔｅＦｉｒｓｔＳｅｔ（）；／／计算Ｆｉｒｓｔ集合中的字符个数ｖｏｉｄＣａｌｃｕｌａｔｅＦｏｌｌｏｗＳｅｔ（）；／／计算Ｆｏｌｌｏｗ集合中的字符个数ｖｏｉｄＣａｌｃｕｌａｔｅＳｅｌｅｃｔＳｅｔ（）；／／计算Ｓｅｌｅｃ集合中的字符个数

３结束语

该分析器不同于传统的多媒体教学软件，用户只要按规定的格式输入问题，系统能自动地给出该问题的答案和解答过程。该系统能作为学生学习的辅助工具，同时也可以作为教师的教学工具。这也是适应新世纪教学改革的需要。本系统是专门针对编译原理这门课程而设计的，因此，它的运用就仅局限于对编译原理的解答。

参考文献：

［１］吕映芝，张素琴．编译原理［Ｍ］．清华大学出版社，１９９８．

［２］ＫｅｎｎｅｔｈＣＬｏｕｎｄｅｒ编，冯博琴，冯岚译．编译原理及实践［Ｍ］．机械

工业出版社，２０００．

［３］陈火旺，刘春林等．程序设计语言编译原理（第３版）［Ｍ］．国防工业出

版社，２００１．

［４］温敬和．ＬＬ（１）代码及分析表的自动构造［Ｊ］．计算机工程与应用，

２００１．２：５０￣５４

ＣＥ

本文来源：https://www.bwwdw.com/article/ftdm.html