Cha

pte

r 4

문법 �

어휘

구조

(렉시

컬구

조;L

exic

al S

truc

ture

)�

신택

스구

조(S

ynta

ctic

Struc

ture

)�

(Syn

tact

ic S

truc

ture

)�

BNF, E

BNF, 신

택스

다이

어그

램(S

ynta

x D

iagra

ms)

�파

스트

리(P

arse

Tre

e), 신

택스

트리

(Syn

tax

Tree

), 그

리고

모호

성(A

mbig

uity

)�

파싱

기술

과도

구

�어

휘(L

exic

s) 대

신택

스(S

ynta

x) 대

구문

(Sem

antics

)

소개

(Introduc

tion)

•형

식적

인언

어구

조(촘

스키

) �

중요

–정

규언

어(R

egul

ar)

–문

맥자

유또

는컨

텍스

트프

리(C

ont

ext-Fr

ee)

–문

맥민

감또

는컨

텍스

트센

서티

브(C

ont

ext-

Sens

itiv

e)–

무제

한(U

nres

tric

ted)

Progra

mm

ing L

angua

ges

2

–무

제한

(Unr

estric

ted)

•프

로그

래밍

언어

의신

택스

구조

�중

요–

렉시

컬구

조(단

어들

의구

조)

•정

규식

으로

나타

내어

질수

있음

–신

택스

구조

(문장

들의

구조

)•

컨텍

스트

프리

문법

(CFG

)으로

나타

내어

질수

있음

•BN

F (B

acku

s-N

aur

Form

) 은

CFG

를나

타내

는방

법

렉시

컬구

조

•렉

시컬

구조

–토

큰의

구조

–토

큰: 프

로그

래밍

언어

의단

어들

•토

큰은

단어

들의

집합

Progra

mm

ing L

angua

ges

3

•토

큰은

단어

들의

집합

•정

규식

–토

큰의

패턴

을기

술하

기위

한것

–텍

스트

검색

에많

이쓰

임

토큰

•토

큰의

종류

들(C

언어

예)

–키

워드

if

–리

터럴

리터

럴리

터럴

리터

럴(상

수상

수상

수상

수)

"if“

–특

별심

볼(s

pec

ial sy

mbols)

;

Progra

mm

ing L

angua

ges

4

–특

별심

볼(s

pec

ial sy

mbols)

;

–식

별자

(iden

tifie

rs)

IF

–커

멘츠

(대부

분공

백으

로취

급됨

)/*if*/

•식

별자

의최

대길

이는

언어

보다

는구

현에

의해

결정

된다

.

렉시

컬구

조이

슈들

•프

로그

램레

이아

웃–

자유

포맷

(fre

e fo

rmat

)–

레이

아웃

의규

칙들

(오프

사이

드규

칙–

offs

ide

rule

s)–

고정

포맷

(fix

ed form

at)

•흰

공백

이무

시되

는가

안되

는가

?

Progra

mm

ing L

angua

ges

5

•흰

공백

이무

시되

는가

안되

는가

?DO 99 I = 1,10

DO 99 I = 1.10

•키

워드

가예

약되

었는

가아

닌가

?–

어떤

언어

들의

키워

드는

예약

되지

않음

–포

트란

(FO

RTRAN

)이그

러한

언어

의예

임IF(IF.LT.0) IF = IF + 1

ELSE IF = IF + 2

정규

식�

중요

•패

턴을

기술

하는

언어

–어

떤토

큰들

의구

조는

매우

복잡

하므

로, 이

러한

구조

를표

현하

기위

한표

현방

법이

필요

함

–정

규식

은토

큰의

패턴

들을

기술

하기

위해

사용

됨

Progra

mm

ing L

angua

ges

6

용됨

•정

규식

의예

–숫

자들

의시

퀀스

[0-9]+

–부

호없

는부

동소

수점

리터

럴[0-9]+(\.[0-9]+)?

스캐

너(S

cann

er) �

중요

•토

큰을

인식

하는

프로

그램

–스

캐너

: 프로

그램

소스

를스

캔해

서토

큰들

을인

식해

서시

퀀스

로반

환하

는프

로그

램

–스

캐너

구축

