[Solved] CSCI-621 Programming Languages Programming Assignment 3 A Non-recursive Predictive Parser

Design and implement a Non-recursive Predictive Parser (NPP) for the following grammar:

<elist> <elist> , <e> | <e>

<e> <n> ^ <e> | <n>

<n> <n> <d> | <d>

<d> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Where ^ is an exponentiation operator (associate to right). This grammar generates statements of the form 2^2^3, 15, 20^2 for which the parser outputs 256 15 400.

Solution:

In order to implement this NPP, a parse table must be constructed by using first sets and follow sets.

The parse table for this parser is shown as follows:

1

The Non-recursive Predictive Parsing Algorithm is:

Let T$ be the input string followed by a $.

Set ip to point to the first symbol of T$. Repeat

Let X be the top of stack symbol.

Let a be the symbol pointed to by ip.

IF X is a terminal or $ THEN

IF X== a THEN

Pop X from the stack and advance ip

ELSE error()

ELSE IF M[X,a] == XY₁Y₂Y_k THEN

BEGIN

pop X from the stack

push Y_k,Y_k-1,,Y₁ onto to the stack with Y₁ on the top

output XY₁Y₂Y_k

END

ELSE error()

UNTIL X == $

2