프로그래밍 언어론 심화학습 - BNF & EBNF & 구문도표 [식별자 정의]

BNF & EBNF & 구문도표 [식별자 정의]

BNF (Backus-Naur form)

BNF는 프로그래밍 언어를 정의하기 위한 최초의 메타 언어였다. ALGOL 58 언어의 구문 기술을 위해 1959년에 John Backus에 의해 처음 도입되었으며, Peter Naur에 의해 강화되어 ALGOL 60을 정의하는데 사용되었다. BNF는 구문 요소를 나타내는 기호 < >, 둘 중 하나의 선택을 의미하는 기호 ∥, 좌변은 우변에 의해 정의됨을 의미하는 기호 ::= 등의 메타 기호들을 사용하여 규칙을 표현한다. BNF의 원형은 원래 "Backus normal form"이었으나, Peter Naur의 이름을 넣어 오늘날과 같이 바뀌었다.

BNF 개발 배경

언어 자체에 관심을 가지고 있었던 학자들은 언어에 대한 욕심을 알골(ALGOL, Algorithm Language)가 그것이다. 그러나 또 다른 측면에서 이는 신대륙(미국)에 대한 구대륙(유럽)의 반항이라고도 할 수 있었다. 1958년 5월 28일 취리히 공과대학에서 과학기술용 범용언어에 대한 회의(ACM/GAMM committee)가 열렸다. 배커스도 초청되었다. 그러나 소수점을 문장의 분리기호를 쓸것인가하는 문제로 격돌을 벌였다. 위원장인 웨그슈타인의 중재로 일단 격돌을 일으키는 부분은 나중에 다루기로 하였다. 사소한 논쟁을 피하고 구조적인 측면을 중시한 언어가 탄생하게 되었다. 그 결과 포트란을 따라잡지는 못했지만, 이후에 나타날 현대적 언어에 많은 영향을 주었고, 특히 배커스표준형식(Backus Normal Form, BNF)이 도입되어 이제 프로그래밍 언어는 하나의 언어과학으로 발전하게 되었다. 미국의 포트란 추종자들은 알골을 헐뜯었다. 입출력도 제대로 없다, 구조가 모호하다는 등 그러나 유럽인들은 알골을 아꼈고, 미국에서는 시들어 갔다. 호퍼여사는 알골을 기절할 정도로 절묘한 구조의 아름다움을 지녔지만, 아무도 쳐다보지 않아 조금 쓸쓸할 따름이라고 표현했다. 그러나 알골설계의 철학은 미국에도 큰 영향을 미쳤다. 블럭구조, 자기호출기능(recursion), BNF형식에 의한 구문 정의가 그것으로 이 선물을 이어받은 파스칼은 포트란을 미국의 대학에서 몰아내고, 교육용 언어로서 자리를 굳혀갔다. Backus-Naur form(일반적으로는 BNF 또는 Backus-Naur Form으로 알려진)은 Algol 58 프로그래밍 언어의 문법을 묘사하기 위해 Jim Backus와 Peter Naur에 의해서 개발되어진 정규 수학적 방법이다. 수학자 Emil Post에 의해 초기 작업된 것에 기초로 하여, JIm Backus가 주요하게 개발한 것으로 알려져 있지만, 그러나 Peter Naur가 향상시켜 그것을 유명하게 만들었다. BNF라 불리는 것도 Peter Naur가 그렇게 불렀기 때문에 그밖에 다른 사람들도 BNF라고 부르게 된 것이다. 무엇이 허락되어지고 무엇이 허락되지 않는지에 대한 모호성과 불일치가 없게 하기 위해서 정규적인 언어의 문법을 정의하는 것을 사용하게 되었다. 사실상, BNF는 다수의 문법에서 많은 수학적인 이론이 있다는 것은 매우 분명하다. 문법에 대해 하나의 BNF문법이 주어진 언어에 대한 하나의 parser로 사실적, 기계적으로 구성 할 수 있다.(몇몇 문법들에서는 불가능하지만, 그러나 그것들을 수동적으로 변환시켜 사용한다.)

BNF 표기법

1. 언어 구문의 형식 정의 (formal definition)

• 언어를 가지고 정상적인 프로그램을 작성하는 규율들의 집합
• 일반적으로 형식 정의에서 이 규율들은 그대로 적용되는 공식이나 순서도(flowchart)를 가지고 표현

