当前位置：网站首页>[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");
}
}边栏推荐
- Problems that need to be solved in distributed system architecture
- 【编译原理】递归下降语法分析设计原理与实现
- Local area network computer hardware information collection tool
- 跨专业考研难度大？“上岸”成功率低？这份实用攻略请收下！
- 自动化办公案例：如何自动生成期数据？
- The use of font compression artifact font-spider
- 工程（五）——小目标检测tph-yolov5
- 如何搭建私有yum源
- Chapter 9 SVM Practice
- QML的使用
猜你喜欢
Ambiguous method call.both
6. Display comments and replies
局域网电脑硬件信息收集工具
Office automation case: how to automatically generate period data?
品牌广告投放平台的中台化应用与实践
【C语言】进制转换一般方法
CorelDRAW2022精简亚太新增功能详细介绍
SQL injection Less54 (limited number of SQL injection + union injection)
跨专业考研难度大？“上岸”成功率低？这份实用攻略请收下！
Project (5) - Small target detection tph-yolov5
随机推荐
Mysql 45讲学习笔记（二十五）MYSQL保证高可用
Discussion on Service Commitment of Class Objects under Multithreading
Local area network computer hardware information collection tool
SQL injection Less47 (error injection) and Less49 (time blind injection)
Problems that need to be solved in distributed system architecture
CloudCompare＆PCL 计算两个点云之间的重叠度
Office automation case: how to automatically generate period data?
【Cocos Creator 3.5】缓动系统停止所有动画
原子操作 CAS
选好冒烟测试用例，为进入QA的制品包把好第一道关
CefSharp入门-winform
Clustering index, and what is the difference between a clustering index
mycat的主从关系 垂直分库 水平分表 以及mycat分片联表查询的配置详解（mysql5.7系列）
自动化办公案例：如何自动生成期数据？
JS 函数 this上下文 运行时点语法 圆括号 数组 IIFE 定时器 延时器 self.备份上下文 call apply
The difference between link and @import
【C语言】表达式求值的一般方法
CentOS7下mysql5.7.37的卸载【完美方案】
【C语言】求两个整数m和n的最大公因数和最小公倍数之和一般方法，经典解法
软件积累 -- 截图软件ScreenToGif