프언 유원희

3장

서론

* Syntax(구문) : 언어의 표현식,문장 그리고 프로그램 단위형식

* Semantics(의미론) : 표현식, 문장, 프로그램 단위에 대한 의미

* syntax 와 semantics 는 언어의 의미를 제공한다.

구문기술의 일반적인 문제 : Terminology (용어들)   

* sentence(문장)  : 언어를 구성하는 알파벳으로 구성된 스트링

* language :  sentence 의 집합

* lexeme(어휘항목)  : 가장 작은 구문단위 -> 식별자, 리터럴, 연산자, 특수어

* token : 어휘항목의 한 부류

언어의 형식적 정의

* Recognizers : 문자열을 읽어서 해당 언어에 속하는지 결정한다.

이에 해당하는 구문분석기는 4장에서 배울 것이다.

* Generators : 생성자의 구조를 비교함으로써 특정 문장의 구문이 올바른지 결정 할 수 있다.

BNF , Contest_Free Grammers

* Context-Free Grammars

- Noam Chomsky 에 의해서 발명됌

- 생성 장치 유형

- Context-free languages 

* Backus_Naur Form 

- syntax of Algol 57기술하기 위해서.

- BNF 는 문맥자유언어와 거의 동일하다. 

BNF Fundamentals

* BNF 는 구문 구조에 대해서 추상화를 사용한다

syntatic variable,  nonterminal symbols, nonterminals 로 불린다.

* Terminals 는 lexmems 나 token 이다.

* LHS 는 nonterminal 을 나타내고 RHS 는 terminal 또는 nonterminal 의 문자열로 이루어진다.

* nonterminal 은 보통 꺽쇄로 표현된다

<ident_list> -> identifier | identifier, <ident_list>

<if_stmt> -> if<logic_expr> then <stmt>

* Grammar : 유한한 규칙들의 모임이라고 할 수 있다.

* start symbol 은 nonterminal 의 특정한 요소이다.

BNF Rules

* abstraction ( nonterminal symbol) 은 1개 이상의 RHS 를 가진다.

<stmt> -> <single_stmt> | begin <stmt_list> end

Describing Lists

* syntatic lists 는 recursion 을 이용해 표현된다.

<ident_list> -> ident | ident,  <ident_list>

*  derivation(유도) 는 일련의 규칙적용을 통해서 생성된다.  start symbol 이라 불리는 문법의 특정 논터미널에서부터 시작되 terminal symbol 로만 이루어진 문장으로 끝난다.

Derivations

* 유도과정에 있는 모든 string을 문장형태( sentential form) 이라고 한다.

* sentence 는 terminal symbol 로만 이루어진 sentential form 이다.

* leftmost derivation은 가장 왼쪾에 우치한 논터미널을대체하는 것이다.

* 유도에서 다른 RHS 규칙을 선택함으로써 언어의 다른 문장을 생성할 수 있다.

* 규칙 선택시 모든 가능한 조합을 선택함으로 써 언어전체를 생성할 수 있다.

* 위 언어는 무한 집합이며 제한 시간에 언어의 모든 문장을 생성할 수 없다.

Parse Tree

* hierachical 한 유도과정

* 모든 중간 노드는 논터미널 기호를 레이블로 가지며 모든 잎 노드는 터미널 기호를 레이블로 가진다. 

Ambiguity in Grammars

* 만약에 sentential form 이 두개이상의 parse tree를 가지는 경우와 필요충분조건이다.  언어 구조가 한개 이상의 파스트리를 가지면 ,그 구조의 의미는 유일하게 결정될 수 없다. 어떤 파서가 모호한 구조를 가지면 설계자가 제공하는 비문법적 정보를 사용할 수도 있다.

unambiguous expression 

* 만약 parse tree 가 연산자 우선순위를 가진다면 ambiguity 를 가지지 않는다. 

Associatively of Operator

* operator associativity  덧셈연산 결합법칙이 성립하지 않을 수도 있다

<expr> -> <expr> + <expr> | const (ambiguous)

<expr> -> <expr> + const + const ( unambiguous)

Extended BNF

*[] 대괄호 : 선택적인 부분을 말한다.

* () 소괄호 : 다중 선택 사항에 관한 것이다., 그룹으로부터 한개의 원소가 선택되어야 할 경우

* {} 중괄호 : 무한정 반복되거나 생략될수 있음을 나타낸다. 0이상의 반복!

