재귀 하향 파서

섬네일 **재귀 하향 파서**(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 . 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;