[프로그래밍 언어론] 구문론과 의미론

구문론과 의미론

• 언어의 형식적 정의
  • 한국어: 주어 + 목적어 + 서술어
  • 영어: 주어 + 동사 + 목적어
• 프로그래밍 언어의 형식적 정의
  • BASIC: PRINT “출력할 내용”; 변수
  • C: printf(”출력할 내용”, 변수);
• 형식적 정의의 필요성
  • 프로그래밍 언어의 명확한 사용체계를 알려 줌
  • 언어 해석의 모호함을 없애 줌
  • 작성된 프로그램의 동작 예측이 가능
• 프로그래밍 언어의 구조
  • 문자: 영어 알파벳과 아라비아 숫자를 근간으로 작성
  • 어휘(토큰): 프로그래밍 언어 문자로 구성된 단어
  • 구문: 프로그래밍 언어로 프로그램을 작성하는 규칙
• 프로그래밍 언어의 의미: 작성된 프로그램을 통해 발생하는 현상
• 프로그래밍 언어의 형식적 정의
  • 구문론: 프로그램의 표면적인 구조를 정의
  • 의미론: 프로그램의 내용적인 효과를 정의

구문의 표현

• 구문론
  • 프로그래밍 언어의 표면적인 구조를 정의
  • 정의된 구문을 통해 모든 정상적인 프로그램을 도출할 수 있음
  • 작성된 프로그램이 정의된 구문에 맞는 프로그램인지 확인할 수 있음
• 구문의 표현
  • 명확한 표현을 위해 문법을 활용
  • 일반적으로 프로그래밍 언어는 문맥 자유 문법으로 표현 가능
• 문맥 자유 문법(CFG: Context-Free Grammer)
  • 구성: 비단말 기호들, 단말 기호들, 시작 비단말 기호, 규칙들
    • 비단말 기호: 정의될 대상
    • 단말 기호: 언어에서 직접 사용되는 표현들
    • 시작 비단말 기호: 언어에서 독립적으로 사용될 수 있는 단위
    • 규칙: 비단말 기호를 구체적으로 정의
  • 각 규칙은 하나의 비단말 기호를 단말 기호와 비단말 기호의 조합으로 정의
  • 문맥 자유 문법은 다양한 방법으로 표현할 수 있음 → BNF, EBNF, 구문 도표
  • 세 가지 표현법은 서로 변환이 가능

BNF(Backus-Naur Form)

• Algol의 구문을 정의하기 위해 배커스와 나우어가 사용한 표현법
  • 메타 기호 ::= : 정의를 표현
  • 메타 기호 | : 택일(or)을 표현
  • 메타 기호 < > : 비단말 기호를 표현
• 문맥 자유 문법의 BNF 표현
  • 비단말 기호: 메타 기호 < > 로 묶인 기호
  • 단말 기호: 비단말 기호 및 메타 기호가 아닌 기호
  • 규칙: 메타 기호 ::= 를 기준으로 왼쪽 부분을 오른쪽 부분으로 정의

EBNF(Extended BNF)

추가적인 메타 기호를 사용하여 보다 간결한 표현이 가능하도록 확장된 BNF

• 메타 기호 [ ] : 생략 가능을 표현
• 메타 기호 { } : 0번 이상 반복을 표현
• 메타 기호 ( ) : 메타 기호 | 와 함께 쓰여 한정된 범위의 택일을 표현
• 메타 기호 ‘ ‘ : 메타 기호를 단말 기호로 사용함을 표현

구문 도표

• 순서도와 유사하게 그림으로 구문을 표현
  • 사각형: 비단말 기호를 표현
  • 원: 단말 기호를 표현
  • 화살표: 비단말 및 단말 기호들을 연결하며 다양한 연결 방법으로 EBNF의 메타 기호를 표현
• 구문 도표의 활용
  • 초기 Pascal UserManual에 사용되었음
  • 직관적인 표현을 통해 초보자들이 구문을 이해하기 쉬움

의미의 표현

• 의미론
  • 프로그램 실행 시 어떤 일이 일어나는지 그 의미를 기술
  • 구문으로 표현하기 어려운 제약사항을 기술하기도 함
• 의미의 표현
  • 사람이 이해할 수 있는 자연어 문장으로 표현하는 것이 일반적임
  • 하지만 자연어는 명확함에 한계가 있기 때문에 엄밀한 표현을 위해 다양한 기법이 개발됨(형식 의미론)
  • 대표적으로 사용되는 기법으로는 추상기계 코드를 사용하거나 수학식 등을 사용하는 방식을 들 수 있음
• 두 가지 의미론
  • 정적 의미론
    • 프로그램을 수행하기 전에 의미가 맞는지 파악하는 방법
    • 주로 타입 검사를 수행할 때 정적 의미론을 활용함
    • 대표적인 표현 방법: 속성 문법
  • 동적 의미론
    • 프로그램 수행 시 나타나게 될 프로그램의 의미를 표현함
    • 프로그램의 수행 측면은 다양하기 때문에 어느 한 방법이 아니라 여러 방법이 사용되고 있음
    • 대표적인 표현 방법: 기능적 의미론, 표기적 의미론, 공리적 의미론 등

속성 문법

• 정적 의미론의 표현 방법
• 각 비단말 기호마다 타입 속성이 있다고 가정하여 이에 대한 규칙을 정의하는 방법

기능적 의미론

• 동적 의미론의 표현 방법 중 한 가지
• 추상기계의 상태를 바꾸는 것으로 프로그램의 의미를 표현하는 방법 → 프로그램 수행은 결국 컴퓨터의 상태를 바꾸는 것이므로

표기적 의미론

• 동적 의미론의 표현 방법 중 한 가지
• 프로그램을 구성하는 각 구문 요소를 수학적 표기에 대응시켜 표현하는 방법 → 대응시키는 함수를 의미함수라고 부름

공리적 의미론

• 동적 의미론의 표현 방법 중 한 가지
• 프로그램의 실행 의미를 프로그램의 효과로 해석하는 방법 → 프로그램의 효과: 프로그램 S가 실행됨으로써 사전조건 P를 사후 조건 Q로 변화시키는 것으로 **{P} S {Q}**로 표기함
• 주변 상황에 대응하는 논리식은 공리 체계로 정확히 구할 수 있음

의미론의 한계 및 효과

• 의미론의 한계
  • 동적 의미론에서 추구하는 수학적 체계는 일반인이 이해하기에 너무 복잡함
  • 여전히 프로그램의 의미는 자연어로 기술되는 추세임
• 의미론의 효과: 다양한 방법론은 프로그램 구현 및 분석 등에 유용하게 사용됨
  • 속성 문법: 인터프리터 및 컴파일러를 구현할 때 트리 생성, 타입 검사, 코드 생성 등에 유용하게 사용
  • 수학적 표기: 언어의 특성을 명확하게 정의해야 할 때 언어 설계 방법론의 일부로 사용
  • 공리적 의미론: 프로그램의 특정 조건 만족 여부를 기계적으로 확인하고자 할 때 사용