카테고리 없음

프로그래밍 언어론 4장

CodeHS 2024. 11. 14. 02:59

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

1. 컴퓨터 시스템의 이해

1.1 컴퓨터 시스템의 정의

  • 프로그램 저장 및 실행 가능한 알고리즘 집합
  • 알고리즘과 자료구조의 결합체
  • 처리 방법과 데이터의 통합 시스템

1.2 컴퓨터 시스템의 분류

  1. 실제 컴퓨터 (Actual Computer)
    • 물리적 하드웨어 시스템
    • 직접 만질 수 있는 실체
  2. 소프트웨어 시뮬레이티드 컴퓨터 (Software Simulated Computer)
    • 가상 컴퓨터 (Virtual Computer)
    • 목적에 따라 다른 형태로 동작
    • 예: C 컴퓨터, Java 컴퓨터, 동영상 재생기 등

1.3 컴퓨터의 용도별 분류

  1. 범용 컴퓨터
    • 다양한 목적으로 사용 가능
    • 소프트웨어에 따라 기능 변경
    • PC, 노트북 등
  2. 임베디드 컴퓨터
    • 특정 목적만을 위한 시스템
    • 예: 항공기 제어 시스템, 게임기
    • 제한된 기능만 수행

2. 프로그래밍 언어의 문자 체계

2.1 기본 문자 집합

  • 언어별 상이한 문자 집합 정의
  • 예시:
    • FORTRAN: 알파벳, 숫자, 13개 특수문자
    • ALGOL 60: 대소문자 구분, 28개 특수문자

2.2 문자 코드 체계

  1. EBCDIC 코드
    • IBM 제안
    • 8비트 조합 코드
    • 한 문자 = 1바이트
  2. ASCII 코드
    • 미국표준코드 (ANSI 제안)
    • 7비트 사용 (128개 문자)
    • 1비트는 패리티 비트로 활용
    • 현재 가장 널리 사용
  3. 유니코드
    • 16비트(2바이트) 체계
    • ISO 표준 규격
    • 국제 문자 통신용
    • Java에서 처음 채택

2.3 문자의 정합 순서 (Collating Sequence)

  • 문자간 순서 관계 정의
  • 코드 값에 따른 순서 결정
  • 정렬과 비교 연산에 활용
  • 예: ASCII 코드 기준 순서

3. 어휘 구조 (Lexical Structure)

3.1 어휘 토큰 (Lexical Token)

  • 더 이상 분할할 수 없는 기본 단위
  • 프로그래밍 언어의 기본 구성 요소
  • 용어:
    • Lexical Token
    • Lexical Element
    • Lexical Unit

3.2 식별자 (Identifier)

  • 언어의 기본 구성 요소
  • 예약어/키워드 포함
  • 변수명으로 사용 불가
  • 장점:
    • 프로그램 판독성 향상
    • 컴파일러의 효율적 처리

3.3 구분자 (Delimiter)

  • 문장과 표현식의 구분
  • 예: 콤마, 세미콜론, 콜론
  • 문법적 역할 수행

프로그래밍 언어의 문법 정의 방법

1. BNF (Backus-Naur Form) 표기법

1.1 기본 개념

  • 베커스와 나우어가 개발한 문법 정의 형식
  • 구문(syntax) 정의를 위한 가장 보편적인 표기법
  • 언어의 문장 생성 규칙을 정의

1.2 생성 규칙(Production Rule)의 구조

  • ::= 기호를 중심으로 좌우 구분
  • 좌측: 정의할 대상 (non-terminal symbol)
  • 우측: 실제 정의 내용
  • 예시:
  • identifier ::= letter | identifier letter | identifier digit letter ::= A | B | C | ... | Z

1.3 확장 BNF (EBNF)

  1. 추가된 메타 기호
    • { }: 반복 (0회 이상)
    • [ ] [ ]: 선택적 사용 (0 또는 1회)
    • { }n,m: n~m회 반복
  2. 메타 기호 목록
    • 기본: 각괄호, 수직바(|), ::=
    • 확장: 중괄호, 대괄호, 숫자 표현

2. 구문 도표(Syntax Diagram)

2.1 기본 특징

  • 문법을 그래픽으로 표현
  • 직관적 이해 용이
  • 순서도와 유사한 형태

