BNF (Backus-Naur Form)

BNF (Backus-Naur Form)

BNF (Backus-Naur Form)은 프로그래밍 언어의 문법 규칙을 표현하기 위한 메타언어입니다.
BNF는 규칙을 생성하기 위한 표기법으로 LHS(left-hand side)와 RHS(right-hand side)로 구성되어 있습니다.

LHS는 한 개의 논터미널(Non-terminal)로 구성된 문자열로 표현되며, BNF에서는 각괄호(<>)를 사용하여 표현합니다.

RHS는 터미널(Terminal)과 논터미널로 구성된 문자열로 표현되며, BNF에서는 각괄호를 사용하지 않고 표현합니다.

즉, 위 예시에서 '<id_list>'와 '<if_stmt>'가 LHS에 해당하며, ‘|’, ‘,’ 등으로 구분된 'id’와 ‘<id_list>’, 그리고 '<logic_expr>'와 '<stmt>'가 RHS에 해당합니다.

BNF 문법은 문법 전체를 형식적으로 정의하기 위해 다음과 같은 네 가지 구성 요소를 가집니다.

• N: 논터미널들의 집합 (a set of nonterminals)
• T: 터미널들의 집합 (a set of terminals)
• S ∈ N: 시작 기호 (start symbol)
• P: 생성 규칙들의 집합 (production rules)
  이 중 P는 BNF 문법에서 가장 중요한 요소로, 각 규칙들은 LHS와 RHS를 포함하며, '|'로 구분하여 여러 개의 RHS를 가질 수 있습니다.

예제 1. BNF 표현 방법

아래 형식 문법을 BNF로 표현하라

• 논터미널 기호인 E, T, F는 각각 <E>, <T>, <F>로 나타내고, 대체인 → 는 ::= 로 표시하면 된다.

P: <E> ::= <E> + <T> | <E> - <T> | <T> 
	<T> ::= <T> * <F> | <T> / <F> | <F> 
	<F> ::= (<E>) | id

예제 2. BNF 표현 방법

첫 번째 기호가 영문 소문자로 시작하고, 두 번째 기호부터는 영문 소문자나 숫자이며, 길이에 제한이 없는 식별자를 BNF 표기법으로 표현해보자.
<식별자> ::= <영문> | <식별자><영문> | <식별자><숫자>
<영문> ::= a | b | c | …| z
<숫자> ::= 0 | 1 | 2 | …| 9

터미널과 논터미널의 차이

컴퓨터 과학에서 문법(grammar)은 언어의 구문(syntax)을 형식적으로 규정한 것입니다.
문법은 규칙의 집합으로 이루어져 있으며, 이 규칙들은 터미널(terminal)과 논터미널(nonterminal)로 구성됩니다.

터미널은 문법에서 더 이상 분해할 수 없는 단말 기호입니다.
예를 들어, 프로그래밍 언어에서 if, else, for, while 등의 키워드나 +, -, *, / 등의 연산자, 1, 2, 3, 4 등의 숫자, 'hello', 'world' 등의 문자열 리터럴 등이 모두 터미널입니다.

즉,문법에서 터미널은 최종적인 단어들을 나타내는 것입니다.

반면에, 논터미널은 문법에서 다른 규칙을 참조하는 규칙입니다.
논터미널은** 다른 규칙들의 조합**으로 구성될 수 있습니다.

예를 들어, 프로그래밍 언어에서 if 문은 if (<condition>) <statement>의 형식을 가지고 있습니다.
이때 <condition>과 <statement>은 논터미널입니다.
이들은 각각 다른 규칙에서 정의된 것으로, <condition>은 불리언 표현식(boolean expression)에 해당하고, <statement>은 문장(statement)에 해당합니다.

즉, 터미널은 최종적인 단어를 나타내는 것이고, 논터미널은 다른 규칙을 참조하여 새로운 구조를 만들어내는 것입니다.
이러한 터미널과 논터미널을 조합하여 문법을 구성하게 되며, 이러한 문법을 이용해 언어의 구문을 형식적으로 규정할 수 있습니다.

레퍼런스

• 어휘 분석(lexical analysis)
• M - 구문 분석(syntax analysis)
• 정규 문법과 문맥 자유 문법

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>