JANGUN


프로그래밍 언어론


지음 : 정광식



목차

요약
1장 프로그래밍 언어의 소개
2장 프로그래밍 언어의 구문
3장 변수, 바인딩, 식 및 제어문
4장 자료형
5장 영역과 수명
6장 기억장소 할당
7장 부프로그램
8장 추상 자료형


요약

언어란? 생각하는 바를 표현하고 전달하기 위해 오랜 시간을 통해 형성된 형식적이고 의미적인 표현 방법
프로그래밍 언어란? 컴퓨터에게 프로그래머의 의사를 전달하는 방법 혹은 프로그램을 작성하는 형식. 컴퓨터가 읽을 수 있고 사람이 읽을 수 있는 형식으로 컴퓨터의 행동을 서술하는 표기 체계
- 프로그래밍 언어의 형식 정의: 구문론(syntax), 의미론(semantics)

언어의 구조 : 문자(ASCII) - 어휘(토큰) - 구문(프로그램 작성 규칙)
- 번역기: 어휘분석 (일련의 문자를 토큰으로 구분) - 구문 분석 (토큰을 처리하여 구문구조를 결정)
- 어휘 토큰, 언어 구성자(if ~ then ~ else ~ ), 식별자(변수), 예약어(if, case, for)
- BNF(Backus-Naur Form), 문맥 자유 문법, EBNF, 구문 도표, 파스 트리, (추상) 구문 트리

변수: 실행시간 동안 값이 바뀔 수 있는 객체, 식별자, 자료속성의 집합, 하나 이상의 주소, 자료값
- 바인딩, 선언, 할당문, 상수
- 표현식: 하나 이상의 피연산자를 가지고 자료값의 계산을 기술하는 것, 피연산자(상수, 변수), 연산자, 사용 가능한 함수 호출
- 제어문: 조건문(IF, SWITCH), 반복문 (WHILE, DO~ WHILE, break, continue, for )

자료형 = 객체의 집합 + 연산(객체들의 실체를 생성, 작성, 소멸, 수정, 분해)의 집합
- 자료형의 구성원(member): 객체, 요소 또는 값, 자료형 영역을 구성, 리터럴(프로그래머가 작성한 구성원)
- 배열 : 이름, 차원, 원소형, 첨자 집합의 형과 범위, 집합체 이름+첨자(인덱스)인 선택자, 선택 연산 (매핑), 행우선/열우선

프로시저(procedure): 명령형 프로그래밍 언어에 국한된 용어, 프로시저 이름, 매개변수 리스트, 몸체, 실행 환경으로 구성
매개변수 (형식 매개변수와 실 매개변수) 전달 기법 : 참조 호출, 값 호출, 결과 호출, 이름 호출

추상화: 속성들의 일부분만을 가지고 주어진 작업이나 객체들을 필요한 정도로 묘사할 수 있는 방법을 지원하는 것으로 유사성을 표현하고 차이점을 삭제함으로써 관련된 사항들을 하나로 묶어 표현하는 방법
추상자료형(ADT, Abstract Data Type) : 자료를 그 자료의 처리 연산과 함께 선언할 수 있는 자료형으로 정보 은닉 개념을 도입 (수정 용이성, 재사용성, 보안성 향상)
캡슐화: 부적당한 사용으로부터 자료형을 보호하기 위한 기법으로 사용자는 윈도우를 통한 사용만 허락됨.


1장 프로그래밍 언어의 소개

언어란? 생각하는 바를 표현하고 전달하기 위해 오랜 시간을 통해 형성된 형식적이고 의미적인 표현 방법
프로그래밍 언어란? 컴퓨터에게 프로그래머의 의사를 전달하는 방법 혹은 프로그램을 작성하는 형식. 컴퓨터가 읽을 수 있고 사람이 읽을 수 있는 형식으로 계산(컴퓨터의 행동)을 서술하는 표기체계

추상화? 속성들의 특징적인 일부분만을 가지고 주어진 작업이나 객체를 표현하고, 그들의 공통점을 추출하여 표현하는 것

