최근 수정 시각 : 2024-11-15 15:43:58

배커스-나우르 표기법


프로그래밍 언어 문법
{{{#!wiki style="margin: -16px -11px; word-break: keep-all" <colbgcolor=#0095c7><colcolor=#fff,#000> 언어 문법 C( 포인터 · 구조체 · size_t) · C++( 자료형 · 클래스 · 이름공간 · 상수 표현식 · 특성) · C# · Java · Python( 함수 · 모듈) · Kotlin · MATLAB · SQL · PHP · JavaScript · Haskell( 모나드)
마크업 문법 HTML · CSS
개념과 용어 함수( 인라인 함수 · 고차 함수 · 람다식) · 리터럴 · 상속 · 예외 · 조건문 · 참조에 의한 호출 · eval
기타 == · === · deprecated · NaN · null · undefined · 배커스-나우르 표기법
프로그래밍 언어 예제 · 목록 · 분류 }}}

1. 개요2. 역사3. 구조
3.1. 트릭
4. 예시5. 단점6. EBNF7. 외부 링크8. 관련 문서

1. 개요

Backus-Naur Form, BNF

임의의 문맥 자유 언어를 기술하기 위해 사용하는 메타 문법(metasyntax)이다. 주로 프로그래밍 언어, 데이터 직렬화 형식 등 기계가 읽을 수 있는(machine-readable) 형식의 문법을 명확히 정의 또는 표준화하기 위해 사용된다.

2. 역사

1959년 IBM의 언어 디자이너 존 배커스(John Backus)가 새 언어 IAL(현 ALGOL 58)의 문법을 정의하기 위해 고안했고, ALGOL 60의 문법을 정의하는 데 처음으로 사용되었다.

이후 알골60의 개발자 중 한 명인 피터 나우르(Peter Naur)가 해당 표기법을 재정의하며 Backus normal form이라고 명명했고, 이후 촘스키 기본형(normal form)과 관련이 없다는 도널드 커누스의 지적에 의해 Backus Naur form으로 불리게 되었다. 해당 재정의 과정에서 치환 정의 기호인 :≡가 더 쓰기 쉬운 ::=로, [math(\rm\bar{or})] 등이 | 등으로 바뀌었다.

3. 구조

BNF 문법은 아래와 같은 유도 규칙들로 이루어지며, 이는 형식 문법의 생성 규칙에 대응한다.

주석은 ;을 사용한다.
; 주석

::=는 <논터미널 기호>가 '대체될 문자열'로 치환됨을 의미한다. 이때, <>로 감싸진 기호는 논터미널 기호를 의미하며, 대체되는 문자열 사이에도 논터미널 기호가 들어갈 수 있다.
<논터미널 기호> ::= 대체될 문자열

문자열은 ""또는 ''로 감싸지며, 두 개의 연속한 문자열 또는 논터미널 기호는 하나의 문자열로 인식된다.
<A> ::= "abc" "def"
<B> ::= "abcdef" ; A = B

만약 하나의 논터미널 기호에 대해 여러 유도 규칙이 존재하면, |를 통해 하나로 묶을 수 있다.
<A> ::= "abc"
<A> ::= "def"
; 다음과 같이 축약 가능
<A> ::= "abc" | "def"

3.1. 트릭

BNF는 극히 제한적인 문법을 가지고 있기 때문에, 반복, 생략 등을 나타내는 고유의 문법이 없다.

생략 가능(optional)한 문법은 다음과 같이 나타낸다.
<A> ::= <B> | ""
이때, ""는 생성 규칙에서의 공문자열 [math(\epsilon)]이다.

0또는 그 이상의 반복이 들어가는 경우 다음과 같이 나타낸다.
<A> ::= <A> <B> | ""
이는 좌선형(left-linear) 정규 언어의 문법과 비슷하게 재귀적으로 자신을 정의하지만, 생성 규칙에서 하나 이상의 논터미널 기호가 온다는 차이점이 있다.

최소 한번 또는 그 이상 반복되는 경우 다음과 같이 나타낼 수 있다.
<A> ::= <A> <B> | <B>
이를 기반으로 우측에 최소 반복횟수를 나타낼 수 있다. 예를 들어 최소 3번 이상 반복이라면 아래와 같이 한다.
<A> ::= <A> <B> | <B> <B> <B>

