当前位置：网站首页>[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");
}
}边栏推荐
- CentOS7下mysql5.7.37的安装【完美方案】
- VS QT——ui不显示新添加成员（控件）||代码无提示
- 8. Unified exception handling (controller notifies @ControllerAdvice global configuration class, @ExceptionHandler handles exceptions uniformly)
- execsnoop tool
- 【C语言】求两个整数m和n的最大公因数和最小公倍数之和一般方法，经典解法
- 编译Hudi
- 【CocosCreator 3.5】CocosCreator 获取网络状态
- 共模电感的仿真应用来了，满满的干货送给大家
- YOLOV5学习笔记（三）——网络模块详解
- 2022 Nioke Multi-School League Game 4 Solution
猜你喜欢
IDEA 注释报红解决
学习DAVID数据库(1)
11. Redis implements follow, unfollow, and follow and follower lists
华为分布式存储FusionStorage知识点总结【面试篇】
品牌广告投放平台的中台化应用与实践
What is a distributed lock?Three ways of implementing distributed lock
刚出道“一战成名”，安全、舒适一个不落
分布式与集群是什么 ？ 区别是什么？
Crypto Firms Offer Offer To Theft Hackers: Keep A Little, Give The Rest
php 网站的多语言设置（IP地址区分国内国外）
随机推荐
8、统一处理异常（控制器通知@ControllerAdvice全局配置类、@ExceptionHandler统一处理异常）
点云DBSCAN聚类（MATLAB，非内置函数）
【编译原理】词法分析程序设计原理与实现
MP使用时的几个常见报错
Project (5) - Small target detection tph-yolov5
Several common errors when using MP
LeetCode中等题之分数加减运算
Discourse 自定义头部链接（Custom Header Links）
【Android】Room —— SQLite的替代品
接口测试关键技术
Clustering index, and what is the difference between a clustering index
学习DAVID数据库(1)
MultipartFile文件上传
局域网电脑硬件信息收集工具
False positives and false negatives in testing are equally worthy of repeated corrections
Moxa NPort 设备缺陷可能使关键基础设施遭受破坏性攻击
JetPack component Databinding
Compile Hudi
Mysql 45讲学习笔记（二十五）MYSQL保证高可用
7年经验，功能测试工程师该如何一步步提升自己的能力呢？