[컴파일러] BNF 정리

 

 

BNF (Backus–Naur Form)란

 

 

BNF는 프로그래밍 언어의 문법(Grammar) 을 형식적으로 표현하기 위한 표기법(Notation)을 말한다. 컴파일러의 구문 분석(Parsing) 의 근간이 된다.

 

프로그래밍 언어의 문법 구조를 분명하고 간결하게 표현할 때 주로 사용된다. 1950년대 후반에 존 배커스(John Backus)와 피터 나우어(Peter Naur)가 개발한 방법이라 'Backus-Naur Form'이라 부르게 되었다.

 

 

BNF 표현 방법 

<비단말기호> ::= 표현식

 

 

 

 

 

 

BNF 예시 

<expr> ::= <expr> + <term> 
         | <expr> - <term> 
         | <term>

<term> ::= <term> * <factor> 
         | <term> / <factor> 
         | <factor>

<factor> ::= ( <expr> ) 
           | <int>

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

 

 

<expr>	전체 수식(expression)	2 + 3 * 4
<term>	곱셈, 나눗셈 단위	3 * 4
<factor>	괄호 또는 정수	(2 + 3) 혹은 4
<int>	실제 정수 리터럴	2, 3, 4 등

 

 

 

 

 

BNF의 역할

 

1. 언어의 구문 정의	문장이 문법적으로 올바른지 판단할 기준 제공
2. 파서(parser) 생성	컴파일러가 소스 코드를 분석할 때 참조하는 규칙
3. 언어 설계 표준화	C, Java, Python 등 대부분의 언어 명세에 사용됨
4. 파스트리 기반	Syntax Tree의 구조적 기반을 제공

 

 

 

 

문법(Grammar), 문자열(String), 문장(Sentence), 표현식(Expression)

 

문법 (Grammar)	언어를 정의하는 규칙의 집합.비단말(Non-terminal)과 단말(Terminal), 생성규칙(Production)으로 구성됨.	<expr> → <expr> + <term><term> → id	언어의 구조적 규칙을 명시함.
문자열 (String)	알파벳(terminal symbol) 들의 유한한 나열.	aab, id + id	실제 입력이 될 수 있는 심볼들의 나열.
문장 (Sentence)	문법의 시작 기호(start symbol) 로부터 유도(derive)될 수 있는 문자열.	id + id * id	문법 규칙을 적용해 만들어진 실제 문장.
표현식 (Expression)	문법 내의 특정 비단말(non-terminal) 이 생성할 수 있는 구조적 단위.	id + id, (id * id)	문법의 일부 구성요소(비단말 단위)로 유도된 문장 조각.

 

 

문법(Grammar)의 구성요소 4가지

 

보통 문법은 다음과 같이 정의 된다  

G = (N,T,P,S)

 

T	Terminal symbol (단말기호)	id, +, *, (, )
N	Non-terminal symbol (비단말기호)	<expr>, <term>, <factor>
P	Production rules (생성 규칙)	<expr> → <expr> + <term> | <term>
S	Start symbol (시작 기호)	<expr>