（1）<声明语句>::=Var <表达式>“:” “integer”“;” （2）<表达式>::=<标识符><表达式> （3）<表达式>::=“,”<表达式> （4）<标识符>:: =id
（5）<表达式>::=@（空操作）
单词序列Var x,y:integer;之所以能表示成如上图4的语法树，依据的是赋值语句和表达式的定义规则。 4. 系统实现
4.1开发工具的选用及介绍
MFC的主要优点是可以用物件导向的方法来使用Windows API，以及应用程式开发的便捷。 MFC将很多应用程序开发中常用的功能自动化，并且提供了文档框架检视结构和活动文档这样的便于自订的应用程序框架。同时，在Visual C++内部也内建了很多对MFC的例如类这样的支援以减少软件开发的时间，使用类可以生成从hello world这样的简单程序到活动文档服务器这样的复杂程序。MFC的消息响应机制也避免了使用性能较低的庞大虚拟函数式表。
MFC,微软基础类(Microsoft Foundation Classes),实际上是微软提供的,用于在C++环境下编写应用程序的一个框架和引擎,VC++是Windows下开发人员使用的专业C++ SDK(SDK, Standard Software Develop Kit,专业软件开发平台),MFC就是挂在它之上的一个辅助软件开发包,MFC作为与VC++血肉相连的部分，MFC同BC++集成的VCL一样是一个非外挂式的软件包,只不过MFC类是微软为VC++专配的。
MFC是对Windows API的封装，大大简化了我们的工作；学VC主要就是要学MFC，大约有100多个类，但常用的也就二三十个。应该像背4级单词一样将这些常用类搞懂；当然不需要死记，通过看帮助、看例子、动手练习就可学会它们；而且，并非每个类内部的所有函数都要学会，要日积月累。如果真的想成为高手，做个笔记本把自己认为重要的类、函数记下来，随时学习，也是很好的突击方法。 4.2本实验实现
在我的毕业设计中，具体实现的是一个Toyl语言语法分析系统的设计与实现，主要的工作有：设计一个词法规则，规定什么样的单词是可接受的即正确的，并将这些正确的单词归类，然后设计一个文法规则，分析输入的程序是否符合所规定文法的规则，如不符合做错误处理。实现步骤如下： 4.2.1词法分析
设计词法规则：确定有如下的单词集和相应的Token表示：
（1）标示符（x,.....） (ID ,\ （2）正整数（10,...） (NUM ,\ （3）加号（+） (ADD ,\ （4）分号（;） (SEMI ,\ （5）冒号（:） (COLON ,\ （6）赋值号（:=） (ASS ,\ （7）小于号（<） (LT ,\ （8）小于等于号（<=） (LE ,\
6
（9）保留字（begin） (保留字 ,\
自动机如下：
L D D L other D other //（标示符和保留字） //（正整数） ?+? //（加号）
?*? //（乘号） ?:? =
?;? //（分号）
?(? //（左括号） ?)? //（右括号） ?#? //# '\\0'
//（结束）
图 5 根据词法规则做出的自动机
注释： 表示结束， 表示中间状态 表示起始状态。自动机以外的情况为出错状态。识别正误单词并进行分类的算法实现如下： While(程序没结束) {
接收下一个字符；
While(如果是空格或tab键或换行键） 接收下一个字符； While (1) {
If(是单词) 退出； Else if(是数字) 退出； Else if（是+号） 退出； Else if（是-号） 退出； Else if（是；号） 退出；
//（赋值号）
7
Else if（是：号） 退出； Else if（是:=号） 退出； Else if（是<号） 退出； Else if（是<=号） 退出； Else if（是保留字） 退出； } }
4.2.2语法分析
设计文法规则：
（1）prog------>begin SL end # （16）P1------>@ （2）SL------>S S1 （17）P------>( E ) （3）S1------>S S1 （18）P------>ID （4）S1------>@ （19）P------>NUM （5）S------>ID := E ; （20）addop------>+ （6）S------>read ( IL ) ; （21）addop------>-
（7）S------>write ( EL ) ; （22）S------>if N then S ELSE （8）IL------>ID I1 （23）N------>ID < NUM （9）I1------>, ID I1 （24）ELSE------>else S （10）I1------>@ （25）ELSE------>@ （11）EL------>E E1 （26）S------>var M : integer ; （12）E1------>, E E1 （27）M------>ID Q （13）E1------>@ （28）Q------>, M （14）E------>P P1 （29）Q------>@ （15）P1------>addop P P1
（30）S------>@
手工分析得到该文法非终极符的First和Follow集如表1
8
表1 First和Follow集
First Follow prog begin # SL id,read,write,if,other end S id,read,write,if,other id,read,if,other,end S1 id,read,write,if,other end E (,id,n id,read,if,other,end,; IL id, ) EL (,id,n ) I1 , ), , E1 , ) , P (,id,n +，-，），； P1 +，- ),; addop +，- (,id,n ELSE else id,read,write,if,other
同时可得该文法的Predict集表，如表2所示
表2 文法的Predict集表 Predict(P) Predict集 First(begin SL end) begin First(S S1) id read write if Var First(S S1) id read write if Var (First(@)-@)uFollow(S1) end First(id:=E;) id First(read(IL);) read First(write(EL);) write First(id I1) id First(, id I1) , (First(@)-@)uFollow(I1) ) First(E E1;) id n ( First(,E E1;) , (First(@)-@)uFollow(E1) ) First(P P1;) id n ( First(addop P P1;) (First(@)-@)uFollow(P1) , ; ) First((E)) ( First(id) id First(num) n First(+) +
9
First(-) First(if N then S ELSE) First(ID < NUM) First(else S) (First(@)-@)uFollow(ELSE) First(var M : integer ;) First(ID Q) First(, M) (First(@)-@)uFollow(Q) (First(@)-@)uFollow(S) - if id else id read write if Var Var id , : id,read,if,other,end
同时可得LL分析表，如表3所示
表3 LL分析表 prog SL S S1 E IL EL I1 E1 P P1 addop ELSE id num := 2 5 5 14 8 11 18 25 14 11 19 , 9 12 ; 11 + - ( 14 11 17 ) begin end read 10 13 16 1 4 2 6 3 25 write 2 7 3 25 # if other else 2 22 3 25 2 23 3 25 24 16 16 15 15 20 21
输入程序于文法进行匹配的算法，实现如下：
注释：st2是从符号栈中弹出来的一个符号，可能是终极符也可能是非终极符； Match为整型数，若接收的Token与st2匹配则置为1；
此函数只是一个大概思想，需要不断重复调用，从第一个文法prog开始，到完全匹配或出错处理为止。
if(st2等于Token的seman或者st2等于Token的classs) {match赋值为1;} //此时st2为终极符； Else if //即为st2为非终极符； {
if(st2等于分析表第一列上的某个非终极符) {
10