Compilation principle - top-down analysis and recursive descent analysis construction (notes)

Purpose

Construct a top-down analysis program without backtracking

• To eliminate the left recursion of grammar
• Overcoming backtracking

Main idea

• The parser consists of a set of recursive procedures , For each syntax variable ( non-terminal ) Construct a corresponding subroutine , Identify the corresponding grammatical unit
• The recognition of input string is realized through the mutual call between subroutines
• Such an analyzer is called a recursive descent analyzer ( Because the definition of grammar
  Usually recursive )

Process and variable

• ADVANCE： Input string indicator IP Point to the next input symbol , That is, read a single word symbol （ Call lexical analyzer , Take down a symbol ）

• SYM：IP The currently indicated input symbol （ Obtained symbol ）

• ERROR ： Error handling subroutine

example

Each non terminator has the definition of the corresponding subroutine , First, in the analysis process , When you need to start from a non terminal ( deduction ) when , Call the subroutine corresponding to this non terminator .

That is to say , Each subroutine corresponds to a non terminator （ Grammatical units ）, When you encounter this grammatical unit , Use the corresponding subroutine .

Such as ,Ｅ There is a subroutine , be responsible for E The identification of 、 deduction . This program is responsible for calling T and E’.T By the same token, such as .
Be careful , Grammar must be LL(1) Grammar can （ The action is unique ）.

Templates

1

2

The first way to write it ,

ELSE IF What we checked was , Whether it is a Terminator , Yes, it's over , Either it is an error .
another

There is no problem with either .

The second kind , Although there is no inspection follow aggregate , But the next character will be checked first aggregate . In other words , That is, let the following program check whether the current result is correct .
This leads to , The difference between program error reporting positions .

The main program is the start character , Yes, start .

Bakos normal form grammar

In the meta symbol “→” and “ |” On the basis of , Expand a few metalanguage symbols

Such as

Drawing

reference

[1] 《 Programming language compilation principle 》 The third edition Chen Huowang
[2] Compiling principle tutorial and courseware