[PL] 02. Describing Syntax and Semantics

기본 개념

Syntax : Expression, Statement, Program unit의 형태 또는 구조 (어떻게 표현하는지)

Semantics : Expression, Statement, Program unit의 뜻 (어떤 의미를 가지는지)

 

Syntax와 Semantics는 언어 정의를 제공

언어 정의의 사용자 : 언어 디지이너, 구현자(언어를 컴퓨터 프로그램으로), 개발자 등

 

Syntax(문법)을 기술하는 것이 Semantics(의미론)을 기술하는 것보다 쉬움 -> 보편적인 표기법이 존재하기 때문

• A sentence : Sentential Form의 하위 분류 / Non-terminal이 아닌 Terminal로만 이루어진 String의 묶음
• A language : Sentence들의 집합
• A lexeme : 언어의 최소한의 구문 단위
• A token : lexeme들의 카테고리

Recognizers : 알파벳으로 이루어진 input string을 읽고 언어에 속하는지 결정한다. 컴파일러의 Syntax 분석 파트
Generators : 언어의 문장을 생성하는 장치. 특정 문장의 Syntax가 구문적으로 올바른지 Generator의 구조와 비교해 결정

---

Formal Methods of Describing Syntax

Context-Free Grammars : 자연어의 구문을 설명하기 위한 언어 생성기. CFG라고 하는 언어의 클래스를 정의

---

Backus-Naur Form : Backus가 Algol58의 구문을 설명하기 위해 고안. BNF와 동등

• 추상화는 구문 구조의 클래스를 나타내는 데 사용.
• syntactic variable처럼 행동
• Terminals은 lexeme/token이다. (보통 nonterminal symbols라고 부른다.)

<assign> -> <var> = <expr>

• 화살표 왼쪽은 left-hand side(LHS)이고 Nonterminal(주로 <>로 표현)이다.
• 화살표 오른쪽은 right-hand side(RHS)이고 Terminal과 Nonterminal의 조합 문자열이다.

Grammar : 비어있지 않은 규칙의 유한한 집합

시작 심볼은 Grammar의 Nonterminal 중 특별한 요소이다.

 

Derivation : 규칙을 반복해서 시작 심볼에서 모두 터미널인 문장으로 끝내는 것.

• 유도에서 심볼의 모든 문자열은 Sentential Form이다.
• Terminal 심볼은 그 언어의 Token이다.

Direct derivation(직접 유도) : 생성 규칙을 한 번 적용(=>)

직접 유도가 아니면(여러 번 적용하면) (=>*)을 사용

 

Leftmost derivation(왼쪽 유도) : 왼쪽부터 Nonterminal을 Terminal로 바꾸는 것

 

Ambiguity in Grammars : 두 개 이상의 다른 파스 트리를 가지는 a sentential form. -> 우선순위가 먼저인 것을 낮게

 

Associativity(결합성) : 같은 우선순위의 연산자의 순위를 지정하는 의미론적 규칙

• LHS가 RHS의 시작 부분에 나타나는 경우 왼쪽 재귀(left recursive)로 표현
• 거듭제곱은 right associativity를 가짐
• right recursive로 표현 <factor> -> <exp> ** <factor> | <exp>

---

Attribute Grammars (속성 문법)

CFG로 표현하기 어려운 언어의 구조를 더 자세히 설명하기 위한 CFG의 확장 버전

 

Static Sementics

• 정적으로 판단을 해야하는데 문법만으로 판단이 안됨
• Syntax로 설명이 어렵고 부가적인 속성을 주고 싶음

Attribute Grammar

• 파스 트리 노드에 몇 의미론적 정보(semantic info)를 전달하는 기능이 있는 확장된 CFG
• 주요 가치 : Static semantics specification(명세), Compiler design (static semantics checking)
• Attribute : 문법 기호(Terminal, Nonterminal 포함)와 연관. 값을 할당할 수 있는 변수와 유사
• 속성 계산 함수 : Semantic function이라고도 함. 속성 값이 어떻게 계산되는지 지정
• Predicate function(술어 함수) : 언어의 정적인 의미론 규칙을 명시. 문법 규칙과 연관
• 문법 기호 x 마다 속성의 집합인 A(x)가 있다.
• 각 규칙마다 그 규칙의 Nonterminal에 대한 특징을 정의하는 함수의 집합이 있다.
• 각 규칙마다 속성의 일관성을 체크하는 술어(predicate)의 집합이 있다. (비어있을 수도 있다.)

