3语法分析方法及分析表设计
3.1语法分析法——LL(1)法
3.1.1基本思想
LL(1)法师一种自顶向下的分析方法。从文法的开始符号出发,根据当前的输入符号(单词符号)唯一的确定选用哪个产生式替换相应非终结符以往下推导,或如何构造一棵相应的语法树。该方法的关键是要确定唯一的候选式。
LL(1)的含义是:第一个L表明自顶向下分析是从左向右扫描输入串;第二个L表明分析过程中将用最左推导,1表明只需向右看一个符号便可决定如何推导即选择哪个产生式进行推导。
3.1.2分析步骤
1 首先要判断该文法是否是LL(1)文法,需要计算该文法中的非终结符的First集,Follow集,从而计算出产生式的Select集,如果同一个非终结符定义的不同产生式的Select集之间交集为空,就唯一的确定下一个产生式,这样就不会出向二义性,确保了能够正确的完成语法分析。
2 构造文法的预测分析表,本文法的预测分析表在下面给出。
3 词法分析输出的单词已经映射成一个个字符,对这些字符构成的字符串进行预测分析。
3.2根据文法得到的预测分析表
While ( ) i n < = > + - * / #
S S->While
(B)
A=G
B B->EYE B->EYE B->EYE
A A->i
G G->E G->E G->E
Y Y->< Y->= Y->>
E E->(E)M E->iM E->nM
R R->+ R->- R->* R->/
M M->ε M->REM M->REM M->REM M->REM M->ε
4中间代码形式的描述及中间代码序列的结构设计
4.1三地址代码的描述
在本程序中用到了三地址语句的输出包括以下的种类:
赋值语句:x:= y Y z
复制语句:x:= y
条件判断语句: x Y y R z Y q
其中Y代表算术运算符,R代表比较运算符。
4.2本程序中的三地址代码
S -> while (B) A=G L0:=if (B) goto L1 else goto Lnext
A -> i A:= i
B -> E Y E B:= E1 Y E2
Y -> < Y:= <
Y -> = Y:= =
Y -> > Y:= >
E -> (E)M E1:= (E2) M
E -> iM E:= i M
E -> nM E:= n M
M -> +EM M1:= +E M2
M -> -EM M1:= -E M2
M -> *EM M1:= *E M2
M -> /EM M1:= /E M2
M ->ε M:= ε
G ->E G:= E
5简要的分析与概要设计
5.1简要分析
首先要进行词法分析,将.txt文件中得字符串读出来,分离成一个个的单词。为了在后面的分析中能够吧一个单词当作一个字符来看,词法分析中要用结构来保存分析出来的单词。
LL(1)分析方法就是根据文法得出的预测分析表,来确定当栈顶符号遇到符号串的首字符是是否有产生式,用哪个产生式,并要保证唯一性,否则就不是LL(1)文法了。这需要先将 # 和文法开始符号 S 压入符号栈中,然后判断栈顶符号和符号串的首字符是否相同。如果相同就消除该符号和字符;否则就着到它们在预测分析表中确定的项(产生式)。将产生式的右部逆序压入栈中来替换左部(该符号),字符串的当前指针也向后移动一个字符,来表示剩余字符串,然后重新比较栈顶符号和符号串的首字符,只到栈中只剩下#,这时如果剩余符号串中也只剩下#就表示该字符串语法正确。然后根据符号串的属性,分析的结果和符号之间的优先关系按三地址形式输出。
当然while语句中式可以还有嵌套的while语句的。但这不影响该方法的分析过程的。另外在分析过程中,用一定的格式输出分析过程,每分析一步就输出一次,出错就报告错误,这样就很容易在结果显示屏幕上看出错误发生在哪个地方。
5.2程序的概要设计
本程序的是此案需要依次经过词法分析,语法分析,语义分析,输出这些步骤,且每部分的输出是下个部分的输入。那我就按该过程来设计程序。用一个函数来进行词法分析,一个函数进行语法分析,一个函数进行属性分析以输出三地址码。当然还要有读取文件和输出的函数,主函数。还要定义个结构来存取单词的属性,另外要有单词的映射函数。
6详细的算法描述
6.1程序的整体流程:在main()主函数的描述
Void main() mian()流程图:
{
open();
lexical();
pasring();
output();
close();
}