[프로그래밍언어론] 언어의 구문과 구현 기법

 

 

이 글은 국민대학교 강승식 교수님의 '프로그래밍언어론' 수업을 토대로
개인적으로 학습한 내용입니다.

 

 

4.1 언어 구문

 

고급언어를 정의할 때는 두 가지 측면에서 설명이 필요함

• 구문 : 문법적인 형식 (Syntax)
  
  
• 의미 : 동작의 의미 (Semantics)
  
  

사람이 읽는 자연어로 설명하는 자연어 정의와 수학적 기호나 형식 언어(BNF 등) 으로 정확하게 정의하는 형식 정의가 있음

=> 구문 형식 정의의 종류에는 BNF, EBNF, 구문 도표 등이 있음

 

가상 컴퓨터

고급 언어 프로그래머는 컴퓨터를 가상의 고급 언어 컴퓨터로 간주함

=> 즉, 개발자마다 컴퓨터 하드웨어를 보는 관점이 다름

 

4.1.1 프로그래밍 언어의 어휘구조

 

프로그래밍 언어의 기본 문자 집합은 알파벳 문자 26개(A - Z) + 아라비아 숫자 10개 (0 - 9) 임

=> Fortran의 경우는 기본 문자 집합에 13개의 특수문자를 더해서 49개의 문자만 사용

=> Algol 60의 경우는 알파벳 대소문자 52개 + 아라비아 숫자 10개 + 28개의 특수문자를 사용

 

문자 코드 체계

 

 

• 1. EBCDIC
  
  IBM에서 제안, 8비트 조합 코드
  
  
• 2. ASCII (개인용 컴퓨터가 자리잡으면서 대중화)
  
  ANSI에서 제안, 7비트 조합 코드(128개의 문자 표현) 
  
  -> 영문자 대소문자 52개 + 숫자 10개 + 33개의 특수문자 + 33개의 제어문자
  
  
• 3. Unicode 
  
  16 bit(BMP) - 초창기, 21 bit(SMP) - 현재
  
  -> Java, Python 등에서 기본 인코딩으로 사용됨 (UTF-8 형식)
  
  (Unicode는 그냥 정의하는 문자표인거고 UTF-8은 그걸 저장하는 방식 즉, 인코딩 형식임 -> Unicode를 표현하는 방법 중 하나)

 

정합 순서(collating sequence) : 문자들 간의 순서 

=> 언어에 제공된 문자 순서, 일반 순서 지킴
(예를 들어, 어떤 기준으로 정렬할지 정해야 할 때 필요함)

ex. 0 < 1 < 2 < .. < 9
ex. A < B < C < ... < Y < Z

특수 문자 순서

=> 코드 체계 따름 (구현시 결정)

(ASCII에서 A는 65, a는 97로 대문자가 소문자 보다 앞섬 -> 사용하는 문자 인코딩 체계를 따름)

RPG, SNOBOL 같은 고전 언어들에서는 프로그래머가 직접 정합 순서를 정의할 수 있음

 

 

4.1.2 문맥 자유문법과 BNF, EBNF

 

BNF (Backus-Naur Form) 표기법

 

• 구문(syntax) 형식을 정의하는 가장 보편적인 표기법
  
  
• 한 언어의 구문에 대한 BNF 정의
  
  => 언어의 문장을 생성하는 생성 규칙(Production rule) 정의
  
  
• 생성 규칙
  
  => 생성 규칙의 왼쪽 (정의될 대상), 오른쪽에는 그 대상에 대한 정의

 

BNF 표기법에 의한 식별자(identifier) 정의

 

 

메타 기호

::= 정의하다
<> 비단말기호(nonterminal symbol)
| 택일 기호

 

 

EBNF (Extended Backus - Naur Form)

 

• BNF 표기법의 확장
  
  => BNF 보다 읽기 쉽고, 간단하게 표현된 표기법

 

• BNF에 추가된 EBNF의 메타 기호
  
  
  • 반복 : { }
    
    
  • 선택 : [ ]
    
    
  • 택일 : (a | b)

 