2. BNF(Backus-Naur Form)표기법

• 구문 형식을 정의하는 가장 보편적인 기법
  →ALGOL을 정의할 때 최초로 사용
• 한 언어의 구문에 대한BNF의 정의는 생성규칙(production rule) 들의 집합
• 생성 규칙은 구문 규율
  ·생성규칙은 하나의 정의를 이루는데, 규칙의 왼쪽에는 정 의될 대상(object)을, 오른쪽에는 그 대상에 대한정의를 표현

• 언어를 가지고 정상적인 프로그램을 작성하는 규율들의 집합
• 일반적으로 형식 정의에서 이 규율들은 그대로 적용되는 공식이나 순서도(flowchart)를 가지고 표현

BNF의 형식

BNF는 하나의 수학적인 게임 같은 종류이다. 즉 당신은 하나의 symbol(s라는 이름으로 약속된 start symbol이 호출되어)과 이 symbol과 함께 위치 할 수 있는 주어진 규칙으로 시작한다. BNF에 의해 정의된 그 언어는 오직 다음의 이들 규칙들에 의해 제공할 수 있는 모든 문자열의 집합이다.

그 규칙들은 production rules라고 불린다. 그것은 다음과 같이 나타낸다.

symbol := alternative1 | alternative2 ....
또는
<identifire> ::=<letter> | <identifire><letter> | <identifire><digit> ....

production rule은 간단하게 ":="의 왼쪽 부분에 있는 symbol이 오른쪽에 있는 alternative 중에 하나와 대체되어야 한다고 말한다. alternative emfdms "|"에 의해서 구별되고, 나누어진다(참고로 ":=" 대신 "::="이 사용되기도 하는데, 의미는 동일하다.). Alternative들은 일반적으로 terminal(단말기호)이라고 불리는 것과 symbol(비단말기호)로 구성된다. Terminal들은 간단하게 symbol들이 아닌 마지막 문자열의 조각들이다. 그들은 production rule에 적용되지 않기 때문에 terminal들이라고 부른다.(Symbol들을 종종 Non-terminal이라고도 부른다.) BNF에서 다른 변동은 symbol들로부터 그들을 분류하기 위해 인용부호로 terminal들을 동봉한다. 몇몇 BNF 문법에서는 공백이 그것에 대해 symbol을 가지는 것을 허락하는 장소나 다른 문법들을 읽는 자가 암시하게 이것을 남겨놓는 장소를 분명하게 보여준다.

ALGOL 60의 BNF 예

<for stmt> ::= <for clause> <stmt> | <label> <for stmt> <for clause> ::= for <variable> := <for list> do <for list> ::= <for list element> | <for list>, <for list element> <for list element> ::= <arithmetic exp> | <arithmetic exp> step <srithmetic exp> until <arithmetic exp> | <arithmetic exp> while <Booleanexp>

BNF 형식 사용예

<sentence:문장> ::= <noun-phrase:명사구><verb-phrase:동사구>. <noun-phrase> ::= <article:관사><noun:명사> <article> ::= a | the <noun> ::= girl | dog <verb-phrase> ::= <verb><noun-phrase> <verb:동사> ::= sees | pets <sentence>로부터 문장 생성의 예 <sentence>-> <noun-phrase><verb-phrase>. -> <article><noun><verb-phrase>. -> the <noun><verb-phrase>. -> the girl <verb-phrase>. -> the girl <verb><noun-phrase>. -> the girl sees <noun-phrase>. -> the girl sees <article><noun>. -> the girl sees a <noun>. -> the girl sees a dog.

EBNF

BNF 표기법으로 모든 프로그래밍 언어를 표기할 수 있지만, 보다 읽기 쉽고 간결하게 표현 할 수 있는 확장된 EBNF(Extended BNF)를 사용하기도 한다. EBNF는 특수한 의미를 갖 는 메타 기호를 더 사용하여 반복되는 부분이나 선택적인 부분을 간결하게 표현할 수 있으 며, 반복되는 부분을 나타내려면 { }를 사용한다. 즉, {a}는 a가 0번 이상 반복될 수 있음 을 의미한다.

구문도표 와 활용

구문도표

BNF / EBNF 의 규칙을 표현하는 그래픽(도식적)인 방법

구문도표 그리는법

구문도표는 형태가 순서도와 유사하다.