2.1 프로그래밍 언어의 정의

제2장 구문(Syntax)

Reading Chap 4

2.1 프로그래밍 언어의 정의

(프로그래밍) 언어 정의

™ 구문법(Syntax)

™ 구성요소를 이용하여 문장/프로그램을 구성하는 방법

™ 이것은 이렇게 쓰는 거야 Æ 겉모양

™ 의미 (Semantics)

™ 문장/프로그램의 의미

™ 이것은 이런 의미란다 Æ 속뜻

™ 프로그래밍 언어 공부하는데 필요한 기본기

™ 어떻게 정의해야 할까요?

QnA

™ 가능한 문장 혹은 프로그램의 개수가 무한하지 않나요?

™ 무한한 것들을 어떻게 유한하게 정의할 수 있나요?

귀납적 정의(Inductive Definition)

™ 처음 들어본 사람?

™ 홀수

™ 1, 3, 5, 7, 9, 11, …

™ 무한한 홀수를 유한한 방법으로 어떻게 정의할까요?

™ a₁ = 1

™ a_n+1 = a_n + 2

귀납적 증명(Inductive Proof)

™ 처음 들어본 사람?

™ 홀수의 합

n

™ Σ 2k -1 = n²

k=1

™ 무한한 걸 어떻게 증명하지?

™ n = 1일 때 2*1 – 1 = 1 = 1²

™ 가정

Σ 2k -1 = nn ² k=1

™ 가정으로부터 다음 증명

n+1Σ 2k -1 = (n+1)²

k=1

귀납적 정의: 이진수/십진수의 구문법

™ 숫자(D)는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9중 하나이다.

™ 말로 정의

숫자(D)는 수(N)이다.

수 다음에 숫자(ND)가 오면 수(N)이다.

™ Induction Rule 형태

™ 문법 형태 N Æ D

N Æ ND ^{N Æ D}

| ND

D is a digit N is a number and D is a digit D is a number ND is a number

이진수: Syntax vs Semantics

D Æ 0

| 1

N Æ D

| ND

™ 101 [101] =

[0] = 0 [1] = 1 [D]

[ND] = [N] * 2 + [D]

십진수: Syntax vs Semantics

D Æ 0

| 1

| 2

…

| 9 N Æ D

| ND

™ 386 [386] =

[0] = 0 [1] = 1 [2] = 2

…

[9] = 9 [D]

[ND] = [N] * 10 + [D]

수식의 구문

™ 좀 현실적인 구문은 없나요?

™ 수식

™ 5, 13, 5 + 13, 5 * 13, (5 + 3), (5 + 3) * 13, …

™ 구문구조 E → E * E

| E + E

| (E)

| N

N → N D | D

D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

수식의 의미

E → E * E

| E + E

| (E)

| N

™ 23 * 5 + 12

™ [23 * 5 + 12] = ?

[E * E] = [E] * [E]

[E + E] = [E] + [E]

[(E)] = [E]

[N]

2.2 프로그래밍 언어 구현

프로그래밍 언어 구현

™ 프로그래밍 언어 구현은 무얼 해야 하나요?

™ 입력 프로그램 → Syntax → Semantics → Interpret or Compile

™ 프로그래밍 언어 구현은 어떻게 해야 하나요?

™ 구문법에 맞춰 작성된 프로그램을 입력 받아

™ 그 의미에 맞게 동작하도록 해석하거나

™ 기계어 명령어들로 번역해야 한다.

(프로그래밍) 언어의 구성

™ 어휘구조(Lexical structure)

™ 단어의 구조, 철자법

™ 구문법(Syntax)

™ 구문 구조

™ 문법을 이용해서 기술

™ Context-free grammar in BNF(Backus-Naur Form)

™

™ 프로그램의 의미

™ 자연어를 이용한 기술

™ 수학적 기술

™ operational semantics

™ denotational semantics

™ axiomatic semantics

인터프리터 vs 컴파일러

소스 프로그램

입력 인터프리터 출력

입력 목적 프로그램 출력

소스 프로그램

컴파일러

컴파일러 구조

Source program Analysis phases

Synthesis phases

Target program

컴파일러 구조

Source

Program Lexical Analyzer

Syntax Analyzer

Semantic Analyzer

Intermediate Code Generator

Code Optimizer

Code Generator Target Program (Parser)

(Scanner)

2.3 구문 및 문법

구문(Syntax)

™ 프로그래밍 언어의 구문구조는 어떻게 표현할 수 있을까 ?

™ 앞에서 살펴본 수식의 구문

