전체 글

범위 규칙 구현 정적 범위 규칙 구현 정적 링크(Static Link) 디스플레이(The Display) 동적 범위 규칙 구현 연관 목록(association lists) 중앙 참조 테이블(Central Referencing Table) 정적 범위 규칙 구현 정적 범위 규칙 구현에는 단순히 스택을 사용하는 것보다 더 많은 관리가 필요하다. foo 프로시저에서 변수 x는 C가 아닌 블록 B의 x를 참조한다. 단, foo에 동적 링크로 연결된 활성화 레코드는 Block C이다. 따라서 블록을 즉시 둘러싸는 블록에 대한 링크가 하나 더 필요하다. 정적 링크(점선)를 사용하여 둘러싸는 블록을 가리킨다. 정적 범위를 관리할 때는 동적 링크 대신 정적 링크를 사용한다. 정적 링크 다음 구조의 예를 고려해보자 블록 ..

동적 관리 정적 관리로는 충분하지 않다. 모든 프로그램 구성 요소가 런타임 전에 결정될 수는 없기 때문이다. 동적 메모리 관리를 위해 스택과 힙을 사용할 수 있다. 스택을 통한 동적 관리 활성화 레코드(activation record)=프레임(Frame) : 활성화된 프로시저(or 인라인 블록)에 할당된 각 메모리 공간 활성화 레코드는 컨텍스트 스위칭을 하기 전에 함수 상태를 기록하고 복원하기 위한 것이다. 메인 함수를 호출하는 순간 메인 함수의 활성화 레코드가 생성된다. 런타임 스택(runtime stack) : 활성화 레코드가 포함된 스택 활성화 레코드에는 무엇이 있을까? 인라인 블록의 활성화 레코드는 프로시저에 비해 훨씬 간단하다. 대부분 프로시저를 고려한다. 인라인 블록의 활성화 레코드에 대한 정..

정적 관리 정적 메모리 관리는 프로그램 실행 전에 컴파일러에 의해 수행된다. 정적으로 할당된 개체는 고정된 메모리 영역에 위치한다. 이러한 개체는 전체 프로그램 실행 동안 해당 위치에 유지된다. 정적으로 할당할 수 있는 것 전역 변수 : 전체 프로그램에서 사용 오브젝트 코드 : 컴파일러에 의해 생성된 기계 명령어 상수 : 해당 값이 컴파일 시간 동안 결정될 수 있는 경우에만 해당 컴파일러에서 생성된 테이블 : 프로그램의 런타임 지원에 사용 재귀가 없다면(without Recursion) 재귀가 없으면 둘 이상의 프로시저를 동시에 활성화할 수 없다. 따라서 프로그래밍 언어의 다른 구성요소를 정적으로 처리하는 것이 가능하다. 예) 지역 변수, 인수, 임시 값, 반환 값 및 반환 주소. 동일한 지역 변수는 스..

