맨위로가기

배커스-나우르 표기법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

배커스-나우르 표기법(BNF)은 프로그래밍 언어의 문법을 표현하기 위한 메타 언어이다. 1950년대 존 배커스에 의해 제안되었으며, ALGOL 60 보고서에서 처음 사용되었다. BNF는 문법적으로 올바른 시퀀스를 생성하기 위해 기호를 결합하는 방법을 설명하며, 비단말 기호, 단말 기호, 규칙의 세 가지 구성 요소로 이루어진다. BNF는 다양한 파생 및 확장을 가지며, EBNF, ABNF, PEG 등이 있다. BNF 또는 그 변형은 ANTLR, JavaCC, Yacc 등 다양한 소프트웨어 및 Algol-60, SQL, Java와 같은 프로그래밍 언어의 문법 정의에 사용된다.

더 읽어볼만한 페이지

  • 컴파일러 구성 - 구문 분석
    구문 분석은 입력 데이터를 구조화된 형태로 변환하는 과정으로, 컴퓨터 언어에서는 소스 코드를 분석하여 추상 구문 트리를 생성하고, 자연어 처리에서는 텍스트의 문장 구조와 의미를 분석한다.
  • 컴파일러 구성 - 바이너리 재컴파일러
  • 형식 언어 - 문자열
    문자열은 사람이 읽을 수 있는 텍스트를 저장하고 정보를 전달하거나 받는 데 사용되는 순서가 있는 문자들의 시퀀스로, 다양한 형태의 데이터를 표현하며 유한한 길이를 가지고, 프로그래밍 언어에서 기본 또는 복합 자료형으로 제공되고, 문자 집합과 인코딩 방식에 따라 표현 방식이 달라진다.
  • 형식 언어 - 튜링 기계
    튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
배커스-나우르 표기법

2. 역사

존 배커스는 ALGOL의 문법을 표현하기 위해 이 표기법을 고안하였다. 1959년 파리에서 열린 세계 최초의 국제 컴퓨터 회의[25]에서 배커스는 논문[26]을 발표했는데, 이는 후에 ALGOL 58이라고 불리는 IAL의 형식 기술이었다. 그가 발표한 형식 언어는 에밀 포스트의 생성 시스템에 기반한 것이었다. 형식 문법은 수학에서의 연구 과제 중 하나였으며, 노엄 촘스키는 자연어의 문법에 적용하는 것을 연구했다.[27][28]

피터 나우어는 배커스의 표기법을 단순화하고 사용하는 문자 집합을 최소화했다. 도널드 커누스는 나우어의 공헌을 기려 BNF를 배커스-나우어 표기법(Backus-Naur Form)으로 부를 것을 제안했다.[29] BNF는 파니니의 문법 규칙과 매우 유사하여 '''파니니-배커스 표기법'''(Panini–Backus form영어)이라고 불리기도 한다.

서양 사회에서 문법은 오랫동안 과학적 연구보다는 교육의 대상이었고, 설명은 비공식적이었으며 실제 사용을 목표로 했다. 20세기 전반기에 언어학자인 레오나드 블룸필드와 젤리그 해리스는 구조 규칙을 포함하여 언어에 대한 설명을 형식화하려는 시도를 시작했다.

한편, 문자열 재작성 규칙은 형식 논리 시스템으로서 악셀 투에(1914년), 에밀 포스트(1920년대~40년대), 앨런 튜링(1936년)과 같은 수학자들에 의해 도입되고 연구되었다. 노엄 촘스키는 MIT에서 정보 이론 학생들에게 언어학을 가르치면서 기본적으로 투에의 형식주의를 자연어의 구문 설명의 기초로 삼아 언어학과 수학을 결합했다. 그는 또한 생성 규칙 (문맥 자유 문법의 규칙)과 변환 규칙 (1956년) 사이의 명확한 구분을 도입했다.[5][6]

BNF는 촘스키의 문맥 자유 문법에 대한 표기법이며, 배커스는 촘스키의 작업에 익숙했다.[10]

3. 기본

BNF 표기는 다음과 같은 유도 규칙의 집합이다.[1]

: `<기호> ::= __표현식__`

여기서:


  • `<기호>`는 항상 `< >` 쌍으로 묶인 ''비단말 기호'' 변수이다.
  • `::=`는 왼쪽에 있는 기호를 오른쪽에 있는 표현식으로 대체해야 함을 의미한다.
  • `__표현식__`은 단말 기호 또는 비단말 기호의 하나 이상의 시퀀스로 구성되며, 각 시퀀스는 수직 막대 ("|")로 구분되어 선택 사항을 나타내며, 전체는 왼쪽에 있는 기호에 대한 가능한 대체물이다.