E → E * E

| E + E

| (E)

| N

N → N D | D

D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

구문법 (Syntax Grammar)

™ 프로그래밍 언어의 구문구조

™ 귀납적 정의(Inductive Definition)

™ 문장 S

™ Id = E

™ if E then S else S

™ while E do S

™ …

™ 문맥-자유 문법(Context-free grammar)

™ 이러한 자기호출 구조를 자연스럽게 표현할 수 있다.

예제

™ if-then-else 문 S → if E then S

| if E then S else S

| …

™ 단순 수식 E → E * E

| E + E

| (E)

| N

N → N D | D

D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

CFG

™ A CFG consists of:

™ a set of terminals T

™ a set of non-terminals N

™ a start symbol S (one of the non-terminals)

™ a set of production rules

X → Y1 Y2 … Yn where X ∈ N and Yi ∈ T ∪N ∪ {ε}

™ Notational convention

™ non-terminals are written upper-case

™ terminals are written lower-case

구문검사

™ QnA

™ 어떤 문장 혹은 프로그램이 구문법에 맞는지는 어떻게 검사하나요?

™ 문법으로부터 유도(derivation)해본다.

™ 유도 가능하면 문법에 맞는 문장이고

™ 그렇지 않으면 문법에 맞지 않는 문장이다.

™ 그러면 유도는 어떻게 하나요?

유도(Derivation)

™ 생성 규칙 X _→ Y₁ Y₂ … Y_n

™ X 는 Y₁ Y₂ … Y_n 으로 대치될 수 있다. 혹은

™ X 는 Y₁ Y₂ … Y_n ^{을 생성한다}

™ 터미널 심볼

™ 대치할 규칙이 없으므로 일단 생성되면 끝

™ 터미널 심볼은 그 언어의 토큰이다.

™ 핵심 아이디어

™ 1. 시작 심볼 S부터 시작한다.

™ 2. 넌터미널 심볼 X를 생성규칙을 적용하여 Y1 Y2…Yn으로 대 치한다.

™ 3. 이 과정을 넌터미널 심볼이 없을 때까지 반복한다.

유도(Derivation)

™ Direct derivation ⇒

X_{1 …}X_i… X_{n ⇒} X_{1 …} X_i-1Y₁ Y₂…Y_n X_{i+1 …} X_n if there is a production X_i → Y₁ Y₂…Y_n

™ Derivation ⇒*

X_{1 …} X_{n ⇒*} Y_{1 …} Y_m if X_{1 …} X_{n ⇒ … ⇒} Y_{1 …} Y_m

(0 or more direct derivations from X_{1 …} X_n to Y_{1 …} Y_m )

유도 예제

™ CFG

E → E * E

| E + E

| (E)

| N

N → N D | D

D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

™ 생성할 스트링: 3 + 15

™ 유도

E ⇒ E + E ⇒ N + E ⇒ D + E ⇒ 3 + E ⇒ …

문법 G 언어

™ The language L(G) of a CFG G

™ 문법 G에 의해서 정의되는 언어

™ 문법 G에 의해서 유도되는 모든 스트링들의 집합

™ {a1 … an | S ⇒* a1 … an and every ai is a terminal}

예제

™

™ Strings of balanced parentheses:

S _{→ (}S) S _{→ a}

™ The language is ?

2.4 파스 트리

유도 및 파스 트리

™ Derivation tree = Parse tree = Syntax tree

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

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

™ A sequence of production applications

S ⇒ … ⇒ … is a derivation.

™ A derivation can be drawn as a tree:

™ S is the tree's root.

™ If the derivation uses production X _{→ Y1} Y₂…Y_n,

™ X has children Y1,…,Yn^.

유도 예제

™ CFG

E → E * E

| E + E

| (E)

| N

N → N D | D

D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

™ 생성할 스트링: 3 + 4 * 5

™ 유도

파스 트리

E

E + E

*

E 4 5 3

유도에 대한 참조(1)

™ A parse tree has

™ terminals at the leaves.

™ non-terminals at the interior nodes.

™ An inorder traversal of the leaves is the original input.

™ The parse tree shows association of operations;

™ 3 + (4 * 5)

유도에 대한 참조(2)

™

™ 각 단계에서 가장 왼쪽 넌터미널이 대치되었음

™ 우우선 유도(Rightmost derivation).

™ 3 + 4 * 5

™ 주의

™ 좌우선 유도와 우우선 유도 모두 같은 파스트리를 갖는다.

™ 차이점은 파스트리에 가지가 추가되는 순서이다.

