Definition

Parser begins with the Sentence symbol S, expands a production for S, and so on recursively until words are reached. (Terminals) If the string of words matches the input, a parsing has been found.

Why Backup May Be Required

This approach to parsing might seem hopelessly inefficient. However, top-down filtering, that is testing whether the next word in the input string could begin the phrase about to be tried, can prune many failing paths early.

For What Kinds of Languages Does It Work Well

Languages with keywords, such as programming languages or natural language application. Easy to program.

Recursive Descent Parser

A parse for some context-free languages can be written using the technique of recursive descent. The basic idea is to write a procedure to parse each kind of statement or expression in the grammar. When such procedures are written in a recursive language, they can call each other as needed.
It works well for a well-structured language such as Pascal. In Pascal each statement other than assignment statements begin with a unique reserved word; thus, it is easy for a “big switch" program to determine which statement parser to call.

Problems with Left Recursion

It may be necessary to restructure a grammar to avoid left recursion, which can cause a recursive descent parser to go into a loop.

Left Factoring

A method of modifying a grammar to eliminate left recursion

Implementation of Top-down Parser by A Recursive Program

be able to write a procedure for a construct such as an IF statement

Avoiding Ambiguity while keeping the syntax

Pascal and C follows this convention.

• If parser is SLR, LR(1), or LALR LR parser generator, the programmer will often rely on the generated parser feature of preferring shift over reduce whenever there is a conflict.
• If the parser is produced by a pruning and deep pruning LR generator, one can issue directives that prune away the ambiguities completely.
• If the parser is hand-written, the programmer may use a non-ambiguous context-free grammar. Alternatively, one may rely on a non-context-free grammar or a parsing expression grammar.

Avoiding Ambiguity By Changing the Syntax

• Have a “end if" statement.
• Disallow following then to be if.
• Require a bracelet when else follows if
• Require every if to be paired with an else

Citation:

• Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools
• UT Austin CS375: Compilers by G.Novak.