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

프로그래밍언어론

(1) 프로그래밍 언어와 추상

① 프로그래밍 언어의 정의 : 인간이 컴퓨터에 계산절차를 알려주는 데 사용하는 기호체계

② 프로그래밍 언어의 요건 : 컴퓨터의 세부적인 지식이 없어도 컴퓨터에 작업을 지시할 수 있는 추상적 표현 가능(자연언어와 닮음)

③ 추상(Abstraction) : 어떤 물체 또는 현상을 중요한 특징 또는 특성만을 추출하여 표현하는 방식

- 어셈블리어의 유일한 추상기구인 기호이름(Symbolic name)은 기게적 표현에 비해 가독성이 높아지고 변경이 용이해진다

- 부프로그램과 매크로 : 여러 연산으로 이루어진 작업을 하나의 이름으로 나타낼 수 있는 기능

· 부프로그램 : 추상적 개념을 만드는 매커니즘이므로 조직적인 프로그램 작성 가능

· 부프로그램의 사용은 □어떻게□는 무시하고 □무엇을□만 알면 된다.

④ 프로그래밍 언어의 추상의 분류

㉠ 자료추상(Data Abstraction) : 문자열, 숫자, 이진나무 등과 같이 계산의 대상이 되는 자료를 추상화하는 것

㉡ 제어추상(Control abstraction) : 프로그램의 실행순서, 즉 제어의 이동을 추상화하는 것

예) 루프, 조건문, 프로시저 호출

⑤ 추상수준

㉠ 기본적 추상 : 컴퓨터의 기본구조를 추상화 한 것

㉡ 구조적 추상 : 프로그램의 구조에 관한 보다 광역적인 정보를 추상화한 것

㉢ 단위추상 : 단위 프로그램 전체를 추상화 한 것

1. 자료추상

① 기본적 추상

㉠ 기본적 자료추상 : 컴퓨터 안에 저장된 자료값을 추상화한 것이다.

㉡ 변수(Variable) : 자료값이 저장된 메모리에는 이름을 부여하여 추상화 시킬 수 있으며 이를 변수라 한다.

㉢ 자료형(Data Type) : 자료값의 종류에 이름이 부여된 것 (예)Interger, real...

㉣ 선언(Declaration) : 변수의 이름과 자료형이 선언을 통해 명시된다.

② 구조적 추상

㉠ 자료구조(Data Structure) : 연관된 자료값의 집합을 추상화하는 주요한 방법이다.

· 레코드 : 상이한 자료형이나 전체로서 하나의 자료형

· 배열 : 동일한 자료형의 항목집합

㉡ 형선언(Type Declaration) : 컴퓨터가 하드웨어적으로 지원하고 있지않는 새로운 자료형에도 기본형과 마찬가지로 형의 이름을 부여할 수 있도록 한다.

③ 단위 추상

㉠ 자료캡슐화(Data Encapsulation) : 추상자료형이라고도 한다. 프로그래머는 자료형의 세부구조 에 신경을 쓰지 않아도 되게 하는 기능을 말한다. (Mudula-2의 module과 Ada의 package)

2. 제어 추상

① 기본적 추상 : 이해하기 쉽도록 하기 위하여 몇 개의 기계어를 묶어 하나의 추상적 문으로 나타낸 것

㉠ 지정문 : 변수값의 게산과 저장을 추상화

㉡ goto문 : 컴퓨터의 제어이동을 직접적으로 추상화

② 구조적 추상

㉠ 구조적 제어 추상 : 조건에 따라 실행될 명령어를 하나의 그룹으로 묶어준다.

㉡ 프로시저(Procedure) : 제어를 구조화한 보다 강력한 형태로 부프로그램 또는 서브루틴이라고도 한다.

· 프로시저 선언 : 프로시저에 이름을 부여하고 수행할 작업을 지정해 주는 것

· 프로시저 호출 : 프로시저 활성화. 해당작업을 수행하는 시점에서 프로시저를 호출하는 것이다.

- 매개변수 : 호출시마다 달라 질수 있는 변수

- 실매개변수 또는 실인자

㉢ CALL : 포트란에서는 프로시저가 서브루틴으로 선언되며 CALL문을 명시하여 호출

㉣ 실행환경 (Runtime Environment)

③ 단위 추상

㉠ 프로그램의 다른 부분에 서비스를 제공하는 논리적으로 연관된 여러 프로시저 집합을 하나의  단위로 추상화할 수 있는 제어구조 (Mudula-2의 module과 Ada의 package)

㉡ 튜링완전(Turing Complete) : 계산만을 기술하기 위한 프로그래밍 언어로 튜링기계가 수행할 수 있는 모든 계산을 기술할 수 있는 것.

(2) 계산전형

① Von Neumann(폰 노이만) 모델 : 대상컴퓨터가 메모리에 저장된 값에 대한 연산명령을 순차로 수행하는 단일 중앙 처리장치를 갖는다.

㉠ 순차실행

㉡ 변수 : 메모리값

㉢ 지정문 : 메모리 값을 조작하는 것.

② 명령형(Imperative)언어 또는 절차적 언어 : 명령어의 순차실행, 메모리 위치를 나타내는 변수의 사용, 변수값을 바꾸는 지정문의 사용 → 메모리를 순서적으로 변화시켜 계산을 수행하는 방법을 표현한 언어

③ 선언형(Declaratove)언어 : 메모리의 변화가 아닌 수행작업을 명시해 주는 언어

1. 명령형 전형

상태의 변경에 의하여 계산을 행하여 나가는 것으로 상태란 컴퓨터 메모리의 상태를 말한다.

① 블록구조 전형

㉠ 포트란 : 서브루틴과 전역 데이터라는 프로그램 블록을 갖춘 최초의 언어

(이제는 블록구조로 간주되지 않음)

㉡ 블록은 실행시 스택에 그 상태를 저장하여 순환이 가능

㉢ ALGOL 60, ALGOL 68, 파스칼, C 등

② 객체지반 전형

㉠ 객체기반언어 : 연관된 자료와 프로시저를 하나로 묶은 객체를 지원하는 언어

㉡ Ada, Mudola-2, Smaltalk 등이 이에 속한다.

③ 분산 프로그래밍 전형 : 여러 프로그래머가 특정 프로그램을 동시에 작성한다든지 통신망에서의 메시지 교환에 의한 통신을 지원하는 기능 등을 갖추고 있는 언어 전형

