개요

Backus-Naur form이고 Backus Normal Form이라고도 불리는 약칭 BNF는 문맥 무관 문법 을 나타내기 위해 만들어진 표기법이다. 존 배커스와 페테르 나우르의 이름을 따서 부른다.

표기법

BNF는 기본적으로 다음의 문법을 따른다.

<기호> ::= <표현식>

• 여기서 기호는 말단 기호 가 될 수 없고, 표현식은 다른 기호의 조합, 또는 여러 가지의 표현식 중 하나를 사용한다는 의미로 |을 사용한다.
• 다른 표현식을 정의되지 않은 기호는 자동적으로 말단 기호 가 된다.
• 기호가 아닌 상수에는 따옴표를 붙혀 구별한다.
• Symbol 요약
  1. ::= : 대입
  2. <> : Nontermial의 유한집합으로 언어에 대한 계층적 구조를 부여하는 역할
  3. | : Alternation으로 Or과 동일하다.

사용 예 - 미국의 우편체계

<postal-address> ::= <name-part><street-address><zip-part>
<name-part> ::= <personal-part><last-name><opt-suffix-part><EOL>
								| <personal-part><name-part>
<personal-part> ::=<first-name>|<initial> "."
<street-address> ::= <house-num><street-name><opt-apt-num><EOL>
<zip-part> ::= <town-name> "," <state-code><ZIP-code><EOL>
<opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | ""
<opt-apt-num> ::= <apt-num> | ""

• postal-address는 noterminal인 name-part, street-address, zip-part의 유한집합입니다.

사용 예 - 숫자

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<number> ::= <digit> | <number><digit>

• 숫자하나하나는 digit 으로 정의할 수 있다.
• number 는 이런 digit의 단일 개채일 수도 있고, Number가 Recursive된 형태로 표현할 수 있다. ⇒ 이렇게 표현하면 몇자리의 숫자가 나와도 compiler에서 number라는 nonterminal로 인식 가능하다.

terminal expression과 nonterminal expression

사용 예에서 <opt-suffix-part>과 같이 더 이상 진행되지 않는 표현을 'terminal expression'이라고 부릅니다. 버스의 종착역인 터미널과 비슷합니다.