[프로그래밍언어] Ch3 Describing Syntax and Semantics

개념 정리

Syntax: 컴퓨터 언어의 문법 또는 구조

 

Semantics: 그 문장의 의미

 

Context-Free Grammars: 문맥에 상관없이 어떤 Non-Terminal이 들어와도 그에 대한 production-rule이 존재하는 문법

• Terminal
• Nonterminal
• 시작 심볼 S
• 문법 규칙들의 집합

 

BNF: 프로그래밍언어의 문법을 만들어놓은 규칙

 

Derivation: Nonterminal들을 적절한 production-rule을 사용하여 다른 표현으로 치환하는 것

• 위의 과정을 Nonterminal 심볼이 없을 떄까지 반복
• 생성 규칙 X -> Y1, Y2, ... Yn 적용

 

1. 좌측 유도(leftmost derivation)

: 각 직접 유도 단계에서 가장 왼쪽 nonterminal을 선택하여 이를 대상으로 생성 규칙을 적용

 

2. 우측 유도(rightmost derivation)

: 각 직접 유도 단계에서 가장 오른쪽 nonterminal을 선택하여 이를 대상으로 생성 규칙을 적용

 

3. 유도 트리(derivation tree)

: 유도 과정 혹은 구문 구조를 보여주는 트리

* 유도 트리 = 파스 트리 = 구문 트리

 

문법의 모호성

문법은 둘 이상의 구별되는 구문 분석 트리를 갖는 문장 형식을 생성하는 경우에 모호하다고 한다.

위 사진에서 같은 수식을 가지고 두 개의 파스 트리가 생성된 것을 볼 수 있을 것이다.

 

그래서 연산자의 우선 순위 수준을 나타내기 위해, 구문 분석 트리를 사용하면 모호성을 줄일 수 있다.

위 파스트리에서 <term>을 선택하는 순간 다시 - 연산을 할 수 없다. 

즉, 강제로 - 연산을 하게 만들어 모호성을 없애는 것이다.

 

구문 다이어그램

 

수식 문법 EBNF

<expr> → <term> {+ <term> | - <term>} 
<term> → <factor> {* <factor> | / <factor>} 
<factor> → number | ( <expr> )

 

Static Semnatics: BNF 만으로는 표현될 수 없는 규칙들을 표현하기 위해 고안된 것

 

Attrubute Grammars: 프로그램 구문과 정적 의미론을 한 번에 표현할 수 있는 문법 

 

BNF에다가 3가지를 더 추가

- Nonterminal이 가질 수 있는 속성을 추가함

- attribute를 계산하는 함수를 추가함

- 제약 조건을 표현함 (명제를 통해)

• synthesized attribute ( 자식 노드로부터 값이 결정 )
• inherited attribute ( 부모 노드로부터 값이 결정 )
• intrinsic attribute ( 스스로 값을 지닌 노드 )

 

Denotation Semantics

• 재귀함수이론에 기초해 있으며,가장 추상적인 의미론적 설명 방법이다.
• 언어 구성은 프로그램 변수 값만으로 정의된다.
• 프로그램의 상태는 모든 현재 변수의 값이다.

 

Decimal Numbers: 10진수로 표현한 것

 

Axiomatic Semantics: Dynamic semantics 표기 방법 중 하나로 어떤 프로그램이 옳음을 수학적으로 증명하는 방법

• {P (사전 조건) } S {Q (사후 조건) }

예시를 들자면 다음과 같다.

 

{x > 10 } y = x + 20 { y > 100} 

{x > 10 } y = x + 20 { y > 0 } ⇒ axiom

{x > -20 } y = x + 20 { y > 0 } ⇒ axiom (이 경우가 제약이 더 작고, 정의역은 제일 넓다. 이를 WP라고 한다.)

* WP: Weakest precondition

분자가 참이면 분모는 무조건 참이라는 동작을 정의할 수 있게 된다.