Bottom-Up Parser

Parsing

Parsing may be defined as the process of analyzing syntax of any programming language. It is the process of analyzing a string of symbols, either in natural language or in computer language, according to the rules of grammar. The main job of parsers for any programming language is to construct parse tree for a given program and also find all the syntax errors, for each, input program and even produce an appropriate diagnostic message and recover quickly.

Parsers are of two types according to the direction in which they build parse trees. They are:

a. Top-down Parser.

b. Bottom-Up Parser.

In this essay, I am going to write in brief about Bottom-Up Parser.

In Bottom-Up Parser, the parse tree is built from the leaves upward to the root, in which attempt is made to rewrite the input to the start symbols. Here, parser attempts to locate the most basic elements and then elements containing these elements and so on. It is technique where a string is recognized by constructing a right-most derivative in reverse. There are many technique of Bottom-Up parsing, among them, I will be writing about 2 of the techniques which are:

a. LR Parser.

b. SLR parser

a. LR Parser:

LR parser is one of the bottom-up parsing technique (also called as canonical LR), uses a relatively small program and a parsing table that is built for a specific programming language. The original LR parsing technique was designed by Donald Knuth in 1965 but it was subsequently derived and several variation were made to make the required computer time and memory use less.

The advantages of LR Parser is that it can be built for all programming language and also it can detect errors as soon as it is possible in a left-to-right scan.

LR parser has a parse stack as:

S0X0S1X1...SmXm(top)

Where S’s are state symbol and X’s are Grammar Symbol .

The detailed form of LR parser configuration is:

(S0X0S1X1...SmXm, aiai+1…an$)

There are two parts, ACTION and GOTO in LR Parsing. ACTION...