BNF  and EBNF

* BNF

<expr> -> <expr> + <term> | <expr> - <term> | <term>

<term> -> <term> * factor | <term> / <factor> | <factor>

* EBNF

<expr> -> <term> { (+ | -) <term> }

<term> -> <factor> { (* | / ) <factor>  }

Recent Variations in EBNF

* Alternative RHS 별도의 줄에 표현한다

* 화살표 대신에 콜론이 사용된다

* 대괄호 선택사항 대신에 opt 작은첨자 사용

* 소괄호 리스트에서 선택사항을 나타내기 위해 oneof 작은첨자를 사용

Static Semantics(정적의미론)

* Nothing to do with meaning

* Context-free grammars 는 프로그래밍 언어의 모든 구문을 표현할 수 없다.

* types of operands in expression 과 같은cumbersome

* non_context-free ( 사용되기 전에 선언되는 변수들)

Attribute Grammars

* 속성문법은 parse tree nodes 에 semantic info 를 준다

* Primary value of AGs

- compiler design

- static Semantics specification

* Definition 어려워...

 속성문법은 다음의 특징들이 첨가된 문법이다.

- 각 문법기호 X 에 속성들의 집함 A(X) 를 연관시킨다.

- 각 rule은 특정 nonterminal 의 속성 값을 정의하는 함수의 집합을 가진다

- attribute consistency 를 체크하기 위한 술어함수를 지닌다.

- X0 -> x1,,, Xn 을 rule이라고 하자.

* 속성값 계산

- 만약 모든 속성이 상속된다면 트리는 top0down 으로 진행된다

- 만약 모든 속성이 합성된다면 잎노드 부터 루트 노드까지 bottom-up 으로 진행된다

- 많은 경우 두가지 모두 사용된다.

Semantics

동적의미론에 대해서 범용적으로 채택되는 표기법이 개발되지 않았다.

Operational Semantics

- 명령어의 의미는 명령어의 실행으로 발생한 컴퓨터의 상태 변화로 표현된다.

- operational semantics 을 high level language 에서 사용하기 위해선 버츄얼머신이 필요하다.

- 하드웨어 pure interpreter 는 너무 비싸다

- 소프트웨어 pure interpreter 도 문제를 지닌다

- 특정 컴퓨터의 특성에 따라서  동작을 이해하기 어렵다

- 단지 동일한 사양을 갖는 컴퓨터에서만 적용가능하다

=> 대안 : complete computer simulation

- 저급언어로 번역해주는 번역기가 필요하다

- 가상 기계를 만든다

=> 사용되는 곳 : language manual , textbook , teaching programming language

Denotational Semantics(표기의미론)

- 가장 엄격하고 널리 알려진 프로그램 의미 기술 방법

- 재귀 함수 이론에 견고하게 기반하고 있다.

* 표기의미론의 절차

- 수학적 객체와 그요소의 사례를 수학적 객체의 사례로 사상하는 함수를 정의

- 언어의 의미구성은 오직 프로그램의 변수값에 의해서 정의된다

program 의 상태는 모든 현재의 변수값이다.

s = {<i1,v1> , <i2,v2> , ... , <in,vn> }

VARMAP 을 변수이름과 상태를 입력받았을때 현재 그 변수값을 리턴하는 함수라고 정의하자

<dec_num> ->   '0' | '1' | '2' | '3' | '4' | '5' | 

              '6' | '7' | '8' | '9' | 

              <dec_num> ('0' | '1' | '2' | '3' |

                         '4' | '5' | '6' | '7' | 

                         '8' | '9')

Mdec('0') = 0,  Mdec ('1') = 1, …,  Mdec ('9') = 9

Mdec (<dec_num> '0') = 10 * Mdec (<dec_num>)

