BNF (Backus–Naur form)

BNF는 언어의 syntax를 나타내는 개념이다.

백문이 불여일견이니 바로 보도록 하겠다.

Grammar in BNF

<expr\> → Non-terminal: Meta-variable

::= Can be written as

| One more choice

<…> literal syntax

Terminal

예시를 들어보자면

<digit\> ::= 0 | <non zero digit>

<non zero digit\> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

이런 식으로 숫자들을 BNF상에 정의를 하면 이제 해당 언어는 digit을 사용할 수 있는 것이다.

여기서 보다시피 0, 1,2,3,4,5,..9등은 더 이상 다른 terminal로 나눠지지 않는다. 그걸 Terminal이라고 하고 terminal보다 상위 layer에 있다면 무조건 non-terminal이다.

어찌됐든 결론적으로 BNF, parser, AST, and interpreter는 밀접한 관계를 가진다. BNF가 먼저 정의되면 parser는 BNF를 통해 AST에 대한 소스코드를 생성한다. AST는 interpreter에 의해 처리된다. interpreter는 AST를 훑으면서 정의된대로 프로그램을 차례대로 실행한다.