도구

: 정규

식으

로쓰

여진

스캐

너의

Progra

mm

ing L

angua

ges

7

–:

스펙

을입

력받

아스

캐너

를구

축하

는프

로그

램

•스

캐너

의예

(그림

4.1)

–토

큰의

종류

: TokenType

–스

캐너

: TokenType getToken(void)

–스

캐너

의드

라이

버: m

ain()

컨텍

스트

프리

문법

•BN

F 예

(간단

한영

어문

장)

(1)문

장→

명사

구동

사구

.

(2)명

사구

→관

사명

사(3)관

사→

a| the

(4)명

사→

girl

| dog

(5)동

사구

→동

사명

사구

(6)동

사→

sees

| pets

Progra

mm

ing L

angua

ges

8

(6)동

사→

sees

| pets

•용

어–

문법

: 다시

쓰기

규칙

들의

집합

(a s

et o

f re

writing

rul

es)

•(메

타심

볼(m

etas

ymbols) : →

, |)

–논

터미

널(n

ont

erm

inal

s): 화

살표

의왼

쪽•

(LH

S’es

of th

e ar

row

(예

를들

어관

사))

–터

미널

(ter

min

als)

: 토큰

들(예

를들

어.)

–시

작심

볼(the

sta

rt s

ymbol):

미리

정의

된논

터미

널, 첫

번째

규칙

의LH

S (문

장)

CFG

는“언

어”를

생성

함

•언

어–

언어

: 문장

들의

집합

–문

장: 터

미널

들의

시퀀

스

•유

도(D

eriv

atio

n)–

시작

심볼

로부

터다

시쓰

기

•유

도의

예문

장문

장문

장문

장

⇒ ⇒⇒⇒명

사구

동사

구.

⇒ ⇒⇒⇒관

사명

사동

사구

.

⇒ ⇒⇒⇒the

명사

동사

구.

⇒ ⇒⇒⇒thegirl

동사

구.

Progra

mm

ing L

angua

ges

9

–시

작심

볼로

부터

다시

쓰기

들의

시퀀

스

–CFG

에의

해기

술되

는언

어는

유도

에의

해정

의될

수있

음

⇒ ⇒⇒⇒thegirl

동사

구.

⇒ ⇒⇒⇒thegirl

동사

명사

구.

⇒ ⇒⇒⇒thegirlsees

명사

구.

⇒ ⇒⇒⇒the girl sees

관사

명사

.

⇒ ⇒⇒⇒the girl sees a

명사

.

⇒ ⇒⇒⇒the girl sees a dog .

CFG

는재

귀적

임

•단

순한

반복

num

ber

→nu

mbe

r di

git

| di

git

digi

t →

0| 1

| 2

| 3

| 4

| 5

| 6

| 7

| 8

| 9

•유

도의

예

•구

조의

반복

expr

→ex

pr+

expr

|ex

pr*

expr

| (

expr

)

| NUMBER

NUMBER = [0-9]+

Progra

mm

ing L

angua

ges

10

•유

도의

예nu

mbe

r⇒ ⇒⇒⇒

num

ber

digi

t ⇒ ⇒⇒⇒

num

ber

digi

tdi

git

⇒ ⇒⇒⇒di

git

digi

tdi

git

⇒ ⇒⇒⇒2

digi

tdi

git

⇒ ⇒⇒⇒23

digi

t ⇒ ⇒⇒⇒

234

NUMBER = [0-9]+

•유

도의

예ex

pr⇒ ⇒⇒⇒

expr

*ex

pr⇒ ⇒⇒⇒

(ex

pr)*

expr

⇒ ⇒⇒⇒(

expr

+ex

pr)*

expr

⇒ ⇒⇒⇒...⇒ ⇒⇒⇒

(2 + 3)* 4

렉시

컬구

조또

한CFG

에

의해

표현

될수

있음

파스

트리

(Par

se T

ree)

•한

가지

관찰

–동

일한

문장

을많

은다

른유

도방

법으

로기

술할

수있

음nu

mbe

r⇒ ⇒⇒⇒

num

ber

digi

t ⇒ ⇒⇒⇒

digi

tdi

git⇒ ⇒⇒⇒

