방송대/프로그래밍언어론

구문론과 의미론

피클s 2022. 9. 7. 16:39

 

구문론과 의미론

구문론(syntax) : 문장이 구성되는 방식에 대해 연구

의미론(semantics) : 문장이 나타내는 의미에 대해 연구

 

예) 나는 너를 사랑한다.

구문 : 주어 + 목적어 + 서술어

의미 : 화자가 청자를 아끼고 귀중히 여긴다.

 

예) PRINT "GCD is"; A

구문 : PRINT "출력할 내용"; 변수

의미 : 출력할 내용과 변수의 값을 순차적으로 출력하라.

 

프로그램의 구조

int x12;
x12 = 1 + 5 * 2;
  • 문자 : 영어 알파벳, 숫자, 특수기호 등
  • 어휘(토큰) : 문자의 모임. 최소한의 의미를 갖는 단어(int, x12, =, +, 1, ...)
  • 구문 : 프로그램을 작성하는 규칙(토큰을 모아 프로그램을 구성)
  • 의미 : 정수 변수 x12에 1 + 5 * 2를 계산해서 대입한다.

 

 

구문의 표현

  • 프로그램의 표면적인 구조를 정의
  • 정의된 구문을 통해 모든 정상적인 프로그램을 도출
  • 작성된 프로그램이 정의된 구문에 맞는 프로그램인지 확인
  • 구문의 표현
    • 문법을 활용하여 명확하게 정의
    • 문법 : 문맥 자유 문법(문맥과 상관없이 정의 할 수 있는 것)을 이용하여 표현한다.

 

문맥 자유 문법(CFC, Context-Free Grammar)

<if문> ::= if <논리식> then <문장>

비단말 기호 : 정의될 대상 (<if문>, <논리식>, <문장>)

단말 기호 : 언어에서 직접 사용되는 표현 (if, then)

시작 비단말 기호 : 언어에서 독립적으로 사용될 수 있는 단위 (<if문>)

규칙 : 비단말 기호를 단말 기호와 비단말 기호의 조합으로 정의 (if <논리식> then <문장>)

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

 

문맥 자유 문법의 표현방법

BNF(Backus-Naur Form)

  • 메타기호 :  ::= 정의, | 택일, < > 비단말 기호
  • 비단말기호 : <>로 묶인 기호
  • 단말 기호 : 비단말 기호 및 메타 기호가 아닌 기호
  • 규칙 : ::=를 기준으로 왼쪽 부분을 오른쪽으로 정의

 

EBNF(Extended Backus-Naur Form)

BNF에 추가적인 메타 기호를 사용하여 규칙을 보다 간결하게 표현

 

[ ] : 생략 가능

<if문> ::= if <논리식> then <문장> [ else <문장> ]

{ } : 0번 이상 반복

<unsigned integer> ::= <digit> { <digit> }

( ) : | 와 함께 쓰여 한정된 범위의 택일

<수식> ::= <수식> ( + | - | * | / ) <수식>

' ' : 메타 기호를 단말 기호로 사용

<BNF 규칙> ::= <왼쪽 부분> '::=' <오른쪽 부분>

 

구문 도표(syntax diagram)

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

 

□ : 비단말 기호

○ : 단말 기호

→ : 비단말 기호 및 단말 기호들을 연결. 규칙

 

예1)

EBNF 표현

<if문> ::= if <논리식> then <문장> [ else <문장> ]

구문도표 

 

예2)

<수식> ::= <수식> ( + | - | * | / ) <수식>

 

예3)

<unsigned integer> ::= <digit> { <digit> }

 

 

의미의 표현

프로그램의 내용적인 효과를 정의

프로그램 실행 시 어떤 일이 일어나는지 의미를 기술

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

일반적으로 자연어 문장으로 표현

 

형식의미론

정적 의미론

프로그램을 수행하기 전 의미가 맞는지 파악 ex) 타입 검사

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

 

예) 변수

<D> : 변수

<T> : 타입

<id> : 변수명

 

구문 규칙

<D> ::= <T> <id> <L> ;
<T> ::= int | char
<L> ::= <id> <L> | e

타입 속성 규칙

id.t = T.t ∧ L.t = T.t
T.t = 정수
T.t = 문자
id.t = L.t ∧ L1.t = L.t

 

동적 의미론

프로그램 수행 시 나타나게 될 의미를 표현

 

기능적 의미론

추상기계의 상태를 바꾸는 것으로 수행 의미를 표현

상태 : <수행할 명령어, 메모리 상태>

   < z=x; x=y; y=z;  ,  [x→5, y→7, z→0] >
=> <      x=y; y=z;  ,  [x→5, y→7, z→5] >
=> <           y=z;  ,  [x→7, y→7, z→5] >
=> <                 ,  [x→7, y→5, z→5] >

표기적 의미론

구문 요소를 수학적 표기에 대응 시켜 수행 의미를 표현

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

구문 규칙 의미함수 Bin
<B> ::= 0
            | 1
            | <B> 0
            | <B> 1		 Bin[[ 0 ]] = 0
Bin[[ 1 ]] = 1
Bin[[ B 0 ]] = 2 * Bin[[ B ]]
Bin[[ B 1 ]] = 2 * Bin[[ B ]] + 1

 

공리적 의미론

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

효과 : 프로그램 S가 실행됨으로써 사전조건 P를 사후조건 Q로 변화시킴 {P} S {Q}

대입문의 효과 공리 : {Q[x→E]}x = E {Q}

ex)
{P}a = b * 2; {a < 10}
P <=> (a < 10)[a→b*2] <=> b * 2 < 10 <=> b < 5
{b < 5}a = b * 2; {a < 10}
저작자표시 비영리