[프로그래밍 언어론] 2.프로그래밍 언어 의미론

용어

• lexeme(어휘소): 문장에서 가장 작은 단위의 의미구조
• Token: lexeme의 종류

언어의 일반적인 정의

• Recognizers
  • 입력 문자열을 읽고 언어의 어느 부분에 속하는지 확인
  • 컴파일러의 syntax analysis
• Generators
  • 언어의 문장을 생성함
  • Generator와 비교함으로써 특정 문장의 구문법이 맞는지 확인할 수 있음

Context-Free Grammars (CFG)

• Terminal 심볼 집합: T
  • 작성법이 문법 규칙에 의해 정해져 있지 않음, 구문적 변수 역할, 왼쪽에 위치 가능
• Nonterminal 심볼 집합: N
  • 작성법이 문법 규칙에 의해 정해져 있음, 오른쪽에만 존재
• 시작 심볼: S(N에 속함)

CFG의 유도

• 입력된 문장이 문법에 맞는지 검사하는것을 유도라고 한다.
• 유도가 가능하다면 문법에 맞는 스트링임

일반 유도

직접 유도

유도 예시

BNF

• 문법을 구성하는 형식

EBNF

• BNF의 확장판

 

• {}: 0번 이상 나타날 수 있음
• []: 0번 혹은 1번 나타날 수 있음

구문 다이어그램

• 넌터미널은 사각형
• 터미널은 원으로

모호성

어떤 스트링에 대해 두 개 이상의 좌측 유도를 갖는 문법을 모호한 문법이라 함

모호성을 해결하기 위한 방법

1. 모호한 문법을 같은 언어를 정의하는 모호하지 않은 문법으로 재작성
2. 언어의 구문법을 모호하지 않도록 일부 수정한다.

정적 의미론(Static Semantics)

정적 의미론은 프로그래밍 언어의 단어와 문구의 의미를 연구하는 학문 분야입니다. 컴파일러 및 인터프리터와 같은 프로그래밍 언어 도구에 의해 프로그램이 실행되기 전에 확인할 수 있는 프로그램의 속성을 다룹니다.

정적 의미론은 다음과 같은 속성을 포함합니다.

• 형식 검사: 변수와 식의 데이터 형식이 서로 호환되는지 확인합니다.
• 범위 검사: 변수가 사용되기 전에 선언되었는지 확인합니다.
• 흐름 제어 검사: 프로그램이 올바른 순서로 실행되는지 확인합니다.

정적 의미론과 문법의 차이점

문법은 프로그래밍 언어의 단어와 문구를 구성하는 규칙을 다룹니다. 반면 정적 의미론은 단어와 문구의 의미를 다룹니다.

예를 들어, 다음 C 코드는 문법적으로 올바르지만 정적 의미론적으로 잘못되었습니다.

int x;
x = y;

이 코드는 문법적으로 올바르지만 y 변수가 선언되지 않았기 때문에 정적 의미론적으로 잘못되었습니다.

정적 의미론을 설명하는 데 사용되는 도구

정적 의미론을 설명하는 데 사용되는 몇 가지 도구는 다음과 같습니다.

• 문맥 자유 문법(CFG): 프로그래밍 언어의 단어와 문구를 구성하는 규칙을 정의하는 데 사용됩니다.
• 속성 문법: CFG에 속성을 추가하여 프로그램의 의미를 정의하는 데 사용됩니다.
• 형식 시스템: 프로그램의 의미를 정의하는 데 사용되는 수학적 시스템입니다.

속성 문법

속성 문법은 문맥 자유 문법(CFG)에 속성을 추가하여 프로그램의 의미를 정의하는 데 사용되는 도구입니다. 속성은 문법 규칙의 노드에 연결된 값입니다. 속성은 다음과 같은 정보를 저장하는 데 사용될 수 있습니다.

• 변수의 데이터 형식
• 식의 값
• 문의 제어 흐름

속성 문법의 구성 요소

속성 문법은 다음과 같은 구성 요소로 구성됩니다.

• 문맥 자유 문법(CFG): 프로그래밍 언어의 단어와 문구를 구성하는 규칙을 정의합니다.
• 속성: CFG의 노드에 연결된 값입니다.
• 속성 규칙: 속성의 값을 계산하는 방법을 정의합니다.

속성 문법을 사용하여 프로그래밍 언어의 정적 의미론을 정의하는 방법에 대한 예

다음은 속성 문법을 사용하여 C 언어의 정적 의미론을 정의하는 방법의 예입니다.