digi

t3⇒ ⇒⇒⇒

23

num

ber⇒ ⇒⇒⇒

num

ber

digi

t ⇒ ⇒⇒⇒

digi

tdi

git⇒ ⇒⇒⇒

2di

git⇒ ⇒⇒⇒

23

Progra

mm

ing L

angua

ges

11

num

ber⇒ ⇒⇒⇒

num

ber

digi

t ⇒ ⇒⇒⇒

digi

tdi

git⇒ ⇒⇒⇒

2di

git⇒ ⇒⇒⇒

23

•파

스트

리

–유

도의

그래

픽표

현

num

ber

num

ber

digi

t

digi

t

2

3

파스

트리

에대

해서

…

•파

스트

리표

현

–내

부노

드는

논터

미널

–리

프노

드는

터미

널

–루

트노

드는

시작

심볼

Progra

mm

ing L

angua

ges

12

–루

트노

드는

시작

심볼

–문

법규

칙은

하나

의레

벨을

가진

파스

트리

를구

성

–예

를들

어A →

xyz…

A

z

y

x

...

추상

신택

스트

리(A

bst

ract

Syn

tax

Tree

)

•기

본적

인관

찰

–번

역을

위해

서파

스트

리내

의정

보가

다필

요한

것은

아님

•추

상신

택스

트리

(AST

)

Progra

mm

ing L

angua

ges

13

•추

상신

택스

트리

(AST

)–

요약

된파

스트

리

–논

터미

널노

드는

없이

지고

, 일부

터미

널노

드가

내부

노드

가됨

파스

트리

와AST

의예

expr

*

expr

number

expr

expr

(

)

Progra

mm

ing L

angua

ges

14

digit

4

expr

expr

+

number

number

digit

digit

2

3

*

4

+

2

3

모호

함(A

mbig

uity

)

•문

법의

모호

함–

만일

특정

문장

이주

어진

문법

에의

해두

개이

상의

파스

트리

또는

AST

를가

진다

면, 그

문법

은모

호함

–모

호함

은어

떤문

장들

을위

한구

조들

은유

일하

게

Progra

mm

ing L

angua

ges

15

–모

호함

은어

떤문

장들

을위

한구

조들

은유

일하

게하

나만

있지

않다

는것

•모

호함

을다

루는

방법

–어

떤파

스트

리가

맞는

지를

결정

하기

위해

의미

론적

으로

검증

–올

바른

선택

을위

해때

로는

문법

이다

시쓰

여짐

모호

함의

예•

문법

:ex

pr→

expr

+ex

pr|ex

pr*

expr

| (

expr

)| NUMBER

•문

장: 2

+ 3 * 4

•파

스트

리:

expr

expr

Progra

mm

ing L

angua

ges

16

expr

expr

expr

+

*ex

pr

expr

+

*ex

pr

expr

expr

NUMBER

(2)

NUMBER

(3)

NUMBER

(4)

NUMBER

(2)

NUMBER

(3)

NUMBER

(4)

모호

함의

다른

예•

문법

:ex

pr→

expr

+ex

pr|ex

pr-

expr

| (

expr

)| NUMBER

•문

장: 2

-3 -4

•파

스트

리:

expr

expr

Progra

mm

ing L

angua

ges

17

expr

expr

expr

-

-ex

pr

expr

-

-ex

pr

expr

expr

NUMBER

(2)

NUMBER

(3)

NUMBER

(4)

NUMBER

(2)

NUMBER

(3)

NUMBER

(4)

결합

성(A

ssoci

ativ

ity)

추가

•결

합성

이추

가되

어논

터미

널의

재귀

를조

절할

수있

음

•좌

결합

성을

주는

경우

expr

→ex

pr+

term

|ex

pr-

term

|te

rm

expr

Progra

mm

ing L

angua

ges

18

expr

→ex

pr+

term

|ex

pr-

term

|te

rm

term

→(

expr

)| NUMBER

term

-

-ex

pr

term

expr

NUMBER

(2)

NUMBER

(3)

NUMBER

(4)

우선

순위

(Pre

ceden

ce) 부

과

•비

슷한

방법

으로

연산

자의

우선

순위

