PyPy 파서

개요

PyPy 파서(parser)는 토크나이저(tokenizer)와 재귀 하향 파서(recursive descent parser)를 포함합니다.

토크나이저

현재 토크나이저는 토큰 목록을 만드는 단일 함수(pypy/interpreter/pyparser/pytokenizer.py의 generate_tokens)로 구현되어 있습니다. 그 후 토큰들은 파서에 전달됩니다.

파서

파서는 CPython의 것과 유사한 단순한 LL(1) 파서입니다.

파이썬 문법 빌드하기

파이썬 문법은 시작 시 순정 CPython 문법 파일로부터 만들어집니다(pypy/interpreter/pyparser/metaparser.py 참고). 문법 빌더는 먼저 문법을 비결정적 유한 오토마톤(Nondeterministic Finite Automaton, NFA) 집합에 대응하는 규칙들로 표현합니다. 그런 다음 이를 결정적 유한 오토마톤(Deterministic Finite Automaton, DFA) 집합으로 변환합니다. NFA와 DFA의 차이는 NFA는 주어진 입력에 대해 다음 상태가 여러 개일 수 있는 반면 DFA는 하나만 가질 수 있다는 것입니다. 따라서 DFA는 더 제한적이지만 파싱에 사용하기에는 훨씬 더 효율적입니다. 마지막으로, 문법 빌더는 각 DFA 상태에 번호를 부여하고 파서가 사용할 수 있도록 리스트로 묶습니다. 최종 결과물은 pypy/interpreter/pyparser/parser.py에 있는 Grammar 클래스의 인스턴스입니다.

파서 구현

파서의 핵심은 Parser클래스의 add_token메서드입니다. 인자로 받은 토큰을 바탕으로 현재 상태에서 다른 상태로의 전이를 찾으려 시도합니다. 전이를 찾을 수 없으면, 현재 상태가 수락 상태(accepting)인지 확인합니다. 아니라면, ParseError가 발생합니다. 오류 없이 파싱이 끝나면, 파서는 Node의 트리를 만든 상태가 됩니다.

Python 파싱

토크나이저와 파서 사이의 접착 코드(glue code)와 Python 전용 추가 코드는 pypy/interpreter/pyparser/pyparse.py에 있습니다. parse_source 메서드는 Python 코드 문자열을 받아 파스 트리를 반환합니다. 또한 코딩 쿠키(coding cookie)가 있으면 이를 감지하여 소스를 디코딩합니다. __future__ import는 파서가 호출되기 전에 pypy/interpreter/pyparser/future.py에서 소스를 수동으로 파싱하여 처리된다는 점에 유의하십시오.

컴파일러

파이썬 바이트코드를 생성하는 다음 단계는 파스 트리(parse tree)를 추상 구문 트리(Abstract Syntax Tree, AST)로 변환하는 것입니다.

AST 빌드

Python의 AST는 pypy/interpreter/astcompiler/tools/Python.asdl에 기술되어 있습니다. 이 정의로부터 pypy/interpreter/astcompiler/tools/asdl_py.py가 pypy/interpreter/astcompiler/ast.py를 생성하며, 이 파일에는 컴파일러용 RPython 클래스뿐만 아니라 AST에 대한 애플리케이션 레벨 코드로의 바인딩도 포함되어 있습니다. AST 클래스에 대한 일부 커스텀 확장은 pypy/interpreter/astcompiler/asthelpers.py에 있습니다.

pypy/interpreter/astcompiler/astbuilder.py는 파스 트리를 AST로 변환하는 역할을 담당합니다. 이는 파스 트리를 따라 내려가면서 노드를 만들어 나갑니다. 그 결과는 최상위 mod 노드입니다.

AST 최적화

pypy/interpreter/astcompiler/optimize.py에는 AST 최적화기가 포함되어 있습니다. 이 최적화기는 표현식에 대한 상수 폴딩(constant folding)을 수행하며, 이름 “None”의 로드(load)를 상수로 바꾸는 것과 같은 다른 간단한 변환들도 수행합니다.

심볼 분석

바이트코드를 작성하기 전에, pypy/interpreter/astcompiler/symtable.py에서 심볼 테이블이 구성됩니다. 이는 소스 코드의 모든 이름이 지역(local)인지, 암묵적 전역(implicitly global, 전역 선언이 없는 경우)인지, 명시적 전역(explicitly global, 해당 스코프에 이름의 전역 선언이 있는 경우)인지, 셀(cell, 중첩된 스코프에서 사용되는 이름)인지, 아니면 자유(free, 중첩 함수에서 사용되는 이름)인지를 판별합니다.

바이트코드 생성

바이트코드는 pypy/interpreter/astcompiler/codegen.py에서 생성됩니다. 각 바이트코드는 pypy/interpreter/astcompiler/assemble.py의 Instruction 클래스로 임시로 표현됩니다. 모든 바이트코드가 생성된 후, 코드 객체를 만들 차례입니다. 점프 오프셋과 줄 번호 표, 스택 깊이 같은 바이트코드 정보가 계산됩니다. 마지막으로, 모든 것이 새로 만들어진 PyCode 객체로 전달됩니다.