구문분석이란?

그림 1. 구문분석

어휘분석기가 생성한 토큰을 기반으로 구문분석기(파서)가 문법이 맞는지 확인하고, 각 단어의 역할을 확인하여 파스트리를 만드는 것을 syntax analysis 즉 구문분석이라고 한다.

 

 

 

프로그래밍 언어 제작자가 문법을 기술하는 방법

 

CFG(Context Free Grammar)

언어의 문법을 정의하는 일반적인 방법이다. 간단하고 이해하기 쉬우며, 표현된 문법으로부터 자동적으로 인식기를 구현 가능하다.

 

  • G = (N, T, P, S)
    • N: non terminal 심벌 집합 (중간 과정 심벌)
    • T: terminal 심벌 집합
    • P: 생성 규칙 집합
    • S: 시작 심벌
  • L(G): 이 문법으로 생성되는 language

 

문법 심벌들

  • Terminal 심벌 (T)
    • a,b,c와 같은 알파벳 시작 부분의 소문자와 숫자 0,1,2,…9;
    • +,- 와 같은 연산자 기호와 세미콜론, 콤마, 괄호와 같은 구분자
    • ‘if’, 또는 ‘then’ 같은 따옴표 사이에 표기된 문법 심벌
  • Nonterminal 심벌 (N)
    • A, B, C와 같은 알파벳 시작 부분의 대문자로 나타나게 된다.
    • S는 보통 시작 심벌(start symbol)을 나타낸다.
    • <stmt>나 <expr>과 같이 < >로 묶어서 나타내기도 한다.

 

문법 생성 규칙

  • 생성 규칙(P)
S → T + T
T → ‘0’
T → ‘1’
T → ‘2’


T → ‘0’ | ‘1’ | ‘2’

위와 같이 생성 규칙의 왼쪽이 모두 같은 A인 경우에  아래처럼 간단히 표기할 수 있다.

 

 

  • 시작 심벌 (S)
    • 만약 아무런 언급이 없으면 첫 번째 생성 규칙의 왼쪽에 있는 것이 시작 심벌이다.

 

정규표현식은 토큰을 기술하거나, DFA로 변환하여 구현하기에 좋다. 그러나 Block, expressions, statments 등의 Nested 구조의 구문을 표현하기에 power가 떨어진다. 즉 유한한 상태로 무한한 중첩 상태 등을 표현할 수 없다. 따라서 문법 기술을 표현하는 데 사용될 수 없다.

 

 

그 외 여러가지 CFG 표기법

  • BNF(Backus-Naur Form)
    • nonterminal 심벌 : <와>로 묶어서 표기
    • terminal 심벌: 문자 스트링
<id> ::= <letter> | <id><letter> | <id><digit>
<letter> ::= a | b | c | … | y | z
<digit> ::= 0 | 1 | 2 | … | 8 | 9
  • EBNF(Extended BNF)
    • 메타 심벌 도입: 반복되는 부분이나 선택적인 부분을 간결하게 표현하기 위한 특수 심벌
<id> ::= <letter>{<letter>|<digit>}07
<letter> ::= a|b|c|…|y|z
<digit> ::= 0|1|2|…|9

 

 

 

 

주어진 input token stream이 기술된 문법에 맞는지 판별하는 방법

  • 문법과 언어
    • 문법: S→ <주어구><동사구>, <주어구>→<관형구><진 주어>
    • 언어: “똑똑한 3학년이 모였습니다”
  • 유도
    • 문법에서 언어를 생성해 내는 것
  • 구문분석
    • 언어에서 문법을 확인해 가는 것
    • 방법은 유도가 되는지 보면 된다

 

 

유도(Derivation)

문법에서 문장(언어)를 생성하는 것을 유도라고 한다. 생성 규칙을 연속적으로 적용하여 Nonterminal을 확장함으로써 얻는다.

 

예시)

  • 문법 : E → E + E | E * E | (E) | a
  • 언어: (a+a)
  • 유도: E ⇒ (E) ⇒ (E+E) ⇒ (a+E) ⇒ (a+a)

 

유도트리는 위와 같은 유도 경로를 추상화시켜 표현한 것으로 아래의 그림과 같다.

그림 2. 유도트리

 

 

Nonterminal 심벌의 대치 순서

생성 규칙 '→' 다음에 하나 이상의 nonterminal 심벌이 올 수 있다.

  • 좌측유도(leftmost derivation): 가장 왼쪽에 있는 nonterminal 먼저 대치
    • E ⇒ (E) ⇒ (E+E) ⇒ (a+E) ⇒ (a+a)
  • 우측유도(rightmost derivation): 가장 오른쪽에 있는 nonterminal 먼저 대치
    • E ⇒ (E) ⇒ (E+E) ⇒ (E+a) ⇒ (a+a)

 

예를 들어 언어가 (a+a)*a 이고 문법이 아래와 같을 때

  1. E → E+E
  2. E → E*E
  3. E → (E)
  4. E → a

 

좌측 유도는

E ⇒ E*E 2 

   ⇒ (E)*E 3

   ⇒ (E+E)*E 1

   ⇒(a+E)*E 4

   ⇒(a+a)*E 4

   ⇒(a+a)*a 4

 