Mdec (<dec_num> '1’) = 10 * Mdec (<dec_num>) + 1

…

Mdec (<dec_num> '9') = 10 * Mdec (<dec_num>) + 9

( 재귀적인 성질이 강함)

* 표기의미론에 대한 평가

- 프로그램의 correctness 를 증명할 수 있다.

- 프로그램을 엄밀한 방법으로 생각할 수 있다

- 언어 디자인에 도움을 준다

- compiler 생성 시스템에 사용된다.

- 그것의 복잡성 떄문에 언어사용자들은 잘 쓰지 않는다

Axiomatic Semantics(공리 의미론)

* 수학 논리에 기반한다

* 공리적 의미론에서 사용되는 논리식을 술어 또는 단언이라고 한다.

* 이러한 단언들을 각각 그 문장에 대한 전조건과 후조건이라 부른다.

* 최약전조건 : 후조건의 유효성을 보장하는 최소로 제약된 전조건이다.

* 프로그램의 증명은 프로그램의 마지막 문장에 대한 후조건으로 사용하는 것으로 시작된다.

* 추론규칙은 한 단언의 참 값을 다른 단언들의 값에 기반하여 추론하는 방법이다.

상단부분을 조건부, 하단부분을 결론부라고 할 때 위부분이 참이면 결론부가 참임을 추론할 수 있다고 한다.

* 공리 : 참이라고 가정되는 논리문장이다. 따라서 조건부가 없는 추론 규칙이다.

예상문제

1. 프로그래밍 언어를 학습하는 이유를 5가지만 서술하시오

- 생각을 표현할 수 있는 능력이 향상된다

- 적합한 언어를 선택할 수 있는 배경이 향상된다.

- 새로운 언어를 배울 수 있는 능력이 향상된다.

- 구현의 중요성에 대해서 보다 많이 이해한다.

- 전반적으로 전자계산 분야의 이해가 향상된다.

1-1. 프로그래밍 언어 평가 기준은 서로 상충되는 평가기준이 있다. 4가 지 예를 들어 설명하시오(20).

판독성 : 얼마나 쉽게 읽고 이해할 수 있느냐

작성력 : 선택된 문제 영역에 대해 프로그램을 생성하는 데 언어가 얼마나 쉽게 사용될 수 있느냐

신뢰성 : 모든 조건 하에서 주어진 명세에 따라 수행한다면 신뢰적이라고 한다.

비용 : 프로그래머 교육비용, 작성비용, 컴파일비용,실행비용,구현시스템비용,신뢰성부족에따른비용,유지보수비용

상충되는평가기준

신뢰성과 실행비용

판독성과 작성력

유연성과 신뢰성

작성력과 신뢰성

1-2. 직교성의 의미, 프로그래밍 언어에 미치는 영향

적은개 수의 기본 구조들이 적은 개수의 방법으로 조합되어 언어의 제어 구조와 데이터 구조가 생성될 수 있다는것.

직교적이면 더 적은 예외사항을 갖는다. 따라서 더 높은 정규성을 의미한다.

지나치게 높은 직교성은 불필요한 복잡성을 초래할 수 있다.

1-3. 프로그래밍 언어 구현방법중 혼합형 구현 시스템에 대하여 설명

컴파일러와 순수 인터프리터 간의 절충이다. 즉, 고급 언어 프로그램을 용이한 해석이 가능하도록 설계된 중간 언어로 번역한다. 이 방법은 원시 언어 문장이 단지 한 번만 해석되기 때문에 순수해석보다 더 빠르다. 이런 구현을 혼합형 구현 시스템이라 부른다.

2. Algol 60의 가장 중요한 개발 사항을 4가지를 서술하라

- 블록 구조 개념이 도입되었다.

- 부프로그램에 매개변수를 전달하는 두 개의 다른 방법이 허용되었다.

- 프로시저는 재귀적일 수 있게 허용되었다.

- 스택-동적 배열이 허용되었다. 

 

2-1.C++는 초기에 클래스를 가진 C라고 불리어 졌다. C++의 초기 목적 은 무엇인가? 간단히 서술하시오(10)

- 클래스와 상속을 사용하여 조직될 수 있듯이 조직될 수 있는 언어를 제공하는것

- 중요한 목적은 C 와 비교해서 성능 저하가 거의 또는 전혀 없어야 한다는 것

- C가 사용될 수 있는 모든 응용에 대해서 사용될 수 있어야 한다는 것

2-2. 별칭의 3가지 예를 쓰시오

- buffer overflow

- pointers

- foreach loop 문에서 사용되기도 한다.

2-3. smalltalk 에 대해서 서술하시오. 

- smalltalk 은 객체지향 프로그래밍을 완전히 지원하는 첫 번째 프로그래밍 언어이다. 

- smalltalk 은 그래픽 사용자 인터페이스와 객체-지향 프로그래밍을 발전시켰다.

- 데이터 추상화, 상속,다이나믹 바인딩 등이 사용된다.

3. 다음 각문장과 후조건에 대해서 최약 전조건을 계산하라(20).

1.  a = 2 * ( b - 1) { a > 0} 

2*(b-1) > 0

{b > 1}  이 최약 전조건이다.

 

2. b = b + 2 * a - 1{b > 1}

b+ 2*a -1 > 1

{b > 2*a+2} 이 최약 전조건이다.

3. a = 2 * b + 1; b = a - 3 {b < 0}

a-3 < 0

a < 3 이 첫번째 배정문의 후조건이 된다.

2*b+1 < 3

{b < 1}이 최약 전조건이다.

4. if( x > 0) then y = y + 1 else y = y-1 { y > 0} 

then 절의 논리문에서 y +1 > 0 으로부터 y > -1 을 생성한다.

else 에 동일한 공리를 적용하여y > 1 을 생성한다. 

{y >1} => {y>-1} 이 성립하기 때문에 {y>1}  을 전조건으로 사용할수 있다.

3-1.  다음 배정문과 후조건에 대하여 각각 최약 전조건(weakest precondition)을 구하시오(20).

1. a := (b + 5) / 2 { a > 6 }

b+5 > 12

{b > 7} 이 최약 전조건이 된다.

2. a := 3 * ( 2 * b + a ) { a < 6 }

{2*b + a < 2} 이 최약전조건이 된다.

3. a := 2 * b +1; b = a –3 {b < 0}

a<3  이 첫번째 논리문의 후조건이 된다.

2*b +1 < 3 이므로 {b<1} 이 최약 전조건이 된다.

4. if (x > 0 ) y := y - 1 else y := y + 1 {y > 0} 

then 절의 논리문에서 후조건 {y>0} 을 이용해 y>1 의 단언을 생성한다.

else 절의 논리문에서 후조건 {y>0} 을 이용해 y>-1 의 단언을 생성한다.

y>-1 => y>1 이므로 {y>1} 이 전조건이 된다. 

3-2. 

 1) 일반

  y = (x-5) / 2 {y < 6}