프로그래밍 언어의 전형: 명령형 언어(절차 언어), 함수형 언어(적용형 언어), 논리형 언어(선언적 언어), 객체 지향 언어

프로그래밍 언어의 형식 정의: 명확한 사용체계를 알려줌, 모호함을 없애줌, 프로그램의 동작 예측이 가능
- 구문론(syntax): 프로그래밍 언어의 표면적인 구조를 정의
- 의미론(semantics): 프로그램 실행 시 어떠한 일이 일어나는가를 기술

프로그래밍 언어의 역사
- 1950년대: 최초의 프로그래밍 언어인 저급언어 (기계어, 어셈블리어), Fortran (IBM John Backus), COBOL, Algol 60(Recursion), LISP, APL
- 1960년대: 다양한 프로그래밍 언어의 출현, PL/1, Algol 68, Snobol, Simual 67, BASIC(교육용, 시분할 시스템)
- 1970년대: 간결성, 추상화, 효율성, Pascal, C
- 1980년대: 통합과 새로운 방향, Ada, Modula-2, Scheme, Prolog, Smalltack, C++
- 1990년대: World Wide Web 프로그래밍, Java (JVM)
- 2000년대: C# (Microsoft), Dart (Google), Swift (Apple)

프로그래밍 언어의 설계 기준
- 효율성 : 목적코드의 효율성(번역기 최적화), 번역의 효율성(크기와 빠르기), 프로그래밍 효율성(쉽게 작성)
- 일반성 : 여러 개념을 일반적인 하나의 개념으로 결합
- 직교성 : 구성 요소들이 각각의 의미를 지닌 채 결합
- 획일성 : 의미적, 형식적으로 유사한 것들은 그 유사성이 일관되게 유지되어야 함
- 표현력 : 복잡한 과정이나 구조를 표현하는 데 용이
- 정확성 : 결과를 예측할 수 있는 정의에 의존
- 독립성 : 하드웨어나 운영체제에 대해 독립적
- 안전성 : 오류를 줄이고 쉽게 발견
- 일관성 : 표준화된 특징과 개념을 갖도록 설계
- 확장성 : 프로그래머에게 언어의 특징을 추가할 수 있는 권한 부여
- 부분성 : 프로그래머가 언어에 대해 부분적인 지식과 일부의 이해만 있어도 효과적으로 프로그램을 작성할 수 있도록 함


2장 프로그래밍 언어의 구문

언어의 구조 : 문자(ASCII) - 어휘(토큰) - 구문(프로그램 작성 규칙)
번역기: 어휘분석 (일련의 문자를 토큰으로 구분) - 구문 분석 (토큰을 처리하여 구문구조를 결정)
- 어휘 토큰, 언어 구성자(if ~ then ~ else ~ ), 식별자(변수), 예약어(if, case, for)

BNF(Backus-Naur Form): 구문에 대한 형식 정의, 비단말 기호(< >), 단말 기호, 메타기호(::=, | )
문맥 자유 문법 : 모든 생성 규칙에서 정의될 대상이 하나의 비단말 기호로만 구성 / 문맥 의존 문법
EBNF: 특수 의미의 메타 기호를 더 사용하여 반복, 선택 부분을 간결하게 표현, [x], {x}, ( x | y ),

구문 도표: 구문에 대한 형식 정의를 하는 또 다른 방법으로 순서도와 비슷하며 EBNF 선언과 바로 대응시킬 수 있음
파스 트리: 주어진 BNF에 의해 어떤 표현이 생성될 수 있는 지 확인하기 위해 작성하는 트리
(추상) 구문 트리 : 파스 트리의 본질적인 구조를 나태내는 트리 (불필요한 비단말 기호 제거)
구문의 모호성 : 구문을 이용한 유도 과정의 다양성으로 서로 다른 파스 트리가 생성
- 모호한 문법 : 동일 표현에 대해 서로 다른 파스 트리가 만들어지는 문법
- 모호성 제거 규칙: 비단말 기호와 구문 규칙을 추가하거나 좌순환 규칙을 사용하여 좌결합 지원
프로그램의 신뢰성: 사람과 기계에 의해 프로그래밍 언어의 구문이 쉽게 분석될 수 있어야 함


