Wikipedia

Recursive descent parser: Difference between revisions

Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
→Example parser: fmt (EBNF grammar example) (spacing and 4-space indent)
→Example parser: fmt (C example) (braces and 4-space indent)
Line 46:
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.
 
Symbol sym;
<pre>
void getsym();
int accept(Symbol s) {
if (sym == s) {
int accept(Symbol s)
getsym();
{
return 1;
if (sym == s) {
}
getsym();
return 0;
return 1;
}
}
 
return 0;
int expect(Symbol s) {
}
if (accept(s))
return 1;
int expect(Symbol s)
error("expect: unexpected symbol");
{
return 0;
if (accept(s))
}
return 1;
 
error("expect: unexpected symbol");
void factor(void) {
return 0;
if (accept(ident)) {
}
;
} else if (accept(number)) {
void factor()
;
{
} else if (accept(lparen)) {
if (accept(ident))
expression();
expect(rparen) ;
} else {if (accept(number))
error("factor: syntax error") ;
else if (accept(lparen)) {
getsym();
expression();
}
expect(rparen);
}
} else {
 
error("factor: syntax error");
void term(void) {
factor getsym();
}
while (sym == times || sym == slash) {
}
getsym();
factor();
void term()
}
{
}
factor();
 
while (sym == times || sym == slash) {
void expression(void) {
if (sym == plus || sym == minusgetsym();
getsym factor();
term(); }
}
while (sym == plus || sym == minus) {
getsym();
void expression()
term();
{
}
if (sym == plus || sym == minus)
}
getsym();
 
term();
void condition(void) {
while (sym == plus || sym == minus) {
if (accept(oddsym)) {
expression getsym();
term();
} else {
expression(); }
}
if (sym == eql || sym == neq || sym == lss ||
sym == leq || sym == gtr || sym == geq) {
void condition()
getsym();
{
expression();
} elseif {(accept(oddsym))
error("condition: invalid operator" expression();
else getsym();{
expression();
}
if (sym == eql || sym == neq || sym == lss ||
}
sym == leq || sym == gtr || sym == geq) {
}
getsym();
 
expression();
void statement(void) {
if (accept(ident)) } else {
error("condition: invalid operator");
expect(becomes);
expression getsym();
}
} else if (accept(callsym)) {
expect(ident); }
}
} else if (accept(beginsym)) {
do {
void statement();
{
} while (accept(semicolon));
expect if (endsymaccept(ident)); {
expect(becomes);
} else if (accept(ifsym)) {
condition expression();
} else if (accept(callsym))
expect(thensym);
statement expect(ident);
} else if (accept(whilesymbeginsym)) {
condition(); do
expect statement(dosym);
while (accept(semicolon));
statement();
expect(endsym);
}
} else if (accept(ifsym)) {
}
condition();
 
expect(thensym);
void block(void) {
statement();
if (accept(constsym)) {
} else if (accept(whilesym)) {
do {
expect condition(ident);
expect(eqldosym);
expect statement(number);
}
} while (accept(comma));
}
expect(semicolon);
}
void block()
if (accept(varsym)) {
{
do {
if expect(identaccept(constsym);) {
} while (accept(comma)); do {
expect(semicolonident);
expect(eql);
}
expect(number);
while (accept(procsym)) {
expect } while (identaccept(comma));
expect(semicolon);
block(); }
expect if (semicolonaccept(varsym)); {
do
}
expect(ident);
 
while (accept(comma));
statement();
expect(semicolon);
}
}
 
while (accept(procsym)) {
void program(void) {
getsym expect(ident);
expect(semicolon);
block();
expect block(period);
expect(semicolon);
}
}
</pre>
statement();
}
void program()
{
getsym();
block();
expect(period);
}
 
== Formalizing recursive descent parsers ==
Retrieved from "https://en.wikipedia.org/wiki/Recursive_descent_parser"