PyPy 파서

개요

PyPy 파서는 토크나이저와 재귀 하강 파서를 포함합니다.

토크나이저

현재 토크나이저는 토큰 리스트를 빌드하는 단일 함수(pypy/interpreter/pyparser/pytokenizer.py의 generate_tokens)로 구현되어 있습니다. 그런 다음 이 토큰들이 파서에 전달됩니다.

파서

파서는 CPython의 파서와 비슷한 간단한 LL(1) 파서입니다.

Python 문법 빌드하기

Python 문법은 시작할 때 수정되지 않은 원본 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 메서드입니다. 이 메서드는 인자로 받은 토큰을 바탕으로 현재 상태에서 다른 상태로 가는 전이를 찾으려고 시도합니다. 전이를 찾지 못하면 현재 상태가 수락 상태인지 확인합니다. 수락 상태가 아니면 ParseError가 발생합니다. 오류 없이 파싱이 끝나면 파서는 Node의 트리를 구축한 상태가 됩니다.

Python 파싱

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

컴파일러

Python 바이트코드를 생성하는 다음 단계는 파스 트리(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”이라는 이름을 로드하는 코드를 상수로 바꾸는 것과 같은 다른 간단한 변환도 수행합니다.

심볼 분석

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

바이트코드 생성

바이트코드는 pypy/interpreter/astcompiler/codegen.py에서 생성됩니다. 각 바이트코드는 pypy/interpreter/astcompiler/assemble.py에 있는 Instruction 클래스로 임시로 표현됩니다. 모든 바이트코드가 생성되고 나면 코드 객체를 빌드할 차례입니다. 점프 오프셋과 함께 줄 번호 테이블, 스택 깊이 같은 바이트코드 정보가 계산됩니다. 마지막으로 이 모든 것이 새로 만든 PyCode 객체에 전달됩니다.