메모리 관리 메모리 관리는 인터프리터의 주요 기능 중 하나이다. 프로그램이 실행되는 동안 다양한 정보가 생성되어 메모리에 로드되거나 저장된다. 예) 지역 변수의 값, 표현식의 임시 값, 함수의 인수 및 반환 값 등. 따라서 프로그래밍 언어에서 이러한 메모리 액세스를 처리하는 방법을 결정하는 것이 필요하다. 서브프로그램(Subprogram) 서브프로그램은 프로시저, 함수, 루틴, 서브루틴과 동의어이다. 실행을 위해 호출할 수 있는 프로그램의 일부 모두 서브프로그램의 개념을 표현하기 위해 사용 일부 언어에서는 의미가 다를 수 있지만 동일한 것으로 간주한다. 이 과정에서는 대부분 프로시저/함수를 같은 의미로 사용한다. 이론적으로 둘 사이의 차이점은 함수가 반환 값을 갖는 하위 프로그램이라는 것 스택(Stack..

가시성 규칙(Visibility Rules) 비공식적인 개념이다. 이름의 가시성을 결정하고 특정 블록에서 어떤 바인딩을 사용할 수 있는지 결정하는 규칙. 블록의 로컬 선언은 해당 블록과 해당 블록 내의 다른 모든 블록에 표시된다. 블록에 동일한 이름의 새 선언이 있는 경우 이 새 선언은 이전 선언을 숨긴다. 0: { int a = 1; 1: { int b = 2; 2: { int b = 3; int c = a + b; printf("%d\n", c); } 3: { int d = a + b; printf("%d\n", d); } } } 블록 0~3이 있다. 현재 블록이 변경되면 환경도 변경된다. 따라서 동일한 이름이 다른 개체에 연결될 수 있다. 변수 c의 값 : 4 변수 d의 값 : 3 먼저 블록 0에 ..

블록(Block)과 환경(Environment)이란? 블록 환경을 이해하기 위해서는 먼저 { ... }에 대해 생각해보자. 블록은 시작과 끝 기호로 식별되는 프로그램의 텍스트 영역이다. 블록에는 해당 지역에 대한 로컬 선언이 포함된다. 그러한 선언은 해당 지역 외부에서는 유효하지 않다. 블록은 다양한 방식으로 표현될 수 있다. 일반적으로 블록에 들어가고 나갈 때마다 환경이 변경된다. 블록은 중첩될 수 있다. 블록의 중복은 절대 허용되지 않는다. 마지막으로 열린 블록이 닫힐 때까지 이전 블록을 닫을 수 없다. 언어별 블록 표현 방식 Java if (a > 0 && b > 0) { q = a / b; } Python if a > 0 and b > 0: q = a /b Scheme (define var "PL..

이름(Name)이란? 이름(Name) 이름은 단지 다른 객체를 대표(represent)하는(또는 의미(denote)하는) 일련의 문자일 뿐이다. 대부분의 프로그래밍 언어에서 이름은 식별자 형식을 갖는다. 예) 영숫자 토큰(v1, v2, func 등) 또는 기타 기호(_, $). 이름(Names) ≠ 개체(object) 이름과 그 이름으로 표시되는 대상은 동일한 것이 아니다. 하나의 이름은 여러 가지 다른 개체를 나타낼 수 있다. 또한 하나의 개체가 여러 가지 다른 이름을 가질 수 있다. 표시 가능한 객체(Denotable Objects) 표시 가능한 개체는 이름을 지정할 수 있는 개체이다. 사용자가 이름을 부여한 객체: 변수(variables), 매개변수(parameters), 함수(functions),..

구문을 파이썬으로 추상 구문 트리(Abstract Syntax Tree; AST)로 분석하고 EBNF로 구현해본다. 'a = 3 + b' 구문을 분석해보자. 파이썬에서는 ast 모듈을 사용하여 코드를 구문 분석할 수 있다. ast 모듈의 사용법은 다음과 같다. import ast t = ast.parse('a = 3 + b') s = ast.dump(t, annotate_fields=False, indent=4) print(s) 코드 결과 Module([ Assign([ Name('a', Store())], BinOp( Constant(3), Add(), Name('b', Load()) ) ) ],[]) 결과 각 노드에 대해 노드 유형(Module, Assign, Name)으로 시작하고 해당 하위 노드를..

변환 방법 BNF EBNF ::= A | AB ::= A [B] ::= '-' | ::= ['-'] ::= {X} A | A ::= A {A} ::= {X} A | ε ::= {A} ::= '+' | '-' ::= ('+' | '-') ::= '+' | '-' | ::= [('+' | '-')] EBNF로 변환할 때 주의점 대부분의 |는 제거된다. 중복되는 요소가 하는 일이 오직 조건을 구체화하는 것이라면, 그것들은 제거된다. 대부분의 재귀적 요소는 제거되고 { } 루프로 대체된다. null을 뜻하는 입실론(ε)이 없어진다. 변환 예시 BNF 표현 ::= int ; ::= | , EBNF 표현 ::= int { , } ; 참고 https://en.wikipedia.org/wiki/Syntax_diagra..

우리가 어떻게 프로그램언어(PL)에 대한 옳고 그름을 판단할 수 있을까? 또한 코드가 올바르게 작성되었는지 판단할 수 있는 기준은 뭘까? 우리는 주어진 코드에 구문 오류가 있는지 확인하면 된다. 형식 언어(Formal Language) 프로그래밍 언어의 일반적인 특성을 추상화 일련의 기호, 일부 형성 규칙(기호를 결합)으로 구성 언어 문법 E → E + E | E * E | N, N → 0N | 1N | λ 배커스-나우르 표기법(BNF) 원래는 John Backus가 개발한 Backus Normal Form Peter Naur가 확장하여 사용한 후 Donald Knuth의 제안으로 Backus-Naur Form(BNF)으로 이름 변경 문맥 자유 문법(context-free grammars)을 위한 표기법..