Compilation Principle-Syntax Analyzer

recursive descent analysis
1. Experimental purpose:
Compile and debug a recursive descent analysis program based on a certain grammar to analyze any input symbol string. The purpose of this experiment is mainly to deepen the understanding of the recursive descent analysis method.
2. Experimental instructions
1. Function of recursive descent analysis method
The function of the lexical analyzer is to simulate the top-down construction process of the syntax tree using recursive calls between functions.
2. Premise of recursive descent analysis method
Transform the grammar: eliminate ambiguity, eliminate left recursion, extract left factors, and determine whether it is an LL (1) grammar.
3. Experimental design ideas and algorithms of recursive descent analysis method
Construct a recursive process for each non-terminal symbol U of G, which may be named U.
The right-hand side of the production of U indicates the code structure of this process:
(1) If it is a terminal symbol, compare it with the look-ahead symbol,
If there is a match, advance one symbol; otherwise, an error occurs.
(2) If it is a non-terminal symbol, call the procedure corresponding to the non-terminal symbol. When there are multiple productions on the right side of A, it can be implemented with a selection structure.
3. Experimental requirements
(1) Preparation:
1. Read the relevant chapters of the textbook,
2. Consider the design plan;
3. Design the module structure, test data, and preliminarily compile the program.
(2) Using the computer in class:
Copy the source code to the computer for debugging, find errors, and then modify and improve them. The second computer debugging passed.
(3) Program requirements:
Program input/output example:
For the following grammar, any input string of symbols is analyzed using recursive descent analysis:
(1)E->eBaA
(2)A->a|bAcB
(3)B->dEd|aC
(4)C->e|dc
The output format is as follows: (1) Recursive descent analysis program, prepared by: name, student number, class
(2) Enter a symbol string ending with #: Enter the symbol string at this position, for example: eadeaa#
(3) Output result: eadeaa# is a legal symbol string
Notice:
1. If an incorrect expression is encountered, an error message should be output (the more detailed the information, the better);
2. For students who have room for learning, you can output the derivation process in detail, that is, list the productions used in each step in detail.
(4) Program ideas
0. Definition part: define constants, variables, and data structures.
1. Initialization: Input the input symbol string from the file into the character buffer.
2. Use the recursive descent analysis method to analyze, write a function for each non-terminal symbol, and call the function of the grammar start symbol in the main function.