만약 유한한 크기의 최대 반복횟수가 정의되어 있다면, 노가다를 통해 가능한 모든 경우의 수를 적을 수 있다. 최소 2개에서 최대 5개라면 다음과 같이 한다.
<A> ::= <B> <B> | <B> <B> <B> | <B> <B> <B> <B> | <B> <B> <B> <B> <B>

4. 예시

  • 아래 예시들에서는 편의를 위해 다음을 미리 정의한다.
    {{{<digit1> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<digit> ::= "0" | <digit1>
<upper> ::= "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"
<lower> ::= "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"
<alpha> ::= <upper> | <lower>
<alphanumeric> ::= <alpha> | <digit>
<word> = <word> <alphanumeric> | ""
}}}
  • BNF 또한 그 자체로 다른 문법을 기술하는 메타문법(metasyntax)이기에 스스로의 문법을 정의하는 문법을 작성할 수도 있다.
    {{{<bnf> ::= <bnf> <rule> | <rule>
<rule> ::= <ws> <nt> <ws> "::=" <ws> <alt> <ws> <eol>
<ws> ::= <ws> " " | ""
<eol> ::= <eol> <ws> <lf> | <lf>
<nt> ::= "<" <nt-name> ">"
<nt-char> ::= <alphanumeric> | "-"
<nt-name> ::= <nt-name> <nt-char> | <alpha>
<alt> ::= <alt> "|" <expr> | <expr>
<expr> ::= <term>
<term> ::= <string> | <nt>
<string> ::= '"' <text-sq> '"' | "'" <text-dq> "'"
<char> ::= <alphanumeric> | "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~"
<char-sq> ::= <char> | "'"
<char-dq> ::= <char> | '"'
<text-sq> ::= <text-sq> <char-sq> | ""
<text-dq> ::= <text-dq> <char-dq> | ""
}}}
  • IPv4
    {{{<ipv4> ::= dec-octet "." dec-octet "." dec-octet "." dec-octet
<zero-to-four> ::= "0" | "1" | "2" | "3" | "4"
<dec-octet> ::= <digit> | <digit1> <digit> | "1" <digit> <digit> | "2" <zero-to-four> <digit> | "25" <zero-to-four> | "255"
}}}
  • URL
    {{{<scheme> ::= <word>
<url> ::= <scheme> "://" <domain> <path> | <scheme> "://" <domain> <path> <query>
<domain> = <domain> "." <word> | <word>
<query> ::= "?" <querystring-comp>
<querystring-comp> ::= <querystring-comp> "&" <querystring-param> | <querystring-param>
<querystring-param> ::= <word> "=" <word>
<path> ::= <path> <word> "/" | "/"
}}}

5. 단점

BNF는 가장 최소한의 요소만을 가지고 존재하는 모든 문맥 자유 언어를 표현할 수 있다는 장점이 있지만 사실 그건 이론상 이야기이고 실제로 실용적인 프로그래밍 언어의 문법을 BNF로 작성하는 것은 굉장한 노력을 필요로 한다.

BNF로 문법을 작성하면 대부분의 내용이 알파벳 등의 흔한 범위 나열, 숫자 범위 지정, 토큰 처리, 문자열의 세세한 부분 처리, 반복 처리, 공백 처리 등 자잘한 부분에 낭비된다. 렉서를 돌리고 토큰 단위로 BNF를 작성하면 ABCDE 나열 등의 수고로움을 덜 수 있기는 하지만 여전히 개발자에게 친숙하지 않은 것은 마찬가지이다. 특히 반복 문법이 없기 때문에 일일이 문법을 나열하다 보면 실수도 생기기 쉽고 무엇보다 표준의 가독성을 심하게 떨어트린다.

6. EBNF

EBNF(Extended Backus-Naur Form)는 BNF의 문법적 단점들을 개선하기 위해 등장한 문법으로, 추가적으로 다음의 문법을 가지고 있다.
  • 반복. 중괄호 사이의 내용을 0번 이상 반복한다.
    {{{{ <A> }
}}}
  • 생략. 대괄호 사이의 내용을 0번 또는 1번 반복한다.
    {{{[ <A> ]
}}}
  • 그룹. 원하는 부분을 괄호로 묶어 반복 등을 정의할 수 있다.
    {{{(<A> <B>) <C>
}}}

7. 외부 링크

8. 관련 문서

분류