파싱에 대해 알아보자!

윤효준·2024년 9월 12일
컴파일러
0

콤퓨타 공부

목록 보기
9/17

1. 파싱이란???

컴퓨터 프로그램이 입력된 데이터(특히 텍스트)를 분석하여 구조화된 정보로 변환하는 과정을 이야기한다. 이 과정에서 입력된 데이터를 특정한 문법에 맞춰 해석하고 그 결과로 의미 있는 구조를 추출한다. 파싱은 주로 프로그래밍 언어나 파일 형식 또는 데이터 포맷을 처리할 때 사용된다.

2. 파싱의 주요 개념

새로운 언어를 만든다고 가정하고 3 + 5 * 2, 3 + 5 & 2와 3 + * 5를 파싱하면서 주요 개념들을 설명하겠습니다!!

2.1 문법(Grammer)

특정 언어에서 사용할 수 있는 구조를 정의한 규칙들의 집합이다. 프로그래밍 언어나 데이터 포멧의 구조가 여기에 해당한다. 보통 정규 문법(Regular Grammar), 상위 문법(Context-Free Grammar) 등의 문법이 사용된다.

문법에 대한 더 자세한 내용은 문법에 대한 게시글 추가 예정에서 보시면 됩니다!

문법 정의

  • Expression -> 숫자 또는 두 Expression을 연산자로 연결한 형태
  • Number -> 정수
  • Operator -> 덧셈 + 또는 곱셈 *

표현

Expression -> Number
Expression -> Expression Operator Expression
Number -> [0-9]+ //+는 정규 표현식의 일부로 앞의 패턴이 하나 이상 반복될 수 있다는 의미다.
Operator -> '+' | '*'

연산자 우선순위(*가 +보다 우선)을 적용하면 다음과 같이 표현할 수 있다.

Expression -> Expression + Term
Expression -> Term
Term -> Term * Factor
Term -> Factor
Factor -> Number
Number -> [0-9]+

2.2 어휘 분석(Lexical Analysis)

데이터를 작은 단위(토큰)로 나누고 각각의 단위가 어떤 의미를 갖는지 파악하는 단계이다.

2.3 토큰(Token)

어휘 분석의 결과물로 입력 데이터에서 추출한 의미 있는 최소 단위이다. 예를 들어 숫자, 연산자, 키워드 등이 모두 토큰에 해당할 수 있다.

어휘 분석 및 토큰 추출

먼저 입력한 문장을 어휘 분석기로 처리하여 토큰(Token)으로 분리한다.

// 3 + 5 * 2의 토큰 추출
[Number(3), Operator(+), Number(5), Operator(*), Number(2)]
// 3 + * 5
[Number(3), Operator(+), Operator(*), Number(5)]
// 3 + 5 & 2의 토큰 추출
//어휘 분석기로 처리하는 과정에서 문법에 없는 문자(`&`)가 있음을 인지하고
//어휘 분석기에서 유효하지 않은 토큰 오류를 발생시킨다.

2.4 구문 분석(Syntax Analysis)

파싱 과정에서 데이터가 주어진 문법을 만족하는지 확인하는 단계이다. 만약 문법에 맞지 않으면 오류가 발생한다.

2.5 구문 트리(Parse Tree 또는 Syntax Tree)

파싱 과정에서 생성되는 트리 구조로 문법에 따라 입력 데이터를 구조화한 결과이다.
(파싱 종류)를 먼저 참고하고 오자!

3 + 5 * 2 파싱하기

하향식 파싱 과정(재귀적 하향 파서 사용)

아래 문법을 참고해서 3 + 5 * 2를 파싱해보자!