모든 문법적으로 올바른 시퀀스는 다음과 같은 방식으로 생성되어야 한다.

  • 시퀀스를 초기화하여 하나의 시작 기호만 포함하도록 한다.
  • 이 시작 기호와 이후의 기호 시퀀스에 파생 규칙을 적용한다.[1]


어떤 문법에서의 모든 유도 규칙 중에서, 유도 규칙군의 좌변에 나타날 수 있는 기호는 "비단말 기호"이며, 어떤 유도 규칙의 좌변에도 나타나지 않는 기호는 "단말 기호"이다. (단말 기호와 비단말 기호도 참조).

4. 예시

다음은 배커스-나우르 표기법 (BNF)을 사용한 미국 우편 주소 표기 예시이다.



::=

::= |

::= | "."

::=

::= ","

::= "Sr." | "Jr." | | ""

::= "Apt" | ""



위 BNF 표기를 풀어서 설명하면 다음과 같다.


  • 우편 주소는 이름 부분, 거리 주소 부분, 우편 번호 부분으로 구성된다.
  • 이름 부분은 개인 부분, 성씨, 선택적 접미사(Jr., Sr. 또는 왕조 번호) 및 줄 바꿈으로 구성되거나, 개인 부분과 이름 부분으로 구성된다. (이는 여러 개의 이름, 중간 이름, 이니셜을 사용하는 경우를 위한 재귀적 정의이다.)
  • 개인 부분은 이름 또는 이니셜 다음에 마침표가 오는 것으로 구성된다.
  • 거리 주소는 건물 번호, 거리 이름, 선택적 아파트 지정자, 줄 바꿈으로 구성된다.
  • 우편 번호 부분은 도시 이름, 쉼표, 주 코드, 우편 번호, 줄 바꿈으로 구성된다.
  • 선택적 접미사 부분은 "Sr.", "Jr." 또는 로마 숫자와 같은 접미사, 또는 빈 문자열(아무것도 없음)로 구성된다.
  • 선택적 아파트 번호 부분은 "Apt"라는 접두사 다음에 아파트 번호가 오거나 빈 문자열(아무것도 없음)로 구성된다.


이 예시에서는 이름, 아파트 번호, 우편 번호, 로마 숫자 등의 형식과 같은 많은 사항이 정의되지 않았다. 필요한 경우, 추가적인 BNF 규칙을 사용하여 이를 정의할 수 있다.

4. 1. BNF 문법 표현

BNF의 구문은 BNF 자체를 사용하여 표현할 수 있다. ``은 적절한 줄 바꿈 지정자를 나타낸다. `` 및 ``는 선언된 규칙의 이름/레이블 또는 리터럴 텍스트로 각각 대체된다.[25]

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" | "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는 `<literal>` 규칙에 표시된 것처럼 따옴표를 사용하지 않았다. 이는 규칙을 적절하게 해석하는 데 공백이 필요하지 않다고 가정한다.

``은 적절한 줄 바꿈 지정자 (ASCII에서 운영 체제에 따라 캐리지 리턴, 라인 피드 또는 둘 다)를 나타낸다. `` 및 ``는 선언된 규칙의 이름/레이블 또는 리터럴 텍스트로 각각 대체된다.

5. 파생

배커스-나우르 표기법(BNF)에는 다양한 파생 및 확장이 존재하며, 단순성과 간결성을 위해, 또는 특정 용도에 맞게 적용하기 위해 확장/수정된다. 자주 사용되는 확장은 `*`나 `+`와 같은 정규 표현식의 반복 연산자 도입이다. IBM의 PL/I 정의에서 처음 사용된 "[]" 괄호를 사용한 표기법은 현재 일반화되었다.

5. 1. 확장 배커스-나우르 표기법 (EBNF)

BNF에는 단순성과 간결성을 위해, 또는 특정 애플리케이션에 맞게 적용하기 위해 다양한 변형과 확장 기능이 존재한다. 많은 변형의 공통적인 특징 중 하나는 `*` 및 `+`와 같은 정규 표현식 반복 연산자를 사용하는 것이다. 확장 배커스-나우르 표기법(EBNF)은 흔히 사용되는 표기법 중 하나이다.[30]

또 다른 일반적인 확장 기능은 선택적 항목을 대괄호로 묶어 사용하는 것이다. 원래 ALGOL 60 보고서에는 없었지만 (대신 몇 년 후 IBM의 PL/I 정의에 도입됨), 현재 이 표기법은 널리 인정받고 있다.[30]