를부

여할

수있

음(우

선순

위단

계; “

pre

ceden

ce

casc

ade”

)•* 를 를를를

+ 보

다보

다보

다보

다우

선함

우선

함우

선함

우선

함ex

pr

Progra

mm

ing L

angua

ges

19

•* 를 를를를

+ 보

다보

다보

다보

다우

선함

우선

함우

선함

우선

함ex

pr→

expr

+te

rm|te

rm

term

→te

rm *

fact

or|fa

ctor

fa

ctor

→(

expr

)| NUMBER

expr

expr

term

fact

or

+

*te

rmNUMBER

(2)

NUMBER

(3)

NUMBER

(4)

확장

된BN

F (E

BNF)

•메

타심

볼들

추가

됨

–[ ] : 옵

셔널

한구

조

–{ } :반

복적

인구

조

•표

현력

Progra

mm

ing L

angua

ges

20

•표

현력

–메

타심

볼이

추가

되어

도, E

BNF의

표현

력은

BNF와

동일

함

EBN

F의예

•반

복

–BN

F:

expr

→ex

pr+

term

| te

rm–

EBN

F:ex

pr→

term

{ +

term

}

•옵

션

Progra

mm

ing L

angua

ges

21

•옵

션

–BN

F:if-

stm

t→

if(

expr

)st

mt

| if(

expr

)st

mt

else

stm

t–

EBN

F:if-

stm

t→

if(

expr

)st

mt

[ else

stm

t ]

EBN

F 사

용에

관한

몇가

지점

•왼

쪽으

로반

복되

는규

칙에

대해

서만

, {…

}를사

용함

:ex

pr→

expr

+te

rm| te

rm는

다음

과같

이바

뀜ex

pr→

term

[+ex

pr ]

•규

칙을

{…}로

시작

하지

않음

:

Progra

mm

ing L

angua

ges

22

•규

칙을

{…}로

시작

하지

않음

:ex

pr→

term

{+te

rm}라

고씀

expr

→{t

erm

+}

term

는틀

렸음

•[…

]는어

디서

든쓰

일수

있지

만, 다

음은

조심

:ex

pr→

expr

+te

rm| te

rm| -

term

은다

음과

같이

쓰여

져야

함ex

pr→

[ [[[-] ]]]te

rm{+

term

}

신택

스다

이어

그램

•EB

NF의

대안

•범

례

–터

미널

은타

원

–논

터미

널은

직사

각형

Progra

mm

ing L

angua

ges

23

–논

터미

널은

직사

각형

–시

퀀싱

을위

해서

는화

살표

•몇

가지

–초

보자

에게

쉬움

–잘

안쓰

임; E

BNF가

크기

가더

작고

간결

함

신택

스다

이어

그램

의예

•반

복–

EBN

F:ex

pr→

term

{ +

term

}

•옵

션

expr

term +

Progra

mm

ing L

angua

ges

24

•옵

션–

EBN

F:if-

stm

t→

if(

expr

)st

mt

[ else

stm

t ]

if-st

mt

if

(ex

pr)

stm

t

else

stm

t

+

파싱

�중

요

•무

엇이

파싱

인가

?–

프로

그램

의신

택스

를분

석–

프로

그램

의신

택스

트리

구성

•파

싱의

종류

–탑

다운

(하향

식)파

싱: 리

커시

브디

슨트

파싱

Progra

mm

ing L

angua

ges

25

–탑

다운

(하향

식)파

싱: 리

커시

브디

슨트

파싱

(rec

ursive

-des

cent

par

sing

), LL

파싱

–바

텀업

(상향

식) 파

싱: 시

프트

-리듀

스파

싱(s

hift-

reduc

e pa

rsin

g)

•파

서생

성기

–파

서표

현에

서파

서를

생성

하는

도구

•YA

CC, B

ison,

BYA

CC, AN

TLR, …

리커

시브

디슨

트파

서(R

ecur

sive

-Des

cent

Par

ser)

•중

요

•문

법에

서파

서를

손으

로만

들었

던옛

날의

방법

•다

음의

문법

변환

이필

요함

–좌

재귀

제거

(left rec

ursion

rem

ova

l)–

좌팩

