BNF와 EBNF 표현 방법

BNF 표현 방법

BNF (Backus-Naur Form)는 프로그래밍 언어의 형식적 정의(formal definition)을 위해 가장 널리 사용되는 방법입니다

이 표기법은 메타 기호(meta-symbol; 메타기호는 표현하려는 언어의 일부분이 아니라, 그 언어를 표현하려고 사용된 특수기호)로서 세 가지 기호를 사용합니다

• 논터미널기호는<, > 로 묶어 표현
• 대체(replacement)는 ::= 사용
• 양자택일은 | 를 사용

예제 3.24 BNF로 표현하기 1

논 터미널 기호인 E,T,F는 각각 <E>, <T>, <F>로 나타난다.
→ 는 ::= 로 표시한다

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

예제 3.25 BNF로 표현하기 2

첫 번째 기호가 영문 소문자로 시작하고, 두 번째 기호부터는 영문 소문자나 숫자이며, 길이에 제한이 없는 식별자를 BNF 표기법으로 표현해보자.

<식별자> ::= <영문> | <식별자><영문> | <식별자><숫자>
<영문> ::= a | b | c | …| z 
<숫자> ::= 0 | 1 | 2 | …| 9

얼추 위와 같이 표현을 할 수 있지만, 완벽하지 않다. 길이에 제한이 없기 때문이다

정확히는 위와 같이 표현해야하는데, 엄청난 가지 수의 생성 규칙이 발생한다
이와 같이 BNF (Backus-Naur Form)는 반복 되는 부분을 표시하는데 어려움이 있다

EBNF 표현 방법

EBNF는 반복되는 부분을 BNF 표기법보다 읽기 쉽고 간결하게 표현한다
BNF 표기법의 세 가지 메타 기호에 반복을 나타내는 { }와[]를 추가하여 사용한다

{a}는 a가 0번 이상 반복 될 수 있다는 것을 의미한다
정규표현 a*와 같은 의미로 생각하면 된다

또한, 선택적인 부분을 표시 할 때는 []로표현
[x]는 x가 나타나지 않거나 한 번 나타날 수 있음을 의미한다
즉 [x]는 {x} 과 같은 의미이다

메타 기호를 terminal로 사용하는 경우, 그 기호를 작은 따옴표('')로 묶어 표현한다
{ }, [ ], |, < >), ::= 와 같이 EBNF에서 사용되어지는 메타기호를 터미널 기호로 사용하 는 경우 발생하는 혼돈을 피하기 위해서 사용한다

예제 3.27 EBNF로 표현하기 1

첫 번재 기호가 영문 소문자로 시작하고, 두 번째 기호부터는 영문 소문자나 숫자이며, 최대 8 글자인 식별자를 EBNF로 표현해보자

예제 3.28 EBNF로 표현하기 2

if 문장에서 else 부분이 선택적으로 나타날 수 있다면 다음과 같이 표현한다

<if_st> ::= if <condition> then <statement> [else <statement>]

예제 3.29 메타 기호를 터미널 기호로 사용하기

메타 기호 ::=와 |를 터미널 기호로 사용하는 경우에 대해 알아보자

<BNF_rule> ::= <left_part>'::='<right_part>
<right_part> ::= <right_part_elemnet>{'|'<right_part_element>}

위는 BNF 표현 방법을 EBNF로 표현하는 식이다.
이렇게 보니 EBNF 최고다…!

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