编译原理实验-LL(1)分析.docx

实验三 语法分析---LL （1）分析器 目录 TOC \o 1-5 \h \z 一 . 实验的目的与思路 2 （1） 目的 2 （2） 思路 2 二 . 基本的功能 3 三．总体设计 4 四．详细设计 5 五 .源程序清单 6 六.源代码 6 实验的目的与思路 1) 目的 用程序的方法实现语法分析的 LL (1)方法。 2) 思路 本程序是采用的LL (1)方法进行的语法分析，而 LL (1)的分析方法是属于自 上而下的方法。 自上而下分析的基本思想是： 对任意输入串， 试图用一切可能的方法， 从文法开 始符号(根结点)出发，自上而下为输入串建立一棵语法树。从推导的角度看，它是 从文法的开始符号出发，反复使用各种产生式，寻找与输入串匹配的推导。 在输入之前必须要进行该文法是不是 LL ( 1 )文法的判断，然后再构造相应的 LL (1)分析表来用预测分析方法进行语法分析，依据下面的文法及分析表来设计程 序实现预测分析的分析过程。 文法 G[E] ： E --E+T|T T --T*F|F F --(E) | i 通过观察可知道该文法是一个左递归文法，要进行语法分析就必须消除左递 归才能继续判断它是不是 LL( 1)文法，然后才能用预测分析方法进行语法分析。 消除左递归： E --TM M --+TM|u T --FQ Q --*FQ|u F --(E) | i 在进行 LL ( 1)文法的判断： ( 1. ) 各非终结符的 FIRST 集如下： FIRST ( E) = FIRST ( TM) = {( ， i } FIRST ( M) = { + } FIRST ( T) = {( ， i } FIRST ( Q) = { * } FIRST ( F) = { ( ， i } 2.)各非终结符的 FOLLOW 集如下： FOLLOW ( E ) = { ) ， # } FOLLOW ( M ) = { ) ， # } FOLLOW ( T ) = { + ， )， # } FOLLOW ( Q) = { + ， )， # }  FOLLOW ( F) = { * ，+， ) ，# } (3.)各产生式的 SELECT集如下： SELECT (E TM ) ={ ( ,i } SELECT (M +TM ) ={+} SELECT (M u) ={ }, #} SELECT (T FQ) ={ ( ,i } SELECT (Q *FQ ) ={ *} SELECT (Q u) ={ +，), # } SELECT (F (E)) ={() SELECT (F i)={ i } 因为： SELECT (M +TM )n SELECT (M u)二① SELECT (Q *FQ )n SELECT ( Q u)=① SELECT (F (E) )n SELECT (F i)二① 因此可以判断该文法是一个 LL (1)文法可以构造预测分析表。 5.根据可选集构造预测分析表如下： 1 1 + * ( ) U E E—TI E-TI[ M I-+TI lku I-u T T-FQ T-FQ Q Q-u Q-*FQ Q讥 Q-u F F-i 1 .基本的功能 下面主要采用了 LL( 1)分析方法来进行语法分析，先通过判断该文法是不是LL( 1)文法，如果不是先将其改写成 LL( 1)文法，再将 LL( 1)文法改造成等 价形式------LL ( 1)分析表，通过分析表来进行语法分析，本程序的主要功能是对 一个文法句子的生成过程进行分析。 三.总体设计 LL (1)的语法分析程序包含了三个部分，总控程序，预测分析表函数，先 进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析其功能模型图如 下： LL( 1)语法分析功能模型图 本程序是采用预测的分析方法，因此预测分析方法的基本算法如下： 判断该文法是不是 LL( 1)文法，如果该文法不是 LL( 1)文法，则修改该文法继 续判断该文法是不是 LL( 1)文法，如果是则进行第二步，否则不运行。 构造预测分析表： 1.对文法G的每个产生式A-a执行第二步和第三步； 2 .对每个终结符 a € FIRST(a),把A-a加至L[A,a]中； 若 € FIRST(a),则对任意 b €FOLLOW(A把 A-a 加至 L[A,b]中； 把所有无定义的 L[A,a]标上“出错标志”; 上述算法可应用于任何文法 G以构造它的预测分析表 L。但是对于某些文 法，有些L[A,a]可能持有若干个产生式，或者说有些 L[A,a]可能是多重定义的。 如果G是左递归或是二义的，那么 L至少含有一个多重定义入口。因此，消除左 递归和提取左因子将有助于获得无多重定义的分析表 L。本题是