5. 2. 확장 배커스-나우르 표기법 (ABNF)

인터넷 기술 태스크 포스(IETF) 프로토콜을 설명하는 데 일반적으로 사용되는 확장으로 확장된 바커스-나우르 표기법(ABNF)과 라우팅 바커스-나우르 표기법(RBNF)이 있다.[15] ABNF(확장 바커스-나우르 표기법)는 IETF의 통신 프로토콜 정의 등에 사용되고 있다.

5. 3. 파싱 표현 문법 (PEG)

파싱 표현 문법(PEG)은 BNF와 정규 표현식을 기반으로 하는 또 다른 형식 문법이다. PEG는 생성적이라기보다는 분석적인 속성을 가진다.[30]

5. 4. 기타 변형

오늘날 온라인에서 발견되는 많은 BNF 명세는 사람이 읽을 수 있도록 의도되었으며 비공식적이다. 이는 종종 다음과 같은 구문 규칙과 확장을 포함한다.

  • 대괄호 안에 선택적 항목이 포함된다: `[<item-x>]`
  • 0회 이상 존재하는 항목은 중괄호로 묶이거나 별표(`*`)가 접미사로 붙는다. (예: `<word> ::= <letter> {<letter>}` 또는 `<word> ::= <letter> <letter>*`)
  • 1회 이상 존재하는 항목은 더하기 기호(`+`)가 접미사로 붙는다. (예: `<word> ::= <letter>+`)
  • 터미널은 이탤릭체가 아닌 굵게 표시될 수 있으며, 비터미널은 꺾쇠 괄호가 아닌 일반 텍스트로 표시될 수 있다.
  • 항목이 그룹화된 경우 간단한 괄호 안에 묶인다.


BNF에는 다양한 파생 및 확장이 존재하며, 일반적으로 단순함과 간결성을 위해 확장/수정되거나 특정 용도에 맞게 적용하기 위해 확장/수정된다. 특히 자주 사용되는 확장은 `*`나 `+`와 같은 정규 표현식의 반복 연산자 도입이다. 전형적인 예로 EBNF(확장 배커스-나우르 표기법)가 있다. 실제로 위의 예는 ALGOL 60 보고서에서 사용된 원본 그대로의 형식은 아니다. "[]" 괄호를 사용한 표기법은 IBM의 PL/I 정의에서 처음 사용되었으며 현재 일반화되었다. ABNF(확장 배커스-나우르 표기법)는 IETF의 통신 프로토콜 정의 등에 사용되고 있다.

파싱 표현 문법은 BNF와 정규 표현식을 기반으로 새로운 형식 문법의 클래스를 형성한 것이다. 그 속성은 생성적이라기보다는 기본적으로 분석적이다.

오늘날 인터넷에서 발견되는 BNF 표현의 대부분은 사람이 읽는 것을 중시하며 비형식적이다.[30] 따라서 다음과 같은 구문 규칙 확장을 하는 경우가 많다.

  • 생략 가능한 항목은 대괄호로 묶는다.
  • 0회 이상 반복되는 항목은 중괄호로 묶는다.
  • 1회 이상 반복되는 항목에는 `+`를 후치한다.
  • 종결 기호를 굵은 글씨체, 비종결 기호를 일반 글씨체로 나타내며, 이탤릭체나 꺾쇠 괄호를 사용하지 않는다.
  • 항목의 반복을 `*`를 후치하여 나타내는 경우가 많다.
  • 생성 시 선택지를 `|` 기호로 구분하여 열거한다.
  • 항목을 그룹화할 필요가 있을 때는 일반 괄호로 묶는다.

