Compiler Design Top Down Parser - Compiler Design

How top-down parser works in compiler design?

In the top-down parser technique, the input is parsed and the parse tree is constructed from the root node and gradually moves down to the left nodes. The different types of top-down parsing are as follows:

Top Down Parsing

Recursive Descent Parsing

Under this technique, the parse tree is constructed from the top and the input is read from left to right. The procedures for every terminal and non-terminal entity are used. The input is recursively parsed by this technique for preparing a parse tree with or without back-tracking. But back-tracking cannot be avoided for the associated grammar. Predictive parsing is the recursive descent parsing without any back-tracking.

This parsing technique is regarded recursive as it uses context-free grammar which is recursive in nature.

Back-tracking

The parse tree is started from the root node and the input string is matched against the production rules for replacing them. An illustration of CFG, makes better understand the concept.

For an input string: read, a top-down parser will behave like this:

It starts S from the production rules and the yield is matched to the left-most letter of the input, i.e. ‘r’. The production of S matches with it. And the top-down parser is advanced to the next input letter ‘e’. The non-terminal ‘X’ is expanded and checked the production from left (X → oa). It does not match with the next input symbol. So the top-down parser backtracks to obtain the next production rule of X, (X → ea).

All the input letters are matched by the parser in an ordered manner and the string is accepted.

back_tracking_1 back_tracking_2 back_tracking_3 back_tracking_4

Predictive Parser

A recursive descent parser that facilitates in predicting the production to be used for replacing the input string is known as Predictive parser. This type of parsing does not suffer from backtracking.

A look-ahead pointer, which points to the next input symbol, is used by the parser for accomplishing the tasks. Some constraints are put on the grammar and only a class of grammar known as LL(k) grammar are accepted to make the parser back-tracking free.

Predictive Parser

A stack is used by predictive parsing and the parsing table is used for parsing the input and thus a parse tree is generated. An end symbol $ is included in both the stack and input for denoting that the stack is empty and that the input is consumed. The parsing table is referred for the parser to decide the combination of the input and stack elements.

Top Down Parser Construction

There is more than on production to choose from a single instance of input in recursive descent parsing in recursive descent parsing and in predictive parser each step has one production to choose.

LL Parser

The LL grammar is accepted by the LL Parser. In order to achieve easy implementation, the context-free grammar to obtain the simplified manner, is included with some restrictions, which is known as LL grammar. Both algorithms – recursive-descent or table-driven can be used for implementing LL grammar.

LL(k) denotes LL parser. The first L in LL(k) is parsing the input from left to right, the second L in LL(k) stands for left-most derivation and k itself represents the number of looks ahead. Generally k = 1, so LL(k) may also be written as LL(1).

LL Parser

LL Parsing Algorithm

The parser explanation is sticked to deterministic LL(1) since the size of the table grows exponentially in relation to the value of k. Secondly, if a given grammar is not LL(1), then usually, it is not LL(k), for any given k.

The algorithm for LL(1) Parsing is as follows:

A grammar G is LL(1) if A → α | β are two distinct productions of G:

  • Both α and β derive the strings beginning with a no terminal.
  • An empty string is derived from among any one of α and β.
  • if β → t, then α does not derive any string beginning with a terminal in FOLLOW(A).

All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Compiler Design Topics