EBNF

1. 개요

EBNF(Extended Backus–Naur Form)는 형식 언어의 구문을 표현하는 데 사용되는 코드이다. 터미널 기호와 비터미널 기호, 그리고 이들이 유효한 시퀀스로 결합될 수 있는 방식을 규제하는 생성 규칙으로 구성된다. EBNF는 선택 사항을 나타내는 대괄호 [ ... ], 반복을 나타내는 중괄호 { ... } 등의 기호를 사용하여 BNF(Backus–Naur Form)보다 간결하게 문법을 표현할 수 있다. EBNF는 ISO/IEC 14977:1996(E)로 표준화되었으며, W3C에서 XML 문법 기술에 사용되기도 한다.

2. 기본

EBNF는 형식 언어의 구문을 표현하는 코드이다. EBNF는 터미널 기호와 비터미널 생성 규칙으로 구성된다.

생략하거나 반복할 수 있는 표현식은 중괄호({...})를 통해 나타낼 수 있다. 예를 들어, 'positive integer = digit excluding zero, { digit } ;'에서 문자열 1, 2, ..., 10, ..., 10000, ... 은 모두 올바른 표현식이다. 중괄호 안의 내용은 포함되지 않거나 여러 번 반복될 수 있다.

옵션은 대괄호([...])를 통해 나타낼 수 있다. 대괄호 안의 내용은 한 번만 존재하거나 전혀 존재하지 않을 수 있다. 예를 들어, 'integer = "0" | [ "-" ], positive integer ;'에서 정수는 0(0) 또는 선택적으로 마이너스 기호가 앞에 오는 양의 정수가 될 수 있다.

EBNF는 이 외에도 반복 횟수를 지정하는 구문, 생성 규칙의 일부를 제외하는 구문, EBNF 문법에 주석을 삽입하는 구문 등을 제공한다.

2.1. 터미널 기호와 비터미널 기호

EBNF는 터미널 기호와 터미널 기호가 유효한 시퀀스로 결합될 수 있는 방식을 규제하는 제약 조건인 비터미널 생성 규칙으로 구성된다. 터미널 기호의 예로는 영숫자, 구두점, 공백 문자 등이 있다.

EBNF에서 터미널 기호(terminal symbol)는 더 이상 분해할 수 없는 기본 단위를 말하며, 따옴표("...")나 아포스트로피('...')로 묶어서 표현한다. 프로그램의 소스 코드는 터미널 기호로 구성되며, 구체적인 문자, 숫자, 기호 등이 터미널 기호에 해당한다.

비터미널 기호(non-terminal symbol)는 터미널 기호 또는 다른 비터미널 기호의 조합으로 구성되는 문법적 단위를 나타낸다. 비터미널 기호는 일반적으로 따옴표 없이 표현하지만, 필요에 따라 꺾쇠 괄호(<...>)로 묶을 수도 있다.

EBNF는 비터미널 기호에 대응하는 기호열을 지시하는 생성 규칙으로 정의된다.

```ebnf
digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit = "0" | digit excluding zero ;
```

위 생성 규칙에서는 비터미널 기호 "digit"이 좌변에 정의되어 있다. 수직 막대는 그 앞뒤에 있는 터미널 기호나 비터미널 기호 중 하나를 선택함을 나타낸다. 또한 터미널 기호는 터미널 문자를 따옴표로 묶어 표현한다. 따라서 "digit"은 '0' 또는 'digit excluding zero' 중 하나이며, 후자는 '1' 또는 '2', 또는 '9'까지의 숫자 중 하나가 된다.

2.2. 생성 규칙

생성 규칙은 비터미널 기호가 어떻게 터미널 기호와 다른 비터미널 기호의 조합으로 구성될 수 있는지를 정의한다. EBNF 생성 규칙은 다음과 같은 요소들을 포함할 수 있다.