2. 선언형 전형

① 함수 프로그래밍

㉠ 적용적(Applicative) 언어 : 함수전형에서는 함수 계산, 함수적용에 의해 계산 내용이 표현되기 때문에 함수 언어를 적용적 언어라고 부른다.

㉡ 함수 계산이나 함수 호출이 기본원리

㉢ 함수값 반환시 Modula-2(return문 사용), LISP(return문 필요 없음)

② 논리 프로그래밍

㉠ 논리 프로그래밍은 기호논리, 특히 술어논리에 기초한다.

㉡ 술어 논리는 공리(Axiom)와 규칙(rule)으로 구성

㉢ 선언형 프로그래밍 : 실행순서는 필요없이 특성만 선언

㉣ Prolog : 논리 프로그래밍 언어 중 현재 널리 쓰이는 언어

③ 데이터베이스 언어 : 지속성과 변경의 관리

㉠ 자료정의 언어 (Data Definition Language, DDL)

㉡ 자료조작 언어 (DAta manipulation Language, DML)

(3) 언어의 정의

1. 신택스(syntax, 구문)

① 정의 : 언어의 구성요소들을 결합하여 다른 요소를 만드는 방법을 설명한 것

② 언어의 신택스는 대부분 문맥무관형 문법으로써 정의

③ 언어의 단위 : 토큰(Token)

2. 시맨틱스(Semantics, 의미)

① 정의 : 프로그램이 무엇을 어떻게  수행할지를 나타내 준다.

② 시맨틱스의 공식적 정의에 대한 접근 방법 : 실행적방법, 함수적 또는 표시적 방법, 공리적방법

(4) 언어 번역

① 인터프리터 : 프로그램과 입력자료가 주어지면 이를 곧바로 실행시켜 결과를 출력

· 대화형 프로그램에 많이 사용

· 초보자가 개발하기 쉽고, 개발 기간 단축

· 프로그램의 실행 속도가 느리다

② 컴파일러(Compiler) : 프로그램을 실행에 적합한 형태로 바꾸는 번역기

· 실행속도가 빠르다

③ 차이점 : 인터프리터 방식은 메모리가 적게 드나, 실행시마다 번역해야 하므로 속도가 느리고, 컴파일러는 한번 목적 프로그램을 만들면 다음번에 컴파일 할 필요가 없어 속도가 빠르다

(5) 프로그래밍 언어의 역사

① FORTRAN, ALGOL60, COBOL : 실행효율 중점

㉠ 포트란과 알골60 : 계산이 복잡한 수치적 과학문제를 풀기 위한 도구로 설계

㉡ 코볼 : 상업 자료 처리문제를 풀기 위한 도구로 설계

② LISP, APL, SNOBOL4 : 수학원리에 기반

㉠ LISP : 함수 및 함수적용이라는 수학적 개념을 기본으로 함

㉡ APL : 함수프로그래밍 방식의 언어(배열)

㉢ SNOBOL 4 : 문자열 조작기능과 패턴정합 기능

㉣ LISP와 SNOBOL4의 중요한 특징은 기호계산 강조

③ PL/I : 범용프로그래밍 언어 추구

④ ALGOL68, SIMULA68, Pascal

㉠ ALGOL68 : ALGOL60의 계승언어로 직교성의 원리를 기본

㉡ SIMULA67 : ALGOL60의 계승언어로 이산 시뮬레이션 문제에 적합

㉢ Pascal : 그 당시 가장 성공한 언어

· 구조화 프로그램을 가르치기 위한 소프트웨어, 언어의 능력을 저하시키지 않으면서 단순

㉣ BASIC : 단순성과 구현의 용이성

· 고도로 대화형이며 해석적인 프로그래밍 형식을 지원

⑤ 1970년대의 언어 : 신뢰성이 있고, 유지 보수가 용이한 소프트웨어 지원의 욕구가 증대

㉠ CLU, Alphard, Mesa, Concurrent Pascal, Euclid, Gypsy 등

㉡ C와 Modula : 시스템 프로그램 작성용으로 개발

⑥ 1980년대의 언어

㉠ Ada : 미국 국방석의 주관하에 개발된 프로그래밍 언어의 개념을 종합

㉡ Mudula-2 : 범용언어로서 파스칼의 결점 보완.

㉢ Prolog(논리 프로그래밍 언어), Smalltalk(객체지향언어), C++(C를 객체지향언어로 확장) 등

(6) 프로그래밍 언어의 설계원칙

① 프로그래밍 언어의 개념이 분명하고 단순해야 하며, 일관성이 있어야 한다.

② 신택스가 분명해야 한다.

③ 자연스럽게 응용할 수 있어야 한다.

④ 추상을 지원할 수 있어야 한다.

⑤ 프로그램 검증이 용이하여야 한다.

⑥ 적절한 프로그램 작성환경이 갖추어져 있어야 한다.

⑦ 프로그램이 호환성이 있어야 한다.

⑧ 효율적이어야 한다.

제 2 장 신택스

(1) 프로그래밍 언어의 어휘구조

① 어휘구조 : 단어, 토큰(예약어, 상수, 특수기호, 식별자로 구성)의 구조를 뜻한다.

② 프로그램 포맷 : 자유포맷언어, 고정 포맷언어

(2) 문맥무관형 문법과 BNF

① 문법규칙 : "< >"로 묶인 문자열과 □::=□기호, 그리고 다른 이름 또는 기호의 순으로 구성

② 메타기호(meta symbol) : 기호를 위한 기호, 신택스 정의 기호를 위한 기호로서 언어에도 나타나는 기호

㉠ □::=□ : □좌측은 우측의 것으로 이루어진다□ 또는 □좌측은 우측과 같다□를 의미

㉡ □< >□ : 문법 구조의 이름과 실제의 단어, 즉 토큰을 구분하기 위해 사용된다.

㉢ □|□ : 선택 즉 □또는□을 의미한다.

③ 문맥무관형 문법(Context-free grammar) : 각 문법 규칙에는 메타기호 □::=□이 있고, 이것의 좌측에는 하나의 문법 구조명이 오며 우측은 기호 또는 구조명들로 구성된다.

㉠ 비종결자 (nonterminal) : "<sentence>"와 같은 문법구조명

㉡ 종결자(terminal) : 단어 또는 토큰 기호

