[Compiler] Extended Backus-Naur Form (EBNF)

지난 포스트를 통해서 Context Free Grammar에 대해 다뤘다. 간단히 요약해보자면 Regular Expression으로 표현하기 힘든 문법들이 존재하기 때문에 표현하기 위한 대체 방안으로 CFG를 언급했고, 여기서 Syntax Tree를 그려보았다. 여기서 Left Recursive문제가 발생하기 때문에 이를 해결하기 위한 방법으로 Left Factoring, 즉 terminal을 오른쪽에 배치해서 해결할 수 있다고 했다. 

 그런데 그때 잠깐 소개했던 내용중에 이런게 있었다.

이 때 이걸 Notational Convention이라고 소개했다. 이게 정의되어 있어야 어떤 부분을 terminal로 할지 또는 nonterminal로 할지를 정할 수 있었다. 사실 위의 내용은 사용자가 임의로 정한 notation이고, 이 것말고도 terminal과 nonterminal로 구분해야 될 내용들이 무척 많다. 물론 이에 대한 grammar도 사용자가 지정해야 한다. 

 이에 대해서 일부 연구자들이 연구했고, 그중에 John Backus가 규격화한 방법을 Backus-Naur Form이라고 한다. 사실 이 이름자체도 원래 Backus가 만든게 아니었다. Backus는 기존의 alan turing이나 Noam chomsky가 소개한 natural Language를 체계적으로 정리한 것이었고, 원래 이름도 multiliguistic formulas 라는 제목으로 소개되었다. 이 내용을 Peter Naur가 조금 더 보완해서 Backus-Normal Form으로 정리했고, 후세에서는 Naur의 업적도 인정해서 결국 Backus-Naur-Form(BNF)으로 소개하게 된 것이다. 

 Backus는 BNF를 ALGOL을 기반으로 작성했고, 형식은 다음과 같다.

여기에는 3가지 정형화된 symbol이 있다. 

 - ::=  - Definition

 - <>   - Nonterminal

 - |      - Alternation

위의 3가지 symbol을 통해서 notation을 표현한다는 것이다. 그래서 위의 형식을 해석해보면 Symbol이라는 Nonterminal은 __expression__으로 정의할 수 있다는 것이다. Wikipedia에 보면 조금더 직관적인 예제가 소개되어 있다.

<postal-address> ::= <name-part> <street-address> <zip-part>
 
      <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> 
                    | <personal-part> <name-part>
 
  <personal-part> ::= <first-name> | <initial> "." 
 
 <street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>
 
       <zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>
 
<opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | "" 

<opt-apt-num> ::= <apt-num> | ""

 이 예제는 미국 우편 체계를 BNF 형식으로 표현한 것이다. 간단하게 첫번째 구문을 해석해보면 미국의 postal-address라는 nonterminal은 name-part와 street-address, zip-part 가 concatenate된 형식으로 구성되어 있다는 것이다. 해석하다 보면 매우 직관적이라는 것을 느낄 수 있을 것이다. 실제로 compiler의 구문 분석시에는 다음과 같은 예제를 적용할 수 있다.

즉, 숫자 하나하나는 digit으로 정의할 수 있고, number는 이런 digit의 단일 개체나 Number가 Recursive된 형태로 표현할 수 있다는 것이다. 두번째 구문처럼 표현하면 우리는 어떤 자리의 숫자가 나와도 그게 compiler 상에서 number라는 nonterminal 로 인식되게끔 할 수 있다. 그런데 여기서 의문을 가지는 사람이 있을 것이다. 만약 위와 같이 number를 정의하게 된다면 음수는 어떻게 정의할 것인가에 대해서 말이다. 사실 이건 ALGOL이라는 연산시에 사용하는 프로그래밍언어에 효율적으로 사용할 수 있던 notation이었지, 조금 더 functional한 프로그래밍 언어에서는 BNF로 notation을 표현하기가 쉽지 않았다. 위와 같이 음수를 인지하기 위한 조건도 notation에 들어가 있어야 했는데 이걸 BNF로 표현한다는게 어려웠다. 또한 정형화된 symbol인 ::= 이나 <> | 같은게 terminal로 정의되어 있지 않아서 구문내에서 분해하기가 어려운 점도 있었다. 그래서 Niklaus Wirth 라는 사람이 조금더 확장된 BNF를 정의했고, 이걸 표준화하면서 Extended Backus Naur Form(EBNF) 이라는 이름으로 소개되었다. 여기서부터는 우리가 흔히 알고 있는 프로그래밍 문법과 매우 유사하게 변했다. Table은 다음과 같다.

그럼 앞에서 BNF로 표현했던 Number form을 EBNF로 바꾸면 어떻게 표현할 수 있을까? 이젠 음수도 option이라는 symbol을 사용해서 표현할 수 있게 된다.

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

number = ["-"] digit { digit } ;

이런식으로 표현하면 되겠다. 똑같이 해석하자면 digit은 0부터 9 라는 terminal string의 alternation으로 구성되어 있고, number는 option에 따라서 - 부호를 집어넣을 수도 있고, 아무튼 digit의 concatenation으로 표현할 수 있다. 여기에 추가적으로 숫자는 special Sequence에 속하므로 다시 이렇게 표현할수 있다.

digit = "0" ... "9"

이런식으로 표현하면 실제 언어에서는 다음과 같이 구현해볼 수 있다.

letter = "A" | "B" | "C" | "D" | "E" | "F" | "G"
       | "H" | "I" | "J" | "K" | "L" | "M" | "N"
       | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
       | "V" | "W" | "X" | "Y" | "Z" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
symbol = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
       | "'" | '"' | "=" | "|" | "." | "," | ";" ;
character = letter | digit | symbol | " " ;

identifier = letter , { letter | digit | " " } ;
terminal = "'" , character , { character } , "'" 
         | '"' , character , { character } , '"' ;

lhs = identifier ;
rhs = identifier
     | terminal
     | "[" , rhs , "]"
     | "{" , rhs , "}"
     | "(" , rhs , ")"
     | rhs , "|" , rhs
     | rhs , "," , rhs ;

rule = lhs , "=" , rhs , ";" ;
grammar = { rule } ;

여기서 더 나가자면 letter는 저런 대문자도 있고 소문자도 포함할 수 있기 때문에 아래와 같이 추가적으로 정의해줄 수 있다.

letter = "A" ... "Z" | "a" ... "z" ;

결구 우리가 이런 과정을 거치는 것은 compiler의 specification을 정해주기 위함이다. 즉 Token이 나왔을 때, 그 token이 terminal인지 nonterminal을 가리는 것부터 letter인지 digit 인지를 가려주는 가장 기본적인 grammar인 것이다. 이렇게 문법을 정의한 후에 어떻게 써먹느냐가 관건인데 가장 쉬운 방법은 이런 문법을 프로그래밍 언어로 바꿔주는 툴을 사용하는 것이다. 보통 그런 걸 Compiler-Compiler (CC)라고 하는데 일반적으로는 Yacc나 Bison같은게 있다. 이렇게 정의된 문법을 해당 툴에 넣어주면 C코드로 된 parser로 바뀐다. 사실 지금 컴파일러 수업은 컴파일러의 구조를 이해하는 단계이기 때문에 저런 자동화툴을 쓰는 것을 다루지 않는다. 교수님이 해당 문법을 정의해서 이미 같은 역할을 하는 것을 만들어 놨다는데 참... 갈수록 복잡해지는 거 같다. 아무튼 이번 포스트는 여기까지..

Reference

- Wikipedia : Backus-Naur Form  - http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form

- Wikipedia : Extended Backus-Naur Form - http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form