* 선택: 수직 막대(|)는 여러 대안 중 하나를 선택할 수 있음을 나타낸다. 예를 들어, `digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;`에서 `digit`은 "0"부터 "9"까지의 숫자 중 하나가 될 수 있다.
* 연결: 쉼표(,)는 여러 터미널 또는 비터미널 기호를 순서대로 나열한다. 예를 들어, `twelve = "1", "2" ;`는 "1"과 "2"가 순서대로 나타나 "12"를 구성함을 의미한다.
* 반복: 중괄호({})는 0번 이상 반복될 수 있음을 나타낸다. 예를 들어, `positive integer = digit excluding zero, { digit } ;`에서 `positive integer`는 `digit excluding zero` 뒤에 `digit`이 0번 이상 반복되는 형태이다. 즉, "1", "10", "123" 등이 모두 가능하다.
* 선택 사항: 대괄호([])는 0번 또는 1번 나타날 수 있음을 나타낸다. 예를 들어, `integer = "0" | [ "-" ], positive integer ;`에서 `integer`는 "0"이거나, 선택적으로 마이너스 기호가 붙은 `positive integer`가 될 수 있다.

EBNF는 이 외에도 반복 횟수를 지정하거나, 특정 생성 규칙을 제외하거나, 주석을 삽입하는 등의 기능을 제공한다.

3. BNF와의 비교

EBNF는 BNF를 확장한 형태로, BNF보다 간결하고 가독성이 높다. BNF에서는 선택 사항이나 반복을 표현하기 위해 중간 규칙을 도입하거나 재귀적인 규칙을 사용해야 했지만, EBNF에서는 `[ ]`, `{ }` 등의 기호를 사용하여 직접 표현할 수 있다.

