Recursive descent parser: Difference between revisions

Revision as of 08:26, 31 March 2006

Revision as of 17:06, 2 April 2006

Line 15:

[[Algorithms + Data Structures = Programs]]) is in [[LL parser|LL(1)]] form:

<pre>

program = block "." .

Line 40 ⟶ 41:

factor = ident | number | "(" expression ")" .

</pre>

[[Terminal symbol|Terminals]] are expressed in quotes (except for the well defined ''ident''

Line 46 ⟶ 48:

Notice how closely the predictive parser below mirrors the grammar above. There is a procedure for each nonterminal in the grammar. Parsing descends in a top-down manner, until the final nonterminal has been processed. The program fragment depends on a global variable, ''sym'', which contains the next symbol from the input, and the global function ''getsym'', which updates ''sym'' when called.

<pre>

Symbol sym;

typedef enum {ident, number, lparen, rparen, times, slash, plus,

void getsym();

minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,

endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,

int accept(Symbol s)

varsym, procsym, period, oddsym} Symbol;

{

if (sym == s) {

Symbol sym;

getsym();

void getsym(void);

return 1;

void error(const char msg[]);

}

void expression(void);

return 0;

}

int accept(Symbol s) {

int expect if (Symbolsym == s) {

getsym();

{

if (accept(s)) return 1;

}
return 10;

}

error("expect: unexpected symbol");

return 0;

int expect(Symbol s) {

}

if (accept(s))

return 1;

void factor()

error("expect: unexpected symbol");

{

return 0;

if (accept(ident))

}

;

else if (accept(number))

void factor(void) {

;

else if (accept(lparenident)) {

expression();

} else if expect(rparenaccept(number);) {

} else { ;

} else if (accept(lparen)) {

error("factor: syntax error");

getsymexpression();

} expect(rparen);

} else {

}

error("factor: syntax error");

getsym();

void term()

}

{

}

factor();

while (sym == times || sym == slash) {

void term(void) {

getsym();

factor();

while (sym == times || sym == slash) {

}

getsym();

}

factor();

}

void expression()

}

{

if (sym == plus || sym == minus)

void expression(void) {

getsym();

if (sym == plus || sym == minus)

term();

while (sym == plus || sym == minusgetsym() {;

getsymterm();

while (sym == plus || term(sym == minus); {

} getsym();

term();

}

}

}

void condition()

{

void condition(void) {

if (accept(oddsym))

if (accept(oddsym)) {

expression();

else { expression();

} else {
expression();

if (sym == eql || sym == neq || sym == lss ||

sym == leq || sym == gtr || sym == geq) {

getsym();

expression();

} else {

error("condition: invalid operator");

getsym();

}

}

}

void statement(void) {

if (accept(ident)) {

{

if expect(accept(identbecomes)) {;

expectexpression(becomes);

} else if (accept(callsym)) {

expression();

} else if expect(accept(callsym)ident);

} else if expect(identaccept(beginsym);) {

else if (accept(beginsym)) do {

do statement();

} while statement(accept(semicolon));

while expect(accept(semicolon)endsym);

} else if expect(endsymaccept(ifsym);) {

} else if condition(accept(ifsym)) {;

conditionexpect(thensym);

expectstatement(thensym);

} else if (accept(whilesym)) {

statement();

} else if condition(accept(whilesym)) {;

conditionexpect(dosym);

expectstatement(dosym);

}

statement();

}

}

}

void block(void) {

if (accept(constsym)) {

void block()

do {

{

expect(ident);

if (accept(constsym)) {

do { expect(eql);

expect(identnumber);

} while expect(eqlaccept(comma));

expect(numbersemicolon);

}

} while (accept(comma));

if (accept(varsym)) {

expect(semicolon);

} do {

if expect(accept(varsymident)) {;

} dowhile (accept(comma));

expect(identsemicolon);

}
while (accept(commaprocsym)); {

expect(semicolonident);

expect(semicolon);

}

while block(accept(procsym)) {;

expect(identsemicolon);

}

expect(semicolon);

blockstatement();

}

expect(semicolon);

}

void program(void) {

statement();

getsym();

}

block();

expect(period);

void program()

}

{

</pre>

getsym();

block();

expect(period);

}

== Formalizing recursive descent parsers ==