배커스-나우르 표기법(Backus–Naur form), 약칭 BNF는 문맥 자유 문법을 나타내기 위해 만들어진 표기법이다. 존 배커스와 페테르 나우르의 이름을 따서 부른다.
BNF는 기본적으로 다음의 문법을 사용한다.
<기호> ::= <표현식>
- 기호는 말단 기호가 될 수 없다.
- 표현식은 다른 기호의 조합, 또는 여러 가지의 표현식 중 하나를 사용한다는 의미로 |를 사용한다.
- 다른 표현식으로 정의되지 않은 기호는 자동적으로 말단 기호가 된다.
- 기호가 아닌 상수에는 따옴표를 붙여서 구별한다.
::=는 왼쪽의 기호가 오른쪽의 기호로 치환됨을 의미한다.
예시
예를 들어, 간단한 Arithmetic expression을 BNF 표기법으로 나타내면 다음과 같다.
expr :: = "(" expr "+" expr ")" // addition
| "(" expr "-" expr ")" // subtraction
| num // number
num :: = "1" | "2" | ... | "42" ... // number
여기서 expr이라는 variable은 집합 즉, addtion, subtraction 그리고 number로 구성된 연산자 정의의 집합으로 구성된다.
- expr은 다음 세개의 조합으로 구성된다.
- 1. expr + expr
- 2. expr - expr
- 3. expr은 <num>
- <num>은 정수중의 하나이다.
이를 Scala로 변환하면 다음과 같다.
trait Expr
case class Num(num: Int) extends Expr
case class Add(left: Expr, right: Expr) extends Expr
case class Sub(left: Expr, right: Expr) extends Expr