【编译原理】递归下降语法分析设计原理与实现程序功能目标任务First集和Follow集递归子程序框图测试用例完整代码增加条件语句的目标任务增加条件语句的First集和Follow集新增子程序框图添加条件语句的测试用例添加条件语句的完整代码

86 阅读 0 评论 57 点赞

我是靠谱客的博主勤劳小馒头，最近开发中收集的这篇文章主要介绍【编译原理】递归下降语法分析设计原理与实现程序功能目标任务First集和Follow集递归子程序框图测试用例完整代码增加条件语句的目标任务增加条件语句的First集和Follow集新增子程序框图添加条件语句的测试用例添加条件语句的完整代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

程序功能

目标任务

First集和Follow集

递归子程序框图

测试用例

完整代码

增加条件语句的目标任务

增加条件语句的First集和Follow集

新增子程序框图

添加条件语句的测试用例

添加条件语句的完整代码

程序功能

输入词法分析输出的二元式序列，即某算术表达式“专题 1”的输出结果；

输出输入串是否为该文法定义的算术表达式的判断结果；

递归下降分析程序应能发现简单的语法错误；

递归下降程序可以分析赋值语句和 if 语句。

目标任务

完成以下描述赋值语句的 LL(1)文法的递归下降分析程序

G[S]: S→V=E

E→TE′

E′→ATE′|ε

T→FT′

T′→MFT′|ε

F→ (E)|i

A→+|-

M→*|/

V→i

终结符号 i 为用户定义的简单变量，即标识符的定义。

First集和Follow集

