Compilation principle learning notes 3 (top-down syntax analysis)

Connect Notes on Compiling Principles 2, Continue to learn grammar analysis

3.3 Top down parsing

The basic idea of top-down analysis is ： For any input sequence , Start with the start sign of grammar , Perform the leftmost derivation , Until you get a legal sentence or find an illegal structure , Establish an analysis tree from top to bottom . The whole analysis is a Probe + to flash back The process of , So there will be some problems .

1） If there is a recursive production , Will cause the derivation to fall into a dead cycle ;
2） If there is a common prefix between multiple productions , It may cause a lot of backtracking ;
3） If there is ambiguity in grammar , Then multiple analyses may produce different results .

In order to overcome the above shortcomings , Some optimization methods need to be taken to rewrite the syntax ：

1） Eliminate left recursion ;
2） Extract the common left factor ;
3） Eliminate ambiguity .

3.3.1 Eliminate left recursion

1） Eliminate direct left recursion of grammar
Direct left recursion , That is, the non terminator on the left of the production appears on the right of the production .
Algorithm ： such as , For production with only two candidates A->Aα|β, Can be converted to A->βA’ and A’->αA’|ε To eliminate left recursion , It can be extended to more candidates , Just add β and α The number of .

The algorithm can be understood in this way ： The language corresponding to the original production is β start , Follow behind n individual α, Therefore, we can make a production formula as A->βA’ To create β, Another production to recursively generate α, And add one ε To end the recursion .

2） Eliminate indirect left recursion of grammar
Indirect left recursion , It can be judged by drawing a directed graph , If there are rings , It means there is recursion .
Algorithm ： such as , For production ,S->Aa|b and A->Ac|Sd|ε（S Recursion of is not direct , But it is transitive ）, Can be converted to S->Aa|b,A->bdA’|A’,A’->cA’|adA’|ε.

The algorithm can be understood in this way ： use S Replace the two production formulas on the right A In the right S, Can be A The production of becomes the form of direct left recursion , Can be combined with the previous algorithm to eliminate .
But if grammar contains A -> A Like production, the algorithm fails .

3.3.2 Extract the left factor

In fact, it is to extract the public prefix , Change the latter part into a new production , It is relatively simple to understand .
Generally, the left recursion is eliminated first , Usually, after elimination, part of the left factor can also be eliminated .

3.3.3 Eliminate ambiguity

If there is ambiguity in grammar , Then repeated derivation will produce different results , Get a variety of analysis trees , As a result, the prediction analysis table cannot work normally , In this case , Need to rewrite grammar .
Ambiguity is usually caused by the priority and associativity of operators , Therefore, the derivation can be guided artificially , About the operator in the production formula On the right Replace the non terminator of with a new non terminator , Generate a new production , The uncertainty is artificially eliminated .

for example ：E->E+E | id I could rewrite it as E->T | E+T and T->id

3.3.4 Recursive descent subroutine

Similar to function call , That is, call the terminator in the production match() Function to match , Instead, the terminator is defined as a function to call .

for example ：A->adSc,S->a The recursive descent subroutine of is ：
A() { match(a); match(d); S(); match; }
S() { match(a); }