当前位置：网站首页>[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");
}
}边栏推荐
- Analysis summary - self-use
- Problems that need to be solved in distributed system architecture
- Getting Started with CefSharp - winform
- IIR滤波器和FIR滤波器
- Moxa NPort device flaw could expose critical infrastructure to devastating attack
- SonarQube的BUG定义
- Mysql 45讲学习笔记（二十四）MYSQL主从一致
- 冒泡排序、选择排序、直接插入排序、二分法查找
- 局域网电脑硬件信息收集工具
- STM32问题合集
猜你喜欢
Detailed explanation of TCP (3)
LeetCode简单题之找到和最大的长度为 K 的子序列
12 Disk related commands
【编译原理】递归下降语法分析设计原理与实现
Software accumulation -- Screenshot software ScreenToGif
![Installation of mysql5.7.37 under CentOS7 [perfect solution]](/img/ef/a89d8bfd09377dc30034bad99dfd07.png)
Installation of mysql5.7.37 under CentOS7 [perfect solution]
11、Redis实现关注、取消关注以及关注和粉丝列表
MultipartFile file upload
4. Sensitive word filtering (prefix tree)
什么是分布式锁？实现分布式锁的三种方式
随机推荐
The use of font compression artifact font-spider
Mysql 45讲学习笔记（二十五）MYSQL保证高可用
CorelDRAW2022 streamlined Asia Pacific new features in detail
【CV项目调试】CUDNN_CONVOLUTION_FWD_SPECIFY_WORKSPACE_LIMIT问题
一份高质量的测试用例如何养成？
SQL injection Less54 (limited number of SQL injection + union injection)
MultipartFile file upload
mycat的主从关系 垂直分库 水平分表 以及mycat分片联表查询的配置详解（mysql5.7系列）
学习DAVID数据库(1)
【Cocos Creator 3.5】缓动系统停止所有动画
TCP详解（二）
想从手工测试转岗自动化测试，需要学习哪些技能？
【C语言基础】解决C语言error: expected ‘；‘, ‘,‘ or ‘)‘ before ‘＆‘ token
The whole process scheduling, MySQL and Sqoop
Chapter 9 SVM Practice
SQL注入 Less54(限制次数的SQL注入+union注入)
WebSocket Session为null
局域网电脑硬件信息收集工具
Ambiguous method call.both
遗留系统的自动化策略