Experiment Name: implementation of PL/0 compiler i. Objective To understand the working mechanism of the compiler and master the construction method of the compiler. To master the usage of LEX, a tool for generating lexical analyzer, to master the usage of YACC, a tool for generating grammar analyzer
1. The experiment is divided into three parts: lexical analysis, grammar analysis, semantic analysis and code generation, which correspond to the compilation process of PL/0 compiler, so that the analysis process can be better experienced in the process of learning the principle.
2. Lexical analysis Write PL/0 language recognition program, and use flex tool to generate a PL/0 language lexical analysis program, scan the input PL/0 language source program, identify the category of word symbols, output information of various symbols.
Refer to LEX source programs for formatting, custom declarations, auxiliary definitions, identification rules and subroutines.
3. Grammar analysis to write a PL/0 language grammar analysis program, with the help of Bison tool generation, so that the program can input the PL/0 source program for grammar analysis, and according to the grammar reduction process output reduction when the grammar rules used.
4. Semantic analysis Using C language to write PL/0 semantic analysis program, which is required to convert it into a pcode language
3. Experimental environment: OS: Windows10 1607 Compiler: Cygwin64 Terminal, YACC, LEX, Bison, Code: Blocks :13.12
Auxiliary: sublime text 3126, notepad++ 7.41
1. Part ONE: Lexical analysis
The specific input and output requirements are as follows
Input: PL0 source program
Output: Word symbols are divided into the following five categories, and then count the number of occurrences of each word symbol in the PL0 source program
Class K (Keywords) Class I (Identifiers) Class C (Constants) Class P (operators and bounders) Class O (others)
According to the requirements, and with reference to the lex syntax format, the design idea is as follows:
1) Build structures for the five types of keywords respectively, similar to the linked list method of Hash. One keyword corresponds to an array, and insert symbols of the same type but different contents into the structure of the corresponding category. The structure is designed as shown in figure.
2) Add keyword information and corresponding semantic action INSERT in the auxiliary definition link
- Parse the read PL/0 file and output the results to another file
The most difficult part of this section is the semantic action insert
In this experiment, the length of the input string is limited, so it needs to be warned in the process of analyzing the language, but at the same time, the compilation action cannot be terminated, because if every compilation error is reported, only one line of error can be reported, which will make the analysis efficiency of the compiler very low. The function corresponding to the insert action in this experiment is as follows:
2. Part II: Grammar analysis experiment Specific input and output requirements are as follows
Input: PL0 source program
Output: an analysis of the syntax structure of the program
Referring to Bison’s explanation, it is generally understood that this experiment is based on the lexical analysis and adds the definition of grammar rules, in which the defined statements should conform to the grammar of C language.
Syntax format: left part (non-terminal) : right part (grammar string);
Non-terminal names are usually lowercase, and terminal names are usually uppercase.
A null right hand indicates that a left nonterminal can match an empty string.
The same grammatical rules on the left side should be combined as much as possible.
When a semantic action occurs at the end of a rule, Bison executes it before reduction; When a semantic action occurs in the middle of a rule, Bison executes it after recognizing several grammar symbols that precede it.
To achieve the idea of reference to the lexical analysis experiment, but this time in the corresponding semantic action link directly output, without the need to insert into the structure.
The experimental output is as follows:
3. The third part: Semantic analysis and target language generation
The specific input and output requirements are as follows
Input: PL0 source program
Output: class Pcode code
First, you need to look at the class Pcode
Object code class Pcode is a stack machine assembly language.
Stack machine system structure: no accumulator and register, only storage stack pointer all operations on the top of the stack
Instruction format fla
F function code
L Hierarchy difference (identifier reference layer minus definition layer)
A It varies according to different instructions
Refer to the function list and interpreter structure of class Pcode to divide the program into three parts: code.l,code.y, and define. H defines the function code code, symbol table and instruction structure of class Pcode, code.l belongs to the lexical analysis part, code.y belongs to the grammar and semantic analysis part. In the part of semantic action description, according to the input situation, $pseudo-variable is used to push the stack out of the stack.
In this experiment, the interpret function has been provided, so the specific description of function code in C language has been omitted. The next idea is to check whether there is any lexical error according to the input program –> construct symbol table –> execute the content of interpret() a output Pcode result
The experimental results are shown in section 5
Five, with a *PL0* of the source for specific explanation
The original PL0 program is as follows:
var a, b, c;
procedure gcd;
procedure rec;
begin
if a <> 0 then
begin
a := a - 1;
end;
end;
begin
if c < b then
begin
c := b;
call rec;
end;
end;
begin
read(a);
read(b);
read(c);
write(a);
call gcd;
write(a);
end.
Copy the codeThere is process nesting in this program, in fact, this experiment also implemented parallel, but I won’t go into the details here. The experimental output is shown in figure
(Note: IN the process of writing the report, I found that I had misread the instruction function sheet of the PPT description and mistook INT as INI, but for the convenience of reading, I will not change it here.)
