Compiler (7) 썸네일형 리스트형 CPython의 새로운 PEG 파서 Overview. PEP는 PEG 기반 파서를 사용하여 현재 CPython의 LL(1) 기반 파서를 대체하는 것을 제안한다. 이 새로운 파서는 LL(1) 한계를 우회하기 위해 현재 문법에 존재하는 다수의 “hack”을 제거할 것을 허용할 것이다. 이는 문법, 파서 그리고 AST 생성과 같은 컴파일 파이프라인과 관련된 일부 구역의 유지 비용을 상당히 줄일 수 있다. 새로운 PEG 파서는 또한 현재 파이썬 문법에 LL(1) 제한을 없앨 것이다. Background on LL(1) parsers 현재 파이썬 문법은 LL(1) 기반 문법이다. 문법이 LL(1)으로 파싱할 수 있다면, LL(1)이라고 말할 수 있다. 이는 결국 왼쪽에서 오른쪽으로 파싱하는 즉, 하나의 lookahead를 사용하여 문장의 leftm.. Python Virtual machine(PVM)-2 From Parse Tree To Abstract Syntax Tree 컴파일 프로세스의 다음 단계는 파이썬 파스 트리를 추상 구문 트리(AST)로 변환하는 것이다. 추상 구문 트리는 파이썬 구문의 세부 사항과 독립적인 코드의 표현이다. 예를 들어 파스트리는 구문 구조이기 때문에 그림 3.0에서 보여지는 것처럼 콜론 노드를 포함한다.하지만 AST는 리스트 3.4에서 보여지는 것처럼 구문 구조를 포함하지 않을 것이다. 다양한 파이썬에 대한 AST 노드의 정의는 파일 Parser/Python.asdl에서 발견할 수 있다. AST에 대부분의 정의는 IF 상태문이나 속성 lookup과 같은 특정한 소스 구조를 따른다. 파이썬 인터프리터의 ast 모듈은 파이썬 AST를 다루기 위한 능력을 제공한다. codegen.. 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) 파서이다. Gr.. Parsing expression grammar 컴퓨터 과학에서 파싱 표현 문법(PEG)는 분석 공식 문법의 유형이다. 이는 형식 언어를 언어의 문자열 인식에 대한 문법의 집합의 관점에서 설명한다. formalism(형식주의)는 2004년 Bryan Ford에 의해 소개되었고, 1970년 초에 소개된 top-down parsing language의 가족과 면밀히 관계되어 있다. 문법적으로 PEG는 CFG와 유사하게 보이는데, 다른 해석을 가지고 있다. 선택 연산자는 PEG에서 처음 일치되는 것을 선택하는거에 반면 CFG에서는 모호하다.이것은 문자열 인식이 recursive descent parser에 의해 실제로 수행되는 경향에 더 가깝다. CFG와 달리 PEG는 모호할 수 없다; 문자열은 정확히 하나의 유효한 파스 트리를 가지거나 아무것도 가지지 않.. Dead-Code Elimination 컴파일러 이론에서 dead code 제거는 dead code를 제거하는 컴파일러 최적화이다. Dead code는 실행 흐름 상 절대 실행되지 않거나 실행되더라도 영향을 주지 않는 코드를 말한다. 1. 일부 문맥에서 중요한 고려사항인 프로그램 사이즈를 줄이고 실행 중인 프로그램은 무관한 연산의 실행을 피하는 것을 허용하여 실행 시간을 줄인다. 2. 또한 프로그램 구조를 단순화함으로써 추가 최적화를 할 수 있게 한다. 3. 데드 코드는 절대 실행할 수 없는 코드와 죽은 변수(작성되었지만 절대 읽지 않는)에만 영향을 주는 즉, 프로그램에 므과한 코드를 포함한다. int function(){ int a = 1; int b = 2; int c; c= a * 3; return c; //아래는 실행되지 않는 코드들 Dominance Frontiers Dominance Frontiers는 제어 흐름 그래프(Control Flow Graph)에서 특정 노드의 지배자가 아닌 다시 말해, 직접 지배되지 않는 노드들의 집합을 뜻한다. 즉, Dominance Frontiers는 해당 블록이 지배하는 블록이 다른 블록을 지배하는 경우를 말한다.(해당 블록에서 특정 블록을 지배하지 않지만 해당 블록을 포함하는 블록에 의해 지배되는 블록의 집합) Dominance Frontiers는 Dominator Tree를 통해 계산된다. ※ SSA에 Φ 함수의 삽입 위치의 결정은 Dominance Frontiers를 통해 구할 수 있다. 아래와 같은 CFG가 있다고 할 때 각 노드의 Dominator는 아래가 될 것이고, CFG의 Dominator Tree(DT)는 아래가 될.. Static single-assignment(SSA) 컴파일러 설계에서, Static single-assignment form(SSA or SSA form)은 중간 표현(intermediate representation, IR)의 하나로, 각 변수를 정확히 한 번 할당할 것을 요구하고 사용하기 전에 정의하는 것을 말한다. 원래 IR의 기존 변수는 version으로 나뉘고, 새로운 변수는 일반적으로 아래첨자와 함께 원래 이름에 의해 표시된다. 때문에 모든 변수의 정의는 자신만의 version을 가진다. 위의 예시에서 변수 y가 사용되며 값이 바뀌는데, SSA를 적용한다면 이렇게 아래첨자를 사용하여 새로운 정의를 만든다. 즉, SSA Form은 다음과 같은 특징을 갖는다 1. 각 변수는 단 한 번만 정의되며, 변수의 값을 변경하는 것이 아니라 새로운 변수를 생.. 이전 1 다음
