CSc 446 Recursive descent example
Given the grammar:
GOAL -> begint STAT_LIST endt .
STAT_LIST -> STAT ; STAT_LIST | e
STAT -> idt := EXPR | read (idt) | write (idt)
EXPR -> idt TAIL
TAIL -> addop idt TAIL | e
The following Recursive descent parser can be constructed:
program RDParser;
uses mylex;
procedure match(desired:symbol);
begin
if token = desired then
GetNextToken
else begin
writeln(‘Parse Error’);
halt;
end;
end;
procedure GOAL;
begin
match(begint);
STAT_LIST;
match(endt);
match(periodt);
end;
procedure STAT_LIST;
begin
if token in [idt, readt, writet ] then begin
STAT;
match(semicolon);
STAT_LIST:
end;
end;
procedure STAT;
begin
case token of
idt: begin
match(idt);
match(assignop);
EXPR;
end;
readt: begin
match(readt);
match(lparen);
match(idt);
match(rparen);
end;
writet: begin
match(writet);
match(lparen);
match(idt);
match(rparen);
end;
else begin
writeln(‘Parse Error’);
halt;
end;
end; {case}
end;
procedure EXPR;
begin
match(idt);
TAIL;
end;
procedure TAIL;
begin
if token = addop then begin
match(addop);
match(idt);
TAIL;
end
end;
begin {MAIN PROGRAM}
GetNextToken; {Prime the parser with the
first token}
GOAL;
if token = eofilet then
writeln(‘Successfull compilation’)
else
writeln(‘ERROR – unused tokens’);
end.
using the program
begin
read(num);
sum := num + num;
write(num);
end.
trace through the program and show that it is syntactically correct.