Top-down Parsing

Syntax analysis deals with derivation of sentence structures and sentences. Main task of syntax analysis is the design of derivation algorithms for languages with complex grammatical structures. 

Top-down parsing can be viewed as an attempt to find left-most derivations of an input-stream by searching for parse-trees using a top-down expansion of the given formal grammar rules. 

As the result of top-down analysis, the language sentence is generated from the start symbol.

Example1:

                                            
                                                
<sentence> ::= <objective> <predicate>
<objective>::= flowers | stars
<predicate>::= bloom | shine
                                            
                                                
<sentence> | stars shine
<objective> <predicate>| stars shine
stars <predicate>| stars shine
<predicate>| shine
shine| shine
- - - | - - -

The sentence was generated from start symbol, in this case it is <sentence>, therefore it belongs to language. The process of sentence parsing has been presented graphically. On the left, the consecutive sequences of derivations from grammar are placed, whereas on the right, there is the input sequence of words remaining to be analysed. According to syntactic rules, the <subject> <predicate>construction can be called a sentence. Based on the second grammatical production, the word stars can be directly generated from the symbol <subject>so the word stars is removed from the input sequence. Next, the parser checks the second part of the sentence. The word shine can be generated directly from the symbol <predicate>so the sentence parsing is completed successfully.
Example 2:

                                        
                                            
S::=xA|
A::= z |yA
                                        
                                            
S xyyz
x A zyyz
A yyz
y A yyz
A yz
y A yz
A z
z z
._ ._ ._. ._._._.

Syntax analysis consists of recreating the steps that generated the sentence. This process is called derivation, that is why the above-described algorithm is called the derivation algorithm. In both cases, the decision to replace a non-terminal symbol could be made after examining the consecutive symbol in the input sequence.