Syntax Parser

HeeJune KIM·2024년 7월 17일

AST(추상 구문 트리)란?

AST(추상 구문 트리, Abstract Syntax Tree)는 소스 코드의 구조를 트리 형태로 표현한 것입니다. 각 노드는 소스 코드의 구성 요소를 나타내며, 트리의 구조를 통해 코드의 구문적 의미를 표현합니다. AST는 컴파일러와 인터프리터에서 코드 분석, 최적화, 변환 등에 사용됩니다.

예시

int x = a + b * c;

이 코드는 AST로 다음과 같이 표현될 수 있습니다:

   =
  / \
 x   +
    / \
   a   *
      / \
     b   c

참고 자료

Wikipedia - Abstract Syntax Tree

정규표현식이란?

정규표현식(Regular Expression)은 문자열에서 특정 패턴을 찾거나, 치환하거나, 추출하는 데 사용되는 도구입니다. 주로 텍스트 처리, 데이터 검증, 검색 및 교체 작업에서 많이 사용됩니다.

주요 구성 요소

리터럴 문자: 예: a, 1, $
메타 문자: 예: . (임의의 한 문자), * (0개 이상의 반복)
문자 클래스: 예: [abc]
경계: 예: ^ (문자열의 시작), $ (문자열의 끝)
그룹화: 예: (abc)

예시

이메일 주소를 검증하는 정규표현식:

^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$

참고 자료

Wikipedia - Regular Expression

컴파일러란?

컴파일러(Compiler)는 고급 프로그래밍 언어로 작성된 소스 코드를 컴퓨터가 이해할 수 있는 저급 언어(기계어)로 변환하는 프로그램입니다. 컴파일러는 코드의 번역뿐만 아니라 최적화, 오류 검출 등의 작업도 수행합니다. 컴파일 과정은 여러 단계를 거치며, 이 과정을 통해 실행 가능한 바이너리 파일을 생성합니다.

컴파일러의 주요 역할

어휘 분석(Lexical Analysis): 소스 코드를 토큰이라는 기본 의미 단위로 분리합니다.
구문 분석(Syntax Analysis): 토큰을 구문 트리(파스 트리)로 구성하여 문법을 확인합니다.
의미 분석(Semantic Analysis): 구문 트리의 의미를 해석하고, 타입 체크 및 변수 범위 확인 등의 작업을 수행합니다.
중간 코드 생성(Intermediate Code Generation): 구문 트리를 중간 표현으로 변환합니다.
최적화(Optimization): 중간 표현을 최적화하여 실행 속도를 높이거나 메모리 사용을 줄입니다.
코드 생성(Code Generation): 최적화된 중간 표현을 기계어 코드로 변환합니다.
어셈블리 및 링킹(Assembly and Linking): 기계어 코드를 실행 파일로 변환하고, 필요한 라이브러리와 링크합니다.

참고 자료

Wikipedia - Compiler

컴파일러 구조: Tokenizer, Lexer, Parser

Tokenizer

Tokenizer는 소스 코드를 가장 작은 의미 단위인 토큰으로 분리하는 단계입니다. 여기서 토큰은 변수, 연산자, 키워드, 숫자 등으로 구성됩니다. 예를 들어, int x = 5;라는 코드에서 int, x, =, 5, ;는 각각 하나의 토큰입니다.

Lexer

Lexer는 Tokenizer가 생성한 토큰을 받아 어휘 분석을 수행합니다. 각 토큰의 유형을 결정하고, 이를 기반으로 어휘적 오류를 처리합니다. 예를 들어, 토큰이 변수인지, 키워드인지, 연산자인지 등을 식별합니다.

Parser

Parser는 Lexer가 생성한 어휘 정보를 받아 구문 분석을 수행합니다. 구문 분석은 토큰의 순서를 바탕으로 문법을 확인하고, 이를 구문 트리(Syntax Tree)로 구성합니다. 구문 트리는 코드의 구조를 표현하며, 컴파일러가 다음 단계로 진행할 수 있도록 돕습니다.

예시

수식 a = b + c의 처리 과정:

Tokenizer: a, =, b, +, c 로 분리
Lexer: 토큰의 유형 결정 (식별자, 연산자 등)
Parser: 구문 트리 생성

   =
  / \
 a   +
    / \
   b   c

참고 자료

LL 파서와 LR 파서 비교

LL 파서

LL 파서는 입력을 왼쪽에서 오른쪽으로 읽고, 왼쪽에서 오른쪽으로 유도식을 생성하는 파서입니다. 주로 재귀 하향식(Recursive Descent) 파서로 구현되며, 문법의 예측과 백트래킹 없이 작동합니다. LL 파서는 문법 규칙이 제한된 언어에 적합하며, 구현이 간단하고 이해하기 쉽습니다.

LR 파서

LR 파서는 입력을 왼쪽에서 오른쪽으로 읽고, 오른쪽에서 왼쪽으로 유도식을 생성하는 파서입니다. 주로 하향식(Shift-Reduce) 파서로 구현되며, 더 복잡한 문법을 처리할 수 있습니다. LR 파서는 문법 규칙이 복잡한 언어에 적합하며, SLR, LALR, Canonical LR과 같은 다양한 변형이 있습니다.

LL 파서와 LR 파서의 차이점

구현 복잡성:
- LL 파서: 구현이 간단하고 이해하기 쉬움. 예측 가능한 문법에 적합.
- LR 파서: 구현이 복잡하고 이해하기 어려움. 더 복잡한 문법을 처리 가능.
처리 가능한 문법의 복잡성:
- LL 파서: 제한된 문법만 처리 가능.
- LR 파서: 더 복잡한 문법을 처리 가능.
사용 예:
- LL 파서: 소규모 언어 또는 제한된 문법을 가진 언어의 파싱에 사용.
- LR 파서: 대규모 언어 또는 복잡한 문법을 가진 언어의 파싱에 사용.

