프로그래밍언어론 강의 4화 :: 구문론과 의미론

프로그래밍언어론 4화를 듣고 배운내용

 

 

구문론

문장이 구성되는 방식

의미론

문장이 나타내는 의미

 

 

프로그램의 구문(구조)

문자: 영어 알파벳, 아라비아 숫자, 특수 기호 등

어휘(토큰): 문자의 모임. 최소한의 의미를 갖는 단어

구문: 프로그램을 작성하는 규칙, 토큰을 모아 프로그램 작성

어떤 형태로 작성해야 하는지

 

프로그램의 의미

프로그램을 통해 발생하는 현상

어떤 일이 일어나는지

 

 

프로그래밍 언어의 구문은 문맥 자유 문법으로 표현된다.

 

문맥 자유 문법(CFG: Context-Free Grammer)

비단말 기호: 정의될 대상

단말 기호: 언어에서 직접 사용되는 표현

시작 비단말 기호: 언어에서 독립적으로 사용될 수 있는 단어

규칙: 비단말 기호를 단말 기호와 비단말 기호의 조합으로 정의

=> 각 규칙은 하나의 비단말 기호만 정의

 

 

구문의 표현

BNF, EBNF, 구문 도표

BNF(Backus-Naur Form)

Algol의 구문을 정의하기 위해 사용된 표현법

세 가지 메타 기호 사용

• ::= ( 정의 )
• | ( 택일 )
• <> ( 비단말 기호 )

 

EBNF(Extended Backus-Naur Form)

BNF에 추가적인 메타 기호 사용

=> 규칙을 더 간결하게 표현 가능

추가된 메타 기호

• [] ( 생략가능 )
• {} ( 0번 이상 반복 )
• () ( |와 함게 스여 한정된 범위 택일 )
• '' ( 메타 기호를 단말 기호로 사용 )

 

구문 도표(syntax diagram)

초기 Pascal의 사용자 설명서에 사용된 표현법

순서도와 유사하게 그림으로 구문 표현

• 사각형 ( 비단말 기호 )
• 원 ( 단말 기호 )
• 화살표 ( 규칙, 비단말 기호 및 단밀 기호들을 연결 )

느낌이 문제로 나온다면 BNF, EBNF => 구문 도표 바꾸는 것이 나올것 같다

 

 

의미의 표현

구문으로 표현하기 어려운 제약사항을 사용하기도 함

의미의 정확한 표현을 위해 다양한 표현법(형식 의미론)

 

형식 의미론

정적 의미론, 동적 의미론

 

정적 의미론

프로그램 수행전 의미를 파악

대표적인 방법: 속성 문법

속성 문법: 비단말 기호마다 타입 속성이 있다고 가정하고 규칙 정의

 

동적 의미론

프로그램 수행시 의미 표현 방법

대표적인 방법: 기능적 의미론, 표기적 의미론, 공리적 의미론

 

표기적 의미론

수학적 표기로 대응

의미함수: 대응시키는 함수

 

공리적 의미론

프로그램 효과로 수행 의미 표현

효과: 프로그램 S가 실행되서 사전 조건 P를 사후조건 Q로 변화

{P} S {Q}

 

 

의미론 한계 및 효과

한계

프로그래밍 언어 전체에 대한 의미 표현 너무 복잡

효과

프로그램 구현 및 분석 등에 유용하게 사용됨

속성 문법: 컴파일러 구현시 트리 생성, 타입 검사, 코드 생성

수학적 표기: 명확하게 정의할 때

공리적 의미론: 조건 만족 여부를 확인할 때