S -> E ;
E -> id | E + E | E * E
id -> <identifier>

<identifier>.type = string
<identifier>.value = NULL

E.type = E1.type + E2.type
E.value = E1.value + E2.value

E1.type = E2.type
E1.value = E2.value

이 속성 문법은 다음과 같은 의미를 정의합니다.

• id 규칙은 식별자의 데이터 형식을 문자열로 설정하고 값을 NULL로 설정합니다.
• E 규칙은 식의 데이터 형식을 두 식의 데이터 형식의 합으로 설정하고 값을 두 식의 값의 합으로 설정합니다.
• E1 규칙은 식의 데이터 형식을 E2 규칙의 데이터 형식으로 설정하고 값을 E2 규칙의 값으로 설정합니다.

속성 문법 트리 예시

 

운영 의미론(Operational Semantics)

운영 의미론은 언어 표현의 의미를 실제 계산 과정으로 정의하는 방식입니다. 즉, 특정 표현을 해석하는 방법을 입력 문자열을 처리하는 추상 기계의 동작 규칙으로 설명합니다. 이 기계는 추상적인 개념이지만, 언어 표현이 어떻게 평가되고 결과를 산출하는지 명확하게 모델링하는 데 도움이 됩니다.

운영 의미론의 한계:

• 더 나은 대안: 완전한 컴퓨터 시뮬레이션: 텍스트는 프로그램 동작을 이해하는 데 있어 전체 컴퓨터 시스템을 시뮬레이션하는 것이 더 직관적일 수 있다고 제안합니다. 여기에는 다음과 같은 단계가 포함됩니다.
  • 번역기 구축: 이 프로그램은 소스 코드(프로그래밍 언어로 작성된 코드)를 가상 컴퓨터의 기계 코드로 변환합니다.
  • 시뮬레이터 구축: 이 프로그램은 가상 컴퓨터의 동작을 모방하여 변환된 기계 코드를 실행합니다.
• 공식적인 사용의 복잡성: 운영 의미론은 비공식적인 설명(예: 언어 설명서)에는 적합하지만 공식적인 정의에 사용될 때 매우 복잡해질 수 있습니다.

Denotational Semantics (지시 의미론)

지시 의미론은 추상적인 수학적 구조를 사용하여 프로그래밍 언어 표현의 의미를 정의하는 방식입니다. 즉, 프로그램의 의미를 함수, 값, 또는 집합과 같은 수학적 개념으로 매핑합니다.

지시 의미론의 주요 특징은 다음과 같습니다.

• 수학적 기반: 수학적 개념을 사용하여 의미를 정의하기 때문에 명확하고 정확한 정의가 가능합니다.
• 구조적: 프로그램을 작은 부분으로 분해하고 각 부분의 의미를 정의하여 전체 프로그램의 의미를 구성합니다.
• 재귀적: 재귀 함수에 기반합니다.
• 종합적: 다양한 프로그래밍 언어 구조 (예: 조건문, 반복문, 함수 등)를 처리할 수 있는 일반적인 프레임워크를 제공합니다.

지시 의미론의 작동 방식

지시 의미론은 일반적으로 다음과 같은 단계를 거쳐 진행됩니다.

1. 문법 분석: 프로그램 문장을 구문 분석하여 문법 구조를 파악합니다.
2. 구조적 의미 해석: 구문 분석 결과를 바탕으로 각 문법 요소의 의미를 정의합니다.
3. 구성: 각 문법 요소의 의미를 조합하여 전체 프로그램의 의미를 정의합니다.

지시 의미론의 예시

예를 들어, 간단한 산술 표현식 2 + 3을 생각해 보겠습니다. 지시 의미론 관점에서 이 표현식을 해석하면 다음과 같이 단계별로 진행됩니다.

1. 문법 분석: 2 + 3을 숫자 2와 연산자 +, 숫자 3으로 구성된 문법 구조로 분석합니다.
2. 구조적 의미 해석:
   • 숫자 2는 그 자체의 값을 의미합니다.
   • 연산자 +는 두 숫자를 더하는 함수를 의미합니다.
   • 숫자 3은 그 자체의 값을 의미합니다.
3. 구성: + 함수에 2와 3을 입력하면 결과값 5를 얻습니다.

따라서, 지시 의미론 관점에서 2 + 3 표현식의 의미는 5라는 값을 반환하는 함수로 해석될 수 있습니다.

지시 의미론의 장점