{ }, [ ], |, ( ), ::= 와 같은 메타 기호를 terminal 기호로 사용하는 경우, ‘|’, ‘::=’ 와 같이 인용부호로 묶어 표현

 

 

4.1.3 구문 도표 (Syntax diagram)

 

구문 도표는 그 형태가 순서도와 유사

 

 

구문 도표는 EBNF와 일대일 대응임

 

• 다시 정의될 대상(nonterminal)은 네모칸
  
  
• 단말 기호(terminal)는 원이나 타원형으로 표시하고 지시선으로 연결

 

구문 도표 그리는 방법

 

 

 

 

 

 

4.1.4 파스 트리와 추상 구문 트리

 

파스 트리(parse tree)

 

• 원시 프로그램의 문장 분석 과정에서 생성되는 트리 형태의 자료구조
  
  
• 어떤 문장이 BNF에 의해 성성될 수 있는지 여부를 나타냄
  
  

식별자 정의 BNF를 통해 'TEST1'의 파스 트리 생성

 

4.1.5 모호성, 결합성 및 우선 순위

 

모호(ambiguous)는 같은 문장에 대해 두 가지 파스 트리가 생성되는 것임

첫 번째 예시

 

 

위의 BNF를 기준으로 서로 다른 유도 과정을 거쳐 "B 3 3" 이 생성되는 것을 보면

 

1. <identifier>

→ <identifier> <digit>

→ <identifier> 3

→ <identifier> <digit> 3

→ <identifier> 3 3

→ <letter> 3 3

→ B 3 3

 

2. <identifier>

→ <identifier> <digit>

→ <identifier> <digit> <digit>

→ <letter> <digit> <digit> 

→ B <digit> <digit>

→ B 3 <digit>

→ B 3 3

 

인데 이 두 유도 과정의 결과로 나오는 parse tree의 모양이 동일하면 상관 없음

 

동일한 parse tree가 그려지면 상관 없음

 

 

두 번째 예시

 

하지만 다른 유도 과정으로 다른 파스 트리가 구성될 수 있는데 이러면 모호한 문법임

 

 

 

모호성 제거 방법

 

결론부터 말하면 결합규칙과 우선 순위로 모호성을 해결할 수 있음

 

 

Precedence cascade : 새 비단말기호 <term>과 문법 규칙을 추가하여 문법의 우선순위를 결정

 

 

 

오른쪽에 자기 자신이 2번 이상 나타나면 모호한 문법임

 

 

예를 들면 "7 - 3- 2" 는 좌 결합 또는 우 결합의 두 가지로 파싱 가능함

 

 

BNF 문법에 좌순환 규칙을 사용하면 좌-결합 지원 가능

 

 

 

<exp> ::= <exp> - <exp> 를 <exp> ::= <exp> - <term> 으로 대치해서 좌-결합으로 파싱

 

또는, <exp> ::= <exp> - <exp> 를 <exp> ::= <term> - <exp> 로 대치해서 우-결합 으로 파싱

 

 

우선 순위와 좌-결합 규칙을 반영하여 모호성 해소

 

 

<exp>
⇒ <exp> - <term>
⇒ <exp> - <term> - <term>
⇒ <term> - <term> - <term>
⇒ <factor> - <term> - <term>
⇒ <number> - <term> - <term>
⇒ 7 - <term> - <term>
⇒ 7 - <factor> - <term>
⇒ 7 - <number> - <term>
⇒ 7 - 3 - <term>
⇒ 7 - 3 - <factor>
⇒ 7 - 3 - <number>
⇒ 7 - 3 - 2

 

=> 위 그림에서 exp가 자기 자신을 왼쪽에 두니까 왼쪽부터 줄줄이 결합되는 좌-결합임

 

모호성 해결에 대해 정리를 해보면

 

• + 나 * 같은 연산 중 무슨 연산이 먼저 수행될지를 precedence cascade로 결정
  
  
• 동일한 우선 순위의 연산자 끼리는 어떤 방향으로 결합할지 결합 규칙(좌/우-결합)을 명시

 