㉢ 생성(production) : 문법규칙

㉣ BNF : 생성이 메타기호로만 표현되었을 경우 BNF라 말한다.

⑤ 문맥의존형문법 : BNF로는 자연언어와 같은 복잡한 언어를 완전히 기술한다는 것은 무리

(3) 분석나무와 추상적 신택스 나무

① 신택스 지시적 시맨택스(Syntax-directed semantics) : 신택스 구조에 의미를 부여

② 분석나무(parse tree) : 프로그램의 시맨틱스를 결정하는 데 신택스 구조를 이용하려면 유도과정이 그대로 반영된 신택스 구조의 표현 방법이 있어야 하는데 이러한 표준적인 방법으로 대표적

③ 추상적 신택스 나무(abstract syntax tree) : 분석나무의 정수만을 추출했다는 의미.

줄여서 신택스 나무라고도 한다.

(4) 모호성, 결합성 우선순위

① 모호한 문법 : 동일한 문자열에 대해 상이한 분석나무가 나타날 수 있는 문법

② 우선순위 해결 : 모호성 제거규칙을 만들어 해결

(5) 확장 BNF와 신택스 도표

① EBNF(Entended BNF) : BNF 표기법을 더 확장한 표기법

㉠ 중괄호 □{ }□ : 0번 이상의 반복을 의히

㉡ 대괄호 □[ ]" : EBNF에서 선택적인 구조

② 신택스 도표 : 문법규칙을 그림으로 나타낸 것

㉠ 종결자 : 원이나 타원

㉡ 비종결자 : 사각형

㉢ 종결자와 비종결자는 순서에 따라 화살표로 연결

㉣ 도표에 나타난 루프 : EBNF의 중괄호로 표시된 반복에 해당

㉤ 신택스 도표는 EBNF를 가지고 만든다 (BNF의 신택스 도표는 잘못된 것)

제 3 장 기초개념

(1) 속성과 바인딩

① 이름(식별자) : 언어의 실체 또는 구조를 표기하기 위하여 사용되는 것으로 가장 기본적

② 이름에 연관된 개념

㉠ 값 : 정수, 실수 또는 배열의 값 등과 같이 저장 가능한 수

㉡ 위치 : 값이 저장되는 장소로서 컴퓨터 메모리의 주소와 유사하나 좀 더 추상적

③ 속성(attribute) : 이름의 의미가 이름에 연관된 특징인 속성으로 정해진다.

④ 바인딩(binding) : 속성을 이름에 묶어 주는 것

㉠ 정적 바인딩(static binding) : 실행 이전에 이루어지는 바인딩

㉡ 동적 바인딩(dynamic binding) : 실행시에 이루어지는 바인딩

㉢ 정적속성 : 정적으로 바인딩되는 속성

㉣ 동적속성 : 동적으로 바인딩되는 속성

⑤ 바인딩 시각(binding time) : 속성이 이름에 묶이는 시점으로 속성에 따라 바인딩이 실행 이전에 이루어질 수 도 있고 실행시에 이루어질 수도 있다.

⑥ 바인딩 시각의 종류

㉠ 언어정의시 : 파스칼의 자료형 boolean, char 등과 같은 기정의 식별자의 의미라는 속성 결정

㉡ 언어 구현시 : maxint의 값이나 integer의 실제 범위 결정

㉢ 번역시

㉣ 링크시 : 외부에 선언된 함수의 본체가 이 때 바인딩된다.

㉤ 로드시 : 파스칼의 전역변수는 이 때에 바인딩된다.

㉥ 실행시 ; 실행시를 제외한 모든 바인딩 시각은 정적바인딩에 속한다.

⑦ 기호테이블(symbol table) : 번역 및 실행시 이름에 관련된 정보를 제공하기 위해 자료구조를 만들게 되는 데 이를 이름과 속성을 타나내주는 함수인 것으로 생각하면 된다.

⑧ 기호테이블 처리방식

㉠ 컴파일러 : 정적속성

· 환경(environment) : 이름을 저장 위치에 바인딩한 정보

· 스토어(store) : 저장 위치를 값에 바인딩해 주는 것.

㉡ 인터프리터 : 정적속성, 동적속성이 모두 실행시 처리되므로 기호테이블과 환경이 하나로 합쳐짐

(2) 선언과 블록

① 선언

㉠ 명시적 : 파스칼이나 대부분의 언어

㉡ 암묵적 : 포트란(이름 자체가 속성을 나타낸다)

② 블록(block) : 주프로그램 블록, 프로시저-함수 블록

㉠ 전역선언 : 주 프로그램 블록에 관련

㉡ 지역선언 : 어떤 프로시저에 관련된 선언

㉢ ALGOL 60 및 ALGOL68 : begin과 end로 둘러싸인다

㉣ C : 중괄호 처리 □{ }□

㉤ Ada : ALGOL 60과는 달리 begin과 end앞에 예약어 declare로 변수를 선언

㉥ Modula-2 : 모듈과 프로시저가 블록에 해당

㉦ 포트란 : 서트루틴과 함수 프로그램이 블록에 해당

③ 범위(scope) : 선언에 의해 이루어진 바인딩이 유효한 프로그램의 영역으로, 이를 바인딩 범위

㉠ 블록구조언어 : Pascal, C와 같이 다중내포 될 수 있는 언어의 경우 선언의 범위는 블록의 안쪽으로 국한된다.

㉡ 어휘적범위 또는 정적범위 : 블록이 프로그램상에 나타나는 외형적 구조에 따른 범위

㉢ 범위의 예

· 파스칼,알골60 : 주프로그램 블록에서 선언된 변수는 전역적, 프로시저에서 선언된 변수는 지역적

· Modula-2 : 파스칼과 유사하나, 범위를 제한하기 위하여 지역모듈(local module)을 사용

㉣ 범위의 섬 : 어떠한 범위도 명시적으로 이입(import) 또는 이출(export)된 것을 제외하고는

이 섬을 통과할 수 없다.

· Mudula-2의 경우 improt와 export

· 포트란의 경우 Common문(전역변수를 만듬)

㉤ 범위 구멍(scope hole) : 내포된 블록의 선언이 상위블록의 선언보다 우선

㉥ 시계(visibility)에는 선언의 바인딩이 적용되는 프로그램 부분만이 포함되나, 범위에는 범위 구멍까지 포함된다. Ada의 경우 감추어진 선언까지도 범위수식어를 붙이면 접근이 가능한 데 이 때 □.□를 사용한다.