3장 변수, 바인딩, 식 및 제어문

- 컴파일 기법: 주어진 고급 프로그래밍 언어로 작성된 프로그램을 실제 주어진 컴퓨터의 기계어로 번역하여 동등한 의미의 기계어 프로그램을 만들어 실행시키는 방법으로 컴파일러, 어셈블러, 링커, 로더, 프리프로세서가 있다.
- 인터프리트 기법 : 고급 언어를 기계어로 취급하여 이를 실행할 수 있는 고급 언어 기계를 소프트웨어로 시뮬레이션하여 구성하는 방법
- 중간코드 실행 기법 : 프로그램을 실행시키기 쉬운 형태로 번역(컴파일) 한 후, 그 번역된 형태의 프로그램을 실행 시뮬레이션으로 실행(인터프리트), JAVA


변수: 실행시간 동안 값이 바뀔 수 있는 객체, 식별자, 자료속성의 집합, 하나 이상의 주소, 자료값


바인딩 : 변수의 네 가지 요소에 값을 확정하는 것, 이름에 어떤 속성을 연결하는 과정
- 바인딩 시간: 바인딩이 어느 시점에 이루어지는 가에 따라 분류되는 시간
- 실행시간(동적 바인딩): 변수의 값을 확정, 자료구조에 기억장소를 할당
- 번역시간(정적 바인딩): 컴파일 시간, 링크 시간, 로드 시간
- 언어의 구현 시간: 정수의 자릿수, 실수의 유효 숫자 개수, 수의 기계 내에서의 표기법
- 언어의 정의 시간: 혼합형 연산이 허용되는 경우, 두 피연산자의 형에 따라 어떤 형 연산을 하지?

효율성 : 실행의 효율성을 중시, 컴파일러 언어
유연성 : FLEXIBILITY, 인터프리트 언어

선언의 의미: 실행 시 사용될 자료의 속성을 컴파일러 등에게 알려주는 것, 바인딩을 제공하는 중요한 방법, 명시적/묵시적 선언
선언의 목적: 주기억장치 사용과 접근방법의 효율성, 주기억장치 경영의 효율성, 정적 형 검사 기능
할당문: 변수의 내용을 변경할 수 있는 연산, 단순 / 다중 목적 (x,y=0) / 조건 목적 (? : ) / 복합 할당 연산자(+=) / 단항 할당 (++) / 식 / 혼합형 할당문
상수: 변하지 않는 값을 갖는 변수의 사용으로 식별자로 주어짐
표현식: 하나 이상의 피연산자를 가지고 자료값의 계산을 기술하는 것, 피연산자(상수, 변수), 연산자, 사용 가능한 함수 호출

제어문
- 조건문: 조건에 따라 실행되는 부분이 달라질 때 사용, IF, SWITCH
- 반복문: 한 개 이상의 문장을 0번 이상 반복하여 실행시키는 문장, WHILE, DO~ WHILE, break, continue, for (제어변수 반복문)


4장 자료형

자료형 = 객체의 집합 + 연산(객체들의 실체를 생성, 작성, 소멸, 수정, 분해)의 집합
- 내장 자료형: 정수형, 실수형, 문자형, 논리형
- 형 시스템: 자료형을 정의하고 변수를 특정된 자료형으로 선언해 주는 도구
- 강 자료형: 자료형에 관한 모든 특성들이 컴파일 시간에 확정되는 프로그래밍 언어 (미리 다 결정하기 어려움, 신뢰성/유지보수성/가독성 향상)

자료형의 구성원(member): 객체, 요소 또는 값, 자료형 영역을 구성, 리터럴(프로그래머가 작성한 구성원)
- 스칼라형 : 정수형, 실수형(부호/지수/유효숫자부), 논리형(참/거짓), 문자형
- 구조형: 배열, 레코드

