[프로그래밍언어론📐] 5장 의미론

출처 : 프로그래밍 언어론 : 원리와 실제 (창병모, 인피니티북스, 2021)

 

5.0 의미론

1) 의미론의 개요

-  프로그램의 의미와 정확한 정의 및 이해

- 소프트웨어의 정확한 명세

- 소프트웨어 시스템에 대한 검증 혹은 추론

- 컴파일러 혹은 해석기 작성의 기초

 

2) 의미론의 종류

- 작동 의미론 (Operational Semantics)

• 프로그램의 의미를 프로그램 실행(작동) 과정으로 설명

- 표기 의미론 (Denotational Semantics)

• 프로그램의 의미를 함수 형태로 정의하여 설명

- 공리 의미론 (Axiomatic Semantics)

• 프로그램의 시작 상태와 종료 상태를 논리적 선언(assertion) 형태로 정의하여 설명

 

5.1 수식의 의미

1) 수식

- 상태에서 수식의 값

- V : (State, Expr) → Value

 

2) 연산자 우선순위

- 연산자를 실행하는 순서

 

3) 연산자 결합성

- 동일한 우선순위를 갖는 연산자가  두 개 이상 인접한 경우 무엇을 먼저 수행하느냐에 대한 규칙

 

4) 결합성

- 좌결합 (left associative)

• 왼쪽부터 우선 결합하는 규칙으로 왼쪽에서 오른쪽으로 수행
• 대부분의 이항 연산자가 따르는 규칙
• 좌순환 규칙(left recursive rule)으로 표현

- 우결합 (right associative)

• 오른쪽부터 우선 결합하는 규칙
• 대부분의 단항 연산자들과 대입 연산자들이 따르는 규칙
• 우순환 규칙(right recursive rule)으로 표현

5.2 구조적 프로그래밍

1) 구조적 프로그래밍

- 기본 아이디어

• goto문을 사용하지 않고 시작과 끝 지점이 일정한 구조적 구문 사용
• 프로그램에 있는 각각의 구조와 그 사이의 관계를 이해하면 프로그램 전체를 보다 십게 이해 가능

- 구조적 프로그램 정리

• 어떤 계산함수든 순차, 서택, 반복의 3가지 제어 구조로 표현 가능

 

2) 설탕 구문 (Syntactic sugar)

- 프로그래밍 편의를 위해 제공하는 부가적인 문장

ex)

• do while 문 ➡️ while문 사용
• for 문 ➡️ while문 사용
• switch문 ➡️ if문 사용

 

5.3 문장의 의미

1) 작동 의미론 (Operational Semantics)

- 기본 아이디어

• 프로그램의 의미를 프로그램 실행 과정을 설명
• 실행 과정을 상태 변환 (state transform) 과정으로 설명
• 각 문장 s마다 상태 변환 함수 정의

 

2) 문장의 의미

- 문장 S의 의미

• 문장 S가 전상태 s를 후상태 s'으로 변경시킨다.
• 상태 변환

- 상태 변환 함수 (state transform function)

• Eval : (State, Statement) → State
• Eval(s,S) = s' for each statement S

ex) 대입문, 복합문의 의미

3) let 문

- 실행 과정

• 변수 선언을 만남 ➡️ 변수가 유효해짐
  • 이 변수를 위한 엔트리를 실행 전상태 s에 추가
• 이 상태에서 문장 S를 실행
• 실행이 끝나면
  • 선언된 변수는 유효하지 않으므로 실행 수 상태 s'에서 해당 엔트리 제거
  • 이 상태가 let문을 실행한 후의 상태

4) 조건문의 의미

5) 반복문의 의미

 

5.4 언어 S의 인터프리터

1) 인터프리터

- 인터프리터

• 프로그램의 AST를 순회(traverse)하면서 수식의 값을 계산하고 문장의 의미에 따라 각 문장에 대한 해석(interpret)을 수행

- 인터프리터 함수 Eval : (Statement, State) → State

 

2) print 문 구현

State Eval(Print p, State state) {
    System.out.println(V(p.expr, state));
    return state; 
}

 

3) read 문 구현

State Eval(Read r, State state) {
    if (r.id.type == Type.INT) {
        int i = sc.nextInt();
        state.set(r.id, new Value(i));
    } 

    if (r.id.type == Type.BOOL) {
        boolean b = sc.nextBoolean();   
        state.set(r.id, new Value(b));
    }

    return state;
}

 

4) 복합문 구현

State Eval(Stmts ss, State state) {
    for (Stmt s : ss.stmts) {
        state = Eval(s, state);
    }
    return state;
}

 

5) if 문 구현

State Eval(If c, State state) {
    if (V(c.expr, state).boolValue( ))
        return Eval(c.stmt1, state);
    else
        return Eval(c.stmt2, state);
}

 

6) while 문 구현

State Eval(While l, State state) {
    if (V(l.expr, state).boolValue( ))
        return Eval(l, Eval(l.stmt, state));
    else 
        return state;
}