当前位置：网站首页>[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");
}
}边栏推荐
猜你喜欢
字体压缩神器font-spider的使用
LeetCode简单题之两个数组间的距离值
SQL injection Less46 (injection after order by + rand() Boolean blind injection)
软件积累 -- 截图软件ScreenToGif
MP使用时的几个常见报错
5. SAP ABAP OData 服务如何支持 $filter (过滤)操作
Addition and Subtraction of Scores in LeetCode Medium Questions
图解lower_bound＆upper_bound
12 Disk related commands
知识蒸馏7：知识蒸馏代码详解
随机推荐
execsnoop 工具
【Android】Room —— SQLite的替代品
工程（五）——小目标检测tph-yolov5
遗留系统的自动化策略
15、网站统计数据
冒泡排序、选择排序、直接插入排序、二分法查找
5. SAP ABAP OData 服务如何支持 $filter (过滤)操作
知识蒸馏7：知识蒸馏代码详解
你们程序员为什么不靠自己的项目谋生？而必须为其他人打工？
TCP详解（三）
The simulation application of common mode inductance is here, full of dry goods for everyone
MP使用时的几个常见报错
C primer plus学习笔记 —— 8、结构体
12 磁盘相关命令
The whole process scheduling, MySQL and Sqoop
Discourse 自定义头部链接（Custom Header Links）
Analysis summary - self-use
[Android] Room - Alternative to SQLite
选好冒烟测试用例，为进入QA的制品包把好第一道关
学习DAVID数据库(1)