2012년 4월 3일 화요일

EBNF(Extended Backus-Naur Form)

참고 : http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form , http://www.w3.org/TR/REC-xml/#sec-notation

1. 정의

컴퓨터 과학에서 Extended Backus-Naur Form(EBNF)는 메타구문 표기법 중에 하나로 context-free grammar(컴퓨터 프로그래밍 언어나 다른 포멀랭귀지를 정식으로 설명하는 방법)를 표현하는데 사용되어진다. Backus-Naur Form(BNF) 메타구문 기술법의 확장형이다.

  • ISO는 EBNF를 표준으로 채택함(ISO/IEC 14977)

2. 기초

EBNF는 컴퓨터 언어의 문법을 설명하는 코드로 터미널심볼과 넌터미널 생성 규칙(어떤 방식으로 터미널심볼이 규칙에 맞는 순서로 조합될 수 있는지를 통제하는 제약사항)으로 구성되어 있다. 터미널심볼의 예로 알파누메릭 문자, 문장 부호 그리고 공백 문자들을 들 수 있다.

EBNF는 생성 규칙에 있어 심볼의 시퀀스 각각을 넌터미널에 할당하는 것으로 정의하고 있다.

digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit = "0" | digit excluding zero ;


식의 왼편에 할당된 digit은 넌터미널로 정의 되고 수직바는 선택적임을 나타내며 터미널심볼은 인용부호로 감싸지며 뒤를잇는 세미콜론은 종료문자를 나타낸다. 그러므로 digit은 0이거나 1 또는 2 또는 3.... 또는 9까지의 수가 될 수 있는 digit excluding zero이다

생성 규칙은 연속되는 터미널 또는 넌터미널을 포함하며 각각은 콤마로 구분된다.

twelve = "1" , "2" ;
two hundred one = "2" , "0" , "1" ;
three hundred twelve = "3" , twelve ;
twelve thousand two hundred one = twelve , two hundred one ;


생략되거나 반복되는 것에 대한 표현은 중괄호를 통해 나타낼 수 있다 {.....}

natural number = digit excluding zero , { digit } ;


이경우는 첫째 자리는 1-9중 하나 뒷 자리는 없을 수도 혹은 중괄호의 값(0-9의 숫자)이 임의의 자릿수 만큼 반복될 수 있는것을 나타낸다.

임의 선택은 대괄호를 통해 나타낼 수 있다 [.....] 이는 대괄호 안의 값이 단 한번 혹은 없을 수도 있다는 것을 나타낸다.

integer = "0" | [ "-" ] , natural number ;


그렇기 때문에 integer는 0이거나 -부호가 있거나 없는 natural number가 된다.

3. 심볼 테이블
 
용법                    표기법
definition          =
concatenation     ,
termination       ;
alternation         |
option               [...]
repetition          {...}
grouping             (...)
terminal string   ...
terminal string   '...'
comment            (*...*)
special sequence   ?...?
exception           -

4. simple EBNF

XML의 정규문법은 simple EBNF표기법을 사용한다. 문법상 각 규칙은 형식상 하나의 심볼로 정의 되어진다.
    symbol ::= expression

      심볼은 정규 언어의 시작 기호인 경우 대문자 머릿글로 그렇지 않은 경우는 소문자 머릿글로 쓰여진다. 문자열이 표기된 그대로를 사용해야 할 경우 인용부호로 감싸서 표현한다. 오른 편에 표기된 식(expression)의 내부 아래에 소개될 규칙을 이용하여 단일 혹은 복수의 문자로 구성된 문자열과 매칭시키는데 사용되어진다.

      #xN
      N은 진수 정수이며 ISO/IEC 10646에서 정의 된 코드 포인트(예를 들자면 ASCII는 128 코드포인트로 구성되어 있고 범위는 0에서 7F까지이다)를 의미하며 식에서 표현하는 것은 N에서 정의된 문자와 일치한다.

      [a-zA-Z], [#xN-#xN]
      표기된 범위 내의 어떠한 문자도 포함 된다.

      [abc], [#xN#xN#xN]
      열거된 문자들 중 어떠한 문자라도 될 수 있고 열거형과 범위는 하나의 괄호셋으로 조합 될 수 있다.

      [^a-z], [^#xN-#xN]
      표기된 범위 이외의 어떠한 문자도 포함 된다.

      [^abc], [^#xN#xN#xN]
      열거된 문자가 아닌 어떠한 문자라도 될 수 있고 사용할 수 없는 값의 열거형과 범위는 하나의 괄호셋으로 조합 될 수 있다.

      "string"
      큰따옴표 안에 표기된 그대로의 문자열이 포함된다.

      'string'
      작은따옴표 안에 표기된 그대로의 문자열이 포함된다.

      이 심볼들은 다음의 좀더 복잡한 패턴들로 조합될 수 있다. A와 B는 간단한 식들을 나타낸다.
      (expression)
      expression은 단위로 취급 되며 다음 리스트에 설명된 것과 같이 조합될 수 있다.

      A?
      A이거나 혹은 없거나; 선택적 A

      A B
      A에 연이어 B가 따라옴. 이 연산자는 |(alternation) 연산자보다 상위 우선순위를 갖는다; 예를 들면 A B | C D 는 (A B) | (C D)로 볼 수 있다.

      A | B
      A이거나 혹은 B이거나

      A - B
      B를 제외한 A에 해당하는 어떠한 문자

      A+
      단일 혹은 복수개의 A. 이 연산자(concatenation)는 |(alternation) 연산자보다 상위 우선순위를 갖는다; 예를 들면 A+ | B+는 (A+) | (B+)로 볼 수 있다.

      A*
      0개 이거나 혹은 복수개의 A. 이 연산자(concatenation)는 |(alternation) 연산자보다 상위 우선순위를 갖는다; 예를 들면 A* | B*는 (A*) | (B*)로 볼 수 있다.

      문서 생성시 사용되는 또다른 표기법은 다음과 같다.
      /* ... */
      코멘트
      [ wfc: ... ]
      적격성 제약; XML문서의 생성과 연관된 적격의 문서(wel-formed documents)에 대한 제약 사항을 이름을 통해 판별한다. (well-formedness constraint : XML 기본 문법을 위반하지 않았는지 여부에 대한 제약)

      [ vc: ...]
      유효성 제약; XML문서의 생성과 연관된 유효한 문서(valid documents)에 대한 제약 사항을 이름을 통해 판별한다. (validity constraint : XML문서는 DTD에 문서에 대해 정의 되어 있는데 이것에 대한 위반 여부를 판단하는 제약)

      댓글 없음:

      댓글 쓰기