jinw00

[컴파일러] Top-down 파싱 & LL 파싱

👑 Top-down 파싱

구문 분석의 한 유형인 Top-down 파싱은 시작 심벌로부터 터미널 노드쪽으로 파스트리를

구성하는 것으로 입력 문자열에 대한 좌측 유도 과정이다. 유도 과정에서 생성 문자열과 입력 문자열을

비교하며, 생성 규칙을 적용해 나가는 방식이며, 백트래킹 기법이 사용된다.



👑 LL 파싱

LL 파싱은 컴파일러에서 사용하는 Top-down 파싱 기법 중 하나로, 입력 문자열을 왼쪽에서

오른쪽으로 한 글자씩 분석하고, 좌파스(Leftmost derivation)를 생성하는 방법이다. LL 파싱은

LL(k)로 표현되며, 여기서 L은 Left-to-right(입력의 왼쪽에서 오른쪽으로 분석), 두 번째 L은

Leftmost derivation(좌파스 유도)을 의미하고, k는 파서가 한 번에 미리 읽어야 할 입력

심볼의 수를 나타낸다.

LL 파싱은 입력 문자에 따라 생성 규칙이 결정적으로 선택되므로, 백트래킹이 필요하지 않다.

하지만, 이를 위해 입력 문자마다 적용될 생성 규칙을 미리 알고 있는 상태에서 시작해야 하며,

이를 위해 FIRST 집합, FOLLOW 집합, LOOKAHEAD 등이 사용된다.



💡 FIRST 집합

FIRST는 nonterminal로 부터 유도되어 첫 번째로 나타날 수 있는 terminal의 집합이다.

예를 들어, 아래와 같은 생성 규칙이 존재한다고 했을 때, 생성 규칙의 각 nonterminal의

FIRST 집합을 구할 수 있다.


FIRST 구하는 방법

  • X가 terminal이면 FIRST(X)는 자기 자신이다.

    • $ FIRST(e) = \lbrace e \rbrace $


  • X → aα 형태의 생성규칙이 존재하면, a는 FIRST(X)에 포함된다.

    • S → aXb 를 통해 $ FIRST(S) = \lbrace a \rbrace $ 가 포함된다.


  • X → ε 의 형태 즉, X가 nullable하다면, ε는 FIRST(X)에 포함된다.

    • A → a | ε 라면, $ FIRST(A) = \lbrace a, ε \rbrace $


  • $ X → Y_1 Y_2 …Y_k $ 인 생성규칙이 존재할 때, $ FIRST(X) = FIRST(X) ∪ FIRST(Y_1 Y_2 …Y_k) $

    • $ FIRST(Y_1 Y_2 …Y_n) = FIRST(Y_1) ⨁ FIRST(Y_2) ⨁ … ⨁ FIRST(Y_n) $

⨁ (Ring Sum) : 두 집합 간의 연산에 사용되는 ⨁ 는 다음과 같이 정의할 수 있다.

if ε ∉ A then A ⨁ B = A
if ε ∈ A then A ⨁ B = (A - {ε}) ∪ B

A의 nullable 여부에 따라 계산 결과가 정해진다.


FIRST 예시



💡 FOLLOW 집합

nonterminal이 ε-생성 규칙을 갖는 경우 FIRST만으로는 생성규칙을 결정적으로 선택할 수

없다. 따라서, nonterminal의 다음에 나오는 심벌에 따라 어느 생성 규칙으로 유도할 것인가를

결정하는 것이 필요하다.

FOLLOW(X)란 시작 심벌로부터 유도될 수 있는 모든 문장 형태에서 X 다음에 나오는

terminal 심벌들의 집합이다. FOLLOW 집합을 구할 때 기호 $가 사용되는데, 이것은 입력 문자열의

끝을 나타내는 기호이다. 시작 심벌은 초기값으로 $를 가져야 한다.


FOLLOW 구하는 방법

  • 시작 심벌은 초기값으로 $를 갖는다.

    • FOLLOW(S) = {$}


  • $ A →αBβ, β ≠ ε $ 의 형태일 때

    • $ FOLLOW(B) = FOLLOW(B) ∪ (FIRST(β) - \lbrace ε \rbrace) $


  • $ A → αB $ 또는 $ A → αBβ $ 에서 FIRST(β)에 ε이 속하는 경우 (β가 nullable한 경우)

    • A의 FOLLOW 전체를 B의 FOLLOW에 추가


FOLLOW 예시



👑 LL 조건 & LL(1) 문법

LL 조건이란, 문법이 LL 파서로 파싱 가능함을 나타내는 조건으로, 다음과 같다.

  • 어떤 nonterminal에 대한 생성 규칙이 두 개 이상일 때, 그 생성 규칙의 FIRST의 교집합이
    공집합이어야 한다.

    • $ A → α | β $   에 대해   $ FIRST(α) ∩ FIRST(β) = ∅ $


  • 만약 한 생성 규칙이 ε를 유도할 수 있다면, FOLLOW와 FIRST도 다른 집합이어야 한다.

    • $ ε ∈ FIRST(α) \; then \; FOLLOW(A) ∩ FIRST(β) = ∅ $


  • 생성 규칙의 FIRST에 공통 원소가 없으면, 각 순간 적용할 생성 규칙이 유일하게 결정된다.



LL(1) 파서는 1개의 토큰을 미리 보고 파싱을 진행하는 방식이다. LL(1) 문법이란, 주어진 문법이

한 개의 lookahead 토큰만으로도 어떤 규칙을 사용할지 결정할 수 있는 문법을 의미한다.

어떠한 문법이 아래와 같다면, 해당 문법은 LL(1) 문법이 될 수 없다.

  • 모호한 문법

  • left factoring이 가능한 부분이 존재

  • left recursive한 문법

