Terminology

Syntax : 프로그램 안의 수식, 명령어와 프로그램 유닛 구조를 정한 것

Semantics: 의미를 정의

Sentence : syntax를 만족시키는 한 문장

language : sentence의 집합

lexeme : 언어가 허용하는 최소한의 단위

token : 하나의 lexeme은 하나의 token에 대응 (identifier 제외)

Recognizer : recognizer에 넣어서 인식되면 맞는 문장, 안되면 틀린 문장

Generators : generator에서 만들어지면 맞는 문장 안만들어지면 틀린 문장. 만들 수 있는 sentence는 모두 language이다

CFG and BNF

CFG: context free grammars

BNF는 CFG이다.

cfg는 논터미널을 대문자로, bnf는 꺽쇠로 표시

CFG

nonterminal → 대문자, terminal → 소문자

BNF fundamentals

• rule 의 LHS는 nonterminal로, RHS는 terminal과 nonterminal로 구성된다.
• terminal은 결국 lexeme or token이다.
• nonterminal은 <> 로 둘러싸임.

• start symbol은 별도의 nonterminal로 설정된다

EBNF

선택적 부분: [] 로 감싼다

한정된 범위의 택일: () 로 감싼다 → 무조건 하나 선택

0번 이상 반복: {} 로 감싼다

구문 다이어그램

• nonterminal: 사각형
• terminal: 원
• 순서: 화살표

Static Semantics

CFG로는 프로그래밍 언어의 모든 syntax 표현 불가

• 어떤 변수는 참조되기 전에 선언된 상태여야 한다 → BNF로 표현 불가

Attribute Grammars

CFG+Semantic rules, static semantics 중 하나
BNF로 표현하기 어려운 것을 위해 사용

• attribute values: BNF에서 쓰이는 각각의 symbol x에다가 A(x)라는 속성을 부여할 수 있음
• computation function: 각 속성을 정의 하기 위한 함수를 정할 수 있음
• predicate: 속성에 대한 명제를 정의하기 위한 predicate(서술부, 참이 되어야 하는 조건)를 줄 수 있음

Grammar

• syntax
• semantic rules
• predicate

속성 종류

• synthesized attribute : 자식 노드로부터 값이 결정
• inherited attribute : 부모 / 조상 노드로부터 값이 결정
• intrinsic attribute : 스스로 값을 지닌 leaf 노드에게 할당 (변수들은 symbol table로부터 값을 가져옴)

Semantics

💡 어떤 의미를 가지는가 = 어떻게 동작하는가

Operational Semantics

동작으로 의미를 표현 ⇒ 구현(코딩)

기계에 넣고 돌리면 기계가 다 보여줄 것이라는 방법. 100% 입증 가능, 확실한 방법이지만 (가능한 기법이긴 하지만) 너무 어려움.

기계에 넣고 돌리는 것: 하드웨어적 방법

virtual machine, interpreter : 소프트웨어적 방법

중간 단계 (불완전)→ 대안: simulator로 simulation (100%는 아니지만 대충 어렴풋이 보여줌)

이 방법은 적당히 추상화 했을 때만 좋음. 확실하게 만들기에는 너무 비싸거나 어려움

Denotational Semantics

수학적 방법, 함수 사용

Functional programming language처럼 함수를 이용해 의미 표현, based on recursive function

x = y + z

if () ____ else _

expression assignment, selection문 등등 자체가 언어의 구성물 → 이걸 수학 요소 (function)으로 동작 표기

수학에서 함수는 variable의 값을 바꾸는 것. ⇒ 장점이자 단점: 프로그래밍언어로 작성된 동작을 variable로 표현해야 함.

variable은 모두 표현 가능하지만, variable로 표현할 수 없는 것은 표현 불가

⇒ 100% 이론적으로 구현 불가

모든 언어요소에 따른 mapping function을 만들어주는 것이 Denotational 방법

mapping function은 BNF에 대응

Axiomatic Semantics

로직으로 의미 표현, 논리식 사용

• assertion (=predicate) : 주장, 쓸 수 있는 명제
  • {x>10} y=x+20 {y>20} → 내가 주장하는 명제, 참인지 거짓인지의 문제는 다른 문제임. {x>10} y=x+20 {y>100} 은 거짓, assertion이지만 axiom은 아님
  • 모든 경우에 참이 되면 axiom이 됨, 아니면 axiom 아님
  • {x>10} y=x+20 {y>0} 은 axiom
  • {P} S {Q} ; 사전조건 (pre condition) S 사후 조건 (postcondition)
  • WP : weakest precondition, x>0보다 x>-20이 정의역이 더 크므로 weakest precondition이 됨
• axiom으로 도저히 표현 안되는 문장이 나오면 inference rule을 만들어서 표현
• inference rule: 하나 이상의 axiom을 가지고 분수를 만든 것 ⇒ 위가 참이면 아래도 참임

- s1과 s2를 sequence로 실행하면 {P1}에서 {P3}으로도 실행 가능하다는 뜻