Compilation principle first set follow set select set prediction analysis table to judge whether the symbol string conforms to the grammar definition (with source code!!!)

Compiler principle

The original

　　 I want to compile here into a new series , Mainly related to my course , But it has nothing to do with homework .

　　 Only speak Lexical analysis and Grammar analysis . Because most colleges and universities focus on learning here , According to the class hours for compilation , What I mentioned later is just a pass .

　　 This series has Explain , note , Source code , exercises , It can be regarded as a quick course .

 

 

Experiment two （ Construction of syntax analysis program based on predictive analysis method ）

 

1. Experimental content

 

2. Experimental instruction

 

 

 

 

 

 

 

 

3. Code implementation

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include<stdlib.h>
#include<string.h>
#define maxsize 100

using namespace std;

struct node {  //  Production data structure 
    char left;
    string right;
};

class Base {
    protected:
        int T;                            //  Number of production 
        node production[maxsize];         //  Production set 
    
        set<char> firstSet[maxsize];      // First Set 
        set<char> followSet[maxsize];      // Follow Set 
        vector<char> terminalNoEmpty;     //  Go to $( empty ) Terminator for 
        vector<char> terminal;          //  Terminator 
        vector<char> nonterminal;          //  non-terminal 
    
        bool isNonterminal(char c);
        int getIndex(char target);      //  get target Subscript in Terminator set 
        int getNIndex(char target);      //  get target Subscript in non terminator set 
        void getFirst(char target);      //  obtain First(target)
        void getFollow(char target);      //  obtain Follow(target)
    
    public:
        Base() {};
    
        void inputAndSolve();  //  Process and find First and Follow Set 
        void displayFirstAndFollow();  //  Output First and Follow Set 

};

bool Base::isNonterminal(char c) { //  Judge c Whether it is a non Terminator 
    if (c >= 'A' && c <= 'Z')
        return true;
    return false;
}
int Base::getNIndex(char target) {  //  get target Subscript in non terminator set 
    for (int i = 0; i<nonterminal.size(); i++) {
        if (target == nonterminal[i])
            return i;
    }
    return -1;
}
int Base::getIndex(char target) {  //  get target Subscript in Terminator set 
    for (int i = 0; i<terminalNoEmpty.size(); i++) {
        if (target == terminalNoEmpty[i])
            return i;
    }
    return -1;
}

void Base::getFirst(char target) {  //  seek FIRST(target）
    int isEmpty = 0;
    int targetIndex = getNIndex(target);  // Find the non terminator subscript  
    for (int i = 0; i < T; i++) { // Traverse every production  
        if (production[i].left == target) {  //  Match the left part of the production 
            if (!isNonterminal(production[i].right[0])) {  //  For terminators , Directly to join first
                firstSet[targetIndex].insert(production[i].right[0]);  // Store the Terminator  ( The first 1)
            }
            else {
                char Yj = production[i].right[0];
                getFirst(Yj);// Yj Yes no terminator , recursive   Find out first FIRST(Yj)
                
                set<char>::iterator it;
                int YjIndex = getNIndex(Yj);  // Find the non terminator subscript  
                for (it = firstSet[YjIndex].begin(); it != firstSet[YjIndex].end(); it++) {  
                    if (*it == '$') {  //  Traversal view FIRST(Yj) Whether contains '$'( Can produce empty )
                        isEmpty = 1;
                        firstSet[getNIndex(target)].insert('$');
                    }
                    else
                        firstSet[targetIndex].insert(*it); // take FIRST(Yj) Middle Africa $ join FIRST(X)
                }
            }
        }
    }
}