(3) 기호 테이블

① 정의 : 선언으로 이루어지 바인딩이 보존되는 데 효율적인 접근이 가능한 여러종류의 자료구조로 조직될 수 있다.

② 동적(dynamic) 범위 규칙 : 선언문이 프로그램의 실행과정에 나타나는 순서대로 처리되는

규칙. 기호테이블을 동적으로 관리(APL, SNOBLO, LISP 등)

- 단점

· 프로그램에 나타나는 이름이 어떠한 선언문과 관계된 것인지를 알기 어렵다.

· 변수의 정적인 형선언에 모순이 발생할 수 있다.

③ 정적범위 규칙 : 선언문이 정적으로, 즉 실행전에 처리될 때의 규칙으로, 기호 테이블은 컴파일러에 의해 관리되며 모드 선언문의 바인딩은 정적이 된다.

(4) 할당과 생명시간 및 환경

① 환경 : 이름을 저장 위치에 바인딩한 정보를 모아놓은 것.

㉠ 정적(로드시에) : 포트란

㉡ 동적(실행시에) : LISP

㉢ 정적과 동적 혼합 : 파스칼, C, Modula-2, 알골형 언어 등

② 컴파일 언어에서 상수와 자료형의 이름은 로드시나 실행시에는 존재하지 않고, 컴파일시에만 존재

③ 선언문에 의하여 기호 테이블과 환경이 생성

④ 할당은 정적 혹은 동적으로 되는데 전역변수는 정적으로 할당되고, 지역변수는 동적으로 할당

⑤ 블록구조 언어의 환경도 스택 형태로 만들어 진다.

⑥ begin-end블록에 대한 환경의 할당과 회수는 비교적 간단하나 프로시저와 함수 블록의 경우 복잡

㉠ 활성화(activation) : 프로시저의 호출

㉡ 활성화 레코드(activation record) : 호출되었을 때 할당된 기억장소 영역

⑦ 객체 : 선언의 처리 결과로 환경에 기억장소가 할당될 수 있는 것을 말한다.

㉠ 객체의 생명시간(life time) :  해당 객체에 기억장소가 할당되어 있는 동안을 말한다.

⑧ 포인터(pointer) : 다른 변수에 대한 차조를 값으로 갖는 변수

㉠ 포인터를 사용할 수 있는 언어에서는 환경의 구조를 더 확장해야 한다.

㉡ 파스칼 : 새 변수에 메모리 할당(new), 메모리 회수(dispose)

㉢ Modula-2 : 파스칼과 유사하나, 라이브러리 모듈 Storage로부터 ALLOCATE, DEALLOCATE 프로시저가 이입되어야 함.

㉣ C : 변수를 할당(malloc)하고, 변수를 반납(free)

㉤ 히프(heap) : new와 dispose를 사용할 때 쓰이는 메모리 영역

㉥ 동적할당 : 히프에서의 할당

⑨ 할당방식

㉠ 정적할당 : 전역변수를 위한 할당

㉡ 자동할당 : 지역변수를 위한 할당

㉢ 동적할당 : 포인터를 위한 할당

⑩ 저장등급(storage class)

(5) 변수와 상수

1. 변수

① 정의 : 실행 도중 저장된  값을 바꿀 수 있는 자료 객체로서 이름, 위치, 값, 자료형, 크기 등의 속성을 갖는다.

② 속성 바인딩도 : 다음과 같이 이름과 위치 간에 그려진 선은 이름을 위치에 바인딩한 것을 나타내며 사각형 안의 원은 그 위치에 바인딩 된, 즉 그 위치에 저장된 값을 나타낸다.

③ 지정문(assignment statement) : 변수가 그 값을 변경시키는 주된 방법

㉠ 저장 시맨틱스(storage semantics) : 지정문 x : = □에서 x는 변수의 이름임 □는 식이다. □가 값으로 게산되어 그 값이 x위치의  기억장소에 복사된다.

· r값 (right-hand side value) : 변수의 값

· l값 (left-hand side value) : 변수의 위치

㉡ 포인터 시맨틱스 : 지정문이 수행되면 값이 아니라 위치가 복사된다. x := y

2. 상수(Constant)

① 정의 : 프로그램 전체에서 고정된 값을 갖는 것으로, 위치가 없고 값만 있다.

② 값 시맨틱스  : 계산된 값은 바뀔 수가 없으며 상수의 위치를 프로그램에서 명시적으로 참조할 수 없음

③ 상수를 하나의 기호로 간주할 수 있다.

④ 상수의 종류

㉠ 정적상수 : 그 값이 실행 이전에 계산됨

㉡ 동적상수 : 실행도중에 계산되는 값.

(6) 이름과 할당에 관련된 문제

① 별명 (Alias) : 하나의 객체에 동시에 서로 다른 두 이름이 바인딩 되어 있을 때 발생→부작용 발생 우려

② 현수참조(dangling reference) : 포인터 사용할 때 발생할 수 있는 것으로서 환경으로부터 반납되어 실질적으로는 없어진 것이에도 불구하고, 프로그램에서 접근이 가능한 위치를 말한다.

→ 변수의 생명시간이 끝난는 데도 그 변수를 접근할 수 있다면 현수참조 발생

③ 가비지(garbage) : 환경에 할당은 되어 있으마, 프로그램에서 접근할 수 없는 기억장소

㉠ 파스칼 : dispose를 하기 전에 포인터 변수를 재지정할 때

㉡ 가비지 수집(garbage collection)

· 가비지를 자동적으로 정리

· LISP시스템이 가비지 수집을 도입한 선구자

㉢ Ada : 포인터 변수를 프로그래머가 반납할 수 없게 하면서도 프로그래머 제어하에 프로그래머가 기억장소를 반납하는 길을 열어 놓았다.

(7) 식의 계산

① 식(expression) : 연산자와 피연산자로 구성

② 명령문 : 값의 게산이 목적이 아니라, 프로그램 메모리를 변경하는 부작용을 위해 수행

③ 식은 연산자와 피연산자로 구성

㉠ 연산자 : 미리 정의된 것을 쓰거나 사용자가 정의하여 사용

· 단항연산자 (unary operator) : 하나의 피연산자를 갖는 것

