Source code repository: CompilePrincipleLearning/experiment_2 · yusixian/CompilePrincipleLearning (github.com)
I. Experiment Purpose#
- Master the basic principles of the LL(1) analysis method
- Master the construction method of the LL(1) analysis table
- Master the construction method of the LL(1) driver program
II. Experiment Content and Requirements#
Write a lexical analysis program to recognize words.
Develop and debug an LL(1) analysis program based on a certain grammar to analyze any input symbol string. The main purpose of this experiment is to deepen the understanding of predictive analysis using the LL(1) analysis method.
Example: Analyze any input symbol string using the LL(1) analysis method for the following grammar:
(1) E->TG
(2) G->+TG|—TG
(3) G->ε
(4) T->FS
(5) S->*FS|/FS
(6) S->ε
(7) F->(E)
(8) F->i
The output format is as follows:
(1) LL(1) analysis program, author: Name, Student ID, Class
(2) Input a symbol string ending with # (including +*()i#): i*(i+i)+(i*i)#
(3) The output process steps are as follows:
| Step | Analysis Stack | Remaining Input String | Used Production |
|---|---|---|---|
| 1 | E | i+i*i# | E->TG |
(4) The input symbol string is an illegal symbol string (or a legal symbol string)
Note:
(1) In the " Used Production " column, if there is a derivation, write out the used production; if it is a matching terminal, specify the matched terminal; if an analysis exception occurs, write "Analysis Error"; if it ends successfully, write "Analysis Successful".
(2) The symbol string input at this position is the symbol string entered by the user.
(3) The output process described above is only part of it.
Note: 1. The expression allows the use of operators (+-*/), delimiters (parentheses), character i, and end symbol #;
-
If an erroneous expression is encountered, an error message should be output (the more detailed the information, the better);
-
For students with extra capacity, test expressions are placed in a text file in advance, with one expression per line, separated by semicolons. The expected output results should also be written in another text file for comparison with the output;
-
Other grammars that can be used
III. Experiment Process#
1. Data Structure Used#
Production type defined as type, left side as origin, uppercase character, right side as the produced character
struct type { /* Production type definition */
char origin; /* Left side character of production, uppercase character */
string array; /* Right side characters of production */
int length; /* Number of characters */
type():origin('N'), array(""), length(0) {}
void init(char a, string b) {
origin = a;
array = b;
length = array.length();
}
};
The initialization of the data structure is as follows:
e.init('E', "TG"), t.init('T', "FS");
g.init('G', "+TG"), g1.init('G', "^");
s.init('S', "*FS"), s1.init('S', "^");
f.init('F', "(E)"), f1.init('F', "i");
2. Header File Declaration and Global Variable Definition#
As follows
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const string ExpFileName = "./exp.txt";
char analyeStack[20]; /* Analysis stack */
char restStack[20]; /* Remaining stack */
const string v1 = "i+*()#"; /* Terminal */
const string v2 = "EGTSF"; /* Non-terminal */
const string acceptStr = "i+*()#"; // Accepted string
int top, ridx, len; /* len is the length of the input string */
struct type { /* Production type definition */
char origin; /* Left side character of production, uppercase character */
string array; /* Right side characters of production */
int length; /* Number of characters */
type():origin('N'), array(""), length(0) {}
void init(char a, string b) {
origin = a;
array = b;
length = array.length();
}
};
type e, t, g, g1, s, s1, f, f1; /* Production structure variable */
type C[10][10]; /* Predictive analysis table */
4. Function Summary#
(1) Function Summary Table#
| Function Name | Brief Function Description |
|---|---|
readFile | File reading function, returns a dynamic array of strings, split by line number |
init | Initialization function, initializes the analysis stack and remaining stack |
print | Outputs the current analysis stack and remaining stack |
isTerminator | Determines whether the current character c is a terminal |
analyze | Analyzes the string s and outputs its analysis steps |
main | Main program entry, from here, fills the initial analysis table and initializes productions, calls the file reading function to start analysis |
(2) Function Call Relationship#
5. Experiment Results#
Input#
File exp.txt
i*(i+i)+(i*i)#
i*i-i/1#
i+i*i+i*(i+i*i)#
i+*i(i)+i(i+i*i)#
i+i(i)#code.txt
Output#
Complete Code#
/*
* @Author: cos
* @Date: 2022-04-12 23:03:36
* @LastEditTime: 2022-04-13 01:32:58
* @LastEditors: cos
* @Description:
* @FilePath: \CS\experiment_2\main.cpp
*/
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const string ExpFileName = "./exp.txt";
char analyeStack[20]; /* Analysis stack */
char restStack[20]; /* Remaining stack */
const string v1 = "i+*()#"; /* Terminal */
const string v2 = "EGTSF"; /* Non-terminal */
int top, ridx, len; /* len is the length of the input string */
struct type { /* Production type definition */
char origin; /* Left side character of production, uppercase character */
string array; /* Right side characters of production */
int length; /* Number of characters */
type():origin('N'), array(""), length(0) {}
void init(char a, string b) {
origin = a;
array = b;
length = array.length();
}
};
type e, t, g, g1, s, s1, f, f1; /* Production structure variable */
type C[10][10]; /* Predictive analysis table */
void print() {/* Output analysis stack and remaining stack */
for(int i = 0; i <= top + 1; ++i) /* Output analysis stack */
cout << analyeStack[i];
cout << "\t\t";
for(int i = 0; i < ridx; ++i) /* Output alignment character */
cout << ' ';
for(int i = ridx; i <= len; ++i) /* Output remaining string */
cout << restStack[i];
cout << "\t\t\t";
}
// Read file
vector<string> readFile(string fileName) {
vector<string> res;
try {
ifstream fin;
fin.open(fileName);
string temp;
while (getline(fin, temp))
res.push_back(temp);
return res;
} catch(const exception& e) {
cerr << e.what() << '\n';
return res;
}
}
bool isTerminator(char c) { // Determine if it is a terminal
return v1.find(c) != string::npos;
}
void init(string exp) {
top = ridx = 0;
len = exp.length(); /* Length of analysis string */
for(int i = 0; i < len; ++i)
restStack[i] = exp[i];
}
void analyze(string exp) { // Analyze a grammar
init(exp);
int k = 0;
analyeStack[top] = '#';
analyeStack[++top] = 'E'; /* '#' and 'E' enter stack */
cout << "Step\t\tAnalysis Stack \t\tRemaining Characters \t\tUsed Production " << endl;
while(true) {
char ch = restStack[ridx];
char x = analyeStack[top--]; /* x is the current top character of the stack */
cout << ++k << "\t\t";
if(x == '#') {
cout << "Analysis Successful! AC!\n" << endl; /* Accepted */
return;
}
if(isTerminator(x)) {
if (x == ch) { // Matched
print();
cout << ch << " matched" << endl;
ch = restStack[++ridx]; /* Next input character */
} else { /* Error handling */
print();
cout << "Analysis Error, erroneous terminal is " << ch << endl; /* Output erroneous terminal */
return;
}
} else { /* Non-terminal handling */
int m, n; // Non-terminal index, terminal index
v2.find(x) != string::npos ? m = v2.find(x) : -1; // m is -1 means the non-terminal cannot be found, error
v1.find(ch) != string::npos ? n = v1.find(ch) : -1; // n is -1 means the terminal cannot be found, error
if(m == -1 || n == -1) { /* Error handling */
print();
cout << "Analysis Error, erroneous non-terminal is " << x << endl; /* Output erroneous non-terminal */
return;
}
type nowType = C[m][n];/* Used to accept C[m][n] */
if(nowType.origin != 'N') {/* Check if it is empty */
print();
cout << nowType.origin << "->" << nowType.array << endl; /* Output production */
for (int j = (nowType.length - 1); j >= 0; --j) /* Push production in reverse order onto the stack */
analyeStack[++top] = nowType.array[j];
if (analyeStack[top] == '^') /* If empty, do not push onto the stack */
top--;
} else { /* Error handling */
print();
cout << "Analysis Error, erroneous non-terminal is " << x << endl; /* Output erroneous non-terminal */
return;
}
}
}
}
int main() {
e.init('E', "TG"), t.init('T', "FS");
g.init('G', "+TG"), g1.init('G', "^");
s.init('S', "*FS"), s1.init('S', "^");
f.init('F', "(E)"), f1.init('F', "i"); /* Structure variable */
/* Fill the analysis table */
C[0][0] = C[0][3] = e;
C[1][1] = g;
C[1][4] = C[1][5] = g1;
C[2][0] = C[2][3] = t;
C[3][2] = s;
C[3][4] = C[3][5] = C[3][1] = s1;
C[4][0] = f1; C[4][3] = f;
cout << "LL(1) analysis program, author: xxx xxx Computer Science Class xxxx" << endl;
cout << "Note: This program can only analyze strings composed of 'i', '+', '*', '(', ')' ending with '#' and read one string per line" << endl;
cout << "The name of the file read is: " << ExpFileName << endl;
vector<string> exps = readFile(ExpFileName);
int len = exps.size();
for(int i = 0; i < len; i++) {
string exp = exps[i];
cout << "------------------String to be analyzed " << i+1 << "："<< exp << "--------------------" << endl;
bool flag = true;
for(int j = 0; j < exp.length(); j++) {
if(!isTerminator(exp[j])) {
cout << "The string entered in line " << i+1 << " is illegal, please re-enter" << endl;
flag = false;
break;
}
}
if(flag) {
cout << "String " << i+1 << "：" << exp << endl;
analyze(exp);
}
}
return 0;
}