6. BNF 또는 변형을 사용하는 소프트웨어


  • ANTLR, 자바로 작성된 파서 생성기
  • Coco/R, EBNF로 속성 문법을 받아들이는 컴파일러 생성기
  • DMS 소프트웨어 리엔지니어링 툴킷, 임의의 언어에 대한 프로그램 분석 및 변환 시스템
  • GOLD, BNF 파서 생성기
  • RPA BNF 파서.[16] 온라인(PHP) 데모 파싱: 자바스크립트, XML
  • XACT X4MR 시스템,[17] 프로그래밍 언어 번역을 위한 규칙 기반 전문가 시스템
  • XPL 분석기, 언어에 대한 단순화된 BNF를 받아들여 해당 언어에 대한 파서를 XPL로 생성하는 도구. 제공된 SKELETON 프로그램에 통합될 수 있으며, 이를 통해 언어를 디버깅할 수 있다.[18] (SHARE 기여 프로그램, 앞서 'A Compiler Generator'가 있었음[19])
  • bnfparser2,[20] 범용 구문 검증 유틸리티
  • bnf2xml,[21] 고급 BNF 매칭을 사용하여 XML 태그로 마크업 입력
  • JavaCC,[22] Java Compiler Compiler (JavaCC) - Java 파서 생성기
  • GNU 바이슨, Yacc의 GNU 버전
  • Yacc, 파서 생성기 (가장 일반적으로 Lex 전처리기와 함께 사용됨)
  • Racket의 파서 도구, lex 및 yacc 스타일 파싱 (Beautiful Racket edition)
  • Qlik Sense, BI 도구, 스크립팅에 BNF의 변형을 사용함[23]
  • BNF 변환기 (BNFC[24]), "레이블된 배커스-나우르 표기법"(LBNF)이라는 변형에서 작동. 이 변형에서 주어진 비단말 기호에 대한 각 프로덕션에는 해당 비단말 기호를 나타내는 대수적 자료형의 생성자로 사용될 수 있는 레이블이 제공됨. 이 변환기는 Haskell 및 Java를 포함한 여러 언어에서 추상 구문에 대한 유형 및 파서를 생성할 수 있음

7. 언어 문법

Algol-60[1], SQL[2], 에이다, 자바[3] 등 다양한 프로그래밍 언어의 문법이 BNF 또는 EBNF 형태로 제공된다. C/C++, 파스칼, COBOL, PL/I 등의 언어에 대한 BNF/EBNF 문법도 자유롭게 이용 가능하다.[4] STEP 표준과 관련된 BNF 파일도 존재한다.[5]

참조

[1] 웹사이트 What is BNF? http://www.cs.umsl.e[...]
[2] FOLDOC Backus-Naur+Form
[3] 웹사이트 Panini biography http://www-gap.dcs.s[...] School of Mathematics and Statistics, University of St Andrews, Scotland 2014-03-22
[4] 간행물 "Pāṇini-Backus Form" Suggested Association for Computing Machinery 1967-03
[5] 간행물 Three models for the description of language http://www.chomsky.i[...]
[6] 서적 Syntactic Structures Mouton
[7] 웹사이트 A COURSE OF ALGO L 60 PROGRAMMING with special reference to the DASK ALGOL system http://archive.compu[...] Regnecentralen 2015-03-26
[8] 서적 Proceedings of the International Conference on Information Processing UNESCO
[9] 웹사이트 Compiler Basics: Extended Backus Naur Form http://www.cs.man.ac[...] 2011-05-11
[10] 웹사이트 John W. Backus (1924 - 2007) http://betanews.com/[...] BetaNews. Inc. 2014-06-03
[11] 간행물 Backus Normal Form vs. Backus Naur Form
[12] 간행물 "Pāṇini Backus Form" suggested
[13] 웹사이트 ALGOL 60 http://www.masswerk.[...] 2015-04-18
[14] 서적 Programming Systems and Languages https://archive.org/[...] McGraw Hill 1967-01
[15] 문서 RBNF http://tools.ietf.or[...]
[16] Citation RPatk http://www.rpatk.net[...] 2011-07-03
[17] Citation Act world http://www.actworld.[...]
[18] 문서 If the target processor is System/360, or related, even up to z/System, and the target language is similar to PL/I (or, indeed, XPL), then the required code "emitters" may be adapted from XPL's "emitters" for System/360.
[19] 서적 A Compiler Generator https://archive.org/[...] Prentice-Hall
[20] project Source forge http://bnfparser2.so[...]
[21] 문서 bnf2xml http://sourceforge.n[...]
[22] 웹사이트 JavaCC https://javacc.java.[...] 2013-09-25
[23] 웹사이트 Script Syntax - Qlik Sense on Windows https://help.qlik.co[...] QlikTech International AB 2022-01-10
[24] Citation Language technology http://bnfc.digitalg[...] Chalmers
[25] 문서 World Computer Congress
[26] 문서 J. W. Backus, The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference, 1959.
[27] 문서 Chomsky, Noam, "Three Models for the Description of Language," ''IRE Transactions on Information Theory'', Vol. 2 No. 2, pp. 113-123, 1956.
[28] 문서 Chomsky, Noam, ''Syntactic Structures'', Mouton, The Hague, 1957.
[29] 문서 Knuth, Donald E. Backus Normal Form vs. Backus Naur Form、Communications of the ACM 誌 7(12):735-736, 1964
[30] 문서 https://www.w3.org/Notation.html
[31] 문서 페테르 나우르는 덴마크인이지만, 한국에서는 영어식 발음으로 '나우어'라고 표기하는 사례가 많다.


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com