재귀 하향 파서

thumb
'''재귀 하향 파서'''(recursive descent parser)는 상호 순환 절차(procedure)의 집합(또는 비재귀 적인 동등한 구문)으로 이루어진 하향식 구문 분석이다. 한 절차는 문법의 한 생성 규칙을 처리한다. 따라서 프로그램의 구조는 문법을 반영한 모양이 된다.
 program = block "." .
 block =
     "const" ident "=" number {"," ident "=" number} ";"
     "var" ident {"," ident} ";"
     {"procedure" ident ";" block ";"} statement .
 statement =
     ident ":=" expression
     
 "call" ident
     
 "begin" statement {";" statement } "end"
     
 "if" condition "then" statement
     
 "while" condition "do" statement .
 condition =
     "odd" expression
     
">=") expression .
 expression = "-" term {("+"|"-") term} .
 term = factor {("*"|"/") factor} .
 factor =
     ident
     
 number
     
 "(" expression ")" .
=== C 구현 ===
typedef enum {ident, number, lparen, rparen, times, slash, plus,
    minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,
    endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,
    varsym, procsym, period, oddsym} Symbol;
Symbol sym;
void nextsym(void);
void error(const char msg);
int accept(Symbol s) {
    if (sym == s) {
        nextsym();
        return 1;
    }
    return 0;
}
int expect(Symbol s) {
    if (accept(s))
        return 1;
    error("expect: unexpected symbol");
    return 0;
}
void factor(void) {
    if (accept(ident)) {
        ;
    } else if (accept(number)) {
        ;
    } else if (accept(lparen)) {
        expression();
        expect(rparen);
    } else {
        error("factor: syntax error");
        nextsym();
    }
}
void term(void) {
    factor();
    while (sym == times 
 sym == slash) {
        nextsym();
        factor();
    }
}
void expression(void) {
    if (sym == plus 
 sym == minus)
        nextsym();
    term();
    while (sym == plus 
 sym == minus) {
        nextsym();
        term();
    }
}
void condition(void) {
    if (accept(oddsym)) {
        expression();
    } else {
        expression();
        if (sym == eql 
 sym == neq 
 sym == lss 
 sym == leq 
 sym == gtr 
 sym == geq) {
            nextsym();
            expression();
        } else {
            error("condition: invalid operator");
            nextsym();
        }
    }
}
void statement(void) {
    if (accept(ident)) {
        expect(becomes);
        expression();
    } else if (accept(callsym)) {
        expect(ident);
    } else if (accept(beginsym)) {
        do {
            statement();
        } while (accept(semicolon));
        expect(endsym);
    } else if (accept(ifsym)) {
        condition();
        expect(thensym);
        statement();
    } else if (accept(whilesym)) {
        condition();
        expect(dosym);
        statement();
    } else {
        error("statement: syntax error");
        nextsym();
    }
}
void block(void) {
    if (accept(constsym)) {
        do {
            expect(ident);
            expect(eql);
            expect(number);
        } while (accept(comma));
        expect(semicolon);
    }
    if (accept(varsym)) {
        do {
            expect(ident);
        } while (accept(comma));
        expect(semicolon);
    }
    while (accept(procsym)) {
        expect(ident);
        expect(semicolon);
        block();
        expect(semicolon);
    }
    statement();
}
void program(void) {
    nextsym();
    block();
    expect(period);
}
=== 파스칼 구현 ===
// Modern Pascal implementation (www.ModernPascal.com)
// C example ported to Pascal by Ozz Nixon
{$S-}
type
   SYMBOL = (ident, number, lparen, rparen, times, slash, plus,
    minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,
    endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,
    varsym, procsym, period, oddsym);
var
   sym:SYMBOL;
procedure expression; forward;
procedure nextsym;
begin
// you implement //
end;
procedure error(const msg:String);
begin
// you implement //
end;
function accept(S:Symbol):boolean;
begin
   if sym=s then begin
      nextsym();
      Result:=True;
   end
   else Result:=False;
end;
function expect(S:Symbol):boolean;
begin
   Result:=accept(s);
   if not result then error('Expect: unexpected symbol');
end;
procedure factor;
begin
   if (accept(ident)) then begin
//
   end
   else if (accept(number)) then begin
//
   end
   else if (accept(lparen)) then begin
      expression();
      expect(rparen);
   end
   else begin
      error('factor: syntax error');
      nextsym();
   end;
end;
procedure term;
begin
   factor();
   while (sym=times) or (sym=slash) do begin
      nextsym();
      factor();
   end;
end;
procedure expression;
begin
   if (sym=plus) or (sym=minus) then nextsym();
   term();
   while (sym=plus) or (sym=minus) do begin
      nextsym();
      term();
   end;
end;
procedure condition;
begin
   if (accept(oddsym)) then begin
      expression();
   end
   else begin
      expression();
      if (sym=eql) or (sym=neq) or (sym=lss) or (sym=leq) or (sym=gtr) or (sym=geq) then begin
         nextsym();
         expression();
      end
      else begin
         error('condition: invalid operator');
         nextsym();
      end;
   end;
end;
procedure statement;
begin
   if (accept(ident)) then begin
      expect(becomes);
      expression();
   end
   else if (accept(callsym)) then begin
      expect(ident);
   end
   else if (accept(beginsym)) then begin
      repeat
         statement();
      until not (accept(semicolon));
      expect(endsym);
   end
   else if (accept(ifsym)) then begin
      condition();
      expect(thensym);
      statement();
   end
   else if (accept(whilesym)) then begin
      condition();
      expect(dosym);
      statement();
   end
   else begin
      error('statement: syntax error');
      nextsym();
   end;
end;
procedure block;
begin
   if (accept(constsym)) then begin
      repeat
         expect(ident);
         expect(eql);
         expect(number);
      until not (accept(comma));
      expect(semicolon);
   end;
   if (accept(varsym)) then begin
      repeat
         expect(ident);
      until not (accept(comma));
      expect(semicolon);
   end;
   while (accept(procsym)) do begin
      expect(ident);
      expect(semicolon);
      block();
      expect(semicolon);
   end;
   statement();
end;
begin
   nextsym();
   block();
   expect(period);
end;
* 자바CC
*  Introduction to Parsing - an easy to read introduction to parsing, with a comprehensive section on recursive descent parsing
분류:파싱 알고리즘