资源描述：
《ll_1_预测分析程序设计与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第21卷第8期重庆工学院学报(自然科学版)2007年8月Vol.21No.8JournalofChongqingInstituteofTechnology(NaturalScienceEdition)Aug.2007【计算机与信息技术】XLL(1)预测分析程序设计与实现曹琼(重庆工学院,重庆400050)摘要:讨论了编译原理中理解和实现都比较困难而又在语法分析中占重要位置的LL(1)预测分析方法.从对该方法的理解入手,构造了该方法实现中的关键数据结构,同时阐述了依据此数据结构编程实现的思路.结果表明:该方法可以正确、准
2、确地识别指定文法的句子.关键词:LL(1)预测分析;编译原理;文法;句子中图分类号:TP314文献标识码:A文章编号:1671-0924(2007)08-0142-03DesignandRealizationofLL(1)PredicativeAnalysisProcedureCAOQiong(ChongqingInstituteofTechnology,Chongqing400050,China)Abstract:ThispaperdiscussesLL(1)predictiveanalysisalgorithm,w
3、hichisaveryimportantingrammat2icalanalysisandisalsohardtounderstandandrealize.Startingwiththeunderstandingofthisalgorithm,thispaperconstructsthekeydatastructureinprogram,andexpatiatesontherealizingroutinesofprogram2mingbasedonthesedatastructure.Resultsshowthatit
4、cancorrectly,exactlyjudgeastatementwhetheragivensentencebelongstoagrammarornot.Keywords:LL(1)predictiveanalysis;compilerprinciples;grammar;sentence在一个编译器中,语法分析器的位置举足轻LL(1)预测分析方法中第1个L代表从左向重,这是因为有不少编译器,在语法分析阶段都伴右扫描输入,第2个L代表产生最左推导,1代表随了语义分析直至中间代码生成,囊括了编译器在决定语法分析器的每
5、一步动作时(选择推导)向[2]中的大部分内容.常见的语法分析方法主要有自前扫描一个输入符号.上而下分析方法和自下而上分析方法2种,其中自上而下的分析方法包括有递归下降法和LL(1)1LL(1)预测分析方法预测分析法,自下而上的分析方法包括算符优先分析和LR分析方法.LL(1)预测分析方法以其执在对文法进行LL(1)预测分析时,要求文法一[1]行效率高,便于维护的优点而被广泛采用.定要是LL(1)文法.LL(1)文法的判定条件是:①X收稿日期:2007-06-12基金项目:国防科工委纵向课题资助项目(H102006A00
6、4).作者简介:曹琼(1979—),女,四川邻水人,硕士,主要从事软件工程方面的研究.©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net曹琼:LL(1)预测分析程序设计与实现143文法不含左递归;②对文法中的任一个非终结符了.A的各个产生式的候选首终结符集两两不相交,即若A→α1/α2/⋯/αn则:First(αi)∩First(αj)=2LL(1)预测分析方法的设计与实现<(i≠j)
7、;③对文法中的每个非终结符A,若它的某个首终结符集含有ε,则First(A)∩Follow(A)=预测分析的核心是构造预测分析表,而预测<.分析表的构造基础是文法非终结符的候选首终结[6]LL(1)预测分析的分析流程为:若a∈符集First(A)和后随符号集Follow(A).所以,预First(A→αi),则使用αi去执行匹配任务.若a不测分析技术的实现可以划分为如下3个步骤:①属于任何一个产生式的首终结符集,当ε不属于求文法非终结符的候选首终结符集和后随符号任何一个First(A→αi)时,则出错,当ε属于某个集;
8、②构造预测分析表;③根据输入符号和预测First(A→αi),同时a∈Follow(A)时,则让A与ε分析表对句子进行分析.自动匹配,否则,a的出现是一种语法错误.考虑到构造预测分析表的需要,对非终结符通常是构造一个预测分析表矩阵M[A,a]来的每个候选式求出其对应的候选首终结符集,也存储从非终结符到终结符(包括#)规则的映就是对
