문법의 표기법 2 (문법 도표, BNF, EBNF)

문법 도표

- 쉽게 이해할 수 있도록 문법을 도식화하는 방법

- 문법 도표는 사각형과 타원, 연결하는 간선(edge)으로 구성

 

그리는 방법

1. 터미널 기호 b는 원 안에 b로 표기하고, 다음 기호를 보기 위해 나가는 간선을 그림

 

2. 논터미널 기호 B는 사각형 안에 B를 표기하고 터미널 기호의 표기법과 같이 간선을 그림

 

3. 생성 규칙 A -> X1X2...Xn은 다음과 같이 문법 도표로 표시. (Xi가 터미널 기호일 경우 원 사용, 논터미널이면 사각형)

 

4. 생성 규칙 A -> X1 | X2 | ... | Xn인 경우 다음과 같이 문법 도표로 표시. (Xi가 터미널 기호일 경우 원 사용, 논터미널이면 사각형)

 

5. 정규 표현 A -> α*는 다음과 같은 문법 도표로 표현

 

 

BNF (Backus - Naur Form) 표기법

- 프로그래밍 언어의 형식적 정의(formal definition)을 위해 가장 널리 사용되는 방법

- 이 표기법은 현재 ALGOL 60의 문법을 표현하기 위해 가장 먼저 사용

- 현재에는 대부분의 언어들을 표현하는데 가장 많이 사용

- 메타 기호로 세 가지 기호를 사용

    - 논터미널 기호는 <, >로 묶어서 사용

    - 대체(replacement)를 나타내기 위해 ::= 사용

    - 양자 택일을 나타내기 위해서 | 을 사용

- 그런데 문제는, 반복되는 부분 그냥 다 써야 하니까 문제가 있음

 

EBNF (Extended BNF)

- 반복되는 부분을 BNF 표기법보다 읽기 쉽고 간결하게 표현 ( {<기호>} 에 위첨자가 최대 아래첨자 최소 )

- 반복되는 부분을 나타내기 위해서 메타 기호로 {}와 <, >를 사용

    - {a}는 a가 0번 이강 반복될 수 있다는 것을 의미

    - 정규 표현 a*와 같은 의미로 생각

- 또한 선택적인 부분을 표시할 때는 []로 표현

    - [x]는 x가 나타나지 않거나 한 번 나타날 수 있음을 의미

    - [x]는 {x}와 같은 의미

- 메타 기호를 터미널 기호로 사용하는 경우에는 그 기호를 작은 따옴표(')로 묶어서 표현

    - {}[]|<>)::= 이런 것들