· 이항연산자 (binary operator) : 두 개의  피연산자를 갖는 것

㉡ 피연산자 : 상수, 변수, 함수호출 등이 올 수 있다.

㉢ 연산자를 피연산자의 중위(infix), 후위(postfix), 전위(prefix)에 위치시켜 각각 표기법 생성

④ 적용순서 계산 : 피연산자를 먼저 계산하고, 이들에 연산자를 적용

⑤ 논리식의 중지계산(short-circuit evaluation) : 왼쪽에서 오른쪽으로 값을 계산하며 식의 값이 결정되면 더 이상 계산하지 않도록 할 수 있는 규칙

⑥ 정상순서 계산(normal order evaluation)

제 4 장 자료형

(1) 자료형 및 형 정보

① 자료형

㉠ 정의 :가질 수 있는 값의 집합과 적용될 수 있는 연산의 집합

㉡ 프로그래밍 언어에 형을 정의해 놓은 것은 신뢰성, 가독성, 유지보수형 때문

② 형정보 : 오류를 검출, 번역기는 변수의 기억장소를 할당하는 데 이용

㉠ 종류

- 암묵적인형 : 상수나 값의 형, 이름 규칙에 의해 알 수 있는 형

- 명시적인 형 : 선언문

㉡ 형조사 : 번역기가 프로그램의 형정보에 일관성이 있는지 조사

㉢ 강형언어/악형언어

- 강형언어(Strongly Typed Language) : 언어의 모든 객체의 형을 정적으로 결정 (Ada, Algol 68)

- 약형언어(Wealky Typed Lagnuage) : 정적인 형 체계를 전혀 갖추지 않은 언어

㉣ 기본자료형은 더 이상 나눌 수 없는 구조이고 구조형 자료형은 기본자료형과 기본자료형 복합

(2) 기본자료형

①기정의 형(Predefinde Type)

㉠ 정수형, 실수형, 불형, 문자형

㉡ 정확도를 부가할 수 있다.

㉢ 정수의 특수한 영역을 쓸 수 있다.

㉣ 기정의 형은 대부분 기본형이고 하드웨어가 직접 제어한다.

② 기정의 되지 않은 기본형

㉠ 열거형 : 형을 구성하는 값이 나열목록으로 주어지기 때문에 원소에 순서가 부여

㉡ 부분영역형 : 기존 정수형 또는 열거형의 일정범위를 취한 부분집합

㉢ 서수형 : 선행자, 후속자 연산이 존재하는 형

③ 기본형 처리형식

㉠ 정수는 2 또는 4바이트처리, 실수는 4또는 8바이트 처리

㉡ 불형이나 문자형은 1바이트 처리

㉢ 열거형은 내부에서 무부호 정수로 번역

㉣ 부분영역형은 기저형과 동일한 기억장소에 할당되거나, 값을 저장하는 데 최소 바이트 할당

(3) 형 구축자

① 곱집합(Cartesian Product) : 레코드 구조, 순차적 할당

두 집합 A, B가 있을 때, A와 B의 모든 원소에 대한 순서쌍으로 정의 A×B = {(a,b) | a는 A의 원소이고 b는 B의 원소}

② 합집합(Union) : 두 형의 값 집합의 합집합을 구하는 것

㉠ 종류

- 구별화 합집합 : 원소의 값이 어떠한 형인지를 구별하기 위한 태그나 구별자가 부가된 것

- 비구별화 합집합 : 태그 없음

㉡ 알골형 언어은 가변레코드로 이루어져 있고, Modula-2나 파스칼, C는 점 표기법 사용

③ 멱집합 : 모든 집합의 부분집합

㉠ 집합은 일반적으로 비트벡터로 구현

④ 함수

㉠ 모든 함수 f: A→B집합은 배열형과 함수형이라는 두형태의 새로운 형을 만들어 낸다

㉡ 배열 : A가 서수형일 때 함수 f는 첨자으 ㅣ형이 A이고 원소의 형이 B인 배열로 간주

- 구현이 매우 효율적. 기억공간은 메모리에서 순차적으로 할당

㉢ 차원배열

- 행우선순(row major order) / 열우선순(column major order)

㉣ 함수 및 프로시저 형을 만들 수 있는 언어

- Modula-2 :정수에서 정수로의 함수형 정의

TYPE InFunction= PROCEDURE (INTEGER) : INTERGER;

- 파스칼 : 함수와 프로시저형의 매개변수 처리

⑤ 포인터 및 순환형

㉠ 포인터형 : 집합 연산과는 관계가 없는 형 구축자로, 특정 형의 모든 주소의 집합으로 구성

- Modula-2 : TYPE IntPtr = POINTER TO INTEGER;

㉡ 포인터의 가장 큰 유용성은 순환형의 생산에 있다.

- 계산과정에서 변하는 자료구조의 표현에 적절

⑥ 기타 형 구축자

㉠ 파스칼의 파일형

㉡ 문자열형 : 임의 길이의 문자의 열.

㉢ 공간 지시어 : 기계의존적

(4) 형 동등성

① 명칭적 동등 : 두 변수가 동일한 이름으로 선언, 구현하기가 쉽지만 매우 엄격

② 구조적 동등 : 두 변수의 형이 동일 구조, 명칭적 동등성보다 융통성이 있으며 구현하기 어렵다. 명칭적 동등에서는 두 형 이름만을 비교하지만 구조적 동등에서는 두 형의 전체구조 비교

③ 선언적 동등 : 일련의 재선언에 의해 원래의 선언과 동일한 구조로 되는 형 이름은 동등하다

- 명칭적 동등과 구조적 동등의 중간단계

(5) 형 조사

① 정의 : 프로그램의 모든 구조에서 상수, 변수, 프로시저 및 기타 실체의 형이 올바른지 조사

② 종류

㉠ 동적형조사 : 인터프리터 (실행시에 조사)

㉡ 정적형조사 : 컴파일러 (실행 이전에 조사)

㉢ 모든 형 오류가 실행이전에 발견되어야 하므로 형이 정적으로 결정되어야 한다.

③ 형추론 : 식의 형을 부분식의 형으로부터 알아내는 것으로 형 조사의 근본적인 부분

1. 형 양립성

① 양립적인 형 :함께 쓰일 수 있는 상이한 형

② 지시적 양립 : X:=e라는 지정문의 형 정확성을 판단하는 규칙으로 사용

2. 중첩 형

