预测分析器的构造
计算机时代２００８年第３期
６３
ＬＬ（１）预测分析器的构造
褚亚飞
（浙江海洋学院高职杭州分院，浙江杭州３１１２５８）
摘
要：着重分析了编译原理课程中的ＬＬ（１）预测分析器的设计算法。对于给定的代码，求出ＦＩＲＳＴ、ＦＯＬＬＯＷ和
ＳＥＬＥＣＴ集，构造相应的ＬＬ（１）预测分析器，给出预测分析表，并对求解ＦＩＲＳＴ集和ＦＯＬＬＯＷ集中存在的环问题提出了
解决算法。
关键词：ＦＩＲＳＴ；ＦＯＬＬＯＷ；ＳＥＬＥＣＴ；ＬＬ（１）；算法
０引言
学好编译原理对计算机专业的学生至关重要。随着计算机科学的迅速发展，程序设计语言也有了飞速的发展，语言的功能、结构均有了本质的改变。相对而言，编译原理课程的教学却大大落后于实际需要，仍然停留在以理论教学为主的状态。编译原理作为计算机专业学生的必修课，较其他专业课程而言，显得过于枯燥、抽象和难于理解，由此出现学生学习积极性不高、兴趣不浓、掌握不透等现象。本分析器以给出解答过程和答案为主要内容，以简单清晰的界面给出问题的具体解答过程，给学习者一个直观的认识，使他们了解编译原理工作的过程，进而提高对编译原理的兴趣。
给γ，γ［ｊ］是指γ串中第ｊ个字符。
⑵逐一扫描产生式右部，要处理如下两种情况：
①若产生式的右部为空字符串或第一个字符为非终结符，
则将‘ε’和终结符加入此非终结符的ＦＩＲＳＴ集合，跳出⑵；
②若产生式右部为非终结符，则将γ［ｊ］的ＦＩＲＳＴ集合加
入该非终结符的ＦＩＲＳＴ集合。
ａ．若γ［ｊ］不能推出空字符串，则结束，跳出⑵；
ｂ．若ｊ＜＝γ串的长度（即该非终结符γ［ｊ］不是产生式最后
一个字符），则继续执行②；否则，结束，跳出⑵。
⑶扫描完所有的产生式，求得所有的非终结符的ＦＩＲＳＴ
集合，跳出⑴。
所求得的ＦＩＲＳＴ集合中还可能存在环的问题（形如产生式
１ＦＩＲＳＴ，ＦＯＬＬＯＷ，ＳＥＬＥＣＴ集的算法设计
１．１求解ＦＩＲＳＴ集合的算法
Ｘ→Ｘ…（Ｘ∈Ｖｎ）或者求非终结符的ＦＩＲＳＴ集合需要先求代码
中其他非终结符的ＦＩＲＳＴ集合的两种情况）和存在重复终结符的问题。下面就这两个问题提出解决的算法。
⑴逐一扫描代码中的产生式，将产生式右部的字符串赋
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
编辑软件，如ＡｄｏｂｅＰｒｅｍｉｅｒｅ对屏幕录像和摄像机的录像进行合成，形成画中画功能，再做流化处理。如电子科技大学网络教育学院的《网页设计教程》课件就是一种有“动态电脑屏幕画面”和（合成为画中画）及“讲课音频”的流媒体课件。“教师讲课画面”
过程录制成上述课件则可以“以不变应万变”。当然日常课堂教学中用的屏幕录像课件可以直接生成ＥＸＥ文件，若不在网上传输可不必进行流化处理。此外，还可以对电脑上播放的一些现成的视频（音频）进行屏幕录像（要注意保护版权）制成课件，但要设置“录像模式／基本设置”中的参数：去掉“帧数过大，自要录动停止录制”和“自动”选项，把录制频率设置成２５帧／秒。制播放中的声音，还需设置好录音来源，可选“ｓｔｅｒｅｏｍｉｘ”，但这时录制的文件数据量将会大增。
“动态屏幕捕获型”流媒体课件的应用３
“动态屏幕捕获型”流媒体课件的应用非常广泛，可用于网上教学、课堂教学。
３．１用于网上教学
流媒体课件的最大优势是实时传输，能实现网上边下载边播放。“动态屏幕捕获型”流媒体课件在现代远程教育（如电大、网络教育学院开办的远程教育）或校园网教学中大有用武之地。若将一些应用软件的教学制成流媒体课件，学习者可以在家里直观自主地学习，定能收到好的学习效果。没有上网的学习者，可以购买配套光盘进行学习。
４结束语
通过所述屏幕录像方式可以将电脑屏幕的动态变化信息以文件的形式记录保存下来，编制成流媒体课件，特别适宜于网上进行应用软件教学。它建构出直观生动的学习情境，避免了教学中出现“只可意会不可言传”的尴尬局面，丰富了教学信息资源，增大了教学信息容量，减轻了教师的劳动强度，取得了良好的教学效果，具有广阔的应用前景。
参考文献：
３．２用于课堂教学
在课堂教学中，公用的多媒体教室讲台上的电脑只安装了一些常用的软件，而且由于大家共用电脑，出现软件故障是常事，再加之教师上课地点的不固定性，给一些上应用软件课的教师带来了诸多不便，经常要装机。教师如果将应用软件教学
［１］陈代武．流媒体课件制作中关键技术研究［Ｊ］．计算机与现代化，
２００７．１０：９￣１１
［２］李志河．多媒体课件制作技术［Ｍ］．清华大学出版社，２００５．
ＣＥ
预测分析器的构造
６４
解决“环”的算法
ＣｏｍｐｕｔｅｒＥｒａＮｏ．３２００８
号对输入串进行预测分析，而预测的信息则存放在分析表的相矩阵的元素Ｍ［Ａ，ａ］中应入口里。分析表可用一个矩阵Ｍ表示。“＃”。矩阵元素的下标Ａ表示非终结符，ａ为终结符或句子括号
⑴将代码中的所有非终结符按预处理的结果顺序处理。⑵三种扫描方式：
①按顺序扫描ＦＩＲＳＴ集合（Ｘ１，Ｘ２，…，Ｘｎ），若该非终结符Ｘｊ需由另一个非终结符的Ｘｉ求得，那么若Ｘｉ排在Ｘｊ前面，则
将Ｘｉ代入Ｘｊ中；
Ｍ［Ａ，ａ］中存放着一条关于Ａ的产生式，即当用非终结符Ａ向
下推导，遇到输入符ａ时所应采取的候选产生式，当元素内容无产生式时，则表明用Ａ为左部向下推导时遇到了不该出现的符号，此时应转向出错处理。分析程序的工作流程如图１所示。
②逐一扫描按顺序排列的ＦＩＲＳＴ集合（Ｘ１，Ｘ２，…，Ｘｎ），若非终
结符的ＦＩＲＳＴ集合中含有它本身，则删除等式右部的该非终结符；
③从序号最大的非终结符的ＦＩＲＳＴ集开始，逐一扫描按顺
序排列的ＦＩＲＳＴ集合（Ｘ１，Ｘ２，…，Ｘｎ），若该非终结符Ｘｊ需由另一个非终结符的Ｘｉ求得，那么若Ｘｉ排在Ｘｊ后面，则将该Ｘｉ回代入Ｘｊ中，调用第②步。
⑶若所有非终结符的ＦＩＲＳＴ集中都已经为终结符，则