예시

LL 파서: 재귀 하향식 파서, 예: Predictive Parsing
LR 파서: 하향식 파서, 예: SLR, LALR, Canonical LR Parsing

참고 자료

문서 객체 모델 (DOM)이란?

문서 객체 모델(DOM, Document Object Model)은 HTML이나 XML 문서를 계층적 트리 구조로 표현한 것입니다. DOM은 브라우저가 웹 페이지를 구조화하고, 자바스크립트를 통해 동적으로 변경할 수 있게 합니다.

DOM 구조

DOM은 문서를 노드 트리로 표현합니다. 각 노드는 문서의 일부(요소, 속성, 텍스트 등)를 나타냅니다.

예시

다음 HTML 문서를 DOM으로 표현:

<!DOCTYPE html>
<html>
  <head>
    <title>Example</title>
  </head>
  <body>
    <h1>Hello, World!</h1>
  </body>
</html>

DOM 트리:

#document
  |-- html
      |-- head
      |   |-- title
      |       |-- "Example"
      |-- body
          |-- h1
              |-- "Hello, World!"

참고 자료

Wikipedia - Document Object Model

XML과 JSON 비교

XML

구조: 태그 기반의 계층적 구조
유연성: 임의의 태그 정의 가능
확장성: DTD나 XML Schema를 사용해 데이터 구조 정의 가능
크기: 태그로 인해 데이터 크기가 큼
사용 예: 문서 중심의 데이터(RSS, SOAP)

JSON

구조: 키-값 쌍 기반의 객체 구조
유연성: 제한된 데이터 타입 (숫자, 문자열, 배열 등)
확장성: JSON Schema 사용 가능
크기: 간결하고 데이터 크기가 작음
사용 예: 데이터 중심의 API(RESTful API)

비교

가독성: JSON이 더 간결하고 읽기 쉬움
파싱 속도: JSON이 더 빠름
표준화 및 호환성: XML이 더 다양한 표준 지원

참고 자료

DOM Parser

정의

DOM Parser는 XML이나 HTML 문서를 파싱하여 DOM 트리를 생성하는 파서입니다. DOM 트리는 문서의 구조를 트리 형태로 표현하며, 각 노드는 문서의 일부를 나타냅니다.

특징

메모리 사용: 문서 전체를 메모리에 로드하므로 메모리 사용량이 큼
임의 접근: 문서의 모든 노드에 임의로 접근 가능
수정 가능: DOM 트리를 수정하여 문서를 동적으로 변경 가능

예시

다음 XML 문서를 DOM Parser로 파싱:

<book>
  <title>XML Guide</title>
  <author>John Doe</author>
</book>

DOM 트리:

#document
  |-- book
      |-- title
      |   |-- "XML Guide"
      |-- author
          |-- "John Doe"

참고 자료

Wikipedia - DOM Parser

트리 형식으로 데이터 구조화하는 이유?

계층적 데이터 표현

트리 구조는 계층적 데이터를 직관적으로 표현할 수 있습니다. 노드 간의 부모-자식 관계를 명확하게 나타낼 수 있어 데이터의 구조와 의미를 쉽게 이해할 수 있습니다.

데이터 탐색 및 수정 용이성

트리 구조를 사용하면 데이터 탐색 및 수정이 용이합니다. 재귀적으로 노드를 탐색하고, 원하는 노드를 쉽게 찾을 수 있습니다. 또한, 노드를 추가하거나 삭제하는 작업이 간단합니다.

효율적인 데이터 처리

트리 구조는 데이터의 삽입, 삭제, 검색 등의 작업을 효율적으로 수행할 수 있게 합니다. 특히, 이진 탐색 트리나 AVL 트리와 같은 특정 트리 구조를 사용하면 데이터 처리 성능을 크게 향상시킬 수 있습니다.

다양한 응용

트리 구조는 다양한 분야에서 널리 사용됩니다. 예를 들어, 파일 시스템, 데이터베이스 인덱스, 컴파일러의 구문 분석, 웹 브라우저의 DOM 트리 등에서 트리 구조가 활용됩니다.

예시

root
  |-- home
  |   |-- user1
  |   |   |-- file1.txt
  |   |   |-- file2.txt
  |   |-- user2
  |       |-- file3.txt
  |-- etc
      |-- config.txt

참고 자료

Wikipedia - Tree Data Structure

HeeJune KIM

이전 포스트

리눅스

다음 포스트

Syntax Parser

AST(추상 구문 트리)란?

예시

참고 자료

정규표현식이란?

주요 구성 요소

예시

참고 자료

컴파일러란?

컴파일러의 주요 역할

참고 자료

컴파일러 구조: Tokenizer, Lexer, Parser

Tokenizer

Lexer

Parser

예시

참고 자료

LL 파서와 LR 파서 비교

LL 파서

LR 파서

LL 파서와 LR 파서의 차이점

예시

참고 자료

문서 객체 모델 (DOM)이란?

DOM 구조

예시

참고 자료

XML과 JSON 비교

XML

JSON

비교

참고 자료

DOM Parser

정의

특징

예시

참고 자료

트리 형식으로 데이터 구조화하는 이유?

계층적 데이터 표현

데이터 탐색 및 수정 용이성

효율적인 데이터 처리

다양한 응용

예시

참고 자료

리눅스

메모리

0개의 댓글

메모리