① 중첩(overlap) : 두 형의 값 집합에 공통되는 부분이 있다면 형이 중첩된 것

② 파스칼과 Modula-2에서 동일 모형의 부분영역형은 비록 공통되는 값이 없다고 할지라도 동등한 것으로 간주

③ Ada는 진정한 새 형과 동적 영역범위 조사를 필요로 하는 형을 구분

㉠ 하위형 : 동적 영역범위 조사를 필요로 하는 부분영역 선언

㉡ 유도형 : 그 자체로 새로운 형이 되는 부분영역

3. 암묵적형

상수나 변수의 형이 명시적으로 선언되어 있지 않을 수도 있어서 형을 문맥이나 표준 규칙에 의해 추론해야 하는 형(예:Modula-2)

4. 공유연산

① 과부하 연산자 : 다른 연산을 동일한 이름으로 나타낸다는 의미

② 다형연산 : 과부하연산자와 유사한 것으로 여러 상이한 형에 적용

5. 중복 형 객체

객체가 하나 이상의 형을 가질 수 있도록 하는 것이 양립성의 면에서 좋은 경우가 있다.

(6) 형 변환

① 암묵적 형 변환 또는 형 강압 : 형 체계에서 자동적으로 행해지도록 하는 자동 형변환

㉠ 장점 : 명백한 변환에 대한 코드를 작성하지 않아도 되어 설계가 간결해진다

㉡ 단점 : 자동 변환을 하면 형 조사 기능을 약화시켜 오류를 찾아내지 못할 수 도 있다.

② 형 변환 함수 : 형 강압의 대안으로서 이 함수는 언어에 내장되어 있거나 라이브러리에 들어 있다.

(예:파스칼의 trunc, round함수나 Modula-2의 FLOAT, TRUNC)

③ 캐스트(Cast) :값 또는 객체 앞에 형 이름을 붙이는 것으로 이렇게 함에 의해 표시된 형으로 변환된다.

㉠ MOdula-2에서는 캐스트가 함수처럼 표기되나 보통 의미의 함수는 아니다.

㉡ C에서 캐스크하면 암묵적인 변환이 행해진다.

㉢ Ada에서는 캐스트를 Modula-2처럼 함수형태로 나타내나 C처럼 변환을 한다.

제 5 장 제어

① GOTO : 프로그래밍 언어에 나타난 첫 번째 제어

② ALGOL 60의 출현 : 구조적 제어 발전(단일입구, 단일출구 형태)

(1) 보호화 명령과 조건절

① 구조화 제어의 가장 기본적인 제어 : 어떤 조건하에서만 일군의 문장을 수행(if-then-else구조)

② 보호와 if는 프로그래밍에 비결정성을 부여해 준다.

1. if 문

① if문은 신택스적으로 모호

② 현수 else 문제 : 파스칼과 Algol 60에서는 else가 어느 if문에 걸리는 것인지를 모를 때 발생

- 파스칼에서는 □else는 else부가 없는 가장 근접한 if문과 짝을 이룬다□라는 모호성 제거규칙

- Algol이나 Ada등은 if문의 끝을 나타내는 키워드를 둔다.

③ 많은 조건을 조사하는 경우 (중첩IF문시)

㉠ Modula-2 : ELSIF	㉡ Ada : elsif

㉢ Algol 68 : elif	㉣ 포트란 77 : ELSEIF

2. case문

① 정의 : 특수한 종류의 보호화 if문

② Modula-2 : 마지막 ELSE부는 선택적

③ 파스칼 : else부가 없어 모든 경우를 나열

④ Algol68 : 선택자를 정수값으로 국한

⑤ C : case문을 변형한 switch문 존재 (break문 사용)

- 다른 조건식 존재

e1 ? e2 : e3 ( e1이 참이면 e2를 실행하고, 그렇지 않으면 e3를 실행)

(2) 루프

① 정의 : 처음부터 컴퓨터 프로그래밍의 주요한 특징이었고 반복계산을 행한다.

일반적 구조는 보호화 do 이다.

② while문 : 근본적으로는 하나의 보호자만 있는 보호화 do로, 루프 구조의 표준

while B do S od (B가 참일때까지만 S가 실행)

③ repeat 문 : S가 최소한 한번은 수행되도록 하는 루프구조

repeat B do S od

④ for 루프 : 루프 구조의 특수한 경우 → 다른 루프 구조보다 최적하하기가 쉽다

㉠ 먼저 한계식을 계산하고 첫 번째 한계를 제어변수의 값으로 한 후 루프 본체를 수행하며 수행후

제어변수를 STEP 식의 값만큼 증가시킨다.

㉡ 최적화하기 용이한 이유는 제어변수를 레지스터에 할당하여 수행속도를 매우 빨리 한다.

(3) GOTO 문제

① 실제의 기계코드와 아주 유사

② 사용지지 입장 : 깊이 다중내포된 구조에서 최상위 수준으로 복귀하는 코드에서 편리

③ 있어야 하나 사용 엄격히 제한한다는 입장 : 파스칼의 경우 자기가 속해 있지 않은 복합문으로 끼어 들어가는 형태의 GOTO문 사용 금지

④ 모든 언어에서 없애야 한다는 입장 : 프로그램을 읽기 어렵게 하므로 절대적으로 없애야 함

(4) 프로시저와 매개변수

① 프로시저 : 프로그래밍 언어에서 일군의 작업이나 계산을 추상화한 것. 이름, 매개변수, 본체로 구성된다.

② 프로시저의 호출 또는 활성화 : 이름과 매개변수의 명시에 의해 이루어진다.

㉠ 형식매개변수 : 프로시저 선언에 나타나는 매개변수

㉡ 실매개변수 : 프로시저 호출시에 공급되는 매개변수

㉢ return 문을 사용하여 제어를 넘기는 언어도 있다.

㉣ 포트란 같은 언어에서는 CALL문을 사용하여 프로시저 호출

③ 함수 : 반환치를 갖는 프로시저

㉠ Modula-2에서 RETURN문은 반환치를 넘길 뿐만이 아니라 제어도 호출부로 되돌린다.

㉡ C는 값을 반환하지 않는 함수를 프로시저로 간주

◎ 매개변수 전달방식

① 주소에 의한 전달(pass by reference)

