当前位置：网站首页>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
边栏推荐
- 【C】 Reverse string (two recursive ideas)
- Dual for loop optimization
- What is in word?:^ p
- Tyrosine decarboxylase -- characteristics of tyrosine decarboxylase of Streptococcus faecalis in Worthington
- Is the declarative code of compose so concise?
- 【MySQL系列】MySQL数据库基础
- 1-8 props的基础使用
- Leetcode59. 螺旋矩阵 II
- SQL implementation merges multiple rows of records into one row
- Detailed principle explanation and verification results of digital clock based on FPGA
猜你喜欢
![[detailed and super simple] how to use websocket links](/img/bf/5068f84e0d81a8330529cc4d7d5d27.png)
[detailed and super simple] how to use websocket links
【C】 Reverse string (two recursive ideas)
【MySQL系列】MySQL数据库基础
熊市下PLATO如何通过Elephant Swap，获得溢价收益？
Doip test development practice
Build SSM project with JSP as view parser
VMware VCSA 7.0 Install
EN 1873 assembly accessories for roofing - plastic single roof lamps - CE certification
Leetcode59. 螺旋矩阵 II
Develop effective Tao spell
随机推荐
@Detailed explanation of the use of transactional annotation
DoIP测试开发实践
leetcode 763. Partition Labels 划分字母区间(中等)
Powercl batch creates and manages virtual switches
Application of Devops in Internet of things solutions
跳表的原理
Leetcode60. permutation sequence
ISO 13400（DoIP）标准解读
Where is the DP interface of desktop computer (what if the host has no DP interface)
Word中的\n是什么？：^p
Install MySQL using Yum for Linux
AutoCAD -- import excel tables into CAD and merge CAD
【C】喝汽水，找单身狗问题
Powercli batch add esxi to vCenter
Virtual lab basic experiment tutorial -8. Fourier transform (1)
JS advanced ES6 ~ es13 new features
After SAP Oracle replicates a new instance, the remote connection of the database reports an error ora-01031
Briefly introduce the working principle and characteristics of block cipher encryption block link mode (cryptography shift cipher encryption and decryption)
GhostNets on Heterogeneous Devices via Cheap Operations
[microservice] Nacos cluster building and loading file configuration