[Compiler] EBNF_Extended Backus-Naur Form

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다.

 

출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler

 

저번 시간에 Context Free Grammar를 보았다. CFG는 Regular Expression으로 표현하기 힘든 문법들을 표현하기 위한 대체 방안으로 Syntax Tree를 그렸었다. 여기서 Left Recursive 문제가 발생하여 이를 위해 Left Factoring, 터미널을 오른쪽으로 배치해서 해결할 수 있다.

 

이제 아래 내용을 살펴보자.

 

 

위의 그림은 Notational Convention 이라고 한다. 이것이 정의되어 있어야 어떤 부분을 Terminal로 할지 또는 NonTerminal로 할지를 정할 수 있다. 위의 그림은 임의로 정한 Notation이고, 이외에도 Terminal과 

Nonterminal로 구분해야 될 내용들이 많다. 이에 따른 문법도 사용자가 지정해야 한다.

 

이에 대해 규격화한 방법을 Backus-Naur Form 이라한다. Backus-Naur Form이라 하는 BNF를 살펴보자.

 

BNF의 형식은 아래와 같다.

<Symbol>      : : =   __expression __

 

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

 

: : =    -> Definition

<>     -> NonTerminal

|        -> Alternation

 

이 3가지 Symbol을 통해 notation을 표현한다. 해석해보면 Symbol이라는 NonTerminal은 __expression__으로 정의할 수 있다. Wikipedia의 예제로 알아보자.

 

https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form

 

위키피디아 공식 문서이다. 미국 우편 체계를 BNF로 표현한 것이다.

1) postal-address라는 nonterminal은 <name-part>와 <street-address>, <zip-part> 가 concatenate되어 구성되어 있다. 실제로 컴파일러의 구문 분석시에는 아래의 예제를 적용할 수 있다.

 

<digit>       : :=    0 | 1 | 2 | 3 | 4 | 5 | 6 |7 | 8 | 9

<number>  : :=    <digit> | <number> <digit>

 

숫자 하나하나는 digit으로 정의하고 number는 이런 digit의 단일 개체나 number가 Recursive된 형태로 표현할 수 있다. 두 번째 구문처럼 표현하면 어떤 자리의 숫자가 나와도 그것이 컴파일러 상에서 number라는 Nonterminal 로 인식되게 할 수 있다. 

여기서 그렇다면 음수는 어떻게 정의할까 에 대한 물음이 나온다.

정형화된 Symbol인 ::= 나 <>, | 이 Terminal로 정의되어 있지 않아 구문내 분해가 힘들고 음수를 인지하기 위한 조건도 notation에 있어야 했는데 이것을 BNF로 표현하기가 어렵다. 

그래서 확장된 BNF라고 해서 EBNF라는 개념이 나온다 테이블은 아래와 같다.

https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form

 

 

이제 앞의 BNF로 표현했던 Number Form을 EBNF로 바꾸면 

 

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는 저런 대문자도 있고 소문자도 포함할 수 있기에 letter = "A" ... "Z" | "a" ... "z" 로 추가정의할 수 있다.

우리가 이런 과정을 거치는 것은 컴파일러의 specification을 정해주기 위함이다. 즉 토큰이 나왔을 때, 그 토큰이 terminal인지 nonterminal을 가리는 것부터 letter인지 digit인지를 구분하는 가장 기본적인 문법인 것이다. 이렇게 문법을 정의한 후에 '어떻게 사용하느냐' 인데 가장 쉬운 방법은 이런 문법을 프로그래밍 언어로 바꿔주는 툴을 사용하는 것이다.

보통 그런걸 Compiler-Compiler (CC)라고 하며 Yacc나 Bison 같은것이 있다. 이렇게 정의된 문법을 해당 툴에 넣어주면 C코드로 된 Parser로 바뀐다.