Compiling principle design and implementation of parser and its correlation

Recursive descent analyzer

Top down analysis

The top-down analysis method starts from the input string and carries out the stipulation step by step until the beginning symbol of the grammar; or from the end of the grammar tree, it starts from the stipulation step by step until the root knot. Recursive subprogram (recursive descent) analysis without backtracking is a top-down analysis method.

Grammar:
E->TE';
E'->+TE' | e
T->FT'
T'->*FT' | e
F->(E) | i

Program design

#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
char str[10];
int index = 0;
int flag = 0;
void E(); //E->TE';
void E1(); //E'->+TE' | e
void T(); //T->FT'
void T1(); //T'->*FT' | e
void F(); //F->(E) | i

void E()  //Write a statement call when a non terminator is encountered
{
	T();
	E1();
}
void E1() {
	if (str[index] == '+') //Encountering |, write if statement
	{
		index++;
		T();
		E1();
	}
}
void T()//Non terminal encountered, write statement call
{
	F();
	T1();
}
void T1()//Encountering |, write if statement
{
	if (str[index] == '*')
	{
		index++;
		F();
		T1();
	}
}
void F()//Encountering |, write if statement
{
	if (str[index] == 'i')
	{
		index++;
		if (str[index] > '0' && str[index] < '9')
			index++;
	}
	else
	{
		if (str[index] == '(')
		{
			index++;
			E();
			if (str[index] == ')')
			{
				index++;
			}
			else {
				flag = 1;
				cout << "sentence in wrong" << endl;    //Error judgment in the last production
			}
		}
		else
		{
			flag = 2;
			cout << "sentence in wrong" << endl;
		}
	}
}
int main()
{
    cout << "Please enter the arithmetic expression to be compiled(input#End: " << endl;
	cin >> str;
	E();
	//len = strlen(str); str[len + 1] = '#';
	if (str[index] == '#' && flag == 0)
		cout << "sentence in correct" << endl;
	system("pause");
}

summary

  • Grammar needs to eliminate recursion / backtracking first
  • Encountering |, write if statement
  • Non terminal encountered, write statement call
  • When A → ε rule is encountered, write statement if (the input symbol currently read does not belong to follow (A)) error();
  • Compiling principle aims to introduce the general principle and basic method of compiler construction, such as a giant algorithm (error). Although few of them are engaged in compiling, as a required professional course, compiling principle can effectively improve students' software ability.

Added by Slashscape on Mon, 11 Nov 2019 23:43:23 +0200