Question

If someone can help me with the recursive descent parsing, it woule be very helpful.

This problem should be completed with only c without using lex or yacc.

Problem — LL(1) Grammars and Recursive Descent Parsing

The Grammar::

<program> ::=      program <block> .

<block> ::=            begin <stmtlist> end

<stmtlist> ::=        <stmt> <morestmts>

<morestmts> ::= ; <stmtlist

<stmt> ::=             <assign> | <ifstmt> | <whilestmt> | <block>

<assign> ::=          <variable> = <expr>

<ifstmt> ::=           if <testexpr> then <stmt> else <stmt>

<whilestmt> ::=    while <testexpr> do <stmt>

<testexpr> ::=       <variable> <= <expr>

<expr> ::=             + <expr> <expr> | ∗ <expr> <expr> | <variable> | <digit>

<variable> :: =      a | b | c

<digit> :: =            0 | 1 | 2

Write a recursive descent parser for the above grammar.

Modify your recursive descent parser so that it prints the number of assignment statements in the input program after it successfully parsed the program, and the number of variable references. For the program listed below, your parser should print ”4 assignments, 13 variable references”. Note that a statement such as “a = + a a” has three references, not just one.

program

begin

if b <= 0 then

while a <= 1 do

begin

a = + a b;

c = + a 1

end

else

begin

a = * a b

end;

c = + a b

end.

Answer 1

procedure <assign>() <variable> if (lookahead'-') match (- expr else error O procedure <ifstmt>) if (<testexpr> ( ) ) ; then <stmt> )); elsestmt> ) else erroro procedure <whilestmt>( while (<testexpr*) () ; dostmt>) else error )

procedure くtestexpr>() <variable> (); if (lookahead = ' <-' ) match ('<-) <expr〉 () ; else error (); procedure <expr> () if (lookahead= ' + ' ) match '+ expr if (lookahead-') match ('*') <variable> () <digit> () else error.)

procedure <variable match ("-) match.('a') match (bc) if (lookahead- a') else error.) procedure <digit> if (lookahead--' match (- if (100kahead-' 01 ' ) match ('01') match ('2')

else error ( procedure match (token t) if (lookahead=t) lookahead - next token; else error ) procedure error print ("ERROR"