Expression -> Expression + Term
Expression -> Term
Term -> Term * Factor
Term -> Factor
Factor -> Number
Number -> [0-9]+
  • Expression 규칙을 호출한다. Expression은 두 가지 형태로 정의되었는데 이때 첫번째로 Term을 처리해야 한다.
  • Term은 Factor * Term 또는 Factor로 정의된다. 파서는 Factor를 처리하려고 시도한다.
  • Factor는 Number로 정의되어 있으므로 3이 숫자인지 확인하고 Factor를 처리한다.
  • Expression으로 돌아와 + 연산자를 처리한 후 Expression의 두 번째 부분인 5 * 2를 처리해야 하므로 다시 Expression 규칙을 호출한다.
  • 5 * 2를 파싱하면서 Term은 Factor * Term 규칙을 따른다. 따라서 Factor를 먼저 처리하고 그 다음에 * 연산자 처리 후 마지막으로 Term을 처리한다.
  • Factor는 Number로 정의되어 있고 5가 숫자인지 확인한다. 이때 5를 Factor로 처리하고 다음으로 넘어간다!
  • 곱셈 연산자 *를 처리한 후 Term의 두 번째 부분인 Factor를 처리해야 한다.
  • Factor는 Number이므로 2가 숫자인지 확인하고 Factor로 처리한다.
  • 모든 요소를 처리했고 모든 부분이 주어진 문법에 맞게 파싱되었다. 파싱을 완료하면서 전체 수식의 구조를 표현하는 구문 트리를 생성할 수 있다.

구문 트리 예시

Expression
├── Expression (3)
├── Operator (+)
└── Term
    ├── Factor (5)
    ├── Operator (*)
    └── Term
        └── Factor (2)

상향식 파싱 과정(LR 파서 사용)

  • Shift(현재 토큰을 읽고 스택에 푸시하는 동작)와 Reduce(스택에 쌓여 있는 토큰들을 하나의 문법 규칙으로 묶어 더 높은 수준의 구조로 변환하는 동작)를 통해 구문을 처리하며 스택에 요소를 쌓는다.

  • 우선순위 테이블: 각 연산자의 우선순위를 지정하는 테이블을 만들어 파싱 과정에서 Shift/Reduce 동작을 결정할 때 참조한다. 예를 들어 *가 +보다 우선이기 때문에 *를 먼저 Reduce하고 나중에 +를 처리한다.

  • 결합 규칙(Associativity): 연산자의 결합 방향(왼쪽 결합성 또는 오른쪽 결합성)을 정의하, 같은 우선순위의 연산자들이 어떻게 결합해야 하는지 결정한다. 덧셈과 곱셈은 왼쪽 결합성이므로 같은 우선순위의 연산자들은 왼쪽에서 오른쪽으로 처리된다.

  • 동작: Shift를 통해 3을 스택에 넣는다.

    • 스택: [3]

  • 동작: 3을 Number로 Reduce

    • 스택: [Number]

  • 동작: Number를 Expression으로 Reduce

    • 스택: [Expression]

  • 동작: Shift를 통해 +을 스택에 넣는다.

    • 스택: [Expression, +]

  • 동작: Shift를 통해 5을 스택에 넣는다.

    • 스택: [Expression, +, 5]

  • 동작: 5를 Number로 Reduce

    • 스택: [Expression, +, Number]

  • 동작: Number를 Expression으로 Reduce

    • 스택: [Expression, +, Expression]

  • 동작: Shift를 통해 *을 스택에 넣는다.

    • 스택: [Expression, +, Expression, *]

  • 동작: Shift를 통해 2을 스택에 넣는다.

    • 스택: [Expression, +, Expression, *, 2]

  • 동작: 2를 Number로 Reduce

    • 스택: [Expression, +, Expression, *, Number]

  • 동작: Number를 Expression으로 Reduce

    • 스택: [Expression, +, Expression, *, Expression]

  • 동작: Expression * Expression을 Expression으로 Reduce

    • 스택: [Expression, +, Expression]

  • 동작: Expression + Expression을 Expression으로 Reduce

    • 스택: [Expression]

구문 트리 예시

Expression
├── Expression (3)
├── Operator (+)
└── Expression
   ├── Expression (5)
   ├── Operator (*)
   └── Expression (2)

3 + * 5 파싱하기