void Base::getFollow(char target) {  //  seek FOLLOW(target）
    int targetIndex = getNIndex(target);
    for (int i = 0; i < T; i++) { // Every production  
        int index = -1;
        int len = production[i].right.length();
        for (int j = 0; j < len; j++) {  //  seek target Position in production index
            if (production[i].right[j] == target) {
                index = j;  // Horizontal coordinates  
                break;
            }
        }
        if (index != -1 && index < len - 1) {  //  find target Position in production index    It means there's something behind it  
                                               //  There is A->αBβ,  take FIRST(β) In addition to empty $ All other than FOLLOW(B) in 
                                               //  here B Corresponding target, β Corresponding nxt
            char nxt = production[i].right[index + 1];  // Extract the following symbol  
            if (!isNonterminal(nxt)) {  // β It's the terminator  FIRST(β)=β, Directly inserted into the β
                followSet[targetIndex].insert(nxt);
            }
            else {  // β Yes no terminator 
                int hasEmpty = 0;
                set<char>::iterator it;
                int nxtIndex = getNIndex(nxt);  //  Insert FIRST(β) In addition to empty $ All but     Find non terminator location  
                for (it = firstSet[nxtIndex].begin(); it != firstSet[nxtIndex].end(); it++) {
                    if (*it == '$')
                        hasEmpty = 1;
                    else
                        followSet[targetIndex].insert(*it);
                }

                if (hasEmpty && production[i].left != target) { //  There is A->αBβ And FIRST(β)->$
                                                             // FOLLOW(A) Put it in FOLLOW(B) in 
                    getFollow(production[i].left);
                    set<char>::iterator it;
                    char tmp = production[i].left;
                    int tmpIndex = getNIndex(tmp);
                    for (it = followSet[tmpIndex].begin(); it != followSet[tmpIndex].end(); it++)
                        followSet[targetIndex].insert(*it);
                }
            }
        }
        else if (index != -1 && index == len - 1 && target != production[i].left) {  //  There is no... After the description   There is A->αB ,FOLLOW(A) Put it in FOLLOW(B) in 
            getFollow(production[i].left);
            set<char>::iterator it;
            char tmp = production[i].left;
            int tmpIndex = getNIndex(tmp);
            for (it = followSet[tmpIndex].begin(); it != followSet[tmpIndex].end(); it++)
                followSet[targetIndex].insert(*it);
        }
    }
}

void Base::inputAndSolve() {  //  Process and find First and Follow Set 
    string s;
    int i=0;
    cout << " The number of production expressions entered ：" << endl;
    cin >> T;
    cout << " Input production ：" << endl;
    for (int index = 0; index < T; index++) {  //  Process every production 
        cin >> s;
        production[index].left = s[0];  //  The left part of production 
        for ( i = 3; i < s.length(); i++) //  The right part of production 
            production[index].right += s[i];

        for (i = 0; i < s.length(); i++) {      //  Store all terminators and non terminators 
            if (i == 1 || i == 2) 
                continue;      //  Skip generating symbols ->
            if (isNonterminal(s[i])) {  // Insert a non Terminator 
                int flag = 0;  //  Whether to find the character  （ If you have it, you won't press it into the stack ） 
                for (int j = 0; j < nonterminal.size(); j++) {
                    if (nonterminal[j] == s[i]) {
                        flag = 1;
                        break;
                    }
                }
                if (!flag) nonterminal.push_back(s[i]);
            }
            else {                       // Insert a Terminator 
                int flag = 0;
                for (int j = 0; j < terminal.size(); j++) {
                    if (terminal[j] == s[i]) {
                        flag = 1;
                        break;
                    }
                }
                if (!flag) terminal.push_back(s[i]);
            }
        }
    }
    terminal.push_back('#');

    for ( i = 0; i < terminal.size(); i++) { //  No storage $ Terminator of symbol 
        if (terminal[i] != '$')
            terminalNoEmpty.push_back(terminal[i]);
    }

    //  get first Set 
    for ( i = 0; i < nonterminal.size(); i++) {
        getFirst(nonterminal[i]);
    }

    //  get follow Set 
    for ( i = 0; i < nonterminal.size(); i++) {
        if (i == 0)  //  Start symbol ,  First add the ending symbol 
            followSet[0].insert('#');
        getFollow(nonterminal[i]);
    }
}

void Base::displayFirstAndFollow() {  //  Output First and Follow Set 
    int i=0;
    cout << "FIRST aggregate " << endl;
    for (i = 0; i<nonterminal.size(); i++) {
        cout << nonterminal[i] << ": ";
        set<char>::iterator it;
        for (it = firstSet[i].begin(); it != firstSet[i].end(); it++)
            cout << *it << "  ";
        cout << endl;
    }
    cout << endl;

    cout << "FOLLOW aggregate " << endl;
    for (i = 0; i<nonterminal.size(); i++) {
        cout << nonterminal[i] << ": ";
        set<char>::iterator it;
        for (it = followSet[i].begin(); it != followSet[i].end(); it++)
            cout << *it << "  ";
        cout << endl;
    }
    cout << endl;
}

class LL1 : public Base {
private:
    vector<char> analyStack; //  Analysis of the stack 
    vector<char> leftExpr;  //  Remaining input string 
    int tableMap[100][100];  //  Forecast table 

public:
    LL1();

    void getTable(); //  Generate forecast table 
    void printPredictTable();  //  Output forecast table 
    void analyExpression(string s);  //  Analyze input statements s
    void getResult(); //  Comprehensive treatment 
};
LL1::LL1() {
    memset(tableMap, -1, sizeof(tableMap));
}