㉠ 호출 프로그램이 피호출 프로시저에 실매개변수의 주소를 전달하는 방식으로 실매개변수로 전달된 변수는 프로시저의 형식매개변수와 기억장소를 공유하여 되어 별명(alias)이 발생

㉡ 포트란은 주소에 의한 전달이 유일한 매개변수 전달방식

㉢ C나 Algol68은 기본적으로 값에 의한 전달방식이나, 명시적으로 가능하다.

(예 : C의 □&□, □*□의 사용, Algol68의 ref 사용)

② 값에 의한 전달 : 실매개변수가 호출시에 계산되는 식으로 간주되면 이 실매개변수의 값이 형식매개변수의 값으로 된다.

- 가장 단순한 형태는 값 매개변수가 프로시저 실행 도중 상수값으로만 쓰이는 경우이다.

③ 값-결과에 의한 전달(pass by value-result)

㉠ 주소에 의한 전달과 비슷한 결과이나 별명은 발생하지 않는다.

㉡ Ada의 in out 매개변수에 해당

㉢ 프로시저 호출시 실매개변수의 값이 형식매개변수에 복사되어  사용되며, 프로시저를 벗어날 때 형식매개변수의 값이 다시 실매개변수에 복사된다.

④ 이름에 의한 전달(pass by name)

㉠ 피호출 프로그램에서 매개변수가 실제로 쓰여지는 시점에서야 실매개변수가 계산된다. 결국 같은 이름의 형식매개변수일지라도 사용되는 시점에 따라 서로 다른 위치의 기억장소를 나타내는 경우가 있다.

(5) 예외조건 처리

① 예외조건(exception)처리 : 오류 조건 또는 프로그램 실행시 발생하는 비정상적 사건의 처리 에서 발생

② 예외조건 선언

㉠ 예외조건 : 첨자 범위 초과나 0으로의 나눗셈과 같은 실행시 오류를 들 수 있다. 비정상적 사건도 예외조건에 속한다.

㉡ 예외조건 처리기 : 특정의 예외조건이 발생하였을 때에 정상적인 수행의 재개가 가능하도록 하기 위해 수행되는 프로시저 또는 코드열이다.

㉢ 예외조건 처리는 프로그래밍 언어에서 하드웨어 인터럽트 또는 에러 트랩을 흉내낸 것으로 오류 발생시 프로그램에서 스스로 오류를 고치고 실행을 계속할 수 있게 한다.

③ BASIC언어의 예외조건 처리 방식

㉠ ON ERROR GOTO 100 : 어떠한 오류가 발생하든 줄번호 100으로 제어를 옮기도록 하여 줄번호 100에 작성된 오류 처리기는 RESUME, RESUME NEXT, RESUME 줄번호의 3종류 중 한 RESUME으로 끝난다.

㉡ 단점

- 하나의 오류처리기만 있을 수 있으며 특정 오류만 처리하도록 할 수 없다.

- 기정의 오류만 처리가능하고, 발생불능 상태로 만들 수 없고 사용자 정의 오류의 선언도 불가능

- 내포된 범위와 활성화 레코드가 없어서 블록구조가 아니면 모든 변수는 전역전이므로 예외조건 처       리도 전역적이며 후속처 구조가 따로 없다.

④ 블록구조 언어의 예외조건 처리방식

㉠ 종류 : PL/I, Mesa, CLU, Eiffel, C++, ML, Ada 등

㉡ Ada

- 기정의 예외조건 : CONSTRAINT_ERROR, NUMERIC_ERROR, PROGRAM_ERROR,

STORAGE_ERROR, TASKING_ERROR 등

- 사용자 정의 예외조건 : exception을 써서 예외조건을 정의

- 예외조건 선언은 다른 선언문과 동일한 정적 범위 규칙을 따른다.

제 6 장 실행시 구조

(1) 실행시 기억장소 사용하는 방식

① 정적언어 (static language) : FORTRAN, COBOL

㉠ 메모리 할당이 실행이전에 이루어진다.

㉡ 순환(recursion)을 사용할 수 없다.

② 스택방식언어(stack-based language) : ALGOL60형 언어

㉠ 메모리 사용 형태가 예측가능한 후입선출방식

㉡ 실행시간 스택(run-time stack)으로 메모리를 할당

㉢ 메모리 필요량을 계산할 수 없는 프로그램도 사용 가능

③ 동적언어 (dynamic language) : LISP, PROLOG, APL, SNOBOL 4

㉠ 메모리 사용형태를 미리 예측할 수 없다.

㉡ 스택에 의한 메모리 할당이 불가능

④ 파스칼, C, Ada 등과 같은 대부분의 언어는 동적기능이 약간 가미된 스택방식 언어

(2) 포트란

① 구성 : 하나 이상의 주프로그램과 0개이상의 부프로그램으로 구성

② 변소의 저장에 필요한 기억장소가 고정적이다

③ 활성화 레크드는 실행시간 이전에 할당(정적변수)되며 생명시간은 실행시간 전체

④ COMMON문으로 전역변수를 선언하며, 모든 다누이 프로그램에 접근 가능

⑤ 포트란의 메모리 구조

㉠ 컴파일 단계 : 각 단위 프로그램은 독립적으로 컴파일된다.

㉡ 링크 단계 : 모든 구성 단위는 링커에 의하여 하나로 합쳐진다.

㉢ 적재(Load)단계 : 로더에 의하여 프로그램이 메모리로 적재된다.

(3) ALGOL형 언어의 구조

① 특징 : 블록구조

② 프로그램단위 : 블록(이름부여되지 않는다), 부프로그램(이름 부여)

③ 정적기억장소 할당을 할 수 없는 이유

㉠ 순환 호출을 허용

㉡ 컴파일시 단위 프로그램의 활성화 레코드의 크기를 확정할 수 없다.

㉢ Algol60을 제외한 대부분의 언어는 자료객체를 프로그래머가 실행도중 임의로 만들 수 있다.

1. 정적 크기의 활성화 레코드

① 지역변수가 단위 프로그램이 활성화되는 시점에서 생성되고 필요한 기억장소의 크기가 번역시에 확정 (C언어, 포인터를 무시한 파스칼)

② 활성화 레크드의 동적할당 이점

㉠ 순환 호출을 구현할 수 있다.

㉡ 기억장소를 효율적으로 이용할 수 있다.

③ 동적링크(dynamic link) : 차감거리 1의 위치에 저장되는 호출단위 프로그램의 활성화 레크드에 대한 포인터

