[3-2강] 언어의 설계와 구현

 

[3-2강]언어의설계와구현.pdf

0.12MB

언어의 설계와 구현

1. 프로그래밍 언어 설계시 고려 사항

1) 프로그래밍 작성 절차

∙ 문제 분석

∙ 입출력 설계

∙ 순서도 작성

∙ 프로그램 구현(코딩)

∙ 프로그램 입력

∙ 컴퓨터 모의실험

∙ 실행

∙ 문서화

2) 프로그래밍 언어 설계의 고려 사항

∙ 개념의 명료성

∙ 구분의 명료성

∙ 문제 해결에 대한 적합성

∙ 프로그램 검증의 용이성

∙ 프로그램의 호환성

∙ 프로그래밍 언어의 효율성 등

 

2. 프로그래밍 언어 구현 기법

1) 번역(Translator) 기법

∙ 인터프리터 - 융통성을 강조한 처리

- 명령 단위 별로 번역 즉시 실행

- 기억 장소가 적게 필요

- 동적(대화식) 자료 구조

- 소프트웨어로 시뮬레이션 하는 방법으로 적절함

- BASIC, LISP, APL, Prolog

∙ 컴파일러

- 반복 작업이 많은 프로그램에 적절함

- 목적 언어 프로그램을 출력함

- 실행 효율이 높음

- FORTRAN, COBOL, PASCAL, Ada, PL/1(Programming Language One)

∙ 어셈블러 : 어셈블리어로 작성된 저급언어를 기계어로 바꾸는 역할

 

2) 언어 번역 방식 비교

 

3. 가상 컴퓨터(Virtual Computer)

1) 가상 컴퓨터 개념

∙ 정의 : 물리적으로 실제 존재하는 컴퓨터가 아니라 다양한 목적을 위해 개념적으로 존재하는 가상의 컴퓨터

∙ 목적 - 인터프리터에 의해 사용

- 컴파일러의 중간 코드 생성을 위해 사용

- 기계 독립적인 프로그램 언어를 만들기 위해 사용

2) 가상 컴퓨터 설계시 고려 사항

∙ 변수의 크기

∙ 레지스터의 집합

∙ 기억장소 구조

∙ 스택의 구조와 관련레지스터 정의

 

4. 바인딩(Binding)

1) 바인딩 개념

∙ 프로그램 내에서 식별자를 그 대상과 관련 짓는 것

∙ 식별자와 그 값을 연결시키는 것

∙ 바인딩 시간(Binding Time) : 프로그램에서 변수들이 갖는 속성이 완전히 결정되는 시간

2) 바인딩 시간의 종류

∙ 동적 바인딩(실행시간 바인딩)

- 프로그램 호출시간

- 모듈의 기동시간

- 실행시간 중 객체 사용시점

∙ 정적 바인딩(번역시간 바인딩)

- 언어정의시간

- 언어구현시간

- 언어번역시간

- 링크시간

 

언어 구문과 번역

1. 언어의 구문

1) 언어의 구문 요소

∙ 문자집합 : 모든 프로그래밍 언어는 알파벳 문자와 숫자로 이루어짐

∙ 식별자 : 변수, 레이블 등의 이름으로 쓰이는 단어

∙ 예약어 : 프로그래머가 변수 이름이나 다른 목적으로 사용할 수 없 는 핵심어

∙ 핵심어 : 특별한 의미를 가진 프로그램 문자의 고정된 부분

∙ 연산자 : 사칙 연산자, 비교 연산자 등

∙ 구분 문자 : 문장이나 식과 같은 구문적인 단위의 시작과 끝을 나타 내기 위하여 사용

∙ 연산식, 주석, 잡음어

 

2) 구문(Syntax) 표기법

∙ BNF : 프로그래밍 언어의 구문 형식을 정의하는데 가장 일반적인 표현방식 ∙ EBNF - BNF 보다 간결하고 효율적인 표기법 - 반복되는 부분을 나타내기 위해 { }를 사용 ∙ 구문도표 ::= 정의 | 선택(택일) <> 비종단(non-terminal)기호 - BNF로 다시 정의될 대상 지시선(→) 흐름의 방향 네모(□) 비종단(non-terminal) 표시 원(○) / 타원 종단(terminal) 표시

 

3) 구문 활용의 목적 및 역할

∙ 목적 : 문맥의 의미를 명확하고 간결하게 하기 위하여

∙ 역할 : 프로그램을 이해하는데 필요한 정보와 프로그램을 목적 프 로그램으로 번역하는데 필요한 정보를 제공

 

2. 형식 언어

1) 형식 언어의 개념 언어의 분석 및 번역을 정확히 하기 위해 수학적 기호를 사용하여 정의한 언어

2) 형식 언어의 구성 요소

∙ 알파벳

∙ 스트링

∙ 언어

∙ 언어에 대한 연산

 

3) 형식 문법의 정의 및 구성 요소

