EBNF(Extended BNF)와 구문 도표

0. EBNF (Extended BNF)

• EBNF는 BNF의 확장팩 정도로 생각할 수 있는데 몇몇 비효율적인 연산을 개선하기 위해서
• 반복 { } , 옵션 [ ] , 다중 선택 ( ) 기능이 추가되었다. 각각의 기능과 얼마나 편해지는지 알아보자.
• 또한 이들 EBNF를 도식적으로 기술하는 구문도표 (syntex diagram)에 대해 알아본다.

 

1. 반복 : { }

• BNF를 써봐서 알겠지만, 당장에 number에서 digit으로 갈때만 해도 수많은 반복과정이 들어간다.
• 이런 반복과정을 표현할때 기존에는 ' | ' 를 이용해서 규칙을 표기하였으나, 그렇게 직관적이지는 않다.

// Backers - Naur Form
<number> → <number><digit> | <digit>
<digit> → 0 | 1 | 2 | 3 | 4 | 5| 6| 7| 8| 9

// Derivation "123"
<number> → <number><digit>
         → <number><digit><digit>    // <--- <number>를 <number><digit>으로 변환
         → <digit><digit><digit>     // <--- <number>를 <digit>으로 변환
         → 1<digit><digit>           // <--- <digit>을 1로 변환
         → 12<digit>                 // <--- <digit>을 2로 변환
         → 123

 

• 때문에 직관적으로 아예 digit이 매우 여러번 반복될 수 있다는 의미로 digit{digit}과 같이 표현한다.
• 바깥쪽 digit은 선택 한개의 digit으로 선택할 수 있고, { }안의 digit은 0개에서 n가까지 선택할 수 있다.
• 굳이 <number><digit>으로 바꾸지 않고 바로 n개의 <digit>으로 변환하여 전보다 훨씬 간편하다.

// Backers - Naur Form
<number> → <digit> {<digit>}         // <--- 중괄호 안의 기호 0~n번 반복 가능
<digit> → 0 | 1 | 2 | 3 | 4 | 5| 6| 7| 8| 9

// Derivation "123"
<number> → <digit><digit><digit>     // <--- <number>를 <digit> * n개로 바로 변환
         → 1<digit><digit>           // <--- <digit>을 1로 변환
         → 12<digit>                 // <--- <digit>을 2로 변환
         → 123

 

2. 옵션 : [ ]

• 기존에 if문과 같은 조건문을 BNF로 구현할 때는 다음과 같이 해야만 했다.
• if 이후에 else가 올 수 있고 없고는 선택이다. 때문에, 이를 논리연산으로 잇는 것이 아니라,
• 옵셔널하게 선택할 수 있는 부분들은 [ ]로 묶어버리자는 것이다.
• 아래를 보면 기존의 중복성이 강한 BNF보다 EBNF가 중복도 적고 깔끔해진 것 알 수 있다.

// BNF
<if> → if(<expr>) <state>
     | if(<expr>) <state> else <state>
     
// EBNF
<if> → if(<expr>) <state> [else <state>]     // <--- option

 

3. 다중 선택 : ( )

• BNF를 쓰다보면 다양한 선택이 가능 한 경우에 모든 부분을 중복해서 쓰고 ' | '로 이어서 연결했는데
• 이는 매우 난잡하고 비효율적인 구성이다. 괄호문자를 사용하면 괄호 안에 있는 모든 사항을 선택할 수 있다.

// BNF
<term> → <term> + <term>
       | <term> - <term>
       | <term> * <term>
       | <term> / <term>
 
 
 // EBNF
 <term> → <term> (+ | - | * | /) <term>

 

4. 구문도표 (Syntex Diagram)

[그림] 구문도표

• 구문도표는 위처럼 그림으로 그리는 방식을 말한다.
• 1) loop를 나타내는 { }는 회전하는 모양으로 그려서 원하는 만큼 반복할 수 있도록 그린다.
• 2) option을 나타내는 [ ]는 옵셔널한 길을 하나 더 그려서 지나치던지, 거쳐갈 수 있게 그린다.
• 3) 선택을 의미하는 | 나 ( | )는 위처럼 여러 길 중 한 곳을 선택하게 그린다.
• 구문도표는 보기에는 좋지만 공간을 많이 차지하고 복잡해서 BNF나 EBNF를 보통 많이 사용한다.