따라서 어떠한 문법을 LL(1) 문법으로 만들기 위해서는 위의 3가지를 없애야만 한다.



💡 Left Factoring

여러 규칙이 같은 심볼로 시작하는 경우, 공통된 부분을 새로운 nonterminal을 도입하여 하나로

묶어주는 방법이다. 아래의 경우를 예로 들면, a가 공통되므로, 새로운 nonterminal A'을 도입하여

인수분해 하듯이 처리해줄 수 있다.

A → aα | aβ

-------------
A → aA'
A' → α | β



💡 Left Recursion

좌측 재귀란 nonterminal 심볼이 자기 자신을 왼쪽에서 참조하는 경우를 말한다.

좌측 재귀는 직접 좌측 재귀와 간접 좌측 재귀로 나눌 수 있다.


  • 직접 좌측 재귀
A → Aα | β

위와 같은 경우 무한 루프로 빠질 수 있는데, 좌측 재귀를 우측 재귀로 바꿔주는 방법으로 해결 가능하다. 

A → βA'
A' → αA' | ε


  • 간접 좌측 재귀
S → Aa | b
A → Ac | Sd | e9da

현재 S → A, A → S 형태로 간접적인 무한 재귀가 발생할 수 있는데, 간접 좌측 재귀의 경우

직접 좌측 재귀로 변환한 후, 우측 재귀로 바꿔주는 방법으로 해결할 수 있다. 간접 좌측 재귀를

변환하는 방법은 생성 규칙을 대입해보면 된다.

S → Aa | b
A → Ac | Aad | bd | e

----------------------
S → Aa | b
A → (bd | e) A'
A' → (c | ad) A' | ε

----------------------
S → Aa | b
A → bdA' | eA'
A' → cA' | adA' | ε



💡 LOOKAHEAD

LOOKAHEAD는 파싱 과정에서 어떤 규칙을 적용할지 결정하기 위해 미리 살펴보는 토큰이다.

즉, 어떤 생성 규칙이 적용되었을 때, 맨 처음 나타날 수 있는 terminal symbol을 말한다.

다음의 문법을 예시로 들면, 이 문법은 시작 기호 S가 Ac 또는 Bd로 파생될 수 있고, A는 a,

B는 b로 파생된다. LOOKAHEAD(S → Ac)는 이 규칙이 적용되었을 때 첫 번째로 나올 수 있는

terminal symbol을 의미하고 A → a 이므로 LOOKAHEAD(S → Ac)는 FIRST(A), 즉 {a}가 된다.

똑같은 방법으로 LOOKAHEAD(S → Bd)도 구해줄 수 있다. S → B d에서 먼저 나올 수 있는 기호는

B이며 B의 파생 규칙을 보면, B → b이다. 그러므로, LOOKAHEAD(S → Bd)는 FIRST(B),

즉 {b}가 된다.

S → A c | B d
A → a
B → b

LOOKAHEAD(S → Ac) = {a}
LOOKAHEAD(S → Bd) = {b}



💡 Strong LL(1) 조건

임의의 생성 규칙 A → α | β 에 대해 다음을 만족한다면, strong LL 조건이라 한다.

LOOKAHEAD(A → α) ∩ LOOKAHEAD(A → β) = ∅

즉, 주어진 상황에서 LOOKAHEAD가 유일하게 결정되며, 이는 LL(1)과 동일한 효과를 가진다.



👑 LL(1) 파서 구현

LL(1) 파서는 주어진 문법을 왼쪽에서 오른쪽으로 읽으면서, 왼쪽 유도(Leftmost derivation)에

따라 한 단계씩 유도하는 파서이다. 구현 방법으로는 Recursive Descent Parser와 Predictive

Parser 두 가지가 존재한다.



💡 Recursive descent parser

  • 각 nonterminal에 대해 재귀적인 함수 호출을 이용하여 파싱을 수행한다.

  • 각 문법 규칙에 대해 별도의 함수를 정의하며, 규칙을 만족하는지 검사한다.

  • 구현이 직관적이고 간단하지만, 생성 규칙이 바뀌면 구문 분석기를 고쳐야 한다.



💡 Predictive parser

  • LL(1) 문법을 사용하여 파싱 테이블을 생성하고, 이를 기반으로 입력을 분석하는 방식이다.

  • 생성 규칙이 바뀌더라도 파싱 테이블만 수정할 뿐 구문 분석기는 고칠 필요가 없다.

  • 파싱 테이블 생성을 위해 FIRST, FOLLOW 집합을 계산하며, 스택을 사용하여 파싱을 수행한다.


파싱 테이블

파싱 테이블은 nonterminal, terminal, 생성 규칙으로 이루어지며, 다음과 같은 규칙에 따라 구성된다.

$ a ∈ LOOKAHEAD(A → α) $ 이면 $ M[A, a] := A → α $

쉽게 설명하면,

  • nonterminal 기호를 기준으로, 생성 규칙을 살핀다.

  • nonterminal A에 대한 생성 규칙 A → α 에서 FIRST(α)에 a가 포함된다면, A, a가 만나는
    칸에 A → α 를 채운다.

  • 만약 FIRST(α)에 ε이 포함된다면, 모든 b ∈ FOLLOW(A)에 대해 A, b 칸을 채운다.


예시



👑 문제

1. 다음 문법에서 FIRST, FOLLOW 집합을 구하시오.


2. 다음 문법이 LL(1) 문법인지를 판별하여라.
⑴
S → Abc | aAcb
A → b | c | ε

⑵
S → aAS | b
A → a | bSA

Categories:

Updated:

Leave a comment

You may also enjoy