프로그래밍 언어의 구문의 표현 - BNF, EBNF, 구분 도표 표현법

BNF 표현법

BNF(Backus-Naur Form)는 Algol의 구문을 정의하기 위해 배커스(Backus)와 나우어(Naur)가 사용한 표현법이다.

 

BNF 기호

메타 기호

BNF는 세 가지 메타 기호를 사용한다.

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

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

- ::=를 기준으로 왼쪽을 오른쪽으로 정의한다.

- ::=의 왼쪽에는 하나의 비단말 기호가, 오른쪽에는 기호들을 활용하여 정의하는 내용이 나와야 한다.

 

단말/비단말 기호

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

 

BNF의 예

<if문> ::= if <논리식> then <문장>

if문의 정의를 BNF로 표현한 규칙의 예이다. 이 규칙은 비단말 기호 <if문>을 단말 기호 if, then 그리고 비단말 기호 <논리식>과 <문장>을 이용하여 정의하고 있다.

 

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

메타 기호 |은 둘 중 하나를 택일한다는 의미이다.

 

BNF로 식별자를 정의해 보자. 식별자는 문자와 숫자로 구성되며 첫 글자는 문자여야 한다. 문자는 대문자 알파벳과 소문자 알파벳이 가능하며, 숫자는 0부터 9까지 가능하다고 가정하면, BNF 표현은 다음과 같다.

<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의 확장 - EBNF 표현법

EBNF(Extended BNF)는 BNF에 메타 기호를 추가하여 규칙을 더 간결하게 표현할 수 있도록 확장된 BNF이다. 4가지 메타 기호가 추가되었다.

구분	메타 기호	의미
BNF	::=	정의
BNF	|	택일(OR)
BNF	<>	비단말 기호
EBNF	[ ]	생략 가능
EBNF	{ }	0번 이상 반복
EBNF	( )	한정된 범위의 택일 |와 함께 쓰임
EBNF	' '	메타 기호 자체를 단말 기호로 사용

 

메타 기호 [ ]의 예

의미 : 생략 가능

앞에서 보았던 <if문> 정의 규칙의 BNF 표현을 EBNF로 표현하면 다음과 같다.

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

EBNF
<if문> ::= if <논리식> then <문장> [ else <문장> ]

 

메타 기호 { }의 예

의미 : 0번 이상 반복

부호 없는 정수(unsigned integer)를 BNF와 EBNF로 각각 표현하면 다음과 같다.

BNF
<unsigned integer> ::= <digit> | <unsigned integer><digit>

EBNF
<unsigned integer> ::= <digit> { <digit> }

 

위 BNF 표현은 반복을 나타내기 위해 |와 재귀적인 표현 방법을 사용하였다.

EBNF 표현에서 비단말 기호 <unsigned integer>는 메타 기호 { }로 묶인 '<digit>'을 0번 사용하여 그냥 한 자리 수인 <digit>이 될 수도 있고 한 번 사용하여 두 자리 수인 <digit><digit>이 될 수도 있으며 그 이상이 될 수도 있다.

 

<unsigned integer> = <digit>

<unsigned integer> = <digit><digit>

<unsigned integer> = <digit><digit><digit>

<unsigned integer> = <digit><digit><digit><digit><digit><digit>, ...

 

메타 기호 ( )의 예

의미 : 범위 중 택일

사칙 연산 수식을 BNF와 EBNF로 각각 표현하면 다음과 같다.

BNF
<수식> ::= <수식> + <수식> | <수식> - <수식> | <수식> * <수식> | <수식> / <수식>

EBNF
<수식> ::= <수식> ( + | - | * | / ) <수식>

 

EBNF 표현에서 ( )로 묶은 범위, 즉 +, -, *, / 중 한 가지 연산자만 택일하여 사용하는 규칙이다.

 

메타 기호 ' '의 예

의미 : 메타 기호 자체를 단말 기호로 사용

BNF 규칙을 ::=를 기준으로 왼쪽과 오른쪽으로 구성됨을 EBNF로 표현하면 다음과 같다.

<BNF 규칙> ::= <왼쪽 부분> '::=' <오른쪽 부분>

 

메타 기호 ::=를 ' '로 묶음으로써 하나의 단말 기호로 사용한다. 만일 메타 기호 ' '를 사용하지 않으면 규칙의 정의를 의미하는 메타 기호가 되어 잘못된 표현이 된다.

 

구문 도표(Syntax Diagram)

구문 도표는 순서도와 유사하게 그림(도표)으로 구문을 표현하는 것이다. 초기 Pascal의 사용자 설명서에 사용되었다.

 

구문 도표의 기본 단위

도형	의미
□ (사각형)	비단말 기호
○ (원)	단말 기호
→ (화살표)	기호 연결

아래 그림에서 if와 then은 단말 기호, 논리식과 문장은 비단말 기호이다. 규칙은 화살표를 따라 순서대로 나열되는 것으로 정의된다. 화살표는 나누어지거나 합쳐지기도 하고 되돌아가기도 하는데 이를 통해 택일, 반복을 표현할 수 있다. 실제 구문이 적용될 때 한쪽 방향으로만 따라갈 수 있다.

 

if문의 구문 도표

• BNF : <if문> ::= if <논리식> then <문장> | if <논리식> then <문장> else <문장>
• EBNF : <if문> ::= if <논리식> then <문장> [ else <문장> ]

 

구문 도표의 예

사칙 연산 수식의 구문 도표

• BNF : <수식> ::= <수식> + <수식> | <수식> - <수식> | <수식> * <수식> | <수식> / <수식>
• EBNF : <수식> ::= <수식> ( + | - | * | / ) <수식>

 

부호 없는 정수의 구문 도표

BNF : <unsigned integer> ::= <digit> | <unsigned integer><digit>

EBNF : <unsigned integer> ::= <digit> { <digit> }

 

표현 방법의 상호 변환

BNF, EBNF, 구문 도표 표현은 상호 변환이 가능하다.

BNF	EBNF	구문 도표
|	[ ]	화살표를 나눔
( )의 바깥 부분을 반복하여 표현	( )	화살표를 나눔
{ }로 묶인 부분이 0번 사용되는 경우와 한 번 이상 반복되는 경우로 나누어 재귀적으로 표현	{ }	화살표를 되돌아가게 함

 

식별자(identifier)의 정의를 세 가지 방법으로 표현해 보자. 문자(letter)와 숫자(digit)로 구성되며 첫 글자는 문자라고 가정한다. 편의상 문자와 숫자에 대한 정의는 생략한다.

 

• BNF

<identifier> ::= <letter> | <identifier><letter> | <identifier><digit>

 

• EBNF

<identifier> ::= <letter> { <letter> | <digit> }

 

• 구문 도표

 

포스팅 마침.