Question

Write a parser program for cSub using the method of recursive descent. The main program here will effectively be the main program of the compiler as a whole. The input to the program will be a Csub source file, specified on the command line. The program will construct a parse tree for the program, with one interior node for every nonterminal in the derivation of the program, and one leaf node for each of the id, num, and real tokens in the program. The root of the tree is a "program" node that represents the entire program.

The program should have two forms of output: a representation of the parse tree, and a list of error messages. To write the parse tree representation, use Scheme-style prefix notation. For each interior node, use a list whose first element identifies the type of node and whose remaining elements represent the subtrees of the node. This output should be written to System.out/cout/stdout. For each tree node or token, define a "toString" method, which produces a string displays the contents of the node in the form of a Scheme expression whose first element identifies the type of the node and whose remaining elements represent the subtrees of the node.

For example, for a node representing the following if statement if(x<=y)z=a+b; toString might produce ( if-stmt( lesseq id(x) id(y) )( expr-stmt ( assign id(z) ( add id(a) id(b) ) ) ) ) After the tree is built, the output can be produced by calling the toString method of the root node.

Error messages should be written to ( System.out | cout | stdout ). They should identify the line number on which the error was detected and give a brief (one-line) description of the error. If an error is detected, try to recover and continue parsing the program. If there is an error, it is not necessary to write tree.out.

Two major design decisions you will face are:

1. How to organize the various components of the recursive descent parsing algorithm, and

2. How to design the syntax tree structure which is to be constructed by the parser. One approach is to start by defining an abstract class for each nonterminal N. Then define a concrete subclass for each right-hand side of a production for N. Each class defined in this way should have an attribute for each symbol in the right-hand side of the production. You should also look for ways to simplify the parse tree, generating an abstract syntax tree, as I've done in the example above.

BNF grammar for a subset of C:

program --> declaration-list

declaration-list --> declaration-list declaration | declaration

declaration --> var-declaration | fun-declaration

var-declaration --> type-specifier id ; | type-specifier id [ num ] ; | type-specifier * id ;

type-specifier --> int | float | void

fun-declaration --> type-specifier id ( params ) compound-stmt

params --> param-list | void

param-list --> param-list ,param | param

param --> type-specifier id | type-specifier id [ ] | type-specifier * id

compound-stmt --> { local-declarations statement-list }

local-declarations --> local-declarations var-declaration | 

statement-list --> statement-list statement | 

statement --> expression-stmt | compound-stmt | if-stmt | while-stmt | for-stmt | return-stmt

expression-stmt --> optional-expression ;

if-stmt --> if ( expression ) statement | if ( expression ) statement else statement

while-stmt --> while ( expression ) statement

for-stmt --> for ( optional-expression ; optional-expression ; optional-expression ) statement

return-stmt --> return ; | return expression ;

optional-expression --> expression | 

expression --> or-exprassignop expression | or-expr

assignop --> = | += | -=

or-expr --> and-expr | or-expr || and-expr

and-expr --> relational-expr | and-expr && relational-expr

relational-expr --> relational-expr relop additive-expr | additive-expr

relop --> <= | >= | < | > | == | !=

additive-expr --> additive-expraddop term | term

addop --> + | -

term --> term mulop unary-expr | unary-expr

mulop --> * | / | % unary-expr --> primary-expr | unaryop unary-expr

unaryop --> + | - | ! | & | *

primary-expr --> ( expression ) | id | id [ expression ] | call | num | real

call --> id ( args )

args --> arg-list | 

arg-list --> arg-list , expression | expression

Answer 1

#program written in C language

#include<stdio.h>

#include<ctype.h>

#include<string.h>

void Tprime();

void Eprime();

void E();

void check();

void T();

char expression[10];

int count, flag;

int main()

{

      count = 0;

      flag = 0;

      printf("\nEnter an Algebraic Expression:\t");

      scanf("%s", expression);

      E();

      if((strlen(expression) == count) && (flag == 0))

      {

            printf("\nThe Expression %s is Valid\n", expression);

      }

      else

      {

            printf("\nThe Expression %s is Invalid\n", expression);

      }

}

void E()

{

      T();

      Eprime();

}

void T()

{

      check();

      Tprime();

}

void Tprime()

{

      if(expression[count] == '*')

      {

            count++;

            check();

            Tprime();

      }

}

void check()

{

      if(isalnum(expression[count]))

      {

            count++;

      }

      else if(expression[count] == '(')

      {

            count++;

            E();

            if(expression[count] == ')')

            {

                  count++;

            }

            else

            {

                  flag = 1;

            }

      }        

else

      {

            flag = 1;

      }

}

void Eprime()

{

      if(expression[count] == '+')

      {

            count++;

            T();

            Eprime();

      }

}