2024年LL1语法分析实验报告

LL(1)語法分析试验名称：实現LL分析。试验规定：输入任意文法消除左递归消除左因子测试任意输入語句与否合法数据构造描述算法阐明输出first集合输出follow集合输出LL(1)表三．设计原理及算法描述所谓LL（1）分析法，就是指從左到右扫描输入串（源程序），同步采用最左推导，且對每次直接推导只需向前看一种输入符号，便可确定目前所应當选择的规则。实現LL（1）分析的程序又称為LL（1）分析程序或LL1（1）分析器。一种文法要能進行LL（1）分析，那么這個文法应當满足：無二义性，無左递归，無左公因子。當文法满足条件後，再分别构造文法每個非终止符的FIRST和FOLLOW集合，然後根据FIRST和FOLLOW集合构造LL（1）分析表，最终运用分析表，根据LL(1)語法分析构造一种分析器。LL（1）的語法分析程序包括了三個部分，總控程序，预测分析表函数，先進先出的語法分析栈，本程序也是采用了同样的措施進行語法分析，该程序是采用了C語言来编写，其逻辑构造图如下：LL（1）预测分析程序的總控程序在任何時候都是按STACK栈顶符号X和目前的输入符号a做哪种過程的。對于任何（X，a），總控程序每次都执行下述三种也許的動作之一：（１）若X=a=‘#’，则宣布分析成功，停止分析過程。（２）若X=a‘#’，则把X從STACK栈顶弹出，让a指向下一种输入符号。（３）若X是一种非终止符，则查看预测分析表M。若M[A，a]中寄存著有关X的一种产生式，那么，首先把X弹出STACK栈顶，然後，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号為ε，则不推什么東西進STACK栈）。若M[A，a]中寄存著“出錯標志”，则调用出錯诊断程序ERROR。实际上，LL（1）的分析是根据文法构造的，它反应了對应文法所定义的語言的固定特性，因此在LL（1）分析器中，实际上是以LL（1）分析表替代對应措施来進行分析的。2．构造LL(1)分析表考察文法G[E]：E→E+T|TT→T*F|FF→(E)|i|x|y我們轻易看出此文法没有左公因子也没有二义性，但却存在两個直接左递归，這裏我們运用引入新非终止符的措施来消除它使措施满足规定，即：對形如：U→Ux|y的产生式（其中x,yV+，y不以U開頭），引入一种新的非终止符U’後，可以等价地改写成為：U→yU’U’→xU’|ε显然改写後，U和U’都不是左递归的非终止符。因此文法G［E］按上述措施消去左递归後可等价地写成：E→TPP→+TP|εT→FQQ→*FQ|εF→(E)|i|x|y在构造LL(1)预测分析表之前，首先要构造该文法的每個非终止符的FIRST和FOLLOW集合，按照下面描述的算法来构造這两個集合。①FIRST集合的构造算法：（1）若X∈VT，则FIRST（X）={X}。（2）若X∈VN，且有产生式X→a……，则把a加入到FIRST(X)中；若X→ε也是一条产生式，则把ε也加到FIRST(X)中。（3）若X→Y……是一种产生式且Y∈VN，则把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；若X→Y1Y2…Yk是一种产生式，Y1，…，Yi-1都是非终止符，并且，對于任何j，1≤j≤i-1，FIRST(Yj)都具有ε（即Y1…Yi-1*ε），则把FIRST(Yj)中的所有非ε-元素都加到FIRST(X)中；尤其是，若所有的FIRST(Yj)均具有ε，j=1,2,…，k，则把ε加到FIRST(X)中。持续使用上面的规则，直至每個集合FIRST不再增大為止。②FOLLOW集合的构造算法：（1）對于文法的開始符号S，置#于FOLLOW(S)中；（2）若A→αBβ是一种产生式，则把FIRST(β)|{ε}加至FOLLOW(B)中；（3）若A→αB是一种产生式，或A→αBβ是一种产生式而βε（即ε∈FIRST(β)），则把FOLLOW(A)加至FOLLOW(B)中。持续使用上面的规则，直至每個集合FOLLOW不再增大為止。目前来构造G［E］的LL（1）预测分析表。预测分析表M[A,a]是如下形式的一种矩阵。A為非终止符，a是终止符或‘#’。矩阵元素M[A,a]中寄存這一条有关A的产生式，指出當A面临输入符号a是所应采用的规则。M[A,a]也也許寄存一条“出錯標志”，指出當A主线不该面临输入符号a。4．运用分析表進行预测分析带预测分析的PDA1）總程序的算法描述如下：BEGIN首先把‘#’然後把文法開始符号推進STACK栈；把第一种输入符号讀進a;FLAG:=TRUE;WHILEFLAGDOBEGIN把栈顶符号出栈到X中；IFXÎVTTHENIFX=aTHEN把下一输入符号讀進aELSEERRORELSEIFX=‘#’THENIFX=aTHENFLAG:=FALSEELSEERRORELSEIFM[A,a]={X®x1x2…xk}THEN把xk,xk–1,…,x1依次進栈/*若x1,x2…xk=e，则不進栈*/ELSEERRORENDOFWHILE;STOP/*分析成功，過程結束*/END四．重要数据构造描述1.chartermin[50];/*终止符号*/charnon_ter[50];/*非终止符号*/charv[50];/*所有符号*/charleft[50];/*左部*/charright[50][50];/*右部*/charfirst[50][50],follow[50][50];/*各产生式右部的FIRST和左部的FOLLOW集合*/intM[20][20];/*二维数组存储分析表*/栈T用来寄存产生式的右边Str数组寄存要分析的句子串运行成果：ERTWF#+*()i#测试文法G[E