产生式	First集	Follow集
S→V=E	{i}	{#}
E→TE′	{(,i)	{),#}
E′→ATE′ E′→ε	{+,-} {ε}	{),#}
T→FT′	{(,i}	{+,-,),#}
T′→MFT′ T′→ε	{*,/} {ε}	{+,-,),#}
F→ (E) F→i	{(} {i}	{*,/,+,-,),#}
A→+ A→-	{+} {-}	{(,i}
M→* M→/	{*} {/}	{(,i}
V→i	{i}	{=}

递归子程序框图

S→V=E

E→TE′

E′→ATE′

E′→ε

T→FT′

T′→MFT′

T′→ε

F→ (E)

F→i

A→+

A→-

M→*

M→/

V→i

测试用例

用例1：

结果：

用例2：

结果：

完整代码

import java.util.*;
import java.io.*;
import java.math.*;

//存放递归子程序
class RecusionFunc{
	public void advance() {    //指针后移一位
		DGXJYF.current++;
	}
	public boolean S() {
		if(DGXJYF.program.get(DGXJYF.current)!=1)  //current=i?
			return false;
		if(!V()) return false;   //V=true?
		if(DGXJYF.program.get(DGXJYF.current)!=27)  //current==?
			return false;
		advance();
		if(!E()) return false;   //E=true?
		System.out.println("S");
		return true;
	}
	public boolean E() {
		if(DGXJYF.program.get(DGXJYF.current)!=1&&DGXJYF.program.get(DGXJYF.current)!=19)  //current=i或(?
			return false;
		if(!T()) return false;   //T=true?
		if(!Ep()) return false;  //Ep=true?
		System.out.print("E<-");
		return true;
	}
	public boolean Ep() {
		if(DGXJYF.program.get(DGXJYF.current)!=14&&DGXJYF.program.get(DGXJYF.current)!=15)  //current=+或-?
		{
			if(DGXJYF.program.get(DGXJYF.current)!=20&&DGXJYF.program.get(DGXJYF.current)!=-1)  //current=)或#?
				return false;
			else{
				System.out.print("E'<-");
				return true;
			}
		}
		if(!A()) return false;   //A=true?
		if(!T()) return false;   //T=true?
		if(Ep()) {
			System.out.print("E'<-");
			return true;
		}
		else return false;
	}
	public boolean T() {
		if(DGXJYF.program.get(DGXJYF.current)!=1&&DGXJYF.program.get(DGXJYF.current)!=19)  //current=i或(?
			return false;
		if(!F()) return false;   //F=true?
		if(!Tp()) return false;  //Tp=true?
		System.out.print("T<-");
		return true;
	}
	public boolean Tp() {
		if(DGXJYF.program.get(DGXJYF.current)!=16&&DGXJYF.program.get(DGXJYF.current)!=29)  //current=*或/?
		{
			if(DGXJYF.program.get(DGXJYF.current)!=14&&DGXJYF.program.get(DGXJYF.current)!=15&&
					DGXJYF.program.get(DGXJYF.current)!=20&&DGXJYF.program.get(DGXJYF.current)!=-1)  
				//current=+或-或)或#?
				return false;
			else{
				System.out.print("T'<-");
				return true;
			}
		}
		if(!M()) return false;   //A=true?
		if(!F()) return false;   //T=true?
		if(Tp()) {
			System.out.print("T'<-");
			return true;
		}
		else return false;
	}
	public boolean F() {
		if(DGXJYF.program.get(DGXJYF.current)!=19)   //current=(?
		{
			if(DGXJYF.program.get(DGXJYF.current)!=1)    //current=i?
				return false;
			else {
				advance();
				System.out.print("F<-");
				return true;
			}
		}
		advance();
		if(!E()) return false;   //E=true?
		if(DGXJYF.program.get(DGXJYF.current)!=20)   //current=)?
			return false;
		advance();
		System.out.print("F<-");
		return true;
	}
	public boolean A() {
		if(DGXJYF.program.get(DGXJYF.current)!=14)  //current=+?
		{
			if(DGXJYF.program.get(DGXJYF.current)!=15)   //current=-?
				return false;
		}
		advance();
		System.out.print("A<-");
		return true;
	}
	public boolean M() {
		if(DGXJYF.program.get(DGXJYF.current)!=16)  //current=*?
		{
			if(DGXJYF.program.get(DGXJYF.current)!=29)   //current=/?
				return false;
		}
		advance();
		System.out.print("M<-");
		return true;
	}
	public boolean V() {
		if(DGXJYF.program.get(DGXJYF.current)!=1)   //current=i?
			return false;
		advance();
		System.out.print("V<-");
		return true;
	}
}


public class DGXJYF {
	public static int current;
	public static ArrayList<Integer> program;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//读入二元式序列
		File file=new File("test2.txt");
		Scanner in=new Scanner(file);
		StringBuffer sb=new StringBuffer();
		while(in.hasNextLine()) {
			String t=in.next();
			sb.append(t);
		}
		in.close();
		//把二元式处理到pragram整型ArrayList中
		program=new ArrayList<Integer>();
		String sp=sb.toString();
		for(int i=0;i<sp.length();i++) {
			//类别编号总跟在(左括号后面，因此识别左括号
			if(sp.charAt(i)=='(') {
				i++;
				int tid=0;
				while(sp.charAt(i)>='0'&&sp.charAt(i)<='9') {  //如果是数字
					tid=tid*10+sp.charAt(i)-'0';    //更新数字，保证多位的数字正确输入
					i++;
				}
				i--;
				if(tid>0)
					program.add(tid);
			}
		}
		program.add(-1);     //表示结束的#
		for(int i=0;i<program.size();i++)
			System.out.println(program.get(i));
		current=0;
		RecusionFunc rf=new RecusionFunc();
		if(rf.S()) System.out.println("语法分析正确！");
		else System.out.println("n赋值语句错误：在第"+current+"个单词符号后");
	}

}

增加条件语句的目标任务

选做：如有可能，考虑如何用文法描述 C 语言的 if 语句，使整个文法仍然为 LL（1）文法，并使得你的递归下降程序可以分析赋值语句和 if 语句。

文法描述if语句大致如下：

<程序>→if(<比较语句>){<程序>}<后续分支> | <赋值语句>

<后续分支>→else{<程序>}|ε

<比较语句>→<变量><比较符号><表达式>

<比较符合>→>|<|==|!=|>=|<=

根据以上分析，得到可以描述C语言中赋值语句和if语句的文法如下：

G[S]: S→if(H){S}J|B

J→else{S}|ε

H→VKE

K→>|<|==|!=|>=|<=

B→V=E;

E→TE′

E′→ATE′|ε

T→FT′

T′→MFT′|ε

F→ (E)|i

A→+|-

M→*|/

V→i

增加条件语句的First集和Follow集

产生式	First集	Follow集
S→if(H){S}J S→B	{if} {i}	{#,}}
J→else{S} J→ε	{else} {ε}	{#,}}
H→VKE	{i}	{)}
K→>\|<\|==\|!=\|>=\|<=	{>,<,==,!=,>=,<=}	{(,i}
B→V=E;	{i}	{#,}}
E→TE′	{(,i)	{;,)}
E′→ATE′ E′→ε	{+,-} {ε}	{;,)}
T→FT′	{(,i}	{+,-,;,)}
T′→MFT′ T′→ε	{*,/} {ε}	{+,-,;,)}
F→ (E) F→i	{(} {i}	{*,/,+,-,;,)}
A→+ A→-	{+} {-}	{(,i}
M→* M→/	{*} {/}	{(,i}
V→i	{i}	{=}

新增子程序框图

S→if(H){S}J

S→B

J→else{S}

J→ε

H→VKE

K→>|<|==|!=|>=|<=

添加条件语句的测试用例

用例1：

结果：

用例2：

结果：

添加条件语句的完整代码

import java.util.*;
import java.io.*;

//存放递归子程序
class RecusionFunc{
	public int times=0;
	public void advance() {    //指针后移一位
		DGXJXZ.current++;
	}
	public boolean S() {
		int did=times;
		times++;
		if(DGXJXZ.program.get(DGXJXZ.current)!=7)    //current=if?
		{
			if(DGXJXZ.program.get(DGXJXZ.current)!=1)   //current=i?
				return false;
			if(!B()) return false;   //B=true?
			return true;
		}
		advance();
		if(DGXJXZ.program.get(DGXJXZ.current)!=19)   //cuurent=(?
			return false;
		advance();
		if(!H()) return false;   //H=true?
		if(DGXJXZ.program.get(DGXJXZ.current)!=20)   //current=)?
			return false;
		advance();
		if(DGXJXZ.program.get(DGXJXZ.current)!=23)   //current={?
			return false;
		advance();
		if(!S()) return false;   //S=true?
		if(DGXJXZ.program.get(DGXJXZ.current)!=24)   //current=}?
			return false;
		advance();
		if(!J()) return false;   //J=true?
		if(did>0)
			System.out.println("S<-");
		else System.out.println("S");
		return true;
	}
	public boolean J() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=8)   //current=else?
		{
			if(DGXJXZ.program.get(DGXJXZ.current)!=24&&DGXJXZ.program.get(DGXJXZ.current)!=-1)
				//current=#或}?
				return false;
			else return true;
		}
		advance();
		if(DGXJXZ.program.get(DGXJXZ.current)!=23)  //current={?
			return false;
		advance();
		if(!S()) return false;   //S=true?
		if(DGXJXZ.program.get(DGXJXZ.current)!=24)   //current=}?
			return false;
		advance();
		return true;
	}
	public boolean H() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=1)   //current=i?
			return false;
		if(!V()) return false;   //V=true?
		if(!K()) return false;   //K=true?
		if(!E()) return false;   //E=true?
		return true;
	}
	public boolean K() {
		if(DGXJXZ.program.get(DGXJXZ.current)==25)   //current=>
		{
			advance();
			return true;
		}
		if(DGXJXZ.program.get(DGXJXZ.current)==26)   //current=<
		{
			advance();
			return true;
		}
		if(DGXJXZ.program.get(DGXJXZ.current)==33)   //current===
		{
			advance();
			return true;
		}
		if(DGXJXZ.program.get(DGXJXZ.current)==32)   //current=!=
		{
			advance();
			return true;
		}
		if(DGXJXZ.program.get(DGXJXZ.current)==30)   //current=>=
		{
			advance();
			return true;
		}
		if(DGXJXZ.program.get(DGXJXZ.current)==31)   //current=<=
		{
			advance();
			return true;
		}
		return false;
	}
	
	
	public boolean B() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=1)  //current=i?
			return false;
		if(!V()) return false;   //V=true?
		if(DGXJXZ.program.get(DGXJXZ.current)!=27)  //current==?
			return false;
		advance();
		if(!E()) return false;   //E=true?
		if(DGXJXZ.program.get(DGXJXZ.current)!=17)   //current=;?
			return false;
		advance();
		System.out.print("B<-");
		return true;
	}
	public boolean E() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=1&&DGXJXZ.program.get(DGXJXZ.current)!=19)  //current=i或(?
			return false;
		if(!T()) return false;   //T=true?
		if(!Ep()) return false;  //Ep=true?
		System.out.print("E<-");
		return true;
	}
	public boolean Ep() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=14&&DGXJXZ.program.get(DGXJXZ.current)!=15)  //current=+或-?
		{
			if(DGXJXZ.program.get(DGXJXZ.current)!=20&&DGXJXZ.program.get(DGXJXZ.current)!=17)  //current=)或#?
				return false;
			else{
				System.out.print("E'<-");
				return true;
			}
		}
		if(!A()) return false;   //A=true?
		if(!T()) return false;   //T=true?
		if(Ep()) {
			System.out.print("E'<-");
			return true;
		}
		else return false;
	}
	public boolean T() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=1&&DGXJXZ.program.get(DGXJXZ.current)!=19)  //current=i或(?
			return false;
		if(!F()) return false;   //F=true?
		if(!Tp()) return false;  //Tp=true?
		System.out.print("T<-");
		return true;
	}
	public boolean Tp() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=16&&DGXJXZ.program.get(DGXJXZ.current)!=29)  //current=*或/?
		{
			if(DGXJXZ.program.get(DGXJXZ.current)!=14&&DGXJXZ.program.get(DGXJXZ.current)!=15&&
					DGXJXZ.program.get(DGXJXZ.current)!=20&&DGXJXZ.program.get(DGXJXZ.current)!=17)  
				//current=+或-或)或#?
				return false;
			else{
				System.out.print("T'<-");
				return true;
			}
		}
		if(!M()) return false;   //A=true?
		if(!F()) return false;   //T=true?
		if(Tp()) {
			System.out.print("T'<-");
			return true;
		}
		else return false;
	}
	public boolean F() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=19)   //current=(?
		{
			if(DGXJXZ.program.get(DGXJXZ.current)!=1)    //current=i?
				return false;
			else {
				advance();
				System.out.print("F<-");
				return true;
			}
		}
		advance();
		if(!E()) return false;   //E=true?
		if(DGXJXZ.program.get(DGXJXZ.current)!=20)   //current=)?
			return false;
		advance();
		System.out.print("F<-");
		return true;
	}
	public boolean A() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=14)  //current=+?
		{
			if(DGXJXZ.program.get(DGXJXZ.current)!=15)   //current=-?
				return false;
		}
		advance();
		System.out.print("A<-");
		return true;
	}
	public boolean M() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=16)  //current=*?
		{
			if(DGXJXZ.program.get(DGXJXZ.current)!=29)   //current=/?
				return false;
		}
		advance();
		System.out.print("M<-");
		return true;
	}
	public boolean V() {
		if(DGXJXZ.program.get(DGXJXZ.current)!=1)   //current=i?
			return false;
		advance();
		System.out.print("V<-");
		return true;
	}
}