Type 0 문법	인식기 : 튜링 기계
Type 1 문법	인식기 : 선형 한계 오토마타(LBA)
Type 2 문법	∙ Context-Free 문법으로 표현된 언어를 인식하는데 사용되는 오토마타 ∙ 인식기 : 푸시다운오토마타(PDA, 스택 자동기계)
Type 3 문법	∙ 컴퓨터 프로그래밍 언어의 어휘구조를 표현하는데 사용 ∙ 정규 표현(Regular Expression)을 받아들이기 효율적인 오토마타 ∙ 인식기 : 유한 상태 오토마타(FA)

 

∙ 유한상태 오토마타(FA) : 이산적인 입력과 출력에 유한 수의 내부 상태를 가진 시스템의 수학적 모델

4) 정규 표현(Regular Expression)

∙ 정규 언어를 나타내는 수식

∙ 상태 전이도로 나타낼 수 있음

∙ 정규 집합을 형성하는 기초가 됨

 

3. 컴파일 과정

1) 선행처리(Preprocessor)

∙ 컴파일러가 원시 프로그램을 처리하기 전에 먼저 필요한 작업을 수 행하는 프로그램

∙ 원시 프로그램을 기계어 프로그램으로 번역하는 대신에 기존의 고수준 컴파일러 언어로 전환

2) 어휘 분석(Lexical Analysis)

∙ 토큰 생성 ∙ 원시 프로그램을 토큰이라는 문법적 단위로 분석

∙ 번역의 가장 기본적인 단계로 나열된 문자들을 기초적인 구성요소 들인 식별자, 구분 문자, 연산기호, 핵심어, 주석 등으로 그룹화하는 단계

∙ 어휘분석기 : 원시 프로그램을 하나의 긴 스트림으로 보고 원시 프로그 램을 문자 단위로 스캐닝하여 문법적으로 의미 있는 일련의 문자들로 분할해 내는 역할

 

3) 구문 분석(Syntax Analysis)

∙ 파스트리 생성

∙ 주어진 문장이 정의된 문법 구조에 따라 정당하게 하나의 문장으로 합법적으로 사용될 수 있는가를 확인하는 작업으로 토큰들을 문법 에 따라 분석하는 작업을 수행하는 단계

∙ 파스트리 : 고급언어로 작성된 프로그램을 구문 분석하여 파서에 의하여 생성되는 결과물로서, 각각의 문장을 문법구조에 따라 트리 형태로 구성한 것

 

4) 의미 분석(Semantic Analysis)

∙ 실행 가능한 중간 코드 생성

∙ 컴파일러에 의해 원시 프로그램이 분석될 때 구문 분석기에 의해 인식된 구문구조가 처리되고, 실행 가능한 목적 코드의 구조가 형 성 되기 시작하는 단계

5) 코드 최적화(Code Optimization)

∙ 실행결과에 변화를 주지 않으면서, 중간 코드를 빠르고 작은 장소가 요구되는 최적화된 코드로 변환하는 작업

∙ 코드 최적화의 필요성 : 의미 분석기는 중간 코드를 생성만 할 뿐 중간 코드 간의 상호 관계에 의한 효율성은 고려하지 않으므로 중간 코드를 그대로 실행할 경우 실행 시간과 기억장소를 낭비 하게 됨

 

6) 목적 코드 생성(Object Code Generation)

∙ 최적화된 코드가 어셈블리 언어 문장이나 기계 코드로 출력되어야 하는 다른 목적 프로그램 형태로 바뀌는 과정

∙ 출력된 코드는 직접 실행 가능하거나, 어셈블리 또는 링크와 적재 등의 다른 번역 과정을 거칠 수 있음

7) 링크(Link)

∙ 목적 코드를 실행하기 위해서는 Main 프로그램에서 호출하는 모듈 을 하나로 연결하여 실행 가능한 파일로 만들어야 함

∙ 목적 코드를 실행 가능한 파일로 변경하는 작업이 링크(Link)임

 

4. 구문 분석(Syntax Analysis)

1) 상향식(Bottom_Up) 기법

∙ 터미널 노드에서 뿌린 노드를 만들어내는 과정으로 뿌리노드, 즉 시작 기호가 만들어지면 올바른 문장이고 그렇지 않으면 틀린 문장임

2) 하향식(Top-Down) 기법

∙ 파싱할 수 있는 문법에 left recursion이 없어야 하고 left factoring 을 해야 하므로 상향식 파서보다는 일반적이지 못함

∙ 루트로부터 preorder 순으로 주어진 문자열에 대해 파스트리를 구성함

∙ 입력 문자열에 대해 좌측 유도(left most derivation) 과정으로 볼 수 있음

 

3) LL 구문 분석 기법(Left, Left : 왼쪽으로부터 읽고, 좌측 유도 함)

∙ 하향식(Top-Down) 과정의 반복 검조(Backtracking) 문제에 대한 해결책이 LL 파싱

∙ 좌측 유도(left most derivation)

4) LR 구문 분석 기법(Left, Right : 왼쪽으로부터 읽고, 우측 유도함)

∙ 상향식(Bottom_Up) 방법으로 가장 보편적인 파싱 방법

∙ 우측 유도(right most derivation)