---

---

Dynamic Semantics

의미론을 설명하기 위한 표준화된 방법은 많다. 의미론에 대한 방법론과 표기법이 필요한 이유는 다음과 같다.

• 프로그래머들이 문장이 무엇을 의미하는지 알아야 함
• 컴파일러 작성자들은 언어의 구조가 정확히 무엇을 하는지 알아야 함
• 올바른 증명이 가능해야 함
• 컴파일러 생성기가 가능해야 함
• 디자이너들은 모호성과 일관되지 않음을 감지해야 함

---

Operational Semantics

• 프로그램의 의미를 그것의 문장을 [기계, 시뮬레이션, 실제]에 실행시킴으로써 설명한다.
• 기계의 변화(메모리, 레지스터) 상태가 문장의 의미를 정의한다. 메모리가 어떻게 바뀌는지 살펴본다.
• 모든 변화를 측정하는 것은 현실적으로 만들기가 어려움 -> 가상 머신으로 대체
• 고수준 언어를 위한 Operational semantics를 쓰기 위해선 가상 머신이 필요하다.
• 하드웨어 순수 인터프리터는 비싸다. / 소프트웨어 순수 인터프리터는 문제가 있다. (정확도가 떨어짐)
• 특정 컴퓨터의 상세한 특성은 작업을 이해하기 어렵게 만든다.
• 의미 정의가 기계에 따라 다르다. -> 더 좋은 대안 : 완전한 컴퓨터 시뮬레이션
• 번역기를 구축(소스 코드를 이상적인 컴퓨터의 기계어로 번역), 이상적인 컴퓨터를 위한 시뮬레이터 구축
• 비공식적인 사용에 좋음 / 형식적으로 쓰면 굉장히 복잡해짐. PL/I의 의미를 설명하는데 사용됨
• Operational Semantics는 언어 매뉴얼, 교재, PL교육에 쓰임
• 두 개의 다른 활용 : Natural Oper.. (소프트웨어에 가까워지는 것), Structural Oper..(하드웨어에 가까워지는 것)

---

Denotational Semantics (함수로 표현하는) (입력이 정의역, 결과값(출력)이 치역)

• 정의역 : 프로그래밍 언어의 문장 하나 하나
• 치역 : (컴퓨터 속)데이터, 힙, 스택 =>즉 변수(추척하고자 하는 것)
• 재귀 함수 이론에 바탕. 가장 추상적인 의미론 표현 방식. (1970년 Scott and Strachey)
• 각 언어 Entity마다 수학적 object를 정의 -> 언어 Entity의 instance를 수학적 object의 instance로 매핑하는 함수를 작성
• 언어 구조의 의미는 프로그램 변수의 값으로만 정의된다.

---

---

Denotational Semantics 평가

• 프로그램의 정확성 증명에 사용될 수 있습니다.
• 프로그램을 생각하는 데 엄격한 방법을 제공합니다.
• 언어 설계에 도움이 될 수 있습니다.
• 컴파일러 생성 시스템에서 사용될 수 있습니다.
• 복잡성 때문에 일반적인 언어 사용자에게는 적합하지 않습니다

---

Axiomatic Semantics

• 논리식을 기반으로 한다.
• 형식적인 프로그램의 검증이 원래 목적
• 언어의 각 문장 유형마다 공리(axiom)나 추론 규칙이 정의됨.
• 논리식을 좀 더 형식적인 논리식으로 변환 가능

논리식은 Assertion이라고 함. (풀어서 쓰는 말, Predicate이랑 같은 뜻) (Ex. x > 20 등)

문장 하나하나가 어떤 의미를 가지는 지를 논리식을 가지고 표현

 

대표적인 Form {P} S {Q} => P라는 precondition이 사실일 때, Statement를 수행을 하고 Q라고 하는 주장이 사실이 된다면 이것이 모두가 사실이라고 생각하는 하나의 문장, Axiom이 되는 것이다.

---