인터프리터...7

BNF 표기법

백커스 표기법이라고도 하며 구문 도표 표현과 달리 문자로만 이론을 표기하는 방법이다.

BNF 표기법의 규칙은 다음과 같다.

• A ::= B A는 B다 혹은 A는 B로 치환된다.
• C D C 뒤에 D가 이어진다.
• E | F E 또는 F
• < > 싸여있으면 비종료 기호 아니면 종료 기호를 나타낸다.

※ BNF 표기법은 엄밀하게 정해져 있는 것이 아니며 쉽게 보기 위해 변형되기도 한다. 가령 ::= 대신 → 가 사용되기도 하며 비종료 기호를 < >로 감싸는 대신 이탤릭체로 표현하기도 한다.

 

BNF 표기법 예제

영어 소문자와 숫자로 구성되고 영어로 시작하는 식별자가 주어지는 경우를 BNF 표기법으로 나타내면 다음과 같다.

---

<식별자> ::= <영문자> | <식별자><영문자> | <식별자><숫자>

<영문자> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

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

---

 

확장 BNF 표기법

BNF 표기법에 반복이나 생략 등의 표현을 추가한 표기법으로 독자적인 확장이 많아 통일되어 있지 않다.

가령 { } 를 반복으로 표기하는 확장 BNF 표기법으로 예제를 나타내면 다음과 같이 표기할 수 있다.

---

<식별자> ::= <영문자> { <영문자> | <숫자> }

---

 

언어 사양 설계

새로운 언어를 개발할 때 언어 사양을 BNF 표기법이나 구문 도표로 새로 설계하는 것은 시간이 걸리고 검증하는 것도 쉽지 않다. 대신에 잘 알려진 언어 사양을 모델로 하고 거기에 추가적인 설명을 덧붙이는 방식을 사용할 수 있다.

 

가령 BASIC을 모델로 하는 경우 다음과 같이 설명할 수 있을 것이다.

• BASIC의 언어 사양을 그대로 따른다.
• BASIC에서 불필요한 기능을 삭제하고 독자적인 편리한 기능을 추가한다.

 

참고문헌

만들면서 배우는 인터프리터하야시 하루히코 상세보기