언어를 한번 정의해보면 어떨까?

Stmt S Æ x = E

| S; S

| if E then S

| if E then S else S

| while E do S

| read x

| print E

Expr E Æ n | x | true | false

| E + E | E – E | E * E | E / E

| E == E | E != E | E < E | E > E | !E Prgm P Æ S

언어 이름은 ?

요약

™ 구문구조

™ 문법을 이용하여 표기

™ CFG in BNF

™ 유도(derivation)

™ 좌우선 유도(Leftmost derivation)

™ 우우선 유도(Rightmost derivation)

™ 파스트리(parse tree)

2.4 모호성

모호성(Ambiguity)

™ 수식을 위한 문법 E → E * E

| E + E

| (E)

| N

™ 스트링 3 + 4 * 5

™ 이 스트링은 두 개의 파스트리를 갖는다.

E

*

+ ⁵

E E

E E E

E + E

*

E 3

모호성(2)

™ 모호한 문법(ambiguous grammar)

™ 어떤 스트링에 대해 두 개 이상의 좌측 (혹은 우측) 유도를 갖는다.

™ 두 개 이상의 파스 트리를 갖는다.

™ 모호성은 나쁘다

™ 왜 ?

모호성 처리

™ 문법 재작성

™ 모호하지 않도록 재작성

™ 예

E → E + T | T T → T * F | F F → N | (E)

™ 우선 순위를 적용

모호성 예: The Dangling Else

™ 모호한 문법

S → if E then S

| if E then S else S

™ 이 문장에 대한 두 개의 파스 트리

if e1 then if e2 then s1 else s2

if e1 S

if

S s1 S

e2 s2 if e1

S

if

S

s1 s2 e2

모호성 예 : The Dangling Else

™ 모호하지 않는 문법

S → MATCH_IF | UNMATCH_IF

MATCH_IF → if E then MATCH_IF else MATCH_IF

UNMATCH_IF → if E then MATCH_IF else UNMATCH_IF

| if E then S

™ 앞의 문법과 같은 스트링을 생성한다.

™ 주의

™ 모호성을 다루는 일반적인 규칙은 없다.

™ 모호하지 않는 문법으로 자동적인 변환 방법은 없다.

2.5 EBNF와 구문 다이어그램

EBNF

™ BNF

E → E + T | T T → T * F | F F → N | (E) N → N D | D

™ EBNF

E → T {+ T}

T → F {* F}

F → N | (E) N → D {D}

구문 다이어그램

™ 구문 다이어그램

™

각 생성규칙을 다이어그램으로 표현

™

넌터미널

™ 사각형

™

터미널

™ 원

™

화살표

™ 순서

™ 예제

™

그림 4.11

2.6 파싱 구현

지금까지 한 것/앞으로 할 것!

™ Topic Logic Implementation

---

™ Syntax Grammar Parser

™ Semantics Semantics rules Interpreter

™ Type Typing rules Type checker

순환-하강 파싱 (recursive-descent parsing)

™ 기본 원리

™ 문법으로부터 직접 파서 프로그램을 만든다.

™ 입력 스트링에 대한 유도(derivation)를 Top-down 방식으로 찾아간다.

™ 구현

™ 각 넌터미널

™ 하나의 프로시저(함수,메쏘드)로 구현한다.

™ 프로시저 호출

™ 생성 규칙을 적용하는 것!

™ 프로시저 내의 동작

™ 생성규칙 우변을 수행 하도록 작성한다.

예제

™ Expr

→

void Expr(void) {

Term( );

while (token == “+”) { match(“+”);

Term();

} }

void match(char c)

{ if (token == c) token = getchar();

else error();

}

예제

™ 그림 4.12

™

순환-하강 파싱 하면서 동시에 수식의 값을 계산

™ Expr

→

int Expr(void) {

int result = Term( );

while (token == “+”) { match(“+”);

result += Term();

}

return result;

}

예제

™ 그림 4.12

™

순환-하강 파싱하면서 동시에 항(Term)의 값을 계산

™ Term → Factor {* Factor}

int Term(void) {

int result = Factor( );

while (token == “*”) { match(“*”);

result *= Factor();

}

return result;

}

숙제 #2

™ 그림 4.12의 순환-하강 파서/계산기 확장

™ 뺄셈(-), 나눗셈(/) 추가

™ 비교연산(==, !=, >, <, !) 추가

™ 문법

E → T {+ T | -T} | T == T | T != T | T > T | T < T | !E T → F {* F | / F}

F → N | (E) N → D {D}