Understanding Predictive Parsing

In this class, We discuss Understanding Predictive Parsing.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of recursive descent parsing. Click Here.

We take an example and understand predictive parsing.

We are using the recursive method in predictive parsing, and in predictive parsing, we eliminate backtracking.

Example:

The below grammar will accept expressions, loop statements, and other statements.

‘expr’ is considered as terminal in our example.

‘optexpr’ is called an optional expression. Used to accept epsilon or expression.

Input string: for( ; expr; expr) other

Look ahead: We take a look-ahead variable, which initially points to the first input symbol.

The lookahead variable is looking at one input symbol in the input.

We can lookahead two symbols or k symbols. But writing the program is complex.

In our examples, we follow lookahead one input symbol.

Based on the lookahead symbol, we are deciding to choose production. So we are eliminating backtracking.

The below code will help to understand how backtracking is eliminated.

We are taking the case statement based on the lookahead symbol in the code.

Thie above is not the situation in recursive descent parsing.

When we go to case ‘if’, we are calling the match(if), match((), match(‘expr’), match()), and calling the ‘stmt’ function.

The case ‘if’ is checking for the syntax of the statement.

We will understand what the match function does in a minute.

By taking the lookahead symbol from the input, we are eliminating backtracking.

The match function will check whether the lookahead and match symbol are the same or not.

If same. The lookahead variable point to the next input symbol.

We have written one ‘if’ condition in the optional expression function.

If the lookahead is not matched to the symbol in the condition, the function completes.

Not matching the ‘if’ condition is accepting epsilon.

The below example shows the predictive parsing execution for expression grammar.

Based on the lookahead input symbol, the grammar is expanding.

Still, the parsing technique is recursive.

We discussed problems with recursive methods in our last class.

In our next class, we discuss a table-driven method for syntax analysis.