x-5 < 12

{x < 17} 이 최약 전조건이 된다.

 2) 순차

  a = 3 * (2b + a)

  b = 2 * a - 1

{b<5}

{a < 3}  이 첫번쨰 논리문의 후조건이 된다.

{2b+a < 1} 이 최약 전조건이다.

 3) if절(imply)

  if(x>0)

y = y+1

  else

y = y-1 {y > 0}

then 절의 논리문에서 후조건 {y>0} 을 이용해 y>1 의 단언을 생성한다.

else 절의 논리문에서 후조건 {y>0} 을 이용해 y>-1 의 단언을 생성한다.

y>-1 => y>1 이므로 {y>1} 이 전조건이 된다. 

 4) while절(loop불변자이용)

 while(y<>x)(y=y+1) {y = x}

3-3 . {s>1} while(s>1){s *=2 }{s=1} 책에 나와있는 문제. 이 프로그램이 옳음을 보이시오.

3-4. 문법이 주어지고 모호함을 보이시오. 모호함을 해결하시오. 

<assign> -> <id> = <expr>

<id> -> A|B|C

<expr> -> <expr> + <expr>

| <expr> * <expr>

| (<expr>)

|<id>

단순 배정문에 대한 모호한 문법

A = B + C * A

 두개의 다른 파스 트리로 표현된다.

따라서 이 모호함을 해결해보자!

<assign> -> <id> = <expr>

<id> -> A|B|C

<expr> -> <expr> + <term> | <term>

<term> -> <term> * <factor> | <factor>

<factor> -> (<expr>) | <id>

이렇게 만들고 최우단유도나 최좌단유도가 모두 같은 파스트리를 만드는것을 보이면 된다.

4. 다음 프로그램이 정확하다는 것을 증명하시오(10). { x = A AND y = B}

t = x;
x = y;

y = t; {x=BANDy= A}

5. 아래에 주어진 문법에 대하여 답하시오(20).

r1. E-> E + T r3. T-> T / F r5. F->(E)

r2. E-> T r4. T->F r6. F->id

1 id / id + id의 최좌단 유도(leftmost derivation)와 최우단 유도(rightmost derivation)을 구하시오.

2 다음 LR 파싱 테이블을 사용하여 id / id + id에 대한 LR 파싱 과정을 보이시오. 

5-1.