ch3. describe syntax and semantics

▷ Language Design / describing

▷ Syntax / Semantics

  - Syntax : the form of its expression, statements, and program units.

문법. 형태. 구조. 

  - Semantics : the meaning of those expression, statements, and program unit

의미. (+가 먼저인가, *가 먼저인가)

♠ Terminologies

  - Alphabet

  - String

  - Language : set of sentences : set of strings of characters from alphabet

  - Sentence(Stmt) : the string of lang. : 문법에 맞는 string : 그 문법에서 되는 것

  - Lexeme - the lowest level of syntatic unit 

  - Token - the category of its lexemes 

(Ex. 변수명, 함수명, 클래스의 이름...등 identifier, lexemes에서 의미형성?!)

  - Language recognizer / generator

▷ Describing Syntax [Formal Methods]

♠ context-free grammar, BNF - 촘스키의 4 개의 문법!

<Context-free grammar>

- type3 : regular grammar (right-linear)

- type2 : context-free grammar : CGF = (N, T, P, S)

- type1 : context-sensitive grammar

- type0 : unrestricted grammar

<BNF> ~ Backus-Naur Form

: CNF를 표현하는메타 문법 표시 방법

: Meta language : a language that is used to describe another language

: CNF도 일종의 메타문법

<Sentential Forms and Derivations>

:Derivation ~ leftmost / rightmost : 어느쪽을 먼저 바꿀 것인가에 따라 다름!

♠ Parse Tree - hierarchical structure

♠ Ambiguity : grammar that generates a sentence for which where are two or more distinct parse trees is said to be ambiguous

* syntax tree가 2개 이상 만들어지는 sentence가 존재하면, 그 문법은 ambiguous

* 모든 sentence에 대해 syntax tree가 2개 이상 만들어지지 않으면 not ambiguous

=> ambiguous하다고 말하기는 쉬워도, ambiguous하지 않다고 말하기는 어려움

※ C도  ambiguous

◇ ambiguous : 컴파일러 설계시 좋지않음. 사람이 이해하기 좋음.

◇ not-ambiguous : 컴파일러 설계시 편함. 이해하기 힘듬.

♠ Operator Precedence & Associativity

◈ Operator Precedence : High-low (문법을 보면 우선순위를 알 수 있다)

◈ Operator Associativity

- left to right / right to left (언어마다 다름)

ex. a*b+(c*d) 

-> c*d가 먼저? 의미상 그렇지

-> 문법의 구조에 따라서 +가 먼저 연산될 수 도있고, *가 먼저 될수도 있고, ambiguous할 수도 있음.

* 구조에 알맞게 컴파일!

♠ExtendedBNF 

♠ syntax diagram (graphic)

cf. 문법은 표현하기 좋은 방법이 있다 ( 예. BNF)

Semantic은 표한할 방법이 없어 ㅠ_ㅠ 말로 해야해

▷ Describing Semantics

제한적(설명이 부족함. 간단한 언어에서는 그나마 표현가능함)

♠ Static (formal) semantics

- Attribute grammars (속성 문법) : CFG + Semantic Rules/Attribute Equation

ex . 기존의 CFG에서 의미를 부여하셔 수식으로 재구성

◇ Attribute 종류 

 - synthesized(자식에게) / inherited(부모에게) / intrinsic(자기자신에게)

◇ Attribute tree 예

♠ Dynamic semantics - 프로그램이 어떻게 동작하는지를 설명

- operational semantics, axiomatic semantics, denotational semantics

◇ axiomatic semantics : 프로그램 증명에 사용

- 접근방법 : experimental 실험적 증명 / analytic 수학적 증명

- rule-1(pre-condition/assertion)

- rule-2(union)

- rule-3(조건에 따라 분기)

※ condition - strong : 조건에 맞는 범위가 좁아짐! ↔ weak

♠ Program verification 

♠ Program correctness Proof