基于VC的LL语法分析器设计和实现

基于 VC++LL（1）语法分析器设计和实现作者姓名：晏丽智 指导老师：王一宾摘要：语法分析是编译过程关键部分，能够粗略分为自上而下分析法和自下而上分析法。LL（1）文法是一类能够进行确定自上而下语法分析文法。本文首先叙述了 LL（1）文法基础理论，然后着重讨论了 LL（1）语法分析器设计，最终用 VC++实现了 LL（1）语法分析器。关键词：LL（1）文法，FIRST 集，FOLLOW 集，估量分析表0 引言语法分析是编译过程关键部分，它任务是在词法分析识别出单词符号串基础上，分析并判定程序语法结构是否符合语法规则。LL（1）文法是一类能够进行确定自上而下语法分析文法。本文讨论了LL（1）语法分析器工作原理和过程，关键说明了 FIRST 集、FOLLOW 集和估量分析表结构。1 LL（1）语法分析器基础理论1.1 理论基础语法分析是编译过程关键部分，它任务是在词法分析识别出单词符号串基础上，分析并判定程序语法结构是否符合语法规则。 语法分析器工作本质：按文法产生式，识别输入符号串是否为一个句子，判定是否能从文法开始符号出发推导出这个输入串。LL（1）文法是一类能够进行确定自上而下语法分析文法。自上而下分析方法基础思想是从文法开始符号出发，向下推导，推出句子；即对任何输入串，试图用一切可能措施，从文法开始符号出发，自上而下地为输入串建立一棵语法树 [1]。实现这种自上而下分析法存在很多困难，首先是递归问题，一个文法是含有左递归，假如存在非终止符 P，有 P Pa，则含有左递归文法将使上述自上而下分析过程陷入无限循环。所以，使用自上而下分析法必需消除文法左递归。其次是回溯问题。因为回溯造成匹配虚假现象，把已经做一大堆语义工作推倒重来。这些事情既麻烦又费时间，所以，最好应设法消除回溯。1.2 左递归消除直接消除见诸于产生式中左递归是比较轻易。假定相关非终止符 P 规则为 P →Pα|ß 其中，ß 不以 P 开头。那么我们能够把 P 规则改写为以下非直接左递归形式：P→ßP’P’→ αP’| ε(ε 为空字)这种形式和原来形式是等价，也就是说，从 P 推出符号串是相同。通常而言，假定相关 P 全部产生式是 P→Pα1|Pα2|…|Pαm|β1|β2|…βn 其中 α 全部不等于 ε ，且每个 β 不以 P 开头。则改写后为 P →β1P´|β2P´|…|βnP´ P´→ α1P´|α2P´|…|αmP´| ε使用这个方法，我们轻易把见诸于表面全部直接左递归全部消除掉，也就是说，把直接左递归全部...