当前位置：网站首页>Compilation principle research study topic 2 -- recursive descent syntax analysis design principle and Implementation
Compilation principle research study topic 2 -- recursive descent syntax analysis design principle and Implementation
2022-07-29 00:11:00 【dor.yang】
1 Experimental content
Complete the following description of the assignment statement LL(1) Recursive descent analysis program of grammar
G[S]: S→ V=E
E→ TE’
E’→ ATE’ | e
T→ FT’
T’→ MFT’ | E
F→ (E) | i
A→ + | -
M→ * | /
V→ i
Design description ： Terminator i Simple variables defined for users , That is, the definition of identifier .
2 The experimental requirements
（1） The input string should be the output binary sequence of lexical analysis , That is, an arithmetic expression “ project 1” Output result of , The output is the judgment result of whether the input string is the arithmetic expression defined by the grammar ;
（2） Recursive descent analysis program should be able to find simple syntax errors ;
（3） Design two test cases （ As complete as possible , Right and wrong ）, And the test results are given ;
（4） Choose to do ： If possible , Consider how to describe C Linguistic if sentence , Make the whole article The law is still LL（1） Grammar , And make your recursive descent program analyze assignment statements and if sentence
3. Program function description
Combined with the experimental requirements , Complete the procedure of Experiment 2 , The specific implementation function is to read the binary file of lexical discrimination output from Experiment 1 in the same directory , According to the given grammar , Judge whether the input statement is reasonable by recursive descent analysis . For the unreasonable part , Output the wrong point after determining the error .
4. Program structure description
Because the grammar is given , So you can finish it first first and follow Calculation of sets ：
according to first and follow Set and given grammar , You can determine the structure of the recursive downward parser .
So the overall expression structure of the program is ：
S The recursive analysis program structure of is shown in the figure below 
E The recursive descent analysis program structure of is shown in the figure below ：
E’ Recursive downward analysis of the structure diagram 
T The recursive descent analysis program structure of is as follows ：
T’ The recursive descent analysis program structure of is as follows ：
F The recursive descent analysis program structure of is as follows ：
A The recursive descent analysis program structure of is as follows ：
M The recursive descent analysis program structure of is as follows ：
V The recursive descent analysis program structure of is as follows ：
5. Implementation code
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include <cassert>
#include<fstream>
#define MAX_LINE 1024
using namespace std;
// Function declaration
void S();
void E();
void E_();
void T();
void T_();
void F();
void A();
void M();
void V();
// Define a length of 100 Array of characters
char s[100];
// Used for array index , When the data is saved successfully every time the match is made index Self increasing 1
int i;
// Used to mark whether the statement is correct
int SIGN;
int main()
{
// printf(" Please enter your statement （ Remember to bring it at the end #）\n");
cout<<" Read the file to know the input statement ："<<endl;
FILE *fp;
char buf[MAX_LINE];
string shizi,like;
if((fp = fopen("text.txt","r"))!=NULL){
while(fgets(buf,MAX_LINE,fp) != NULL)
{
int len = strlen(buf);
buf[len-1] = '\0'; /* Remove the newline */
printf("%s \n",buf);
int flag=0;
if(buf[1]=='1'){
like+='i';
}
for(int i=0;i<len;i++){
if(buf[i]=='"'&&flag==0){
i++;
while(buf[i]!='"'){
shizi+=buf[i];
if(buf[1]!='1'){
like+=buf[i];
}
i++;
}
}
}
}
}
shizi+='#';
like+='#';
fclose(fp);
cout<<" The entered statement is ："<<shizi<<endl;
cout<<" It can be understood as ："<<like<<endl;
SIGN = 0;// Whether the statement is used correctly SIGN
i=0;
// Modify the input formula to string format char*
int length=like.length();
for(int i=0;i<length;i++){
s[i]=like[i];
}
// When the first character entered is # when , The program ends directly
if( s[0] == '#')
return 0;
S();
// If the last character begins with # When finished, output the following
if(s[i]=='#'&&SIGN==0){
printf("\n The sentence is legal \n");
}else{
printf("\n Illegal statement \n");
}
// printf(" Please enter your statement （ Remember to bring it at the end #）\n");
// }
return 1;
}
void S()
{
if(SIGN==0)
{
printf("S Check ");
// When the first letter in the input string is a when
if(s[i]=='i'){
V();
if(SIGN==0&&s[i]=='='){
// printf("(%c) ",s[i]);
i++;
E();
}
else{
SIGN=1;
cout<<"S An error occurred at "<<endl;
}
}
else{
SIGN=1;
cout<<"S An error occurred at "<<endl;
}
}
}
void E()
{
if(SIGN==0){
printf("E ");
if(s[i]=='('||s[i]=='i'){
T();
if(SIGN==0){
if(s[i]=='+'||s[i]=='-'){
E_();
}
else if(s[i]==')'||s[i]=='#'){
return;
}
else{
SIGN=1;
cout<<"E An error occurred at "<<endl;
}
}
}
else{
SIGN=1;
cout<<"E An error occurred at "<<endl;
}
}
}
void E_()
{
if(SIGN==0){
printf("E' ");
if(s[i]=='+'||s[i]=='-'){
A();
if(SIGN==0){
if(s[i]=='('||s[i]=='i'){
T();
if(SIGN==0){
if(s[i]=='+'||s[i]=='-'){
E_();
}
else if(s[i]==')'||s[i]=='#') {
return;
}
else{
SIGN=1;
cout<<"E' An error occurred at "<<endl;
}
}
}
else{
SIGN=1;
cout<<"E' An error occurred at "<<endl;
}
}
}
else if(s[i]==')'||s[i]=='#'){
return;
}
else{
SIGN=1;
cout<<"E' An error occurred at "<<endl;
}
}
}
void T()
{
if(SIGN==0){
printf("T ");
if(s[i]=='('||s[i]=='i'){
F();
if(SIGN==0){
if(s[i]=='*'||s[i]=='/'){
T_();
}
else if(s[i]=='+'||s[i]=='-'||s[i]==')'||s[i]=='#') {
return;
}
else{
SIGN=1;
cout<<"T An error occurred at "<<endl;
}
}
}
else{
SIGN=1;
cout<<"T An error occurred at "<<endl;
}
}
}
void T_()
{
if(SIGN==0){
printf("T' ");
if(s[i]=='*'||s[i]=='/'){
M();
if(SIGN==0){
F();
if(SIGN==0){
T_();
}
}
}
else if(s[i]=='+'||s[i]=='-'||s[i]==')'||s[i]=='#'){
return;
}
else{
SIGN=1;
cout<<"T' An error occurred at "<<endl;
}
}
}
void F()
{
if(SIGN==0){
printf("F ");
if(s[i]=='('){
// printf("(%c) ",s[i]);
i++;
if(s[i]=='('||s[i]=='i'){
E();
if(SIGN==0){
if(s[i]==')'){
// printf("(%c) ",s[i]);
i++;
}
else{
SIGN=1;
cout<<"F An error occurred at "<<endl;
}
}
}
else{
SIGN=1;
cout<<"F An error occurred at "<<endl;
}
}
else if(s[i]=='i'){
// printf("(%c) ",s[i]);
i++;
}
else{
SIGN=1;
cout<<"F An error occurred at "<<endl;
}
}
}
void A()
{
if(SIGN==0){
printf("A ");
if(s[i]=='+'||s[i]=='-'){
// printf("(%c) ",s[i]);
i++;
}
else{
SIGN=1;
cout<<"A An error occurred at "<<endl;
}
}
}
void M()
{
if(SIGN==0){
printf("M ");
if(s[i]=='*'||s[i]=='/'){
// printf("(%c) ",s[i]);
i++;
}
else{
SIGN=1;
cout<<"M An error occurred at "<<endl;
}
}
}
void V()
{
if(SIGN==0){
printf("V ");
if(s[i]=='i'){
// printf("(%c) ",s[i]);
i++;
}
else{
SIGN=1;
cout<<"V An error occurred at "<<endl;
}
}
}
6. Program testing
According to the requirements of the experiment , Provide two test samples , One right, one wrong ：
The first is the correct test sample , take a=b*(c+d) Enter in input In file , Start the program lab1, Generate the corresponding binary formula , Here for the convenience of judgment and operation , Change the binary output of the identifier to （1,‘ Symbol ’）, The output binary formula obtained is as follows ：
Next launch Lab2, You can get the following results ：
Display the output part of the above figure separately ：
Read the file to know the input statement ：
(1,“a”)
( Operator ,“=”)
(1,“b”)
( Operator ,"“)
( Separator ,”(“)
(1,“c”)
( Operator ,”+“)
(1,“d”)
( Separator ,”)")
The entered statement is ：a=b(c+d)#
It can be understood as ：i=i*(i+i)#
S Check V E T F T’ M F E T F E’ A T F T’
The sentence is legal
The output of the penultimate line is in the process of recursive descent analysis , Each non terminal symbol corresponds to the output of the function used .
Next is the wrong test sample ： take a=b*(c+d Enter in input In file , Start the program lab1, Generate the corresponding binary formula , The output binary formula obtained is as follows ：
start-up Lab2 The results obtained after the program are as follows ：
Display the program output part separately ：
Read the file to know the input statement ：
(1,“a”)
( Operator ,“=”)
(1,“b”)
( Operator ,"“)
( Separator ,”(“)
(1,“c”)
( Operator ,”+")
(1,“d”)
The entered statement is ：a=b(c+d#
It can be understood as ：i=i*(i+i#
S Check V E T F T’ M F E T F E’ A T F
F An error occurred at
Illegal statement
边栏推荐
- 【MySQL系列】MySQL数据库基础
- Detailed explanation of 9 common reasons for MySQL index failure
- Develop effective Tao spell
- 数仓：Doris在美团的应用实践
- Please briefly describe the respective characteristics of list, set and map type sets (briefly describe three different inheritance methods)
- Leetcode64. Minimum path sum
- Is the declarative code of compose so concise?
- [detailed and super simple] how to use websocket links
- mysql索引失效的常见9种原因详解
- Eight performance analysis indicators of effective supply chain management (Part 1)
猜你喜欢
Detailed principle explanation and verification results of digital clock based on FPGA
Leetcode63. Different paths II
Pycharm configuring the running environment
Worthington RNA determination detailed introduction
EN 1873屋面用装配附件.塑料单个屋面灯—CE认证
curl (7) Failed connect to localhost8080； Connection refused
Genomic DNA isolation Worthington ribonuclease A
GhostNets on Heterogeneous Devices via Cheap Operations
Es6操作教程
Detailed explanation of 9 common reasons for MySQL index failure
随机推荐
EN 1873屋面用装配附件.塑料单个屋面灯—CE认证
【C】逆序字符串(俩种递归思路)
Zibo station construction guide (aigler)
Detailed principle explanation and verification results of digital clock based on FPGA
【MySQL 8】Generated Invisible Primary Keys(GIPK)
研发效能的道法术器
How can Plato obtain premium income through elephant swap in a bear market?
1-7 solve the problem of this pointing of methods in classes
PMP Exam countdown, look at 3A pass bag!
leetcode 763. Partition Labels 划分字母区间(中等)
Doip communication of canoe application case
Powercl batch creates and manages virtual switches
EN 1935 building hardware. Single axis hinge - CE certification
Leetcode59. Spiral matrix II
After SAP Oracle replicates a new instance, the remote connection of the database reports an error ora-01031
实时数仓：网易严选基于Flink的实时数仓实践
Dual for loop optimization
Build SSM project with JSP as view parser
PowerCL 批量创建及管理虚拟交换机
双重for循环优化