当前位置：网站首页>[Compilation principle] Design principle and implementation of recursive descent parsing
[Compilation principle] Design principle and implementation of recursive descent parsing
2022-07-31 03:05:00 【Somia8889】
目录
Recursive subroutine block diagram
Aim to increase the conditional statements task
The new subroutine block diagram
Add conditional statements of test case
Add the conditional statements complete code
程序功能
Input the lexical analysis output of binary sequence,即某算术表达式“专题 1”的输出结果;
Output to the input string to the arithmetic expression of definition method of judging the result;
递归下降分析程序应能发现简单的语法错误;
Recursive drop program assignment statements can be analyzed and 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} | {=} |
Recursive subroutine block diagram
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.*;
//Storing recursive subroutine
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
//Read binary sequence type
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();
//The binary type processing topragram整型ArrayList中
program=new ArrayList<Integer>();
String sp=sb.toString();
for(int i=0;i<sp.length();i++) {
//Category number always tell in(左括号后面,Therefore identify left parenthesis
if(sp.charAt(i)=='(') {
i++;
int tid=0;
while(sp.charAt(i)>='0'&&sp.charAt(i)<='9') { //如果是数字
tid=tid*10+sp.charAt(i)-'0'; //更新数字,Ensure correct several digital input
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("Syntax analysis correctly！");
else System.out.println("\nAssignment statements wrong：在第"+current+"After the word symbol");
}
}
Aim to increase the conditional statements task
选做：如有可能,考虑如何用文法描述 C 语言的 if 语句,使整个文法仍然为 LL（1）文法,并使得你的Recursive drop program assignment statements can be analyzed and if 语句.
文法描述if语句大致如下：
<程序>→if(<比较语句>){<程序>}<Subsequent branches> | <赋值语句>
<Subsequent branches>→else{<程序>}|ε
<比较语句>→<变量><比较符号><表达式>
<比较符合>→>|<|==|!=|>=|<=
根据以上分析,Get can describeCLanguage assignment statements andif语句的文法如下：
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} | {=} |
The new subroutine block diagram
S→if(H){S}J
S→B
J→else{S}
J→ε
H→VKE
K→>|<|==|!=|>=|<=
Add conditional statements of test case
用例1：
结果：
用例2：
结果：
Add the conditional statements complete code
import java.util.*;
import java.io.*;
//Storing recursive subroutine
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
//Read binary sequence type
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();
//The binary type processing topragram整型ArrayList中
program=new ArrayList<Integer>();
String sp=sb.toString();
for(int i=0;i<sp.length();i++) {
//Category number always tell in(左括号后面,Therefore identify left parenthesis
if(sp.charAt(i)=='(') {
i++;
int tid=0;
while(sp.charAt(i)>='0'&&sp.charAt(i)<='9') { //如果是数字
tid=tid*10+sp.charAt(i)-'0'; //更新数字,Ensure correct several digital input
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("Syntax analysis correctly！");
else System.out.println("\nifStatements or assignment statements wrong：在第"+current+"After the word symbol");
}
}边栏推荐
猜你喜欢
YOLOV5学习笔记（三）——网络模块详解
10 Permission introduction
The whole process scheduling, MySQL and Sqoop
Moxa NPort 设备缺陷可能使关键基础设施遭受破坏性攻击
Getting Started with CefSharp - winform
Discourse 自定义头部链接（Custom Header Links）
YOLOV5 study notes (2) - environment installation + operation + training
自动化办公案例：如何自动生成期数据？
STM32问题合集
What is a distributed lock?Three ways of implementing distributed lock
随机推荐
SQL注入 Less47(报错注入) 和Less49(时间盲注)
Mysql 45讲学习笔记（二十五）MYSQL保证高可用
【shell基础】判断目录是否为空
【CocosCreator 3.5】CocosCreator 获取网络状态
Moxa NPort device flaw could expose critical infrastructure to devastating attack
CorelDRAW2022 streamlined Asia Pacific new features in detail
刚出道“一战成名”，安全、舒适一个不落
[Godot][GDScript] 二维洞穴地图随机生成
12 Disk related commands
局域网电脑硬件信息收集工具
JetPack component Databinding
【编译原理】递归下降语法分析设计原理与实现
The difference between link and @import
【C语言】求两个整数m和n的最大公因数和最小公倍数之和一般方法，经典解法
共模电感的仿真应用来了，满满的干货送给大家
IDEA 注释报红解决
2022 Nioke Multi-School League Game 4 Solution
分布式与集群是什么 ？ 区别是什么？
Map.Entry理解和应用
软件积累 -- 截图软件ScreenToGif