토링

(left fac

toring

)

Progra

mm

ing L

angua

ges

26

–좌

팩토

링(le

ft fac

toring

)

•구

축방

법–

논터

미널

에부

합하

는재

귀프

로시

쥬어

의집

합들

을만

듦

–각

프로

시쥬

어의

동작

은상

응하

는논

터미

널의

프로

덕션

의RH

S에

기반

함

–각

토큰

을하

나하

나읽

어들

여정

합하

는“m

atch

”라는

프로

시쥬

어가

있음

리커

시브

디슨

트예

•문

법ex

pr→

term

{ +

term

}te

rm→

fact

or{*

fact

or }

fact

or→

(ex

pr)

| nu

mbe

r

•코

드스

케치

expr()

factor()

Progra

mm

ing L

angua

ges

27

expr()

{ term();

while (token == '+')

{ match(token);

term();

}

}

factor()

{ if (token == '(')

{ match(token);

expr();

match(')');

} else

number();

}

파싱

의문

제들

•프

리딕

티브

파서

–하

나의

룩어

헤드

(미리

보기

; looka

head

–다

음에

읽을

토큰

) 심

볼에

의해

어떤

동작

을할

지를

정하

는파

서

•Fi

rst

와Fo

llow

–Fi

rst(α):

스트

링α의

처음

시작

하는

토큰

들의

집합

Progra

mm

ing L

angua

ges

28

–Fi

rst(α):

스트

링α의

처음

시작

하는

토큰

들의

집합

–Fo

llow

(α): 스

트링

α다

음에

오는

토큰

들의

집합

•예 –

Firs

t( (

expr

)) = { (

}–

For th

e gra

mm

ar r

ule

fact

or→

(ex

pr), )

∈ F

ollo

w(e

xpr)

LL(1

) 조

건�

중요

•프

리딕

티브

파싱

의조

건

–두

개의

프로

덕션

A→ →→→

α1

| α

2 에

대해

First(α

1) ∩

First(α

2)

는반

드시

공집

합이

어야

함

–만

일A 가

옵셔

널이

면,First(

A) ∩

Follo

w(A

) 는

공집

합이

어야

함

Progra

mm

ing L

angua

ges

29

집합

이어

야함

•반

례

S→

if

C then

S| if

C then

Selse

SL

→a

La

| ε εεε

•더

자세

한부

분은

컴파

일러

구성

에대

한과

목에

서다

룸

스캐

너/파

서생

성기

�중

요

•컴

파일

러구

축도

구–

스캐

너생

성기

는주

어진

정규

식파

일에

서스

캐너

코드

를생

성함

–파

서생

성기

는주

어진

문법

파일

에서

파서

코드

를생

성함

•전

형적

인예

–유

닉스

툴Le

x (L

esk,

197

5)와

YACC (Jo

hnso

n, 1

975)

이제

일많

Progra

mm

ing L

angua

ges

30

–유

닉스

툴Le

x (L

esk,

197

5)와

YACC (Jo

hnso

n, 1

975)

이제

일많

이쓰

임

–최

근의

공짜

버전

은Gnu

Bison

과Fl

ex (“F

ast le

x”).

–자

바: J

avaC

C, J

Flex

/CUP, A

NTL

R, 등

등

•YA

CC/B

ison

스펙

의예

(Fig

ure

4.13

)•

더자

세한

부분

은컴

파일

러구

성에

대한

과목

에서

다룸

렉식

스(L

exic

s),신

택스

, 시맨

틱스

•렉

식스

와신

택스

간의

명확

한경

계가

없음

–토

큰의

구조

가문

법으

로설

정될

수있

음

–구

현에

서이

러한

것에

대한

결정

을함

•정

적인

시맨

틱스

를어

떻게

봐야

할지

에대

Progra

mm

ing L

angua

ges

31

•정

적인

시맨

틱스

를어

떻게

봐야

할지

에대

한합

의가

없음

–정

적시

맨틱

스는

CFG

로기

술되

지않

는신

택스

로볼

수있

음.

–정

적시

맨틱

스는

번역

시간

에결

정되

는시

맨틱

스로

볼수

있음

. (이

교재

의관

점).