다형성: 한 연산자가 속성은 같은데 피연산자의 자료형에 의존되어 실제 기계에서 다른 것으로 간주되는 것
열거형: 단순형의 일종으로 리스트로 정해 줌 ex) enum size { default, plus, minus};
배열과 레코드: 여러 자료를 묶어서 하나의 단위로 처리할 수 있는 구조형 (집합체 또는 복합형), 배열(첨자, 동질형), 레코드(키, 이질형)
배열 : 이름, 차원, 원소형, 첨자 집합의 형과 범위, 집합체 이름+첨자(인덱스)인 선택자, 선택 연산 (매핑), 행우선/열우선
배열의 명세표 : 기억장소 사상을 구현하기 위해 배열에 관한 정보 저장 (배열이름, 원소의 형과 길이, 배열의 시작 주소, 각 차원의 하한과 상한)
연상 배열 : 키라 불리는 값에 의해 접근되는 순서를 갖지 않는 데이터 원소의 집합체 (해시), 사용자 정의 키가 배열에 함께 저장
포인터 : 어떤 객체에 대한 기억장치 주소 참조 방법으로 실행 전에 결정되지 않은 배열의 크기 문제, 작성력 향상, 구조형이나 스칼라형이 아님
포인터 변수: 객체를 참조하기 위한 기억장치 주소를 값으로 취하는 식별자
힙(heap): 동적으로 객체가 배당되는 기억장소 영역
자료형 변환 : 주어진 자료형의 값을 다른 자료형의 값으로 변환하는 것. 정적 형 검사 (컴파일 시간에 수행), 동적 형 검사 (실행 시간에 수행)


5장 영역과 수명

영역(scope): 프로그램에서 사용되는 식별자가 의미를 가질 수 있는 범위, 식별자의 사용이 허락되는 프로그램 범위
블록(block): 내부에서 식별자를 선언하여 새로운 프로그램 환경을 설정할 수 잇는 특별한 언어구조를 제공
변수의 수명: 변수에 의미 있는 기억장소가 할당되어 있는 기간, 자동/정적/프로그래머 지정 할당

식별자의 영역 결정
- 정적 영역 규칙: 번역시간에 결정, 컴파일러 언어
- 동적 영역 규칙: 실행시간에 결정
- 자유 변수 : 현 블록에서 정의되지 않은 변수, 가장 안쪽의 블록에서 바깥쪽 블록으로 조사
- 영역 구멍: 전역 선언이 지역 선언 때문에 보이지 않음. 가시성이 숨겨짐
- 자유 변수 문제 : 정적 영역 규칙 (프로그램 문맥으로 해결), 동적 영역 규칙(프로그램이 실행되는 순서로 해결)

환경: 지역 단위로 묶여진 장소와 관련된 모든 식별자를 정의, 실행시간 동안 각 블록은 하나의 새로운 환경을 가짐
- 선언문은 새로운 환경을 만들고 할당문은 새로운 값의 저장을 의미
- 기억장소 회수 방법: 정적 할당 회수, 명시적 해제, 쓰레기 수집


6장 기억장소 할당

기억장소 할당 기법: 정적(번역 시간), 동적(실행 시간)
- 배열에 할당된 기억장소의 크기나 위치 등이 정적으로 결정되는 경우
- 배열에 대한 접근 코드를 더욱 효율적으로 작성 가능 (Fortran 77)
- 모든 배열은 확정된 고정 크기로 선언되어야 함, 부프로그램은 재귀호출이 허용되지 않아야 함
- 인터프로티의 언어의 경우 동적 기억장소 할당: 프로그램은 매우 간결하게 처리되지만 많은 실행시간을 요구
- 단위 프로그램: 모듈 프로그램 또는 블록
- 지역 변수: 단위 프로그램이나 블록에서 선언하여 사용하는 변수
- 활성화 상태: 한 단위 프로그램의 실행 시작부터 종료까지의 시간
- 단위 활성화: 실행 시간에 한 단위 프로그램이 표현된 상태, 코드부 + 활성화 레코드
- 코드부 : 고정된 크기로, 내용이 프로그램의 실행 동안 변하지 않음
- 활성화 레코드: 프로그램 샐행에 필요한 모든 정보를 가지고 있음, 내용이 프로그램의 실행에 따라 변함