• 명확성: 수학적 개념을 사용하여 의미를 정의하기 때문에 명확하고 정확한 정의가 가능합니다.
• 정확성: 모호성을 줄이고 프로그램의 의미에 대한 일관된 해석을 제공합니다.
• 분석력: 복잡한 프로그램 구조를 작은 부분으로 분해하고 각 부분의 의미를 명확하게 분석할 수 있도록 합니다.
• 구현 가능성: 수학적 개념을 기반으로 하기 때문에, 컴퓨터 프로그램으로 구현하여 자동화된 의미 분석 도구를 개발하는 데 활용할 수 있습니다.

공리 의미론(Axiomatic Semantics)

공리 의미론은 논리적 체계를 사용하여 프로그래밍 언어 표현의 의미를 정의하는 방식입니다. 즉, 프로그램의 의미를 논리적 명제와 추론 규칙으로 구성된 형식 시스템으로 표현합니다. 이를 통해 프로그램의 동작을 추론하고, 정확성을 증명할 수 있도록 합니다.

공리 의미론의 주요 특징은 다음과 같습니다.

• 논리적 기반: 논리적 명제와 추론 규칙을 사용하여 의미를 정의하기 때문에 명확하고 엄밀한 정의가 가능합니다.
• 구조적: 프로그램을 작은 부분으로 분해하고 각 부분의 의미를 정의하여 전체 프로그램의 의미를 구성합니다.
• 추론 가능성: 프로그램의 동작을 추론하고, 정확성을 증명하는 데 활용될 수 있습니다.

공리 의미론의 작동 방식

공리 의미론은 일반적으로 다음과 같은 단계를 거쳐 진행됩니다.

1. 문법 분석: 프로그램 문장을 구문 분석하여 문법 구조를 파악합니다.
2. 구문적 의미 해석: 구문 분석 결과를 바탕으로 각 문법 요소의 의미를 정의합니다.
3. 구성: 각 문법 요소의 의미를 조합하여 전체 프로그램의 의미를 정의합니다.
4. 추론: 프로그램의 동작을 추론하고, 정확성을 증명하기 위해 논리적 추론 규칙을 적용합니다.

공리 의미론의 예시

예를 들어, 간단한 산술 표현식 2 + 3을 생각해 보겠습니다. 공리 의미론 관점에서 이 표현식을 해석하면 다음과 같이 단계별로 진행됩니다.

1. 문법 분석: 2 + 3을 숫자 2와 연산자 +, 숫자 3으로 구성된 문법 구조로 분석합니다.
2. 구문적 의미 해석:
   • 숫자 2는 그 자체의 값을 의미하는 논리적 명제로 표현됩니다.
   • 연산자 +는 두 숫자를 더하는 함수를 의미하는 논리적 명제로 표현됩니다.
   • 숫자 3은 그 자체의 값을 의미하는 논리적 명제로 표현됩니다.
3. 구성: + 함수에 2와 3을 입력하면 결과값 5를 얻는 논리적 명제를 구성합니다.
4. 추론: 논리적 추론 규칙을 사용하여 표현식의 의미가 5임을 증명합니다.

공리 의미론의 활용

공리 의미론은 프로그래밍 언어, 타입 시스템, 정형 증명 등 다양한 분야에서 활용됩니다.

• 프로그래밍 언어: 프로그래밍 언어의 명확하고 엄밀한 의미 정의를 제공합니다.
• 타입 시스템: 타입 체크 시스템의 기반을 제공합니다.
• 정형 증명: 프로그램의 정확성을 증명하는 데 사용됩니다.

공리 의미론의 장점

• 명확성: 논리적 명제와 추론 규칙을 사용하기 때문에 명확하고 엄밀한 정의가 가능합니다.
• 정확성: 모호성을 줄이고 프로그램의 의미에 대한 일관된 해석을 제공합니다.
• 추론 가능성: 프로그램의 동작을 추론하고, 정확성을 증명하는 데 활용될 수 있습니다.
• 분석력: 복잡한 프로그램 구조를 작은 부분으로 분해하고 각 부분의 의미를 명확하게 분석할 수 있도록 합니다.

공리 의미론의 단점

• 추상성: 논리적 개념을 사용하기 때문에 이해하기 어려울 수 있습니다.
• 복잡성: 복잡한 프로그램의 경우 의미 정의와 증명이 매우 복잡해질 수 있습니다.
• 비효율성: 추론 과정이 비효율적일 수 있습니다.