배커스-나우르 표기법
배커스-나우르[주해 1] 표기법(Backus–Naur form), 약칭 BNF는 문맥 자유 문법을 나타내기 위해 만들어진 표기법이다. 존 배커스와 페테르 나우르의 이름을 따서 부른다.
BNF는 기본적으로 다음의 문법을 사용한다.
<기호> ::= <표현식>
여기에서 기호는 말단 기호가 될 수 없고, 표현식은 다른 기호의 조합, 또는 여러 가지의 표현식 중 하나를 사용한다는 의미로 |를 사용한다. 다른 표현식으로 정의되지 않은 기호는 자동적으로 말단 기호가 된다. 또한, 기호가 아닌 상수에는 따옴표를 붙여서 구별한다.
예를 들어, 16진수를 BNF 표기법으로 나타내면 다음과 같다.
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<letter> ::= "A" | "B" | "C" | "D" | "E" | "F"
<number> ::= <digit> | <letter>
<integer> ::= <number> | <number><integer>