되부름 하향 (recursive descent parser)는 상호 순환 절차(procedure)의 집합(또는 비재귀 적인 동등한 구문)으로 이루어진 하향식 구문 분석이다. 한 절차는 문법의 한 생성 규칙을 처리한다. 따라서 프로그램의 구조는 문법을 반영한 모양이 된다. program = block "." . block = "const" 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 ")" . 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 slash) do begin nextsym(); factor(); end; end; procedure expression; begin if (sym minus) then nextsym(); term(); while (sym minus) do begin nextsym(); term(); end; end; procedure condition; begin if (accept(oddsym)) then begin expression(); end else begin expression(); if (sym lss) 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 분류:파싱 알고리즘