2.2 표현 방법

  1. 기본 요소
    • 사각형: non-terminal 심볼
    • 원/타원: terminal 심볼
    • 화살표: 흐름 방향
  2. 주요 표현
    • 순차: 직렬 연결
    • 선택: 병렬 경로
    • 반복: 순환 경로

2.3 EBNF와의 대응

  1. 반복 표현
    • { }: 순환 경로로 표현
    • [ ] [ ]: 우회 경로 제공
  2. 선택 표현
    • |: 병렬 경로로 표현

3. 적용 예시: Pascal 프로그램 구조

3.1 기본 구조

SubPascal ::= program identifier ; block .
block ::= [constant-declaration]
          [variable-declaration]
          {procedure-declaration}
          compound-statement

3.2 구문 도표 표현

  1. 프로그램 구조
    • program → identifier → ; → block → .
  2. 블록 구조
    • 상수선언 (선택)
    • 변수선언 (선택)
    • 프로시저선언 (반복)
    • 복합문 (필수)

3.3 변수 선언 예시

var identifier : type ;

구문 도표:

  • var → identifier → : → type → ;
  • 다중 선언: identifier → , → identifier → … → : → type

4. 문법 정의의 장점

  1. 형식적 명세
    • 명확한 문법 규칙 정의
    • 모호성 제거
  2. 자동화 도구 활용
    • 컴파일러 생성 도구 사용 가능
    • 문법 검증 자동화
  3. 문서화
    • 명확한 언어 규격 제시
    • 학습 및 참조 용이

파스 트리와 프로그래밍 언어 구현 기법

1. 파스 트리 (Parse Tree)

1.1 기본 개념

  • BNF로 정의된 문법의 트리 형태 표현
  • 컴파일러의 구문 분석에서 주로 사용
  • 파싱(parsing): 문법 검사 과정

1.2 파스 트리의 고려사항

  1. 모호성(Ambiguity)
    • 동일한 식별자에 대한 여러 해석 가능성
    • 예: test1 식별자의 다양한 생성 경로
    • 컴파일러는 결정적(deterministic) 해석 필요
  2. 결합성(Associativity)
    • 연산자의 결합 방향 중요
    • 예: 거듭제곱 연산의 우측 결합성
  3. 우선순위(Precedence)
    • 연산자 간의 우선순위 고려
    • 예: 7-3-2의 올바른 계산 순서

2. 프로그래밍 언어의 신뢰성 문제

2.1 구문 오류 사례

  1. FORTRAN의 모호성
    • 콤마 누락으로 인한 해석 모호성
  2. DO 2.6
  3. PL/I의 연산자 모호성
    • 대입연산자와 비교연산자 구분 불가
  4. A = B = C
  5. IF-ELSE 문제 (Dangling Else)
    • ELSE 문장의 소속 모호성
    • 중괄호/블록 사용으로 해결

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

3.1 번역 기법 (Translation)

  1. 구성 요소
    • 컴파일러
    • 어셈블러
    • 링커(Linkage Editor)
    • 로더
    • 전처리기(Preprocessor)
  2. 처리 과정
    • 원시 프로그램 → 목적 모듈(.obj)
    • 목적 모듈들의 링킹 → 로드 모듈(.exe)
    • 로더를 통한 메모리 적재 및 실행

3.2 인터프리터 기법 (Interpreter)

  1. 특징
    • 직접 실행 방식
    • 중간 코드 생성 후 즉시 실행
    • 예: SQL, PHP 등
  2. 장단점
    • 장점: 높은 유연성, 적은 메모리 사용
    • 단점: 상대적으로 느린 실행 속도

3.3 효율성과 적응성의 관계

  • 번역 기법: 높은 효율성, 낮은 적응성
  • 인터프리터 기법: 낮은 효율성, 높은 적응성

3.4 하이브리드 접근

  • 순수 번역/인터프리터의 혼합
  • 각 방식의 장점 활용
  • 현대 언어들의 일반적 접근법

4. 대표적 언어별 구현 방식

4.1 컴파일러 언어

  • C/C++/C# 계열
  • FORTRAN, Pascal
  • Ada

4.2 인터프리터 언어

  • LISP
  • SNOBOL
  • APL
  • Prolog