BNF는 자체적으로 `<`, `>`, `|`, `::=` 기호를 사용하고 터미널 문자열 주위에 따옴표를 포함하지 않아, 해당 기호들을 언어에서 사용할 수 없었고 빈 문자열을 위한 특수 기호가 필요했다. 반면 EBNF에서 터미널은 따옴표("..."")나 아포스트로피('...')로 묶이고, 비터미널에 대한 꺾쇠 괄호(<...>)는 생략할 수 있다.

BNF 구문은 한 줄로만 규칙을 나타낼 수 있지만, EBNF에서는 종료 문자(;)를 사용하여 규칙의 끝을 표시한다.

BNF의 문제점과 EBNF의 해결책은 다음과 같다.

* BNF는 `<`, `>`, `|`, `::=` 기호를 사용하므로, 정의 대상 언어에 이러한 기호가 사용되는 경우 다른 것으로 바꿔 표현해야 했다. EBNF에서는 터미널 기호를 반드시 인용 부호("..." 또는 '...')로 둘러싸고, 비터미널 기호를 감싸던 꺾쇠 괄호(<...>)를 생략하여 이 문제를 해결했다.
* BNF는 하나의 규칙을 한 줄로 표현해야 했다. EBNF에서는 규칙 마지막에 세미콜론(;)을 붙여 규칙의 범위를 명확히 했다.

4. 확장

ISO 14977 표준 EBNF는 확장을 위한 두 가지 기능을 제공한다.

* 특수 시퀀스: EBNF 문법의 일부로, 물음표로 묶인 임의의 텍스트는 EBNF 표준의 해석 범위를 벗어난다. 예를 들어, 공백 문자는 다음과 같이 정의할 수 있다.

```ebnf
space = ? ASCII character 32 ?;
```

* 괄호 표기: EBNF에서 괄호는 식별자 바로 옆에 올 수 없다는 점을 이용한다. 예를 들어, 다음은 유효하지 않은 EBNF이다.

```ebnf
something = foo ( bar );
```

이러한 표기법을 활용하여 EBNF를 확장할 수 있다. 예를 들어, 리스프 문법에서 함수 적용은 다음 규칙으로 정의할 수 있다.

```ebnf
function application = list( symbol, { expression } );

5. 관례

ISO/IEC 14977 표준에 따른 관례는 다음과 같다.

* 확장 EBNF의 각 메타 식별자는 하나 이상의 단어가 하이픈으로 연결되어 작성된다. 단어 연결은 메타 언어 자체 외부의 메타 식별자를 참조하는 데에만 적용되는 것으로 보인다.
* '-symbol'로 끝나는 메타 식별자는 확장 EBNF의 터미널 기호의 이름이다.

확장 EBNF의 각 연산자와 암시된 우선 순위는 다음과 같다 (가장 높은 우선 순위가 맨 위에 있음):

* 반복 기호
- 제외 기호
, 연결 기호
| 정의 구분 기호
= 정의 기호
; 종료 기호
. 종료 기호

일반적인 우선 순위는 다음 괄호 쌍으로 재정의된다:

(* 시작 주석 기호 종료 주석 기호 *)
' 첫 번째 따옴표 기호 첫 번째 따옴표 기호 '
( 시작 그룹 기호 종료 그룹 기호 )
[ 시작 옵션 기호 종료 옵션 기호 ]
{ 시작 반복 기호 종료 반복 기호 }
? 특수 시퀀스 기호 특수 시퀀스 기호 ?
" 두 번째 따옴표 기호 두 번째 따옴표 기호 "

첫 번째 따옴표 기호는 ISO/IEC 646:1991에 정의된 아포스트로피로, 유니코드 U+0027(`'`)이다. ISO/IEC 14977:1996(E)에서 사용된 글꼴은 이를 급성 부호인 유니코드 U+00B4(`´`)와 매우 유사하게 렌더링하므로 혼동이 발생할 수 있지만, ISO 확장 EBNF 표준은 "정보 교환을 위한 ISO 7비트 코드 문자 집합"인 ISO/IEC 646:1991을 규범적 참조로 호출하며 다른 문자 집합에 대해서는 언급하지 않으므로 공식적으로 7비트 ASCII 범위를 벗어난 유니코드 문자와의 혼동은 없다.

다음은 반복을 표현하는 몇 가지 예시이다.

aa = "A";
bb = 3 * aa, "B";
cc = 3 * [aa], "C";
dd = {aa}, "D";
ee = aa, {aa}, "E";
ff = 3 * aa, 3 * [aa], "F";
gg = {3 * aa}, "G";
hh = (aa | bb | cc), "H";

위 규칙에 의해 정의되는 터미널 문자열은 다음과 같다:

aa: A
bb: AAAB
cc: C AC AAC AAAC
dd: D AD AAD AAAD AAAAD 등.
ee: AE AAE AAAE AAAAE AAAAAE 등.
ff: AAAF AAAAF AAAAAF AAAAAAF
gg: G AAAG AAAAAAG 등.
hh: AH AAABH CH ACH AACH AAACH

6. 관련 표준

* W3C는 XML 구문을 지정하기 위해 [http://www.w3.org/TR/REC-xml/#sec-notation 자체적인 EBNF 표기법]을 사용한다.
* 영국 표준 협회(British Standards Institution)는 1981년에 EBNF 표준인 BS 6154를 발행했다.
* IETF는 RFC 5234에서 ABNF를 정의하고 있으며, 인터넷 표준 문서에서 널리 사용된다.

7. 예시

EBNF는 다양한 표기법을 사용하여 문법을 표현한다. 다음은 EBNF에서 사용하는 표준적인 표기법이다.

다음은 EBNF 생성 규칙의 예시이다.

```ebnf
digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit = "0" | digit excluding zero ;
```

위 규칙에서 "digit"은 비터미널 기호이며, 수직 막대(|)는 선택을 나타낸다. 터미널 기호는 따옴표로 묶어 표현한다. 따라서 "digit"은 '0' 또는 'digit excluding zero' 중 하나이며, 'digit excluding zero'는 '1'부터 '9'까지의 숫자 중 하나가 된다.

생략 가능하며 반복 가능한 부분은 중괄호({…})로 표시한다. 예를 들어, 'natural number' 규칙은 다음과 같이 정의할 수 있다.

```ebnf
natural number = digit excluding zero , { digit } ;
```

위 규칙에서 자연수(natural number)는 '1', '2', '10', '12345' 등과 같이 표현될 수 있다. 중괄호 안의 내용은 0회 이상 반복될 수 있다.

생략 가능한 부분은 대괄호([…])로 표시한다. 예를 들어 'integer' 규칙은 다음과 같이 정의할 수 있다.

```ebnf
integer = "0" | [ "-" ] , natural number ;
```

위 규칙에서 정수(integer)는 '0'이거나, 선택적으로 마이너스 부호(-)를 붙인 자연수가 될 수 있다.

7.1. 파스칼(Pascal) 언어

파스칼과 유사하게, 할당만 허용하는 프로그래밍 언어는 다음과 같이 EBNF로 정의할 수 있다.

```ebnf
(* EBNF로 표현한 간단한 프로그램 구문 - 위키백과 *)
program = 'PROGRAM', white space, identifier, white space,
'BEGIN', white space,
{ assignment, ";", white space },
'END.' ;
identifier = alphabetic character, { alphabetic character | digit } ;
number = [ "-" ], digit, { digit } ;
string = '"' , { all characters - '"' }, '"' ;
assignment = identifier , ":=" , ( number | identifier | string ) ;
alphabetic character = "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" ;
white space = ? white space characters ? ;
all characters = ? all visible characters ? ;
```

예를 들어, 구문상 올바른 프로그램은 다음과 같다.

```pascal
PROGRAM DEMO1
BEGIN
A:=3;
B:=45;
H:=-100023;
C:=A;
D123:=B34A;
BABOON:=GIRAFFE;
TEXT:="Hello world!";
END.
```

이 언어는 제어 흐름, 산술 표현식 및 입/출력 지침으로 쉽게 확장할 수 있다. 그러면 작고 실용적인 프로그래밍 언어를 개발할 수 있다.

7.2. EBNF 자체 정의

EBNF는 자기 자신을 사용하여 정의할 수도 있다. 다음은 EBNF를 사용하여 EBNF 자체를 정의한 예시이다(집합 분리를 나타내는 "-" 기호, 하나 이상의 일치를 나타내는 "+" 기호, 선택적 요소를 나타내는 "?" 기호와 같은 규칙 사용).

```
문자 = "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" | "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" ;

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

기호 = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
| "'" | '"' | "=" | "|" | "." | "," | ";" | "-"
| "+" | "*" | "?" | "\n" | "\t" | "\r" | "\f" | "\b" ;

문자 = 문자 | 숫자 | 기호 | "_" | " " ;
식별자 = 문자 , { 문자 | 숫자 | "_" } ;

S = { " " | "\n" | "\t" | "\r" | "\f" | "\b" } ;

터미널 = "'" , 문자 - "'" , { 문자 - "'" } , "'"
| '"' , 문자 - '"' , { 문자 - '"' } , '"' ;

종결자 = ";" | "." ;

항 = "(" , S , 우변 , S , ")"
| "[" , S , 우변 , S , "]"
| "{" , S , 우변 , S , "}"
| 터미널
| 식별자 ;

요소 = 항 , S , "?"
| 항 , S , "*"
| 항 , S , "+"
| 항 , S , "-" , S , 항
| 항 , S ;

결합 = ( S , 요소 , S , "," ? ) + ;
교대 = ( S , 결합 , S , "|" ? ) + ;

우변 = 교대 ;
좌변 = 식별자 ;

규칙 = 좌변 , S , "=" , S , 우변 , S , 종결자 ;

문법 = ( S , 규칙 , S ) * ;