void LL1::getTable() {   // Get the forecast table  
    for (int index = 0; index < T; index++) {//   Ergodic production      For each production ( Number index):A->α
        int row = getNIndex(production[index].left);  //  Left   Subscript  
        int emptyCount = 0;
        char tmp = production[index].right[0];  
        if (!isNonterminal(tmp)) { // tmp It's the terminator 
            if (tmp != '$')
                tableMap[row][getIndex(tmp)] = index;
            if (tmp == '$')
                emptyCount++;
        }
        else {  // tmp Yes no terminator 
            set<char>::iterator it;
            int tmpIndex = getNIndex(tmp);  // Find non terminator subscript  
            //  Yes FIRST(tmp) Every terminator in a, take i Join in (A, a) in 
            for (it = firstSet[tmpIndex].begin(); it != firstSet[tmpIndex].end(); it++) {
                tableMap[row][getIndex(*it)] = index;
            }
            if (firstSet[tmpIndex].count('$') != 0)     // 2)  If empty $ stay FIRST(tmp) in , Continue to look at α The next symbol in 
                emptyCount++;
        }

        // 2)  If empty $ stay FIRST(α) in , Yes FOLLOW(A) Each terminator or in the b, take i Join in (A,b) in 
        if (emptyCount == production[index].right.size()) {  //  The right part of production is empty  
            set<char>::iterator  it;
            for (it = followSet[row].begin(); it != followSet[row].end(); it++) {
                tableMap[row][getIndex(*it)] = index;       // Put the left follow Put it in the forecast table  
            }
        }
    }
}

void LL1::analyExpression(string s) {
    int i=0;
    for (i = 0; i < s.size(); i++)
        leftExpr.push_back(s[i]);    //  Stack the remaining string  
    leftExpr.push_back('#');   // Pressure # 

    analyStack.push_back('#');
    analyStack.push_back(nonterminal[0]);  //  Add the start symbol 

    while (analyStack.size() > 0) {   //  There are values in the analysis stack  
        //cout<<" Analysis of the stack ：";
        string outs = "";
        for (i = 0; i < analyStack.size(); i++)
            outs += analyStack[i];
        cout << setw(30) << outs;

        //cout<<" Remaining input string ：";
        outs = "";
        for (i = 0; i < leftExpr.size(); i++)
            outs += leftExpr[i];
        cout << setw(30) << outs;

        //  matching 
        char char1 = analyStack.back();
        char char2 = leftExpr.front();
        if (char1 == char2 && char1 == '#') {
            cout << setw(15) << "Accepted!" << endl;   
            return;
        }
        if (char1 == char2) {
            analyStack.pop_back();
            leftExpr.erase(leftExpr.begin());
            cout << setw(15) << " matching ：" << char1 << endl;
        }
        else if (tableMap[getNIndex(char1)][getIndex(char2)] != -1) {  //  There is a push down item in the forecast table , It can be deduced 
            int tg = tableMap[getNIndex(char1)][getIndex(char2)];
            analyStack.pop_back();

            if (production[tg].right != "$") {
                for ( i = production[tg].right.length() - 1; i >= 0; i--) //  Note that this is the reverse stack  
                    analyStack.push_back(production[tg].right[i]);
            }

            cout << setw(15) << " deduction ：" << production[tg].left << "->" << production[tg].right << endl;
        }
        else {  //  error 
            cout << setw(15) << "error!" << endl;
            return;
        }
    }
}

void LL1::printPredictTable() {
    int i=0;
    //  Header 
    for (i = 0; i < terminalNoEmpty.size(); i++) {   
        cout << setw(10) << terminalNoEmpty[i];   // Space  
    }
    cout << endl;
    for (i = 0; i < nonterminal.size(); i++) {
        cout << nonterminal[i] << ": ";
        for (int j = 0; j < terminalNoEmpty.size(); j++) {
            if (tableMap[i][j] == -1)
                cout << setw(10) << "   ";
            else
                cout << setw(10) << production[tableMap[i][j]].right;
        }
        cout << endl;
    }
    cout << endl;
}

void LL1::getResult() {  // Get the results  
    //int a = 0;
    inputAndSolve();
    displayFirstAndFollow();
    getTable();
    printPredictTable();
    // Stack matching 
    string ss;
    cout << " Please enter the symbol string ：" << endl;
    cin >> ss;
    cout <<setw(30) << " Analysis of the stack " << setw(30) << " Remaining input string " << setw(16) << " The derived type " << endl;
    analyExpression(ss);

}


int main() {
    // $ Said empty , # To terminate 
    LL1 res;
    res.getResult();
    system("pause");
    return 0;
}

/*
E->TA
A->+TA
A->$
T->FB
B->*FB
B->$
F->i
F->(E)
*/
//  i+i*i

 

4. test result