比较一下此时的Token的seman或classs是否与该终极符对应的该行上的某一个 非终极符相等，若有一个且只有一个相等，取出该行该列的数，赋值给 index， 则将该数对应的第index文法放进符号栈；
}
Else 为出错； }
Else 否则出错；
4.2.3画出一颗语法树
画一棵语法树的具体算法实现： While(输入的待分析程序没有结束) {
接收进一个token;
从符号栈中弹出一个符号赋值给st2；
弹出当前st2的层数，以及他的父节点有几个子节点和它是第几个子节点； 弹出父节点的坐标；
根据上述信息计算出st2点的坐标， 并将st2 和他的父节点连接起来； 接收下一个token； }
在这个实现中主要用到9个堆栈，五个是第一次画树时使用的，剩下四个栈是在窗口重绘时使用的。 例：输入下列程序： begin
var x,y:integer; read(y); end #
画出的树如下图6所示
11
prog : M ; integer ； S S1 Var ： ID Q read ( IL ) ; @ , I D I1 M @ ID Q @ S S1 Begin SL end # 图6 语句“begin var x,y:integer;read(y);end” 语法树
4.3界面设计与重点代码的设计
（1）首先将覆盖在主框架上的CEditView分为两个视类，使得在第一个类中输入程序，第二个
视中输出分析结果
BOOL CMainFrame::OnCreateClient(LPCREATESTRUCT lpcs, CCreateContext* pContext) {
// TODO: Add your specialized code here and/or call the base class //创建一个静态分栏窗口，分为二行一列
if(m_wndSplitter1.CreateStatic(this,2,1)==NULL)
return FALSE;
// 将CCuteFTPView连接到0行0列窗格上
m_wndSplitter1.CreateView(0,0,RUNTIME_CLASS(CCompileView),CSize(100,100), pContext);
m_wndSplitter1.CreateView(1,0,RUNTIME_CLASS(CView2),CSize(100,100), pContext);
12
}
// 将CView4连接到0行1列 return TRUE;
//return CFrameWnd::OnCreateClient(lpcs, pContext);
图7 运行出来的界面
如图7中，上边一个文本框为第一个view,其中输入要分析的源程序，下边的文本框为第二个view，在其中输出分析结果。
（2）点击各个菜单项即可运行相应功能并能做出相应结果
例如输入一段程序后，点击词法分析的各个键的结果
图9 词法分析的功能键
（3）点击语法分析的各个键的结果
图10 语法分析各个功能键
4.4 实现环境 （1）软件环境 Windows XP Visual studio C++6.0 （2）硬件环境
Pentium III 450以上的CPU处理器，64MB以上的内存，200MB的自由硬盘空间、CD-ROM
驱动器、能支持24位真彩色的显示卡。
13
5 结束语
本程序基本实现的功能有：输入一个程序，按照规定的文法可以进行词法与语法分析并构造出一棵语法树，可以在分析的同时检查出一些错误，如果是一些严重的错误，程序就直接结束。 下面再谈一下需要继续改进的地方
（1）系统的设计有些欠妥当，因为文法已经写进程序中，只能分析固定文法的程序。解决办法：编一个程序，输入一个文法，然后用程序将这一文法的first 集和follow集识别出来，自动生成一个分析表，然后再与输入的待分析程序进行比较、匹配。
（2）因为整个系统的设计是一边学MFC一边做的，所以数据结构方面感觉安排的不是很好 致在最后做语法分析那一块，用了需要申请很大的内存，空间效率和时间效率都有待提高！解决办法：可以用MFC自带自带的堆栈结构等尽量解决这一问题。 致谢
首先衷心感谢我的导师谷波老师，本论文是在他的精心指导下完成的。在我的学习和实习 的过程中，谷老师给与我很大的帮助，他严谨的治学态度，广博的专业知识，对工作认真负责的精神，和蔼可亲的为人给我留下了深刻的印象，并深深地影响着我，这将使我在今后的工作和学习中受用无穷。在此，我想谷老师表示衷心的感谢。另外我还特别要感谢我的同学们，感谢你们在平时的学习和生活中的热心帮助。我还要感谢我的家人，是他们对我的无私支持，使我安心完成学业。感谢所有在我学习期间给予我帮助的所有老师、同学和朋友们！ 参考文献
[1] HAlshawi and D Carter. Training and Scaling P reference Functions for Disambiguation.
Computational Linguistics, 1996,20 (4),635-638
[2] R Bod. Data-Oriented Parsing (DOP). Proceedings COLING'92, Nantes, France. 1992
[3] T L Booth and R A Thompson. Applying Probability Measures to Abstract Languages. IEEE Transactions on Computers, C-22(5),442-450
[4] E Brill. Automatic Grammar Induction and Parsing Free Text, A Transformation-Based Approach. In
Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics.1993 [5] K Church. A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text. Second
Conference on Applied Natural Language Processing, ACL,1988
[6] M Collin. Head-Driven Statistical Models for Natural Language Parsing. Ph, D. Thesis, the
University of Pennsylvania, 1999 A P Dumpster, N M Laird and D B Rubin. Maximum Likelihood
from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society,1977
[7] J Goodman. Parsing Algorithms and Metrics. In Proceedings of the Fourth International Workshop on
Parsing Technologics,1997
[8] J Goodman. Parsing Inside-Out. h. D .Thesis, Harvard University,1998
[9] F Jelinek, JD Lafferty and R L Mercer. Basic Methods of Probabilistic Context Free Grammars.
14
NATOASI Series, 1992,F75,345-360
[10] M A Jones and J M Eisner. Anrobahilisci, n-a., A its application. In Proceedings of National
Conference on Artificial Intelligence( AAAI-92).San Jose,1992,32 2-328 [11] Joshua T. Goodman. Parsing Inside-Out. Ph. D. thesis, Harvard University,1998
[12] 朱胜火，周明，刘听，黄昌宁.一种有效的概率上下文无关文法分析算法.软件学报，1998;9(8),592-597 [13] 王挺，史晓东，陈火旺，杨谊.一种用未分析语料训练文法的方法.软件学报，1998,9(l）；36-42 [14] 周强，黄昌宁.基于局部优化的汉语句法分析方法学报，1999,10(l）；4-6
Design and Implementation of the system on Toyl Language grammar
Analysis
Abstract：In this paper, a more comprehensive overview to the status of the compiler and the role of the principle has done, including the status and role in the history of the computer industry, as well as the main role it in computer systems. A detailed introduction about the design process which is involved in compile ，and about the main focus of the experiment---lexical analysis, syntax analysis and syntax tree structure and the achievement , and a brief overview on other processes has done . The concrete realization of the lexical analysis, syntax analysis, and syntax tree structure are introduced with the design of key algorithms and key algorithm. Through the work of this thesis, the reader can fully understand a complete analysis to the system of Toyl language grammar Design and Implementation of the process.
Keywords：Compilation Principle; lexical analysis; syntax analysis; LL analysis; grammar
15