| 프로그래밍 언어 문법 | ||
| {{{#!wiki style="margin: -16px -11px; word-break: keep-all" | <colbgcolor=#0095c7><colcolor=#fff,#000> 언어 문법 | C(포인터) · C++(자료형 · 특성 · 클래스 · 이름공간 · 상수 표현식) · C# · Java · Python · Kotlin · MATLAB · SQL · PHP · JavaScript |
| 마크업 문법 | HTML · CSS | |
| 개념과 용어 | 함수 · 인라인 함수 · 고차 함수 · 람다식 · 리터럴 · size_t · 상속 · 예외 · 조건문 · 참조에 의한 호출 · eval | |
| 기타 | == · === · NaN · null · undefined · 모나드 · 배커스-나우르 표기법 | |
| 프로그래밍 언어 예제 · 목록 · 분류 | }}} | |
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> | ""
최소 한번 또는 그 이상 반복되는 경우 다음과 같이 나타낼 수 있다.
<A> ::= <A> <B> | <B>
<A> ::= <A> <B> | <B> <B> <B>
만약 유한한 크기의 최대 반복횟수가 정의되어 있다면,
<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
Extended Backus-Naur Form, EBNFBNF의 문법적 단점들을 개선하기 위해 등장한 문법으로, 추가적으로 다음의 문법을 가지고 있다.
반복. 중괄호 사이의 내용을 0번 이상 반복한다.
{ <A> }
생략. 대괄호 사이의 내용을 0번 또는 1번 반복한다.
[ <A> ]
그룹. 원하는 부분을 괄호로 묶어 반복 등을 정의할 수 있다.
(<A> <B>) <C>