4.1.6 구문과 프로그램의 신뢰성

 

구문 (syntax) : 언어의 신뢰성에 영향

 

FORTRAN

 

DO 10 I = 2.6
A(I) = B + C(I)
10 CONTINUE

 

FORTRAN은 공백(띄어쓰기)를 무시하는 특성이 있기에 기존에 의도했던 I를 2부터 6까지 변화시키는 DO 루프가 아니라 DO10I 라는 변수에 2.6을 할당하는 문장으로 해석됨

=> ' . ' 말고 ' , ' 를 사용해야함

 

PL/I

 

A = B = C;

 

 

PL/I 에서 다중배정문의 의미는 A와 B에 C 값을 저장하는 것임

=> 다중 배정문이 우-결합 으로 처리되므로 먼저 B=C 가 평가가 되고 그 결과가 다시 A = (B = C) 로 평가되므로 A 와 B 모두 C 값을 갖게됨

초보자는 왼쪽부터 평가되는줄 알 수 도 있기에 굉장히 모호한 문법임
(우결합인지 좌결합인지를 알고 있어야 정확히 동작을 이해할 수 있기에 가독성과 신뢰성 저하)

 

Dangling else 문제

 

중첩된 if 문에서 else는 어떤 if의 else인가?

 

 

4.2 프로그래밍 언어 구현 기법

 

컴퓨터 프로그램의 번역 및 실행

 

• Actual computer (hardware) - 기계어만 이해 , software simulated computer - 실제 하드웨어 위에 만들어진 가상 환경
  
  ex. Cobol computer(가상 컴퓨터) → 번역기 구성
  
  (COBOL은 고급 언어이기 때문에 직접 CPU에서 실행할 수 없고 COBOL 컴퓨터라는 가상 개념을 만드는 것임)
• 번역된 프로그램 실행 → hardware + software(virtual computer)
  
  (COBOL 컴퓨터 = 실제 컴퓨터 + COBOL을 흉내내는 번역기 소프트웨어)
  
  
• 이론적으로 고급 언어를 기계언어로 하는 hardware 구성 가능
  
  → 속도는 빠를 수 있지만 적응성, 비용의 문제로 저급 수준의 언어(C, 어셈블리)를 기계언어로 하는 컴퓨터 제공 
  
  
• 사용자 : 고급언어 프로그래밍 →  기계 : 저급 언어 프로그래밍
  
  (컴파일러/인터프리터 등 언어구현 과정을 통해 변환)

 

4.2.1 번역 기법

 

 

 

컴파일 할 때 는 상대 주소 (시작점으로 부터 +n 바이트 형식인 +10) 를 주고 링커에서만 절대 주소(메모리 상의 정확한 위치인 0x0040100 ~)를 줘버릴 수 도 있고

 

컴파일할 때 미리 절대 주소를 줘버릴 수 도 있어서 목적 모듈과 로드 모듈은 일치할 수 도 있고 안할 수 도 있음

 

번역기의 종류

 

• 컴파일러(compiler)
  
  • 원시 언어 : 고급 언어
    
    
  • 목적 언어 : 실제 기계 언어에 가까운 저급 언어
    
    => 목적 모듈(.obj)는 기계어와 유사한 저급 언어지만, 아직 실행은 안됨!
    (링커를 통해 연결돼야 실행 가능한 파일이됨)
    
    

GPT

큰 프로그램을 여러 소스 파일로 나누고 각각을 따로 컴파일한 다음 나중에 링크해서 하나로 만드는 방식을 분리 컴파일이라고 하는데 Python 같은 언어에서는 이게 불가능하기에 큰 프로젝트에서 불리함 
(Python에서 큰 프로젝트를 분리하고 싶으면 모듈화 해야함)

 

• 어셈블러(assembler)
  
  
  • 원시 언어 : 어셈블리 언어
    
    
  • 목적 언어 : 준기계어 형태
    
    