하향식 파서(재귀적 하향 파서 사용)

  • Expression 규칙을 호출하여 3으로 시작하는 문장이므로 Expression -> Term을 호출한다.
  • Term 호출하여 3을 파싱한다.
  • 3이 Factor인지 확인한다.
  • 다음 토큰 +를 만나 +는 Expression -> Expression + Term을 적용한다.
  • Term을 처리하려는데 현재 입력이 * 5이고 Term의 첫 번째 토큰은 Factor가 와야 하는데 *가 나왔으므로 오류를 발생한다.

상향식 파서(LR 파서 사용)

  • 동작: Shift를 통해 3을 스택에 넣는다.

    • 스택: [3]

  • 동작: 3을 Number로 Reduce

    • 스택: [Number]

  • 동작: Number를 Expression으로 Reduce

    • 스택: [Expression]

  • 동작: Shift를 통해 +을 스택에 넣는다.

    • 스택: [Expression, +]

  • 다음 동작을 수행하려고 하는데 파서는 + 뒤에 Term을 기대한다. 이때 Term은 Factor로 시작해야 하고 Factor는 Number여야 한다. 근데 다음 입력은 *이다. 그렇기에 *는 문법적으로 Term의 시작 토큰이 될 수 없고 Shift와 Reduce 중 어느 것도 수행할 수 없다. 이 상황은 Shift/Reduce 충돌로 인식되며 파서는 오류로 검출한다.

2.6 추상 구문 트리(Abstract Syntax Tree)

  • 구문 트리 (Parse Tree) : 문법에 충실하여 입력된 코드를 문법 규칙에 따라 세밀하게 표현한 트리이다. 모든 문법적 요소가 포함되며 각 단계에서 규칙이 어떻게 적용되었는지를 보여준다.

  • 추상 구문 트리 (AST) : 구문 트리에서 불필요한 문법적 요소를 제거하고 코드의 의미를 간결하게 표현한 트리이다. 실행이나 최적화를 위해 필요한 핵심 정보만 남긴다.

그렇기에 단순화, 의미 중심 표현, 코드 실행 최적화를 위해 구문 트리에서 추상 구문 트리로 바꾸는 과정이 필요하다.

아래의 구문 트리를

Expression
├── Expression (3)
├── Operator (+)
└── Expression
    ├── Expression (5)
    ├── Operator (*)
    └── Expression (2)

이렇게 추상 구문 트리로 바꿀 수 있다.

   +
  / \
 3   *
    / \
   5   2

해당 트리를 postorder traversal(후위 순회)로 방문해주면 된다!

트리 탐색법이 더 궁금하다면 트리 탐색 방법에 대해 알아보자!을 참고하자!!

3. 파싱의 종류

3.1 하향식 파싱(Top-down Parsing)

하향식 파싱은 문법의 상위 규칙에서 시작하여 점점 더 작은 부분으로 나누어가는 방식이다. 재귀적 하향 파싱이 대표적인 방법으로 문법 규칙을 재귀적으로 호출해가며 파싱을 진행한다.

3.1.1 하향식 파싱의 진행 과정:

  1. 문법의 최상위 규칙(루트 느드)을 설정:

    • 하향식 파싱은 가장 상위 규칙에서 시작한다. 이 방식의 핵심은 전체 구조를 먼저 정의하고 그 구조가 문법에 맞는지 점검하는 것이다.
    • 예를 들어 수식을 파싱할 때는 가장 먼저 Expression이라는 상위 규칙에서 시작한다.

    왜 상위 규칙부터 시작할까??

    • 상위 규칙에서 시작하면 문장을 전체적으로 보는 시각을 유지할 수 있다.
    • 전체 구문의 틀이 맞는지 먼저 확인하는 것이다.
      이 접근 방식은 트리 구조의 루트 노드를 먼저 만들어놓고 그 아래로 차례대로 자식 노드를 추가해 나가는 방식이다.

  2. 하위 규칙으로 내려가며 재귀적으로 분석:

    • 상위 규칙에서 각 하위 요소(자식 노드)를 재귀적으로 분석한다. 예를 들어 Expression이 Number + Number라는 규칙을 따른다면 Number 규칙을 재귀적으로 호출해서 각각의 값을 확인한다.

    왜 재귀적으로 진행할까??

    • 재귀적인 방식은 복잡한 문법을 자연스럽게 처리할 수 있는 강력한 방법이다.
    • 각 하위 요소를 다시 분석할 필요가 있을 때 재귀적으로 호출함으로써 문법의 구조를 더 세밀하게 파악할 수 있다.

  3. 각 규칙이 맞는지 확인:

    • 파서는 문법 규칙에 맞는지 확인하면서 파싱을 진행한다. 예상된 구조와 실제 입력이 일지하지 않으면 그 즉시 오류를 반환한다.

    • 예를 들어 3 + 5를 파싱할 때 + 연산자 뒤에는 Expression이 와야 하지만 예상하지 못한 문자가 나오면 오류가 발생한다.

