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.