Friday 22 July 2016

What are the Different Types of Parsers

                  In this post, we will see different types of parsers.

Check following diagram:

                  Broadly, parsers can be classifies into two major categories:
1. Top Down Parser
2. Bottom Up Parser

                  In Top Down Parser, we start with a Starting Non-Terminal , we use the grammar productions and try to reach to the string.

                  Bottom Up Parsing is opposite to the Top Down Parsing. Here we start with String. We reduce it by using grammar productions and try to reach to the Start symbol.

I. Top Down Parser
                 Top Down Parsers can be categorized as follows:

i. TDP with full backtracking
ii. TDP without backtracking 
                 TDP without backtracking is again categorized as follows:
a. Recursive Descent Parser
b. Non-recursive Descent Parser/ LL(1) Parser

II. Bottom Up Parser / SR Parser
                  Bottom Up Parsers can be categorozed as follows:

i. Operator Precedence Parser
ii. LR Parser
                  LR Parsers are again categorized as follows:
a. LR(0) Parser
b. SLR(1) Parser
c. LALR(1) Parser
d. CLR(1) Parser

Next: How To Construct SLR(1) Parsing Table

Previous: How To Construct LL(1) Parsing Table

No comments:

Post a Comment