④ 동적체인(dynamic chain) : 활성상태인 활성화 레코드에서 시작되는 동적링크의 사슬로 단위프로그램의 동적인 내포 관계를 가진다.

⑤ 활성화 레코드는 스택에 할당

2. 크기가 단위 활성화시에 확정되는 활성화 레코드

① 준동적(semidynamic) 변수 : 실행시에 한계가 결정되는 동적배열의 변수-실행시에야 확정

② 준동적변수에 대한 접근은 설명자으 ㅣ포인터를 통한 간접 참조로 번역된다.

3. 동적 가변 크기의 활성화 레코드

① 알골60을 제외한 PL/I, 파스칼, Ada등의 언어에서는 실행중 크기가 바뀔 수 있는 자료 객체도 사용할 수 있다.

② 동적변수

㉠ 단위 프로그램이 활성화되는 시점에서 기억장소의 양이 확정되는 변수로 그 크기와 수가 생명시간 동안 동적으로 변한다.

㉡ 동적변수의 예

- 신축배열 : 저장할 객체의 크기에 맞추어 프로그램 실행도중에 한계가 변화하는 배열(알골68)

- 프로그래머가 임의로 할당하는 변수(PL/I, PASCAL)

③ 동적 변수의 할당 : 히프(heap)라 부르는 메모리 영역에 할당

㉠ 준정적, 준동적 변수 : 스택변수

㉡ 동적변수 : 히프변수

4. 비지역환경의 접근

① 정적언어 : 전역변수는 시스템 제공 활성화 레코드에 속하며 시스템 제공 활성화 레크드는 모든 단위에 전역적이다.

② 알골형 언어 : 정적 체인 혹은 디스플레이를 이용하여 비지역환경에 접근한다.

(4) 동적 언어의 구조

① 동적언어(dynamic language)

㉠ 동적 규칙을 사용하는 언어

㉡ 종류 : APL, LISP, SNOBOL 4

② 활성화 레코드에는 변수의 설명자가 저장된 히프를 지시하는 포인터를 둔다.

③ 히프의 설명자에는 다시 변수가 저장된 히프를 지시하는 포인터가 저장

④ 규칙

㉠ 주 프로그램과 부프로그램으로 구성

㉡ 형식매개변수는 부프로그램 선언의 첫 줄에 선언

제 7 장 추상자료형

(1) 추상자료형(abstract data type, ADT)

① 추상자료형의 두 기준의 유용성

㉠ 수정의 용이성 : 구현에 대한 변경이 다른 부분에 영향을 주지 않으므로 수정의 용이성이 높다

㉡ 재사용성 : 표준적인 연결부를 사용하므로 다른 프로그램이 코드를 재사용할 수 있다.

㉢ 보안성 : 프로그램의 다른 부분에서 구현 내용을 바꿀 수 없도록 하기 때문에 보안성도 높아진다.

② 추상자료형의 필수적 특성

㉠ 캡슐화 : 자료형에 관한 모든 정의를 한곳에 모아 놓고 이곳에서 정의된 연산만이 그 자료형을 쓸 수 있도록 제한하는 것

㉡ 정보으폐 : 구현과 정의를 분리하고 사용자는 세부적인 구현사항에 접근할 수 없도록 하는 것

③ 객체지향 프로그래밍

(2) Modula-2의 추상자료형

① 구현 : DIFINITION MODULE, IMPLEMENTATION MODULE로 분리

② DM에는 정의나 선언문만이 올 수 있으며 이 모듈에 나타나는 선언문만이 다른 모듈이 쓸수 있도록 이출(export)될 수 있다. 세부적인 선언은 IM안에 은폐되어 있어 다른 모듈에서 접근할  수 없다.

(3) Ada의 추상자료형

Ada에서는 모듈을 패키지(package)라고 부르며, 패키지는 패키지 명세와 패키지 본체로 나뉘다.

(4) 기타 언어의 추상자료형

① Euclid : 모듈이 형이다. - 인스턴스화

② CLU : cluster구조를 써서 정의

(5) 과부하와 다형성

① 과부하 함수 : 미리 정해진 형의 집합에 대해서 동일 또는 유사한 연산을 적용하는 것으로 특수 다형성이라 한다.

② 다형적 함수 : 미리 정해지지 않은 모듈형에 적용될 수 있다고 하여 매개변수적 다형성이라고 한다.

(6) 추상자료의 문제점

① Ada와 Modula-2등의 언어는 모듈이 연산뿐만 아니라 형까지 이출하여야 하기 때문에 어려움이 발생한다.

② 새 모듈이 필요한 경우 일일이 복사하여야 한다.

③ 올바른 할당과 초기화가 보장되지 않는다.

④ 이입협에 대한 모듈의 의존관계가 적절하게 표현되지 않는다.

⑤ 대부분의 언어의 경우 주석으로 시맨틱스를 대신한다.

제 8 장 객체지향 프로그래밍 언어

(1) 소프트웨어 재사용과 독립성

① 소프트웨어 구성부의 재사용

② 다른 구성부와의 독립성 유지

(2) 기본구성요소

① 기본구성요소 : 객체, 클래스, 메소드

② 객체지향언어에서의 객체의 상태는 그 객체에 내부적, 지역적이고 각 객체는 지역 상태를 바꿀수 있는 함수와 프로시저의 집합을 포함하고 있다.

(3) 계승(Inheritance)

상속이락도 하는데 클래스간에 데이터와 연산을 공유하게 해주는 객체지향언어의 주된 구조

(4) 동적바인딩

(5) C++

C++는 C에 Simula식의 클래스를 추가하고자 하여 개발된 언어. 사용자의 필요에 의해 개발된 효율적이고 실용적인 언어로서 1985년 소개된 후 몇 년 안 되어 가장 많이 사용되는 객체지향 언어가 되었다.

(6) Eiffel

Eiffel은 파스칼형 신택스이지만 앞선 언어에 기초하여 만들어진 것은 아니며 파스칼형 객체지향언어 중 가장 일관성 있게 설계된 언어

(7) Smalltalk

Simula와 LISP의 영향을 받은 Smalltalk는 객체지향언어 중 가장 객체지향 전형에 충실하고, 수와 문자 등의 상수를 포하한 거의 모든 언어 실체가 객체이므로 순수객체 지향언어라고 말할 수 있다.