[컴파일러] 구문 분석 (Syntax Analysis)

👑 구문 분석 (Syntax Analysis)

구문 분석 (Syntax Analysis)은 컴파일러의 전반부(Front-end) 단계 중 하나로, 어휘 분석을 통해

얻은 토큰 스트림을 입력으로 받아, 주어진 토큰 스트림이 특정 언어의 문법 규칙에 맞는지 확인한다.

문법 규칙은 문맥 자유 문법(Context-Free Grammer, CFG)으로 정의되며, 이를 기반으로 프로그램의

구문을 검사한다. 구문 분석 과정에서는 파서(Parser)가 사용되는데, 파서는 토큰들을 분석하여

파스 트리(parse tree)를 생성한다. 구문 분석의 유형으로는 상향식(bottom-up)과

하향식(top-down)이 존재한다.

💡 CFG (Context Free Grammar)

우리가 어떤 문장이 문법에 맞는지를 확인하려면 당연하게도 해당 언어의 문법을 알고 있어야 한다.

이와 같이, 컴파일러 또한 프로그래밍 언어의 문법을 알고 있어야 파싱을 할 수 있다. 일반적으로 프로그래밍

언어의 문법은 문맥 자유 문법(Context Free Grammar, CFG)으로 정의되어 있다.

CFG는 다음과 같이 정의된다.

G = (N, T, P, S)

- N : nonterminal 심벌들의 집합
- T : terminal 심벌들의 집합
- P : 생성 규칙의 집합
- S : 시작 심벌

예:
S → A + A
A → a | b | c

문맥 자유 문법을 표현하기 위한 표기법으로 BNF(Backus-Naur Form)와 EBNF(Extended

Backus-Naur Form)가 존재한다. 두 표기법 모두 프로그래밍 언어나 언어 구문을 명확하게

정의하기 위해 사용되며, EBNF는 BNF의 확장된 형태이다.

✔ BNF (Backus-Naur Form)

BNF는 언어의 문법을 형식적으로 정의하는 데 사용된다. BNF는 다음의 규칙을 기반으로 문법을 표현한다:

• nonterminal 기호 : 문법 규칙에 따라 더 확장될 수 있는 기호. “<>”로 묶어서 표기한다.

• terminal 기호 : 더 이상 확장되지 않는 실제로 사용되는 문자나 토큰을 의미한다.

• 생성 규칙 : ::= 기호를 사용하여 nonterminal 기호가 어떻게 생성될 수 있는지를 정의한다.

<id> ::= <letter> | <id><letter> | <id><digit>
<letter> ::= a | b | c ... y | z | A | B ... Y | Z
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

✔ EBNF (Extended Backus-Naur Form)

EBNF는 BNF를 확장한 것으로, 보다 간결하고 강력한 문법 표현을 지원한다.

• [] : 생략 가능. 대괄호 안에 선택적으로 나타날 수 있는 기호를 표시한다.

• {} : 반복. 중괄호 안에 들어가는 기호는 0번 이상 반복될 수 있다.

• () : 그룹화. |와 함께 사용하여 괄호 안의 범위 내에서 하나를 고를 수 있다.

<id> ::= <letter>{ <letter> | <digit> }
letter ::= a | ... | z | A | ... | Z
digit ::= 0 | ... | 9

💡 유도 (Derivation)

위의 내용을 통해 프로그래밍 언어에서 문법을 기술하는 방법(CFG)에 대해 알 수 있었다.

입력된 토큰 스트림이 기술된 문법에 맞는지를 확인하기 위한 방법으로 유도(derivation)를

사용한다. 유도(derivation)는 구문 분석의 한 과정으로, 시작 기호에서 출발하여 문법 규칙을

적용해 최종 문자열을 생성하는 과정을 의미한다.

예를 들어, 다음과 같은 CFG가 있다고 가정하고, 문자열 aaabbb를 유도해 볼 수 있다.

<S> ::= "a" <S> "b" | ε

• <S> ::= "a" <S> "b" 적용

  • S ⇒ aSb

• <S> ::= "a" <S> "b" 적용

  • ⇒ aaSbb

• <S> ::= "a" <S> "b" 적용

  • ⇒ aaaSbbb