• 링키지 에디터(linkage editor)
  
  
  • 여러 개의 프로그램(재배치 형태 기계어)을 묶어서 로드 모듈 생성
    
    
  • 로드 모듈 : 어느 정도 실행 가능한 하나의 기계어 프로그램
    
    =>여러 개의 .obj 파일을 묶어서 .exe파일 (로드 모듈) 을 만들고 절대 주소를 부여한 상태임
    
    
• 로더(loader)
  
  
  • 기계어 프로그램(로드 모듈)을 실제 실행 가능한 기계어로 번역하여 주기억 장치에 적재
    
    => .exe 를 메인 메모리(RAM)에 올려서 기계어 명령이 CPU에서 실행 가능하도록 만들어줌
    
    
• 프리프로세서(preprocessor)
  
  
  • 원시 언어와 목적 언어가 모두 고급 언어인 번역기
    
    
  • 고급 언어 프로그램을 다른 고급 언어로 번역 후, 출력된 고급 언어를 이미 구현된 방법으로 실행시킬 때 사용
    
    
  • 고급 언어에 대한 언어 확장하여 구현 시 유용 (C++, concurrent C)

 

4.2.2 인터프리터 기법

 

하드웨어로 인터프리터를 구현할 수도 있음

 

 

4.2.3 인터프리터 기법과 번역 기법

 

번역기(컴파일러) : 원시 코드와 동일한 의미의 목적 코드 생성
인터프리터 : 원시 코드를 문장 단위로 해석하여 직접 실행

 

 

순수 번역 기법이나  순수 시뮬레이션 기법은 실제로 거의 존재치 않음

 

 

순수 번역 기법 : 고급언어를 번역하여 바로 실행

=> object module로 번역 -> link -> load -> 실행

(한 번에 전체 프로그램을 기계어로 변환하고, 그걸 실행하는 방식)

순수 시뮬레이션 기법 : JCL, APL 등

(고급 언어 프로그램을 기계어로 바꾸지 않고, 인터프리터가 명령어를 직접 읽고 수행하는 방식)

 

 

현실에서는 순수 번역 기법에서 보통 컴파일한 뒤에도 다양한 런타임 작업들이 있고 시뮬레이션 기법에서도 실제로는 해석 + 번역 + 캐싱 등 다양한 기법이 섞여 있기에 순수 번역 기법이나  순수 시뮬레이션 기법은 실제로 거의 존재치 않음

 

컴파일러와 인터프리터

 

번역 기법(컴파일러)의 장단점

 

• 장점 : 실행 시간 효율성 제공 (한 번 디코딩으로 반복 실행)
  
  => 컴파일러는 소스코드를 한 번에 전부 기계어로 번역해서 .exe, .out 같은 실행파일로 만들고 이 실행파일은 이미 CPU가 바로 이해할 수 있는 기계어(binary)로 되어 있으니까, 실행할 때 더 이상 해석이 필요 없이 실행 가능함
  
  (여러 번 반복해서 실행하는 경우 빠르고 효율적)
  
  
• 단점 : 번역된 프로그램이 큰 기억장치(메모리나 디스크) 요구 (I/O routine 등)
  
  => 컴파일러는 실행파일을 만들 때 사용자가 작성한 코드뿐 아니라, 필요한 표준 입출력 루틴(I/O routine), 라이브러리 코드, 런타임 환경 등을 전부 포함시키기에 실행파일의 덩치가 커지고 메모리(RAM)나 디스크 저장 공간이 더 필요함
  
  

인터프리터 기법의 장단점

 

• 번역 기법과 장단점이 반대임
  
  
• 사용자 유연성(flexibility) 제공
  
  => 코드를 조금 바꾸고 컴파일 없이 곧바로 실행 가능
  (한 줄 한 줄 실행하기에 원하는 부분만 테스트하거나 실행해볼 수 있음)

 

하이브리드 기법

 

 

 

프로그램을 실행시키기 쉬운 형태로 번역한 후, 그 번역된 형태의 프로그램을 디코드하여 시뮬레이션으로 실행

현재 대부분의 인터프리터 언어가 이 방법을 따름 
(중간 형태 코드가 저급이면 번역 기법으로 간주되기도함)