참조 환경 : 지역 변수(자신의 활성화 레코드에 할당)와 비지역 변수(다른 단위 프로그램의 활성화 레코드에 저장)로 구성됨.
- 재귀 호출 : 하나의 코드부와 여러 개의 활성화 레코드 생성
- 정적 기억장소 할당 : 각 단위 프로그램에서 지역 변수들에 필요한 기억장소의 총합은 컴파일 시간에 결정됨 (실행 시간에 변하지 않음)
- 활성화 레코드: 실행 전에 할당하여 실행이 종료될 때까지 유지됨, 변수의 수명은 프로그램 실행시간 전체 (정적 변수)
- 변수에 대한 기억장소 위치는 번역시간 마지막 단계인 프로그램 실행 전에 링크되어 적재할 때 확정되는 기법. 단순하여 쉽게 구현 가능
- 유연성 부족 / 재귀호출 불가 / 활성화되지 않을 수도 있는 활성화 레코드 역시 주기억장소를 항상 차지함
- 차감거리(offset): 단위 프로그램을 컴파일 할 때 지역 변수는 프로그램에서 발생한 순서대로 단위 활성화 레코드의 연속된 장소를 차지함.
- 번역시간에는 활성화 레코드에 대한 기억장소 위치가 결정되지 않으므로, 변수에 대한 기억장소 위치가 확정되지 않음, 차감거리가 변수를 대표함

동적 기억장소 할당 기법 : 프로그램 실행 중에 기억장소를 할당하는 기법 (인터프리터 언어 및 상당수 컴파일러 언어(Pascal, C, Java 등), 블록 기반 언어)

블록 기반 언어 : Algol 60의 영향을 받아 설계, 변수들의 영역을 제한하고 프로그램을 적당한 단위 프로그램으로 나누어 구성할 수 있도록 블록 개념 도입
- 블록 : 특정 블록의 실행 차례가 되었을 때 활성화됨, 지역 선언문을 가지며 새로운 실행 환경을 정의하기 위한 단위
- 부프로그램: 호출문에 의하여 호출되었을 때 활성화됨. 변수 영역이 블록에서의 변수 영역과 동일한 규칙을 따름

활성화 레코드의 크기가 정해지는 시점
- 정적 (번역시간) : 지역 변수들이 필요로 하는 기억장소 용량이 번역시간에 결정, 지역변수들의 생성은 단위 프로그램이 활성화되는 시점에 결정(동적)
- 준정적 변수: 활성화 레코드의 크기는 정적 바인딩, 기억장소 할당은 동적 바인딩을 하는 변수 (재귀호출 가능, 스택 기반 기억장소 할당으로 효율적)
- 준동적 변수: 단위 프로그램이 활성화되는 시점에 지역 변수들이 필요로 하는 기억장소 용량이 결정되고 생성됨. 지역변수들의 차감거리가 번역시간에 상수값으로 확정되지 못하여 주소에 대한 최종 확정을 실행시간까지 늦추어야 함. 활성화 레코드의 크기가 동적 바인딩 되지만, 한 번 바인딩되면 활성화된 프로그램이 종결될 때까지 크기가 변할 수 없음 (스택 기반)
- 동적 변수 : 단위 프로그램의 실행 중에 새로운 자료값이 생성되고 회수되어 활성화 레코드의 크기가 동적으로 변함. 프로그래머가 실행 중에 기억장소의 크기를 변화시키는 자료값을 다룰 수 있음. 활성화 레코드가 활성화되는 시점에서도 활성화 레코드의 크기를 알 수 없음. 힙 동적 배열(유연성 배열), 실행문으로 자료 구조를 생성하여 확장 가능