• <S> ::= ε 적용

  • ⇒ aaabbb

유도는 두 가지 방식으로 구분될 수 있다.

• 좌측 유도 (leftmost derivation)

  • 가장 왼쪽에 있는 nonterminal 기호 먼저 규칙 적용

• 우측 유도 (rightmost derivation)

  • 가장 오른쪽에 있는 nonterminal 기호 먼저 규칙 적용

위의 그림의 경우, 좌측 유도와 우측 유도의 유도 트리가 같다. 문법 G가 모호하지 않다면 그로 인해

생성되는 모든 문장의 유도 트리는 하나이다. (모호한 문법이더라도 어떤 문장이 유도 트리를

하나만 가질 수도 있음)

💡 모호성 (Ambiguity)

문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도 트리를 갖는다면 문법 G는 모호하다고

(ambiguous) 한다.

문법이 모호한 경우 파서가 어떠한 생성규칙을 선택할지를 결정할 수 없기 때문에 모호성을 피하는 것이

중요하며, 모호성 해결을 위한 많은 방법들이 존재한다.

• 연산자 우선순위 도입

  • 연산자 우선순위를 도입하면 각 연산자의 적용 순서를 명확히 하여, 동일한 표현식에 대해
    예측 가능한 결과를 보장할 수 있다.

  • 연산자마다 새로운 nonterminal을 도입하고, 재귀를 왼쪽, 오른쪽 중 하나만 두며, 시작 심벌과
    가까운 쪽에 연산자 우선순위가 낮은 것을 둔다.

  • E → E - E | E ÷ E | (E) | e (연산자 간의 우선순위가 명확하지 않음)

  • 위 문법을 연산자 우선순위를 도입하여 다음과 같이 변환할 수 있다. (나눗셈 > 뺄셈)

    E → E - T | T
    T → T ÷ F | F
    F → (E) | e
    

• 결합 법칙 도입

  • 연산자가 어떻게 결합되는지를 정의하여, 주어진 표현식의 의미를 명확하게 한다.

  • Left Recursion 은 좌측결합에 사용한다. A → A + a | a

  • Right Recursion 은 우측결합에 사용한다. A → a ^ A | a

💡 파싱 (Parsing)

구문 분석(Parsing)이란 주어진 문자열이 정의된 문법에 의해 생성될 수 있는지 여부를

결정하는 과정이라고 볼 수 있다. 위에서 보았듯이 유도를 통해 시작 기호로부터 문법 규칙을

적용하여 최종 문자열을 생성할 수 있었다. 따라서, 특정 문자열이 언어의 문법 규칙에 의해 유도될

수 있는지 확인하는 과정은 컴파일러의 구문 분석 단계에서 매우 중요하다.

구문 분석의 방법에는 루트 노드로부터 시작하여 단말노드를 생성하며 확인하는 Top-down 방식과

단말 노드로부터 루트 노드를 향하여 위로 생성하며 확인하는 Botton-up 방식이 있다. Top-down

방식은 좌측유도와 같은 순서의 생성규칙을 적용하며 생성규칙을 적용한 순서를 좌파스라 한다.

Bottom-up 방식은 우측유도의 역순의 생성규칙을 적용하며 생성규칙의 역순을 우파스라 한다.

👑 문제

1. 다음 정규 표현식을 CFG로 바꾸시오.
⑴ (a|b)c
⑵ $ a^+ $
⑶ (1(0|1)*) | 0
⑷ 괄호 매치에 대한 CFG

• (a|b)c

<S> ::= <A> "c"
<A> ::= "a" | "b"

• $ a^+ $

<S> ::= "a" <S> | "a"

• (1(0|1)*) | 0

<S> ::= "1" <A> | "0"
<A> ::= "0" <A> | "1" <A> | ε

• 정상적인 괄호 매치

<S> ::= "(" <S> ")" | <S> <S> | ε

2. 다음 문법에서 '!', '¡'가 우선순위가 가장 높고, '&'가 우선순위가 가장 낮다고 할 때,
변경된 문법을 적으시오.

S → '!' S '¡'
S → S '&' S
S → S '|' S
S → a


S → S '&' E | E
E → E '|' T | T
T → '!' S '¡' | a