3.1.2 하향식 파싱의 특징

  • 예측 기반: 상위 구조를 예측하고 그것이 맞는지 확인하는 과정에서 오류를 검출한다.

  • 문법 규칙에 강하게 의존: 문법에 잘 맞는지 한 단계씩 재귀적으로 확인하기 때문에 문법 규칙이 명확하고 단순한 경우에 적합하다.

  • 좌측 재귀 문제: 좌측 재귀가 있는 문법에서는 무한 루프에 빠질 수 있어 재귀적 하향 파서가 실패할 수 있다.

예시를 들어 좌측 재귀 문제를 더우 자세히 설명하겠다.

Expression -> Expression + Term | Term
Term -> Number
Number -> [0-9]+

해당 문법에서 Expression은 다시 Expression + Term이라는 형태로 시작하기에 좌측 재귀(A가 다시 A로 시작하는 형태)를 포함하고 있다.
그럼 Expression을 파싱하려고 하자마자 다시 Expression + Term을 파싱해야 하고 이는 또 다시 Expressioin을 호출하기에 무한 루프에 빠지게 된다!

3.2 상향식 파싱(Bottom-up Parsing)

상향식 파싱은 입력 데이터를 작은 단위에서부터 점차 상위 규칙으로 확장해가며 문법을 분석하는 방식이다. 가장 대표적인 알고리즘은 LR 파서로 대규모 컴파일러에서 자주 사용된다.

3.1.1 상향식 파싱의 진행 과정:

  1. 토큰화된 데이터를 분석:

    • 상향식 파싱은 입력된 문장을 먼저 어휘 분석하여 각 토큰을 추출한다.

  2. 토큰을 결합해 상위 구조로 확장:

    • 파서는 각 토큰을 결합하여 상위 구조를 만들어 간다.

  3. 각 규칙이 맞는지 확인:

    • 각 단계에서 문법 규칙에 맞지 않으면 그때 바로 오류를 반환한다.

3.1.2 상향식 파싱의 특징

  • 데이터 기반: 상위 구조를 미리 예측하지 않고 실제로 입력된 데이터를 분석해 문법 구조를 완성해 나간다.

  • 복잡한 문법 처리 가능: 상향식 파싱은 복잡한 문법도 처리할 수 있으며 특히 LR 파서는 문법의 모호성을 잘 처리한다.

  • 단계적 확장: 작은 단위에서 시작해 점차 상위 구조로 확장해 나가는 방식으로 오류 방생 시 그 지점에서 멈춘다.

  • 파싱은 컴파일러, 데이터 처리, 웹 스크레이핑 등 다양한 분야에서 활용된다.
    특히 프로그래밍 언어의 구문 분석이나 데이터 형식의 해석에 필수적인 역할을 하며 올바른 파싱을 통해 데이터의 정확한 이해와 처리가 가능하게 한다!
profile
윤효준
작은 문제를 하나하나 해결하며, 누군가의 하루에 선물이 되는 코드를 작성해 갑니다.
이전 포스트

브라우저 화면 랜더링 과정

다음 포스트

트리 탐색 방법에 대해 알아보자!

0개의 댓글