编译原理实验（自上而下的语法分析）

自上而下的语法分析（Java描述）

【问题描述】
依据给定的LL(1)文法，识别输入符号串是否是文法的合法句子。

【基本要求】
1、输入 LL(1)文法、待识别的符号串。
2、实现由 LL(1)文法构造 First 集和 Follow 集的算法。
3、根据First 集和 Follow 集构造相应的预测分析表。
4、实现预测分析技术的总控程序。
5、输出识别过程(推导或语法树)及结论。

【测试用例】

$\bullet$ 文法G[S]产生式如下：

S -> (L) | a
L -> L,S | S

$\bullet$ 我们不难发现给定文法中存在左递归，消除左递归后的文法：（程序中使用‘&’表示空）

S -> (L) | a
L -> Sl
l -> ,Sl | $\epsilon$

$\bullet$ 测试输入串：

合法：(a,(a,a))#
合法：(a,(a,a),(a,a))#
非法：(a,(aa))#


【构造文法First集】

先声明文法类的数据结构：

    public class WenFa {char BeginSymbol; //文法的开始符StringBuffer terminator; //终结符StringBuffer nonterminator; //非终结符ArrayList<startNode> production; //文法产生式存储入口WenFa(){terminator = new StringBuffer("");nonterminator = new StringBuffer("");}}

构造 First(A)集的步骤如下：
扫描所有左部为 A 的产生式，

(1)、若Ａ->$\epsilon$ ，则将$\epsilon$并入 First(A)。

(2)、若Ａ->a ，则将 a 并入 First(A)。

(3)、若Ａ->B……，则将 First(B)并入 First(A)。

(4)、若Ａ->XB……或Ａ->Xa……，且 X->$\epsilon$，则类似于(2)、(3)处理。

下面是文法类（WenFa）所拥有的方法，功能是求一个非终结符的First集：

    //求一个非终结符的first集public HashSet getFirstCollection(char C){HashSet firstSet = new HashSet(); //定义first集for(startNode startnode : production){ //遍历非终结符if(startnode.val==C){ //非终结符匹配Node node = startnode.next;while(node!=null){//遇到终结符，直接加入first集if(isTerminator(node.val)==true){firstSet.add(node.val);while(node.next1!=null) //其他产生式node = node.next1;node = node.next2;}//遇到非终结符else if(isNonterminator(node.val)==true){HashSet ha = new HashSet(getFirstCollection(node.val));ha.remove('&'); //非终结符First集去空firstSet.addAll(ha); //递归调用while(node.next1!=null) //转至其他产生式node = node.next1;node = node.next2;}	}}//System.out.println(firstSet);}return firstSet;}

测试输出First集：



【构造文法Follow集】

构造 Follow(A)集的步骤如下：
扫描所有右部包含 A 的产生式，

(1)、若 B->xAy ，则将 First(y)中的非$\epsilon$终极符并入 Follow(A)。

(2)、若 B->xA，或者 B->xAy 且 y->$\epsilon$则将 Follow(B)并入 Follow(A)。

(3)、若Ａ是开始符，则将 ‘#’ 并入 Follow(A)。

注意：Follow集中是不出现$\epsilon$的

算法思路：
在每一个产生式中逐个字符匹配A，若匹配成功则检查A的下一个字符char；

1、若char是终结符，则将char加入Follow(A)。

2、若char是非终结符，将First(char)加入Follow(A)；若char还可以推出空，将Follow(char)加入Follow(A)。

3、若char为空，即不存在下一个字符，A是产生式最末端的字符。则将此产生式左端的字符的Follow集加入Follow(A)。此处注意判断此产生式左端的字符与A是否相同，若相同会出现无限递归的情况。注意避免。

4、对Follow(A)去空。

求一个非终结符的Follow集算法同样是文法类（WenFa）所有的方法：

    //求一个非终结符的follow集public HashSet getFollowCollection(char C){HashSet followSet = new HashSet(); //定义follow集//是开始符号if(C==BeginSymbol)followSet.add('#');for(startNode startnode : production){ //遍历非终结符Node node = startnode.next;while(node!=null){//1当前字符与C匹配成功if(node.val==C){ //1.1当前字符不在产生式末端if(node.next1!=null){//1.1.1下一个字符是终结符if(isTerminator(node.next1.val)==true){followSet.add(node.next1.val); //情况1：将后一个终结符字符加入//转下一个产生式while(node.next1!=null){node=node.next1;}node = node.next2;}//1.1.2下一个字符是非终结符else{ //System.out.println("getFirstCollection of "+node.next1.val+" = "+getFirstCollection(node.next1.val));//====followSet.addAll(getFirstCollection(node.next1.val)); //加入非终结符的First集if(getFirstCollection(node.next1.val).contains('&')) //如果此非终结符可推出空followSet.addAll(getFollowCollection(node.next1.val)); //加入Follow集while(node.next1!=null){node=node.next1;}node = node.next2;}}//1.2当前字符在产生式末端else{if(C!=startnode.val){ //此判断避免陷入无限递归//System.out.println("getFollowCollection of "+startnode.val+" = "+getFollowCollection(startnode.val));//====followSet.addAll(getFollowCollection(startnode.val));}node = node.next2;}}//2当前字符与C未匹配成功else{ if(node.next1!=null) //检验下一个字符node = node.next1;else				//检验下一个产生式node = node.next2;}//System.out.println(followSet);}	}followSet.remove('&'); //集合去空（空用‘&’表示）return followSet;}

测试输出Follow集：

【构造预测分析表】

预测分析表中存储的是某一非终结符遇到某一终结符时可使用的关于此非终结符的产生式。

此处不显式用数组存储预测分析表，只给出相关算法，支持查询相关产生式的功能，代替预测分析表。

下面算法接受两个字符：一个非终结符statue和一个终结符letter。返回一个StringBuffer类的字符串对应产生式信息。

1、若letter在First(statue）中，查询左端为statue的产生式：

（1）若产生式右端第一个字符是letter，搜索成功，返回当前产生式；否则，进行（2）

（2）若产生式右端第一个字符是非终结符，判断letter是否在这个非终结符的First集中。若在，搜索成功，返回当前产生式。

2、letter不在First(statue)中但在Follow(statue)中：搜索成功，返回空转换$\epsilon$。

3、letter既不在First(statue)中又不在Follow(statue)中：搜索完成，返回产生式为空。（输入串错误）

	//查询预测分析表得到对应产生式public StringBuffer searchProduction(char statue,char letter){StringBuffer pro = new StringBuffer("");//输入字符在当前非终结符的First集中if(getFirstCollection(statue).contains(letter)){for(startNode startnode : production){ //遍历非终结符if(startnode.val==statue){ //定位到非终结符Node node = startnode.next;while(node!=null){if(isTerminator(node.val)==true){ //遇终结符if(node.val==letter) //锁定first集，生成产生式{while(node!=null){pro.append(node.val);node = node.next1;}}}else{ //遇非终结符HashSet set = new HashSet(getFirstCollection(node.val));if(set.contains(letter)){ //锁定first集，生成产生式while(node!=null){pro.append(node.val);node = node.next1;}}}//进行下一产生式if(node!=null){ //避免指针指空while(node.next1!=null)node = node.next1;node = node.next2;}}}}}else{//输入字符在当前非终结符的Follow集中if(getFollowCollection(statue).contains(letter)){pro.append('&'); //空转换}			}return pro;}

【输入串分析】

根据预测分析过程的特点，定义两个数据结构：

符号栈：stack，存储分析过程中的匹配符号。

输入串队列：queue，存储分析过程中的输入串。

算法步骤：

1、输入串以字符形式进入队列，’#’ 和文法开始符依次入栈。

2、设置文法分析循环标志 analyseFlag，并赋初值为0。

3、弹出stack栈顶元素c1并获取队列queue首个元素c2

若c1= ‘#’，且c1=c2，则输入串分析成功，文法合法。analyseFlag=1，算法结束。

若c1= ’#‘，但c1!=c2，则输入串分析成功，文法不合法。analyseFlag=-1，算法结束。

若c1!= ‘#’，但c1=c2，则表明匹配成功一次，队列queue首元素弹出。

若c1!= ‘#’，且c1!=c2，则表明此次匹配不成功，查询预测分析表，获取当前已出栈元素和当前队列首元素所对应的产生式。将产生式划分为字符，倒序入栈。若对应的产生式为$\epsilon$，则空字再紧接着出栈。输出显示stack和queue中的元素，展示分析过程。

4、若文法分析循环标志 analyseFlag = 0，重复步骤3。

对输入字符分析的算法同样是文法类（WenFa）所有的方法：

    //对输入串进行语法分析public void AnalyseSentence(StringBuffer inputSen){LinkedList queue = new LinkedList(); //输入串队列for(char c : inputSen.toString().toCharArray()){queue.add(c);}int analyseFlag = 0; //文法分析循环标志Stack stack = new Stack(); //符号栈stack.push('#'); //'#'进栈		stack.push(BeginSymbol); //文法开始符进栈System.out.println(stack);System.out.println(queue);while(analyseFlag == 0){char c1 = (char) stack.pop(); //出栈char c2 = (char) queue.getFirst(); //获取队列首元素if(c1=='#'){if(c1==c2){analyseFlag = 1; //分析成功stack.push('#'); //多余一步，为了输出方便观察break;}else{analyseFlag = -1; //分析失败，出现错误break;}}if(c1==c2){queue.pollFirst(); //首元素出队列}//c1!=c2，产生式入栈else{String str = searchProduction(c1,c2).toString();System.out.println("Production = "+str+"\n");if(str!=null){char[] array = str.toCharArray();for(int i=array.length-1;i>=0;i--){stack.push(array[i]); //产生式倒序入栈}if(array.length==1){if(array[0]=='&')stack.pop(); //空字出栈}System.out.print("stack = "+stack+"   ");System.out.print("queue = "+queue+"   ");}elseanalyseFlag = -1; //出现错误}}System.out.println("\n\nstack = "+stack+"   queue = "+queue);switch(analyseFlag){case 1:System.out.println("\n分析成功！语句合法！");break;case 0:System.out.println("\n分析失败...");break;default:System.out.println("\n分析完成，语句不合法");}}

【实例测试】
1、输入串为 “(a,(a,a))#”

2、输入串为 “(a,(aa))#”

写在最后：

由于本人水平有限，数据结构设计及算法实现不可避免会有漏洞或不足之处。欢迎大家指出思路和代码中的不足，也期待大佬分享更简洁精巧的代码实现。

欢迎转载！（注明出处 嘻嘻）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！