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 ")" === 구현 === 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 else if expression(); expect(rparen); else error("factor: syntax error"); nextsym(); void term(void) factor(); while (sym == times sym == slash) nextsym(); factor(); void if (sym == plus sym == minus) nextsym(); term(); while (sym == plus sym == minus) nextsym(); term(); void condition(void) if expression(); else expression(); if (sym == eql sym == neq sym == lss sym == leq sym == gtr sym == geq) nextsym(); expression(); else invalid operator"); nextsym(); void statement(void) if (accept(ident)) expression(); else if expect(ident); else if do statement(); while expect(endsym); else if (accept(ifsym)) condition(); statement(); else if condition(); expect(dosym); statement(); else syntax error"); nextsym(); void block(void) if do expect(ident); expect(eql); expect(number); while if do expect(ident); while while expect(ident); block(); statement(); void program(void) nextsym(); block(); expect(period); === 파스칼 구현 === // Modern Pascal implementation // 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 begin if sym=s then begin nextsym(); Result:=True; end else Result:=False; end; function begin if not result then error('Expect: unexpected symbol'); end; procedure factor; begin if (accept(ident)) then begin // end else if then begin // end else if 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 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 invalid operator'); nextsym(); end; end; end; procedure statement; begin if (accept(ident)) then begin expression(); end else if then begin expect(ident); end else if then begin repeat statement(); until not expect(endsym); end else if (accept(ifsym)) then begin condition(); statement(); end else if then begin condition(); expect(dosym); statement(); end else begin syntax error'); nextsym(); end; end; procedure block; begin if then begin repeat expect(ident); expect(eql); expect(number); until not end; if then begin repeat expect(ident); until not end; while do begin expect(ident); block(); end; statement(); end; begin nextsym(); block(); expect(period); end; == 같이 보기 == 자바CC == 외부 링크 == Introduction to Parsing an easy to read introduction to parsing, with comprehensive section on recursive descent parsing 분류:파싱 알고리즘