재귀 하향 파서

재귀 하향 파서(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 ("="|"#"|"&lt;"|"&lt;="|"&gt;"|"&gt;=") 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
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;