Python Virtual machine(PVM)-1

Compiling Python Source Code

1. 파이썬 코드를 파트 트리로 파싱

2. 파스 트리를 AST(Abstract syntax tree)로 변환한다.

3. 심볼테이블을 생성

4. AST로 부터 코드 오브젝트 의 생성. 이 단계는

  1) AST를 CFG(Control Flow Graph)로 변환

  2) CFG로 부터 코드 오브젝트를 내놓는다(emitting)

 

소스 코드를 파스 트리로 파싱하고 파스트리를 AST로의 변환은 표준 과정이고 파이썬은 복잡한 늬앙스를 도입할 수 없다. 따라서 AST에서 CFG로의 변환과 CFG로 부터 코드 오브젝트를 내보내는 것(Emission)에 집중한다. 

 

From Source To Parse Tree

파이썬 파서는 책의 설명을 기반으로 한 LL(1) 파서이다.  Grammar/Grammar 모듈은 파이썬 언어의 EBNF(Extended Bckus-Naur Form) 문법 사양을 포함한다.

커맨드라인의 인터프리터에 전달하는 모듈이 실행될 때 PyParser_ParseFileObject 함수를 호출하여 파싱을 시작한다. 이 함수는 인수로 모듈 파일 이름을 전달하는 PyTokenizer_FromFile 토큰화 함수를 호출한다. 토큰화 함수는 모듈의 내용을 분해하여 적법한 파이썬 토큰이나 부적법한 값을 찾았을 때 예외를 던진다.

 

Python Tokens

파이썬 코드는 토큰으로 구성된다. 예를 들어 return 이란 단어는 키워드 토큰, 리터럴 -2는 숫자 상수 토큰이다. 파이썬 코드를 파싱하는 동안 첫 번째 작업은 소스코드를 토큰화(tokenize)하는 것이다. 파이썬은 다음과 같은 토큰이 있다.

 

1. identifiers: 프로그래머에 의해 정의되는 이름이다. 함수 이름, 변수 이름, 클래스 이름 등을 포함한다. 파이썬 문서에 명시된 것 처럼 identifiers의 규칙을 반드시 따른다. 

2. operators: +, *, /, %과 같이 값을 계산하고 결과를 생성하는 특별한 심볼이다.

3. delimiters: 이 그룹 기호는 표현을 그룹화하고, 구분자와 할당을 제공한다. ex) (, ), {, }, =, *= 등등

4. literals: 일부 타입에 대한 상수 값을 제공하는 기호. 문자열과 바이트 리터럴인 "Fred", b"Fred"와 정수 리터럴을 초함하는 숫자 리터럴인 2, 1e100과 같은 실수 리터럴 그리고 10j와 같은 허수 리터럴이 있다.

5. comments: 해쉬 심볼로 시작하는 문자열 리터럴. Comment 토큰은 항상 physical 라인의 끝에서 끝난다.

6. NEWLINE: logical 라인의 끝을 표기하는 특별한 토큰

7. INDENT 와 DEDENT: 혼합문을 그룹화하는 들여쓰기 레벨을 나타낼 때 사용하는 토큰

---

※ physical line이란 소스 코드에서 한 줄을 의미.

※ logical line이란 파이썬에서 문장을 나누는데 사용하는 개념 

print("Hello,")  # 물리적 줄 1
print("world!")  # 물리적 줄 2

# 논리적 줄 1로 물리적 줄 2개 사용
a = 5 + 3 \
    + 2

# 논리적 줄 1로 물리적 줄 2개 사용
b = [1, 2, 3,
     4, 5, 6]

---

토큰의 그룹은 logical 라인을 구성하는 NEWLINE 토큰에 의해 묘사된다. 그런 이유로 우리는 파이썬 언어를 NEWLINE 토큰에 의해 묘사된 각 logical 라인을 가지는 "logical 라인 시퀀스의 구성"이라 부를 수 있다. 이러한 logical 라인은 파이썬 상태문을 매핑한다. 또한 각 logical 라인은 각각 라인 끝 시퀀스로 종료되는 여러 physical 라인으로 구성된다. 파이썬에서 대부분의 경우 logical 라인은 physical 라인에 매핑되므로 "라인 끝 문자로 구분된 logical 라인" 이 있다. 복합 명령문은 그림 3.0과 같이 여러 physical 라인에 걸쳐 있을 수 있다. 표현식이 괄호, 대괄호 또는 중괄호 안에 있을 때 암시적으로 또는 백슬래시 문자를 사용하여 명시적으로 logical 라인을 결합할 수 있다.

 

들여쓰기는 또한 파이썬 문을 그룹화하는 데 중심적인 역할을 한다. 따라서 파이썬 문법의 라인 중 하나는 suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT, 따라서 Python 토크나이저의 주요 작업 중 하나는 파스 트리로 들어가는 들여쓰기 및 내어쓰기 토큰을 생성하는 것이다. 토큰화는 스택을 사용하여 들여쓰기를 추적하고 3.1의 알고리즘을 사용하여 INDENT 및 DEDENT 토큰을 생성한다.

 

 

Parser/parsetok.c 모듈 안의 PyTokenizer_FromFile 함수는 파이썬 소스 파일을 왼쪽에서 오른쪽으로 그리고 위에서 아래로 파일의 내용을 토큰화하기 위해 스캔한다. 종결자 이외의 공백 문자는 토큰을 구분하는 역할을 하지만 필수는 아니다. 2+2와 같이 모호성이 있는 경우, 토큰은 오른쪽에서 왼쪽으로 읽는 적법한 토큰을 구성하는  가능한 가장 긴 문자열을 구성한다. 이 예제에서 토큰은 리터럴2, + 연산자 그리고 리터럴 2이다.

 

토큰화로 부터 생성된 토큰은 파이썬 문법에 따라 파스 트리를 구성하는 파서로 전달된다. 파서가 문법을 위바하는 토큰을 만나면, SyntaxError 예외가 던져진다. 파서의 결과는 파스 트리이다. 파서 파이썬 모듈은 파이썬 코드 블록의 파스트리에 대한 제한된 엑세스을 제공하고, 파스트리의 구체적인 데모를 얻기 위해 리스트 3.2에서 사용된다. 

 

위 목록 3.2의 parser.suite(source) 호출은 소스 코드가 구문적으로 올바른 경우 제공된 소스 코드에서 구문 분석 트리에 대한 파이썬 중간 표현인 구문 분석 트리(ST) 개체를 반환한다. parser.st2list에 대한 호출은 Python 목록 형식으로 표현된 실제 구문 분석 트리를 반환한다. 목록의 첫 번째 항목인 정수는 Python 문법에서 생성 규칙을 식별한다.

 

그림 3.0은 일부 토큰이 제거된 목록 3.2의 동일한 구문 분석 트리를 보여주는 트리 다이어그램이며 각 정수 값이 나타내는 문법 부분을 볼 수 있다. 이 생성 규칙은 Include/token.h (terminals)과 Include/graminit.h (terminals) 헤더 파일에 모두 명시되어 있다.

CPython virtual machine에서 트리 데이터 구조는 파스 트리를 나타내는데 사용된다. 각 생성 규칙은 트리 데이터 구조의 노드이다. 이 노드 데이터 구조는 Include/node.h로 부터 리스트 3.3에서 볼 수 있다.

 

파스 트리가 진행됨에 따라, 노드는 그 타입, 자식(있는 경우), 주어진 노드의 생성을 이끄는 라인 넘버 등에 대해 쿼리할 수 있다. 파스트리 노드와 상호 작용하기 위한 매크로도 Include/node.h 파일에 정의되어 있다.