Lab 1.2: 구문 분석기

오늘은 구문 분석기를 만듭니다. 구문 분석기를 단독으로 만들 수도 있지만 어휘 분석기와 함께 만드는 것이 좋습니다. 어휘 분석기와 구문 분석기의 기능을 간단히 요약하면 다음과 같습니다.

• 어휘 분석기: 문자열을 토큰열로 변환
• 구문 분석기: 토큰열을 구문 트리로 변환

일단 구문 트리가 만들어지면 트리를 출력할 수 있겠지요? 지난 시간에 데이터를 출력하는 루틴을 만들었으니 이를 이용하여 출력할 수 있을 겁니다. 지난 시간의 미진한 부분은 동료 코드를 보고 수정하기 바랍니다.

#LISP의 EBNF

구문 분석기를 만들 때에는 문법이나 EBNF(Extended Backus-Naur Form)가 있으면 좋습니다. 이를 바탕으로 구문 분석기 코드를 작성할 수 있으니까요. LISP의 BNF는 다음 링크에서 찾을 수 있습니다.

iamwilhelm.github.io/bnf-examples/lisp

이를 바탕으로 EBNF를 작성하면 다음과 같습니다.

<sExpr> ::= <atom>
          | "(" <sExpr> "." <sExpr> ")"
          | <list>
   
<list>  ::= "(" { <sExpr> } ")"

<atom>  ::= SYMBOL 
          | LITERAL
          | ID   

위 EBNF는 토큰을 추가하여 링크의 BNF를 조금 개선한 것입니다. 위 EBNF에서 대문자로 쓴 SYMBOL, LITERAL, ID는 토큰입니다.

#문법 변환

위 EBNF는 구문 분석에 적합하지 않습니다. 먼저 "(" 부분이 중복되므로 좌측 인수분해를 수행하거나 다른 방식을 이용해야 합니다. EBNF의 선택(optional) 기능을 이용하면 이를 다음과 같이 간단히 쓸 수 있습니다.

<sExpr> ::= <atom>
          | "(" [ <sExpr> ( "." <sExpr> | { <sExpr> }+ ) ] ")"

<atom>  ::= SYMBOL 
          | LITERAL
          | ID   

<sExpr>의 두 번째 규칙이 너무 복잡하다면 별도의 비단말기호 <list>를 이용해도 됩니다.

#이후 방향

구문 분석기라는 큰 과제를 끝내고 나면 큰 산을 하나 넘은 것입니다. 이후 과정은 상대적으로 쉽게 진행할 수 있을 것이니 힘 내세요.