우측 유도는

E ⇒ E*E 2

   ⇒ E*a 4

   ⇒ (E)*a 3

   ⇒ (E+E)*a 1

   ⇒ (E+a)*a 4

   ⇒ (a+a)*a 4

 

순서로 진행된다. 이때 좌측 유도와 우측 유도의 유도 트리는 각각 아래의 그림과 같은데,

그림 3. 좌/우측 유도트리

순서가 다를 뿐 유도트리는 같은 것을 확인할 수 있다.

 

 

 

 

모호성(Ambiguity)

문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도트리를 갖는다면 문법 G는 모호하다(ambiguous) 한다. 앞서 좌측 유도와 우측유도는 유도트리가 같다고 했다. 단 이는 모호성이 없는 문법의 경우에만 해당된다.

 

예: 문장 “if b then if b then a else a”에 대해 아래의 문법으로 유도를 진행한다고 가정하자.

 

S → if C then S else S

S → if C then S

S → a

C → b

그림 4. 모호성 예시 1

else 가 첫번 째 if문에 걸릴 수도, 두 번째 if문에 걸릴 수도 있다. 하나의 문법에 의해 두 개의 트리가 생겼으므로, 모호한 문법이라고 볼 수 있다.

 

또한 입력이 a + a * a 일 경우, 다음 문법으로 유도를 진행하면 E→ E +E | E * E | (E) | a

 

그림 5. 모호성 예시 2

위와 같이 두 가지의 트리가 나타날 수 있고, 마찬가지로 모호한 문법으로 볼 수 있다.

 

 

모호성 해결

같은 뜻을 가지는 동일한 문법을 생성하면 된다.

 

1. 연산자 우선 순위 도입

 

연산자마다 새로운 Non-terminal을 도입하되, Recursion을 left나 right 둘 중 하나만 두고 시작 심벌과 가장 가까운 쪽에 연산자 우선순위가 낮은 것을 둔다.

 

E→ E + E | E * E | (E) | a에 적용하면 아래의 문법이 완성된다.

 

E → E + T

E → T

T → T * F

T → F

F → ( E )

F → a

 

앞서 두 개의 유도 트리가 생성되었던 a + a * a 입력에 대해 새로운 문법을 적용하여 유도트리를 그리면 아래와 같다.

그림 6. 모호성 예시

좌측 유도 트리와, 우측 유도 트리가 같은 것을 확인할 수 있다.

 

2. 결합 법칙 도입

 

연산자 우선 순위를 도입한 동일한 문법을 만든다. 모든 연산자는 좌측, 또는 우측 결합이거나 결합이 생성되지 않는다.

  • Left: a + b + c = (a + b) + c
  • Right: a ^ b ^ c = a ^ (b ^ c)
  • Non: a < b < c 오류 (결합 불가)

 

원한다면 문법에서 Recursion을 잘 배치해서 결합법칙을 강제한다.

  • Left Recursion은 좌측 결합에 사용 (A → A + a | a)
  • Right Recursion은 우측 결합에 사용 (A → a^A | a)

 

 

 

 

유도를 이용한 구문 분석

그림 7. 구문분석


구문분석(파스)란 주어진 스트링이 정의된 문법에 의해 생성될 수 있는 지의 여부(적합성)를 결정하는 과정이다. 이를 위해서는 유도가 되는지 보면 된다.  올바른 문장에 대해서는 ‘문장 구조’를, 틀린 문장에 대해서는 오류 메시지를 나타낸다.

 

 

파스트리(parse tree)는 문장 구조를 나타내는 트리이다. 문장을 나타내는 생성 규칙을 적용한 유도 트리와 같은 모양의 트리이다.

  • 루트노드 : 정의된 문법의 시작 심벌
  • 중간노드: 각 생성 규칙의 좌측 nonterminal 심벌
  • 단말노드: 주어진 스트링을 생성하는 terminal 심벌

생성규칙번호 리스트는 문법의 생성 규칙을 통해 유도하는 과정에서 적용되어 온 일련의 생성 규칙 번호이다.

 

 

 

구문 분석의 두 가지 방법으로는 루트 노드로부터 시작하여 단말노드를 생성하며 확인하는 Top-down 방식과, 단말 노드로부터 루트 노드를 향하여 위로 생성하며 확인하는 Bottom-up 방식이 있다.

 

그림 8. top-down, bottom-up

 

 

 

좌파스는 좌측 유도 중 적용된 생성 규칙들의 리스트를 말하며, Top-down 방식은 좌측유도와 같은 순서의 생성규칙이 적용된다. 우파스는 우측유도 중 적용된 생성규칙 리스트의 역순을 말하며, Bottom-up 방식은 우측 유도의 역순의 생성규칙 적용과 같다.(입력 스트링의 왼쪽부터 매치하므로)

그림 9. 좌파스, 우파스

 

'CS > 컴파일러개론' 카테고리의 다른 글

[컴파일러개론] Lexical Analysis (어휘분석)  (0) 2025.11.08
[컴파일러개론] 개요  (1) 2025.10.25

티스토리툴바