Mypy의 동작 방식: #2-side AST가 왜 필요할까?
Introduction
이 포스트에서는 대규모 파이썬 프로젝트에서 특정 함수의 호출자를 찾는 mypyind를 작성하면서 mypy에 대해 부차적으로 공부했던 내용들을 정리했습니다.
이 내용은 pycon 발표 덧붙인 설명입니다.
이 포스트는 아래 포스트들로 연결됩니다.
Mypy의 동작 방식: #2-side mypy는 AST가 왜 필요할까?(현재 글)
Overview
이전 포스트에서는 mypy가 어떻게 파일을 파싱하는지에 대해 알아보았습니다. 이번 포스트에서는 mypy가 이후에 의미 분석을 하려면 왜 AST가 필요한지 알아보겠습니다. Python의 문법에 연관된 formal grammar 및 context free grammar에 대해 알아보고, AST가 왜 필요한지 알아보겠습니다.
Python의 문법
Formal grammar
Formal grammar는 언어의 syntax를 정의하는데 사용되는 형식화된 표기법입니다. Formal grammar는 의미를 설명하지 않고, 언어의 형태만을 나타냅니다.
Formal grammar는 “start symbol”에서 시작해서 rewriting rule을 적용해 언어를 생성합니다. 이때, rewriting rule은 한 symbol(들)을 다른 symbol(들)로 바꾸는 규칙입니다. 이러한 규칙을 적용해 언어를 생성하는 과정을 derivation이라고 합니다.
Context free grammar(CFG)
Context free grammar(CFG)는 formal grammar의 한 형태로, 좌항에 single nonterminal 이 있고 우항이 제한되지 않은 형태의 문법입니다.
CFG는 이렇게 표현됩니다.
A -> alpha
A: nonterminal
alpha: terminal 또는 nonterminal 로 구성된 문자열
이 때 nonterminal이란 확장할 수 있는 알파벳이고, terminal은 더 이상 확장할 수 없는 알파벳입니다.
CFG 예시
예를 들어, 아래와 같은 문법은 context free grammar입니다.
S -> aSb
S -> ab
여기서 S가 nonterminal입니다. 이 문법은 a와 b로 이루어진 문자열을 생성합니다. S가 aSb로 확장되거나 ab로 확장됩니다.
a와 b는 terminal입니다. a나 b가 더 이상 확장되지 않습니다.
이 Context free grammar를 이용해서 어떤 string이 문법에 맞는지를 체크할 수 있습니다. 예를 들어 아래 문장은 위 문법에 맞습니다.
aaabbb
이 문장에 위 문법을 적용하면 아래와 같이 derivation이 가능합니다.
S -> aSb -> aaSbb -> aaabbb
Syntax tree
위 derivation 과정을 트리로 표현할 수도 있습니다.
S
├── a
├── S
│ ├── a
│ ├── S
│ │ ├── a
│ │ └── b
│ └── b
└── b
이 트리는 문장을 생성하는 derivation을 표현합니다. 이 트리를 syntax tree라고 합니다.
AST
하지만 syntax tree는 괄호나 쉼표같은 컴파일러에게는 필요 없는 내용도 포함합니다. 이런 내용을 추상화시키고 구조적 의미만 담고있는 트리로 만든 것이 abstract syntax tree입니다.
예를 들어 이런 문장이 있다고 했을 때,
def f(a: int, b: int) -> int:
return a + b
Syntax tree를 만든다면 이렇게 표현되겠지만,
def
├── f
├── (
├── a
├── :
├── int
├── ,
├── b
├── :
├── int
├── )
├── ->
├── int
├── :
└── return
├── a
├── +
└── b
AST로 표현하면 이렇게 표현됩니다.
FunctionDef
├── f
├── arguments
│ ├── a
│ ├── b
│ └── int
├── int
└── Return
├── BinOp
│ ├── a
│ ├── +
│ └── b
└── int
위의 syntax tree에서 def, :, ->, return 같은 것들은 AST에서는 노드로 표현되지 않습니다. 이렇게 구조만 표현되어있는 트리를 AST라고 합니다.
이렇게 만들어진 AST는 코드의 구조를 표현하므로, AST를 해석한다는 것은 코드의 구조를 해석한다는 것과 거의 동일한 의미입니다.
Wrap up
이번 포스트에서는 mypy가 AST를 사용하는 이유에 대해 알아보았습니다. 그렇다면 이 AST로 어떤 일을 할 수 있을까요? AST를 어떻게 사용할까요?
다음 포스트(Mypy의 동작 방식: #3 의미 분석)에서는 mypy가 AST를 이용해 의미 분석을 하는 방법에 대해 알아보겠습니다.