비지역 변수 참조 방법
- 정적 체인 사용 기법: 모든 활성화 레코드의 정적 링크를 할당, 비지역 변수에 대한 참조 시 정적 체인을 따라 검색해서 먼저 발견된 변수를 참조
- 정적 링크(작성된 프로그램의 정적 내포관계에 있는 활성화 레코드를 가리키는 포인터), 정적 체인 (현재 활성화 레코드로부터 연결된 정적 링크의 순서)
- 디스플레이 사용 기법: 비지역 변수들의 자료값에 대한 참조 시간을 줄이기 위한 구현 기법. 정적 링크 대신에 실행 시간 어느 시점에서나 정적 체인 관계를 디스플레이라고 부르는 1차원 가변 배열을 사용하여 유지


7장 부프로그램

프로그램을 모듈화 (함수, 서브루틴)
프로시저(procedure): 명령형 프로그래밍 언어에 국한된 용어, 프로시저 이름, 매개변수 리스트, 몸체, 실행 환경으로 구성

매개변수 (형식 매개변수와 실 매개변수) 전달 기법
- 참조 호출 : 실 매개변수의 주소를 대응되는 형식 매개변수에게 보내는 방법
- 값 호출 : 형식 매개변수에 해당되는 기억장소를 별도로 유지하는 방법, 실 매개변수 값이 변하지 않음
- 결과 호출: 값 호출과 마찬가지이나, 호출 프로그램에게 반환하기 직전에 형식 매개변수 값을 실 매개변수에 복사
- 이름 호출: 형식 매개 변수가 사용된 모든 자리에 실 매개변수의 이름을 그대로 복사한 것처럼 간주하여 사용

부작용: 지역 변수 이외의 변수 값을 변화시키는 것 (참조 호출, 이름 호출)
별명 : 한 변수에 대해 그 변수명을 대체할 수 있는 다른 식별자, 동일한 기억장소를 함께 사용하고 있는 다른 이름


8장 추상자료형

추상화: 속성들의 일부분만을 가지고 주어진 작업이나 객체들을 필요한 정도로 묘사할 수 있는 방법을 지원하는 것으로 유사성을 표현하고 차이점을 삭제함으로써 관련된 사항들을 하나로 묶어 표현하는 방법
- 프로시저 추상화: 어떻게 수행되는 가를 기술하지 않고 무엇이 수행되는 가를 묘사
- 자료 추상화: 자료형의 표현과 그에 관련된 연산들을 함께 묶어 캡슐화

추상자료형(ADT, Abstract Data Type) : 자료를 그 자료의 처리 연산과 함께 선언할 수 있는 자료형으로 정보 은닉 개념을 도입
- 수정 용이성: 프로그램 전체에서의 사용에 영향을 끼치지 않고 구현에 변화를 줄 수 있음
- 재사용성: 상이한 프로그램에서도 그 코드를 재사용할 수 있음
- 보안성 향상: 구현의 세부 사항을 프로그램의 다른 부분이 마음대로 바꾸지 못하도록 보호할 수 있음

캡슐화: 부적당한 사용으로부터 자료형을 보호하기 위한 기법으로 사용자는 윈도우를 통한 사용만 허락됨.
- 공용부(public part), 전용부(private part), 공개(export), 도입(import)

C++의 클래스 : 변수를 선언할 수 있는 자료혐, 데이터 멤버, 멤버 함수, 생성자, 소멸자, public / protected / private
- 인스턴스 : 객체 선언 결과로 생성됨.
- 한 클래스의 모든 인스턴스는 멤버 함수 집합 하나만 공유하지만 각 인스턴스는 각자 자신의 데이터 멤버 집합을 가짐
- 틀(template) 매개변수 : 클래스 틀을 만들 때 스택의 원소형을 매개변수로 사용할 수 있음

Java의 추상 자료형
- 모든 사용자 정의 자료형이 클래스임
- 모든 객체는 힙에 할당되고 참조형 변수를 통하여 접근됨
- 패키지: 한 개 이상의 클래스 정의를 가지며, 패키지 내에서 각 클래스는 다른 클래스의 부분 프랜드임