语法分析程序2

语法分析和语法分析程序4.1重点和难点4.1.1语法分析程序的功能语法分析程序乂简称称为分析器，它以单词串形式的源程序作为输入或分析的对象， 其基本任务是：根据程序设计语言的语法规则（即定义该语言的前厉文无关文法），分析 源程序的语法结构，即分析如何由这些单词纟fl成该源程序的各种语法成分（如下标变量、 函数、各种表达式、各程语句等等）,并在分析过程中进行语法正确性检查,产生内部形 式的中间代码，供编译程序后续阶段处理。日前，已存在许多语法分析方面的方法，但就产生语法树的方向而言，可人致把它们 分为自顶向下分析和自底向上分析两人类。4.1.2自顶向下的语法分析所谓自顶向卜的语法分析，是指对于给定输入串w,试图为其构造一个从文法开始符 号到w的最左推导S n w,或为w自上而下地构造一棵以S为根结点的语法树。如果这 -尝试得到成功，则证明w是相应文法的一个句子；反Z,则不是。在进行白顶向下的语法分析时，通常有下列两个障碍须加以解决：（1）由于采取了最左推导，故当相应方法法G中含有左递归的非终结符号时，便会 使语法分析过程陷入循环不己的状况。（2）采用最左推导以实现对符号串w的匹配，实际上杲一个用文法产生式的诸候选 式反复进行试探的过程，这势必会出现人量的冋溯，从而导致语法分析效率的大幅度下降。因此，欲实现白顶向下的语法分析，其首要任务是改造程序设计语言的文法,以消除 其中的左递归和避免冋溯的出现。1. 消除文法的左递归如果一个文法GS=（Vn, Vt, P, S）中的A产生式具有如下的形式：A-*A ci |IA a 2IIA aB il B 2II B m其中每个B i均不以A打头，则A是一个直接左递归的非终结符号。为消除此种左递归， 可引入一个新的非终结符号A，,并将上述A产生式改写为A->P1A,IP2A,l-l3mA,A-a 】AlgAITcinA即可。如果一个非终结符号A是经多步推导而出现的左递归，则可对相关产生式作代入操 作，将A产生式化成胃接左递归的，再按上面的方法将左递归消除。下面，再给出-种通过将文法G=(Vn, Vt, P, S)表示成矩阵形式而一次消除G的全部左递归的方法。 首先，令Vn=X, X2,，Xn),且对G的每个产生式Xjf Y |l Y 2I 丫 m(i=1,2,!)可将其写成Xi=Xi a 1 汁X2(I 2汁+Xna n汁Bi(i=l,2,n)其中：“二”和“ + ”分别代表原产生式中的“一”和若原产生式中不含以Xj开头的 候选式，则相应的aji=(b； “是原产生式中以终结符号开头的诸候选式之“和”。于是， 文法G的诸产生式便可写成如下的矩阵方程X,X2，,XJ=(X,X2,X"alla12alna21 a22 a2n anlan2 ann+ |PpP2,Pn或X=AB+B此方程有形如X=BA*的最小解，由于A*=I+AA若令Z11Z12InZ21Z22Z2nZnlZn2Znn则有其中X=BZZ=I+AZe e e将上述两矩阵式写成分量式，便得到一纟fl新的产生式，设它们所构成的文法为G，,则有 L(GO=L(G)0另外，由于向量B的各元素的每一项均是以终结符号打头的符号串，故矩阵 式X=BZ相应的齐产生式不含左递归的非终结符号；与矩阵式Z=I+AZ相应的各产生式显 然也不是左递归的。也就是说，通过两述两矩阵式，我们L1消除了原文法G的一切左递归。2. 消除回溯对于给定的文法GS=(Vn, Vt, P, S)和给定的输入符号串w=a】a2an(aVT),为 判断w是否为L(G)中的句子，现试图为w建立一个从S出发的最左推导，设经过若干步 推导后，得到S=>”A0 AevN P e(VNUVT)* 其中wI=a1a2-ai.1,即w的一个前缀切已从上而的推导得到匹配，现需对A B继续进行推 导，以期使余下的输入$ aiai+1-an也获得匹配。此时应使用A产生式进行推导，现设G 中的全部A产生式为A-* Y |l Y 2卜诃 Y m且对这m个候选式Yk (lWkWm),要么全部Y k B均不能推岀以舛打头的符号串(此时 wEL(G),要么若存在一个Y”能使丫沖推导出以舛打头的符号串，而其余的丫汁(lWkWm, kHj)则不能推出，这样，上述推导过程在产生式选择上的试探将可避免. 如果文法G中的全部产生式均满足上述要求，则消除冋溯的问题白然就解决了。可见，要实现无冋溯的白顶向下语法分析，对相应文法须有一定的要求。为导出文法 应满足的条件，需定义候选式y的终结首符集和非终结符号A的后继终结符号集如K：FIRST(y)二al Y,且 aevT, WFOLLOW(A)=alS#=>f a A a S ,且 aeVTU#); a , B eV*于是，对于一个己化简的非左递归文法G,在进行白顶向下语法分析时，不出现回溯 的必要充分条件是，对于G中的每个产生式A-Y.lYd-lYnp其各候选式均应满足：(1) 不同的候选式不能推出以同一终结符号打头的符号串，即FIRST( Y j) AFIRST( Yj)= * (IWi, jWm； iHj)(2) 若有Yjd f ,则其余候选式“所能推出的符号串不能以FOLLOW(A)中的终结 符号开始，即有FIRST( Y i) A FOLLOW(A)=(iW 1,2,m； iHj)通常，我们将满足上述条件的文法称为LL(1)文法。即对于此种文法，可采用自左至右扫 视源程序P,并按最左推导的方式求得与P中务符号的匹配，而且每步推导只需查看一个 输入符号，就可准确地选择所用的产生式。卜面，给出对给定文法G求出各个FIRST集和FOLLOW集的算法。由于每个产生式 的各候选式均是一个由文法符号所组成的符号串，因此仅须给出对单个文法符号求这两个 集合的方法即可。构造FIRST集合的算法对于G中的每一个文法符号XGVnUVt,为求FIRST(X),可反复应用如下的规则， 直到所求的FIRST集不再增大为止。(1) 若 XEVT,则 FIRST(X)= Xo(2) 若 XGVn，且有 X-aci ep(aevT),则令 aeFIRST(X)；若有 X- ep,则令 eFIRST(X)o(3) 若 X-Y,Y2-Ykep,且 YCVn，则令FIRST(Yi)- e )oFIRST(X)；而对任意的j (lWjWi1), YjGVn，且Yj=>l,则令FIRST(Y|)- oFIRST(X) (lWjWi) 特别当 eFIRST(Yj) (lWjWk)时,令 GFIRST(X)O构造FOLLOW集的算法对于G中的每一 AFVn,为构造FOLLOW(A),可反复使用如下的规则，直到每个 FOLLOW集不再增人为止。(1) 对于文法的开始符号S,令#eFOLLOW(S)o(2) 对于每 一 A-(iBBEP,令 FIRST(B)- gFOLLOW(B)。(3) 对于每 一 A-*ciBGP 或 A-aBBP,且 eFIRST(B),则令 FOLLOW(A) eFOLLW(B)o用來对LL(1)文法进行自顶向下语法分析的方法主要有两种，即递归下降分析法和预 测分析法。3. 递归下降分析法设G=(Vn, Vt, P, S)为一LL文法,并设VN=X1，X2,，Xn),所谓递归下降法, 是指对G的每个非终结符号Xi，都根据相应产生式各候选式的组成结构，为其构造一个子 程序(或函数)Pi (),用于识别X.所表示的语法成分.这组子程序便组成了所需的分析 器。构造子程Pi ()的方法如下：(1) 对于形如Xj- Y!lY2l-lYm的产生式，在相应子程序Pi()中，应含有判断当 前输入符号a属于哪个候选式Yj的FIRST集，并转入该候选式相应代码段继续识别的功 能。对候选式的选择可用if语句或case语句实现。(2) 于形如XlYiY?Yk (YjGVnUVt)的产生式，相应子程R ()是一个依次识 别其右部各符号Yj (j=1,2,k)的过程：如果YjevT,则判断当前输入符号是否与Yj匹 配；若YjW Vn则应有调用相应于Yj的子程序的代码。(3) 对于形如Xl 的产生式，在相应的子程序R()中，应含有判断当前输入符 号a是否属于集合FOLLOW(X.)而决定是从R ()返冋还是报错的代码(4) 在各个子程序R ()中，均应含有进行语法检查的代码。4. 预测分析法预测分析法是一种比递归下降法更为有效的白顶向下的语法分析方法。预测分析器由 一张预测分析表(也称为LL(1)分析表)、一个表驱动程序及一个分析栈组成，其输入是一 个以右界符#结尾的符号率。分析器在驱动程序的控制下，根据预测分析表的指示來完成 对输入符号串的分析。对不同的文法而言，驱动程序均一样，仅预测分析表不同。因此， 设计预测分析器的关键，在于根据给定文法构造其预测分析表。预测分析表可视为一个二维数组，它的每一行与文法的一个非终结符号相关联，而其 每一列则与一 个终结符号或界符井相关联。对于一个已给的LL(1)文法G,首先按前而所给出的算法分别求出各非终结符号的 FIRST集和FOLLOW集，然片再按如卜规则确定预测分析表的各个元素MA, a (AF VN, aeVTU#)0对于文法中的每个产生式A Y il 丫2卜1 Yju：(1) 若aeFIRST(Yi),则置MA, a二“A-Yi”,即当当前分析栈的栈顶符号为A, 而正扫视的输入符号为a时，按产生式A-Yi进行推导；(2) 若 WFIRST(Vj)且aWFOLLOW(A),贝置MA,缶“A-Yj”，即在此情况下按 产生式A-厂进行推导；(3) 除上述两种情况外，其余的一切表元索均置为“出错”。采用预测分析表的语法分析过程人致是：在分析开始时，甘先将界符#和文法的开始 符号s置于栈中，并使输入指示器指向输入串的首符号；然片按预测分析表的指示，逐步 対栈顶非终结符号进行推导，直到所推导出的终结符号串与输入符号串完全匹配（分析成 功），或分析器报错（输入串有语言错误）为止。4.1.3自底向上的语法分析所谓白底向上的语法分析，是指从给定的输入串w=a|a2-an岀发，试图利用相应文法 中的产生式,逐步将其归约为文法的开始符号S,即从叶结点aba2,-,an出发，试图逐步向 上构造一个语法树，而其根结点恰好为S。由于上述分析过程通常采用的是最左归约（即 规范归约），所以实现此种语法分析的关键，是在分析的每一步，如何寻找或确定当前句 型的句柄（或应最先归约的子串），以及确定将其归约为什么非终结符号。和白顶向下的分析过程一样，实现白底向上的分析，通常也需使用一个分析栈來存放 分析过程中所得的文法符号。分析开始时，在栈底放置一个界符#,然后将输入符号逐个 推入栈内，一旦在分析栈的栈顶出现句柄，就用相应产生式的左部去替换这个句柄，即进 行一次归约。由于归约，便得到了新的栈顶，此时再查看栈的顶部是否形成新的句柄：若 是，再进行归约；反之，则继续将后续的输入符号移入栈内，并重复上述过程。若最终能 将全部输入符号（不包括它的右界符#）移抻，且分析栈中只留下栈底符号#及最厉一步归 约所得的文法开始符号，则表明对输入串的分析己经成功。但若全部输入符号已被移掉， 而分析栈却不能出现上述格