public class DGXJXZ {
	public static int current;
	public static ArrayList<Integer> program;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//读入二元式序列
		File file=new File("test4.txt");
		Scanner in=new Scanner(file);
		StringBuffer sb=new StringBuffer();
		while(in.hasNextLine()) {
			String t=in.next();
			sb.append(t);
		}
		in.close();
		//把二元式处理到pragram整型ArrayList中
		program=new ArrayList<Integer>();
		String sp=sb.toString();
		for(int i=0;i<sp.length();i++) {
			//类别编号总跟在(左括号后面，因此识别左括号
			if(sp.charAt(i)=='(') {
				i++;
				int tid=0;
				while(sp.charAt(i)>='0'&&sp.charAt(i)<='9') {  //如果是数字
					tid=tid*10+sp.charAt(i)-'0';    //更新数字，保证多位的数字正确输入
					i++;
				}
				i--;
				if(tid>0)
					program.add(tid);
			}
		}
		program.add(-1);     //表示结束的#
		for(int i=0;i<program.size();i++)
			System.out.println(program.get(i));
		current=0;
		RecusionFunc rf=new RecusionFunc();
		if(rf.S()) System.out.println("语法分析正确！");
		else System.out.println("nif语句或赋值语句错误：在第"+current+"个单词符号后");
	}

}