BNF

Last updated - 2023년 03월 10일 Edit Source

프로그래밍 언어론

BNF(Backus-Naur Form)는 프로그래밍 언어 Algol(알골)의 구문을 정의하기 위해 배커스와 나우어가 사용한 표현법이다. 구문(syntax) 형식을 정의하는 가장 보편적인 표기법이다.

메타기호	의미
`::==`	정의
`\|`	택일(OR)
`< >`	비단말(nonterminal)

BNF에서 규칙은 메타 기호(::==)를 이용하여 표현한다.

생성 규칙
- 생성 규칙의 왼쪽 : 정의될 대상
- 생성 규칙의 오른쪽 : 그 대상에 대한 정의

메타 기호의 왼쪽에는 하나의 비단말 기호가, 오른쪽에는 기호들을 활용하여 정의하는 내용이 나오는 것이다. 참고로, 꺽쇠가 없는 것은 단말(terminal)이다.

기호	의미	예시
단말 기호	비단말 기호 및 메타기호가 아닌 기호	A, B, a, b, 0, 1, if, then, +, -, 등등
비단말 기호	메타 기호 `< >`로 묶인 기호	`<identifier>`, `<letter>`, `<digit>`, 등등

사용 예시

1
<if문> ::= if <논리식> then <문장> else <문장> | if <논리식> then <문장>

1
2
3
<identifier> ::= <letter> | <identifier><letter> | <identifier><digit>  
<letter> ::= A | B | C | ... | X | Y | Z | a | b | ... | z |  
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

한 표현이 BNF에 의해 작성될 수 있는지 여부를 나타내는 것이 파스 트리 (parse tree)이다. 참고로 BNF를 확장한 것은 EBNF이다.

Comment