[Compiler] 3-3. 문법 표기법

대표적인 문법 표현 방법은 정규 표현, 구문 도표, BNF, EBNF가 있다.

1. 정규 표현

정규 표현(regular expression)은 정규 언어를 가장 잘 표현할 수 있는 방법이다.

정규 표현은 다음과 같이 재귀적으로 정의된다.

• 기본 단계 : 기본을 정의하는 세 가지 규칙이 있다.
  1. \(\varnothing\)는 공집합을 나타내는 정규 표현이다.
  2. \(\varepsilon \)은 공문자열을 나타내는 정규 표현이다.
  3. 터미널 기호인 a는 집합 {a}를 나타내는 정규 표현이다.
• 귀납 단계 : r과 s가 정규 언어 L(r)과 L(s)를 나타내는 정규 표현이라면
  1. (r) + (s)는 L(r) \(\cup\) L(s)를 나타내는 정규 표현이다.
  2. (r) \(\cdot\) (s)는 L(r) \(\cdot\) L(s)를 나타내는 정규 표현이다.
  3. (r)\(^*\)는 \((L(r))^*=\{\varepsilon\} \cup (L(r))^1 \cup (L(r))^2 \cup (L(r))^3 \cdots\) 를 나타내는 정규 표현이다.

정규 표현을 구성하는 연산자는 *(클리니 클로저), \(\cdot\)(결합), +(합집합) 등이 있으며 연산자의 우선 연산 순위는 * > \(\cdot\) > + 이다. 괄호는 연산 순위 때문에 사용한 것이다. 만약 연산자의 우선순위와 결합 법칙이 결정되면 괄호를 사용하지 않아도 된다. 또한 연산자 \(\cdot\)은 생략 가능하다.

예를 들어 정규 표현 (a + b)*abb(a + b)는 다음과 같은 순서로 실행된다.

정규 표현의 대수학적 성질

1. (\(\alpha + \beta ) + \gamma = \alpha + (\beta + \gamma \)) (+에 대한 결합 법칙)
2. \((\alpha \beta )\gamma = \alpha (\beta \gamma)\) (접속에 대한 결합 법칙)
3. \(\alpha + \beta = \beta + \alpha \) (+에 대한 교환 법칙)
4. \(\alpha + \alpha = \alpha \)
5. \(\alpha (\beta + \gamma ) = \alpha \beta + \alpha \gamma \) (분배 법칙)
6. \((\beta + \gamma )\alpha = \beta \alpha + \gamma \alpha \) (분배 법칙)
7. \(\varepsilon \alpha = \alpha = \alpha \varepsilon \) (접속 연산의 항등원)
8. \(\alpha^* = \varepsilon + \alpha \alpha^*\)
9. \((\alpha^*)^* = \alpha^*\)

2. 구문 도표

구문 도표(syntax chart)는 문법을 잘 모르는 초보자가 쉽게 이해할 수 있도록 문법을 도식화하는 방법이다. 구문 도표는 사각형과 타원 그리고 사이를 연결하는 간선(edge)으로 문법을 표현한다.

 

1. 터미널 기호 b는 원 안에 b로 표기하고 밖으로 나가는 간선을 그린다.

2. 논터미널 기호 B는 사각형 안에 B로 표기하고 밖으로 나가는 간선을 그린다.

3. 생성 규칙 \(B \Rightarrow X_1X_2\cdots X_n\)은 \(X_i\)가 논터미널 기호인 경우 다음과 같이 표기한다.

만약 터미널 기호인 경우 사각형 대신 원을 사용한다.

 

4. 생성 규칙 \(B \Rightarrow X_1|X_2|\cdots |X_n\)은 \(X_i\)가 논터미널 기호인 경우 다음과 같이 표기한다.

만약 터미널 기호인 경우 사각형 대신 원을 사용한다.

 

5. 정규 표현 \(B \Rightarrow \alpha^*\)는 다음과 같이 표기한다.

3. BNF 표기법

BNF(Backus-Naur Form) 표기법은 프로그래밍 언어의 형식적 정의에 가장 널리 사용되는 방법이다. 이 표기법은 알골 60의 문법을 표현하는 데 가장 먼저 사용되었으며, 현재 대부분의 언어를 표현하는 데 가장 많이 사용되고 있다.

BNF 표기법은 메타 기호로 <, >, ::=, | 등을 사용한다. 그리고 논터미널 기호는 <와 >로 묶어 나타내며 대체는 ::= 를, 양자택일은 | 를 사용한다.

예를 들어 다음과 같은 문법이 있다.

• P : E \(\to\) E + T | E - T | T, T \(\to\) T * F | T / F | F, F \(\to\) (E) | id

 

이를 BNF 표기법으로 나타내면 다음과 같다.

• P : <E> ::= <E> + <T> | <E> - <T> | <T>, <T> ::= <T> * <F> | <T> / <F> | <F>, <F> ::= (<E>) | id

 

BNF 표기법은 반복되는 부분을 나타내는 데 어려움이 있어 이를 쉽게 표현하기 위해 나온 방법으로 EBNF 표기법이 있다.

4. EBNF 표기법

EBNF(Extended BNF) 표기법은 반복되는 부분을 BNF 표기법보다 읽기 쉽고 간결하게 표현할 수 있다. 이는 BNF 표기법에서 사용하는 세 가지 메타 기호에 반복을 나타내는 { }와 [ ]를 추가하여 다섯 가지 메타 기호를 사용하여 문법을 표현한다. 예를 들어 {a}는 a가 0번 이상 반복될 수 있다는 것을 나타내며, 정규 표현 a*와 같은 의미로 볼 수 있다. 또한 선택적인 반복을 표시할 때는 [ ]로 나타낸다. 즉 [a]는 a가 나타나지 않거나 한 번 나타날 수 있음을 의미하며 \(\{x_0^1\}과 같다고 볼 수 있다.

한편 { }, [ ], |, < >, ::= 과 같이 EBNF 표기법에서 사용되는 메타 기호를 터미널 기호로 사용하면 혼동이 일어난다. 따라서 메타 기호를 터미널 기호로 사용하는 경우에는 이를 피하기 위해 작은따옴표(' ')로 묶어서 나타낸다.

• 첫 번째 기호가 영문 소문자로 시작하고, 두 번째 기호부터는 영문 소문자나 숫자이며, 최대 여덟 자인 식별자를 EBNF 표기법으로 표현하라

고 하면 다음과 같이 나타낼 수 있다.

 

<식별자> ::= <영문>{<영문>|<숫자>}\(_0^7\)

<영문> ::= a | b | c | ... | z

<숫자> ::= 0 | 1 | 2 | ... | 9