1 of 105

구문 분석

최 광 훈

​

전남대학교

1

2 of 105

목차

  • 개요

​

  • 어휘 분석 (lexical analysis)

​

  • 구문 분석 (syntax analysis)

2

3 of 105

구문 분석

  • 어휘 분석 (Lexical analysis)과 구문 분석 (Parsing)

​

​

3

공통 주제

- 오토마톤(결정적, 비결정적), 문법, 언어

- 촘스키 계층

어휘 분석 주제

- 가장 작은 구문 요소 분석

- 유한 오토마타

- 정규식 ( == 오토마톤 == 문법 == 언어)

- 어휘 분석기 구조

구문 분석 주제

- 구문 구조 분석

- LR 오토마톤 (LR 파싱)

- Generalized LR (GLR, 모호한 문법 처리)

- 구문 에러 처리

- LR 구문 분석기 구조

4 of 105

While 프로그래밍언어

  • 최대공약수 구하는 예제 프로그램

​

4

5 of 105

구문 분석: 어휘 분석

  • 어휘 분석 (Lexical analysis)
  • 소스 프로그램 텍스트(문자열)를 어휘 (토큰)들의 리스트로 나누는 과정

data Token =

TkEndOfTokens

​

| TkCInt Int -- 1, 2, 3

| TkCBool Bool -- true, false

​

| TkIdentifier String -- x, y, abc123, _z

| TkTyInt -- int

| TkTyBool -- bool

5

6 of 105

구문 분석: 어휘 분석

  • 어휘 분석 (Lexical analysis)
  • 소스 프로그램 텍스트(문자열)를 어휘 (토큰)들의 리스트로 나누는 과정

data Token =

…

| TkAdd -- +

| TkSub -- -

| TkMul -- *

| TkDiv -- /

| TkMod -- %

6

| TkLessThan -- <

| TkGreaterThan -- >

| TkLessThanEqualTo -- <=

| TkGreaterThanEqualTo -- >=

| TkEqualTo -- ==

| TkNotEqualTo -- !=

| TkAnd -- &&

| TkOr -- ||

| TkNot -- !

7 of 105

구문 분석: 어휘 분석

  • 어휘 분석 (Lexical analysis)
  • 소스 프로그램 텍스트(문자열)를 어휘 (토큰)들의 리스트로 나누는 과정

data Token =

…

| TkSkip -- skip (keyword)

| TkSemicolon -- ;

| TkAssign -- =

| TkRead -- read

| TkWrite -- write

​

7

| TkIf -- if

| TkThen -- then

| TkElse -- else

| TkWhile -- while

| TkOpenBrace -- {

| TkCloseBrace -- }

| TkOpenParen -- (

| TkCloseParen -- )

8 of 105

8

int at (6, 1): TkTyInt

t at (6, 5): TkIdentifier

; at (6, 6): TkSemicolon

int at (7, 1): TkTyInt

p at (7, 5): TkIdentifier

; at (7, 6): TkSemicolon

int at (8, 1): TkTyInt

q at (8, 5): TkIdentifier

; at (8, 6): TkSemicolon

read at (10, 1): read

( at (10, 5): TkOpenParen

p at (10, 6): TkIdentifier

) at (10, 7): TkCloseParen

; at (10, 8): TkSemicolon

read at (11, 1): TkRead

( at (11, 5): TkOpenParen

q at (11, 6): TkIdentifier

) at (11, 7): TkCloseParen

; at (11, 8): TkSemicolon

if at (13, 1): TkIf

( at (13, 4): TkOpenParen

q at (13, 5): TkIdentifier

<= at (13, 7): TkLessThan

p at (13, 10): TkIdentifier

) at (13, 11): TkCloseParen

then at (14, 1): TkThen

skip at (15, 3): TkSkip

else at (16, 1): TkElse

{ at (17, 3): TkOpenBrace

t at (18, 5): TkIdentifier

= at (18, 7): TkAssign

p at (18, 9): TkIdentifier

; at (18, 10): TkSemicolon

p at (19, 5): TkIdentifier

= at (19, 7): TkAssign

q at (19, 9): TkIdentifier

; at (19, 10): TkSemicolon

q at (20, 5): TkIdentifier

= at (20, 7): TkAssign

t at (20, 9): TkIdentifier

; at (20, 10): TkSemicolon

} at (21, 3): TkCloseBrace

; at (21, 4): TkSemicolon

while at (23, 1): while

( at (23, 7): TkOpenParen

p at (23, 8): TkIdentifier

% at (23, 10): TkMod

q at (23, 12): TkIdentifier

!= at (23, 14): TkNotEqualTo

0 at (23, 17): TkCInt

) at (23, 18): TkCloseParen

{ at (24, 3): TkOpenBrace

t at (25, 5): TkIdentifier

= at (25, 7): TkAssign

p at (25, 9): TkIdentifier

% at (25, 11): TkMod

q at (25, 13): TkIdentifier

; at (25, 14): TkSemicolon

p at (27, 5): TkIdentifier

= at (27, 7): TkAssign

q at (27, 9): TkIdentifier

; at (27, 10): TkSemicolon

q at (28, 5): TkIdentifier

= at (28, 7): TkAssign

t at (28, 9): TkIdentifier

; at (28, 10): TkSemicolon

} at (29, 3): TkCloseBrace

; at (29, 4): TkSemicolon

write at (31, 1): TkWrite

( at (31, 7): TkOpenParen

q at (31, 8): TkIdentifier

) at (31, 9): TkCloseParen

어휘 분석 결과 예시:

각 토큰에 대하여:

  • 토큰에 해당하는 텍스트
  • (시작 라인, 시작 컬럼)
  • 토큰 종류

9 of 105

구문 분석: 어휘 분석

  • 어휘 분석 (Lexical analysis)
  • 소스 프로그램 텍스트(문자열)를 어휘 (토큰)들의 리스트로 나누는 과정

​

Q. 여러분이 사용하는 프로그래밍언어를 하나 선택하고 (C, C++, Java, Python, JavaScript 등) 어휘 분석 결과를 표현할 수 있는 자료 구조를 작성하시오.

  • ./example/ifcond1.while 프로그램을 분석한 결과를 그 자료 구조로 작성하시오.

​

9

10 of 105

구문 분석

  • 구문 구조 분석(Parsing)
  • 어휘 (토큰)들의 리스트를 구문 구조의 트리로 변환하는 과정

​

​

10

data Prog = Prog { progDecls :: Decls, progComms :: Comms }

​

type Decl = (Type, VarName) -- 타입과 변수명의 쌍

type Decls = [ Decl ] -- Decl 원소들의 리스트

​

type Comms = [ Comm ] -- Comm 원소들의 리스트

​

data Type = TyInt | TyBool -- 두 가지 종류의 타입 int, bool

11 of 105

구문 분석

  • 구문 분석(Parsing)
  • 어휘 (토큰)들의 리스트를 구문 구조의 트리로 변환하는 과정

​

11

data Comm =

CSkip

| CSeq Comm Comm

| CAssign VarName Expr

| CRead VarName

| CWrite Expr

| CIf Expr Comm Comm

| CWhile Expr Comm

data Expr =

ECst Const

| EVar VarName

| EBinOp Op Expr Expr

| EUnaryOp Op Expr

​

​

data Const =

CInt Int

| CBool Bool

data Op =

OpAdd

| OpSub

| OpMul

| OpDiv

| OpMod

| OpLessThan

| OpEqual

| OpAnd

| OpOr

| OpNot

12 of 105

12

Prog {

progDecls = [ (TyInt,"t"), (TyInt,"p"), (TyInt,"q") ],

progComms = [

CRead "p",

CRead "q",

​

CIf (EBinOp OpOr

(EBinOp OpLessThan (EVar "q") (EVar "p"))

(EBinOp OpEqual (EVar "q") (EVar "p")))

CSkip

(CSeq (CAssign "t" (EVar "p"))

(CSeq (CAssign "p" (EVar "q"))

(CAssign "q" (EVar "t")))),

​

CWhile (EUnaryOp OpNot ,

(EBinOp OpEqual (EBinOp OpMod (EVar "p") (EVar "q")) (ECst 0)))

(CSeq (CAssign "t" (EBinOp OpMod (EVar "p") (EVar "q")))

(CSeq (CAssign "p" (EVar "q"))

(CAssign "q" (EVar "t")))),

​

CWrite (EVar "q")

]

}

구문 분석 결과 예시:

13 of 105

구문 분석

  • 구문 분석(Parsing)
  • 어휘 (토큰)들의 리스트를 구문 구조의 트리로 변환하는 과정

Q. 앞의 구문 분석 결과 예시를 보고 분석 대상이 되었던 소스 프로그램의 텍스트를 복원해보시오.

​

Q. 어휘/토큰 리스트에는 나타난 어휘들 중 구문 트리에서는 사라진 어휘들은 무엇인가? 그 이유는 무엇인가?

​

Q. 여러분이 사용하는 프로그래밍언어를 하나 선택하고 (C, C++, Java, Python, JavaScript 등) 구문 분석 결과를 표현할 수 있는 자료 구조를 작성하시오.

  • ./example/ifcond1.while 프로그램을 분석한 결과를 그 자료 구조로 작성하시오.

​

13

14 of 105

실습

  • (하스켈/Haskell로 작성한) while 프로그래밍언어 파서를 다운받아 구문 분석을 수행하시오.
  • $ git clone https://github.com/kwanghoon/Lecture_SAV
  • $ cd Lecture_SAV/whilelang
  • $ stack ghci
  • > doLexing “./example/while2.while”
  • > doParsing “./example/while2.while”
  • stack exec -- yapb-exe -show-items mygrammar_whilelang.grm

​

  • n번째 피보나치 수를 출력하는 while 프로그램을 작성하시오. (./example 디렉토리)
  • $ stack ghci
  • > doRun False “./example/fib.while”

6 <= (입력) 6번째 피보나치 수

8 => (출력) 1 1 2 3 5 8의 8을 출력

14

하스켈 stack 프로그램 설치 : https://docs.haskellstack.org/en/stable/install_and_upgrade/

15 of 105

구문 분석기

  • 어휘 분석기(Lexer)
  • 정규식 (Regular expressions)으로 분석 대상 어휘를 각각 기술
  • 정규식을 유한 오토마타(Finite automata)로 변환
  • 주어진 입력 문자열을 유한 오토마타로 어휘를 분석하여 어휘/토큰 리스트를 출력
  • 예) LEX (C/C++)

​

  • 구문 분석기(Parser)
  • 문법(Grammar) 생산 규칙(production rules)으로 분석 대상 구문 트리 구조를 기술
  • 문법을 파싱 오토마타(Parsing automata)로 변환
  • 주어진 어휘/토큰 리스트를 파싱 오토마타로 구문 구조를 분석하여 구문 트리를 출력
  • 예) YACC (C/C++), JavaCC (Java), YAPB (Haskell)

​

Q. 여러분이 사용하는 프로그래밍언어를 지원하는 어휘 분석기 생성 도구와 구문 분석기 생성 도구를 조사하시오. (lex, yacc, javacc 등등)

15

16 of 105

목차

  • 개요

​

  • 어휘 분석 (lexical analysis)

​

  • 구문 구조 분석 (syntax analysis)

16

17 of 105

구문 분석

  • 구문 분석
  • 소스 프로그램 (텍스트 문자열)를 프로그램 구조의 구문 트리(syntax tree)로 변환
  • 어휘 분석 (Lexical analysis) + 구문 구조 분석 (Parsing)

​

  • Why 구문 분석?
  • 프로그램 분석 : 구문 트리는 이 트리가 표현하는 프로그램을 분석하기 편리한 구조
  • 컴파일러 : 구문 트리로부터 목적 코드를 만들기 쉬운 구조

​

  • 구문 분석 vs. 정적 분석
  • 정적 분석 : 프로그램을 실행하지 않고 수행하는 분석
  • 구문 분석도 정적 분석으로 간주할 수 있지만
  • 보통 정적 분석은 의미 기반 분석을 가리킴

​

17

18 of 105

구문 분석

  • 구문 분석 기반 프로그램 분석 도구 (오픈소스 소프트웨어)
  • PMD (다양한 프로그래밍언어 지원)
  • SonaQube (다양한 프로그래밍언어 지원)
  • CodeNarc (Groovy)
  • Checkstyle (Java)
  • FindBugs (Java)
  • Cppcheck (C, C++)

​

(참고)

​

18

19 of 105

개요

  • 어휘 분석 (Lexical analysis)과 구문 분석(Syntax analysis)

​

[한글의 어휘 분석]

​

19

20 of 105

개요

  • 프로그램의 어휘 분석 (Lexical analysis)과 구문 분석(Syntax analysis)

​

[한글 구문 분석]

​

20

국민대 자연어 연구실 : http://nlp.kookmin.ac.kr/cgi-bin/parse.cgi

21 of 105

어휘 분석과 구문 분석

  • 어휘 분석 (Lexical analysis)
  • 입력 : 문자열
  • 출력 : 어휘/토큰 시퀀스

​

  • 어휘 분석과 구문 분석과 시맨틱 분석의 관계

21

22 of 105

어휘 분석(lexical analysis)

  • 어휘 분석 : lexical analysis 또는 scanning

“position = initial + rate * 60”

==>

<id,“position”>, <=>, <id,“initial”>, <+>, <id,“rate”>, <*>, <number, “60”>

​

  • 토큰 (token) : < 토큰 이름(token name), 토큰 내용(lexeme) >

<id, “position”> : 토큰(의 종류, 태그)

id : 토큰 (대표) 이름

“position” : 토큰 텍스트 내용(lexeme)

Q. 특정 토큰들에는 왜 그 내용이 없나? 예) <=>, <+>, <*>

Q. 심볼 테이블 항목 숫자를 토큰 내용으로 두기도 한다. 두 형식을 비교하시오.

​

​

22

23 of 105

구문 분석: 어휘 분석

  • 어휘 분석 개요
  • 명세는 작성하기 쉬운 정규식으로, 어휘 분석은 빠른 유한 오토마타를 이용

​

​

​

​

​

​

23

​

명세 작성 방법

명세 구현 방법

어휘 분석기

정규식

유한 오토마타

구문 분석기

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

푸시다운 오토마타(Push-down automata)

24 of 105

어휘 분석 명세

  • (예제) if, then, else, 비교 연산자, 변수, 숫자를 어휘 분석하는 정규식 명세

​

24

digit -> [0-9]

digits -> digit+

number -> digits ( . digits)? (E [+-]? digits)?

letter -> [A-Za-z]

id -> letter ( letter | digit )*

if -> if

then -> then

else -> else

relop -> < | > | <= | >= | = | <>

​

ws -> ( blank | tab | newline )+

25 of 105

어휘 분석 명세

  • (예제) if, then, else, 비교(<,>,<=,>=,=,<>), 변수, 숫자를 어휘 분석하는 명세

​

25

Lexemes

Token name

속성 값

ws 매칭

-

​

if

if

​

then

then

​

else

else

​

id 매칭

id

id 매칭 문자열

number 매칭

number

number 매칭 문자열

<

relop

LT

<=

relop

LE

=

relop

EQ

<>

relop

NE

>

relop

GT

>=

relop

GE

26 of 105

어휘 분석 명세

  • (예제) 앞의 예제 토큰을 표현하는 자료 구조 [Java 클래스]

​

26

abstract class Token {

private int line, col;

// getter, setter

}

​

class TkIdentifier extends Token {

private String text;

public Identifier (String text) { this.text = text; }

public String getText() { return text; }

}

​

class TkIf extends Token { }

class TkThen extends Token { }

class TkElse extends Token { }

​

27 of 105

기본 정규식

  • 정규식 (r, s)
  • epsilon L(epsilon) = { }
  • 심볼 a L(a) = { a }
  • r | s L(r) U L(s) 합집합 union
  • r s L(r) L(s) 붙이기 concatenation
  • r* L(r)0 U L(r)1 U L(r)2 U … 클린 클로저 Kleene closure

(참고: r,s는 정규식, L(r)은 정규식 r이 표현하는 언어)

Q. 다음 정규식이 나타내는 집합은?

  • a | b
  • (a|b)(a|b)
  • a*
  • (a|b)*
  • a | a*b (*를 먼저, 붙이기가 그 다음, |가 맨 나중에 계산)

​

​

27

28 of 105

정규식 정의

  • 정규식 정의
  • d1 -> r1
  • d2 -> r2
  • …
  • dn -> rn

(참고: di는 심볼, ri는 정규식, ri에 기본 알파벳(∑)과 함께 di가 나타남)

​

예) C언어 식별자로 이루어진 언어를 표현하는 정규식 정의

  • letter_ -> A | B | … | Z | a | b | … | z | _
  • digit -> 0 | 1 | … | 9
  • id -> letter_ ( letter_ | digit )*

​

​

28

29 of 105

정규식 정의

Q) 부호없는 숫자 (정수 또는 실수)는 5280, 0.01234, 6.336E4, 1.89E-4와 같은 형식의 문자열이다. 정규식 정의를 완성하시오.

  • digit -> 0 | 1 | … | 9
  • digits -> digit digit*
  • optionalFraction -> . digits | epsilon
  • optionalExponent -> ( E ( + | - | epsilon ) digits ) | epsilon
  • number -> digits optionalFraction optionalExponent

​

(힌트: optionalFraction의 예시: 0.01234의 .01234 또는 5280의 epsilon)

(힌트: optionalExponent의 예시: 6.336E4의 E4 또는 그 변형 E+4, E-4, epsilon)

​

​

29

30 of 105

확장 정규식

  • 확장 정규식 표기법(+ 기본 정규식으로 재작성)
  • r+ r r*
  • r? r | epsilon
  • [a1a2…an] a1 | a2 | … | an (예: [abc] a | b | c )
  • [a1-an] a1 | a2 | … | an (예: [a-z] a | b | … | z )
  • ​

Q. C언어 식별자로 구성된 언어를 표현하는 정규식 정의를 확장 정규식 표기법으로 간략하게 작성하시오.

  • letter -> [A-Za-z_]
  • digit -> [0-9]
  • id -> letter ( letter | digit )*

​

​

30

31 of 105

확장 정규식

Q) 부호없는 숫자 (정수 또는 실수)를 표현하는 정규식 정의를 확장 정규식 표기법으로 간략하게 작성하시오.

  • digit -> [0-9]
  • digits -> digit+
  • number -> digits (. digits)? (E [+-]? digits)?

​

​

​

31

32 of 105

확장 정규식: Lex 프로그램

  • Lex 프로그램에서 지원하는 확장 정규식

​

​

​

32

정규식 온라인 테스트 https://regexr.com/

33 of 105

어휘 분석 명세 예시

​

​

​

33

34 of 105

배경: 언어, 문법, 오토마타

  • 언어 (Language)

- 유효한 문자열의 집합

예) L1 = { a, ab, abb, abbb, … } 예) abbbb : 유효, bbb 유효하지 않음

​

L2 = { }

​

L3 = { empty_string }

​

- 유효한지 여부는 누가 결정? 언어를 만드는 사람의 필요에 의해 결정

​

34

cf. 아무것도 없는 심볼

- λ (lambda)

- ε (epsilon)

- empty_string => “”

35 of 105

배경: 언어, 문법, 오토마타

  • 언어를 기술하는 방법

1) 문법(grammar) :

* 터미널(terminal) 심볼, 넌터미널(non-terminal) 심볼, 생산 (production)

* 언어에 포함된 모든 유효한 문자열만 유도(derivation, =>)

예) G(L1): S -> a

S -> S b

​

S => S b => S b b => S b b b => a b b b

35

터미널: a, b

넌터미널: S

시작 (넌터미널) 심볼: S

유도 과정 : … => …

G(L1) : L1 언어를 생성하는 문법

36 of 105

배경: 언어, 문법, 오토마타

  • 언어를 기술하는 방법

2) 오토마톤(automaton) :

* 상태, 상태 전이 규칙,

* 언어에 포함된 모든 유효한 문자열만 인식

36

상태: q0, q1

상태 전이 규칙:

q0 -a->a1 (또는, delta ( q0, a, q1 ) )

q1 -b-> q1 (또는, delta ( q1, b, q1) )

​

시작 상태: q0

종료 상태: q1

a

b

37 of 105

배경: 언어, 문법, 오토마타

  • 문법의 계층 (촘스키 계층, Chomsky Hierarchy)

1) 정규 문법 (regular grammar) => 정규 언어

2) 문맥 자유 문법 (contrext-free grammar) => 문맥 자유 언어

3) 문맥 의존 문법 (context-sensitive grammar) => 문맥 의존 언어

4) 무제약 문법 (unrestricted grammar) => 재귀적 열거 가능 언어(recursively enurable set)

​

​

​

37

https://ko.wikipedia.org/wiki/촘스키_위계

38 of 105

배경: 언어, 문법, 오토마타

  • 오토마타 계층

1) 유한 상태 오토마타(finite state automata) => 정규 언어

2) 비결정론적 푸시다운 오토마타(Nondeterministic push-down automata) => 문맥 자유 언어

3) 선형 제약 비결정론적 튜링 기계(Liniearly bounded nondeterministic turing machine) => 문맥 의존 언어

4) 튜링 기계 (Turing machine) => 재귀적 열거 가능 언어

​

​

​

38

https://ko.wikipedia.org/wiki/촘스키_위계

39 of 105

배경: 언어, 문법, 오토마타

  • 언어 vs. 문법 vs. 오토마타 (촘스키 계층)

​

​

​

​

​

​

​

​

=> 정규식(regular expression): 제3유형의 언어를 기술하는 또다른 편리한 방법!

​

​

​

​

39

https://ko.wikipedia.org/wiki/촘스키_위계

a, b : 터미널

A : 넌터미널

alpha, beta : 터미널과 넌터미널 심볼 리스트 (비어있는 리스트도 가능)

40 of 105

정규식에 매칭하는 문자열 인식

  • 배경: 정규식 매칭

- 정규식 ( == 오토마톤 == 문법 == 언어)

- 정규식 -> 비결정 유한 오토마타 -> 결정 유한 오토마타

​

Q1. 왜 문법이 아니고 정규식으로 어휘 분석기 명세 작성?

=> 정규 언어의 경우 문법 보다 정규식이 간결하게 명세 작성 가능

Q2. 왜 정규식을 바로 결정 유한 오토마타로 변환하지 않나?

=> 정규식을 비결정 유한 오토마타로 옮기기 쉬움

=> 비결정 유한 오토마타를 결정 유한 오토마타로 변환하는 알고리즘 존재

​

​

​

40

41 of 105

정규식에 매칭하는 문자열 인식

  • 배경: 정규식 매칭

​

​

​

​

41

q0

q1

q2

a

a

q0

q1

q2

a

λ

q0에서 입력을 취하지 않고 (λ) q1으로 이동

비결정 유한 오토마타

결정 유한 오토마타

q0

q1

q2

a

b

q0

q1

q2

b

q0에서 입력 a를 받으면 에러

42 of 105

정규식에 매칭하는 문자열 인식

  • 정규식으로 언어의 명세를 작성한 다음 이것에 속하는 문자열을 인식하는 문제
  • 예: digits = [0-9]+
  • L(digits) = {0, 1, … , 9, 01, 02, 03, …, 11, 12, 13, … }
  • 입력받은 문자열 s가 L(digits)에 속하는가 판단하기

=> 정규식을 정규 오토마타로 바꾸어 정규식 매칭 문자열을 효율적으로 인식

( 어휘 분석기의 일반적인 구현 방법 )

​

  • 정규 오토마타(FA - Finite Automata)
  • 문자열을 입력 받고 주어진 정규식에 매칭되면 Yes, 아니면 No를 출력
  • 상태 머신 형태로 기술
  • 결정 유한 오토마타 (DFA - Deterministic FA)와 비결정 유한 오토마타 (NFA - Nondeterministic FA)
  • 정규식 ⇔ NFA ⇔ DFA 는 서로 상호 변환 가능

​

​

​

42

43 of 105

정규식 => 비결정 유한 오토마타

  • 정규식 (a | b)* a b b에 매칭하는 문자열을 인식하는 비결정 유한 오토마타(NFA)
  • 상태 머신 = 상태 집합, 상태 전이 규칙, 시작 상태, 최종 상태
  • 상태 집합 : { ns0, ns1, ns2, ns3 }
  • 시작 상태 : ns0, 최종 상태 : { ns3 }
  • 상태 전이 규칙 : ns0 =a=> ns0, ns0 =b=> ns0, ns0 =a=> ns1, …

(ns0에서 a를 입력 받으면 ns0 또는 ns1로 임의로 선택하여 이동. 비결정 상태 전이 Nondeterministic state transition!!)

  • 시작 상태에서 입력 받은 문자열에 따라 전이하여 최종 상태에 도달 가능하면 Yes, 도달할 수 있는 전이가 없다면 No.

43

44 of 105

정규식 => 비결정 유한 오토마타

  • 정규식 (a | b)* a b b에 매칭하는 문자열을 인식하는 비결정 유한 오토마타(NFA)

​

Q. 앞 슬라이드 예시 비결정 유한 오토마타의 전이 규칙을 모두 나열하시오.

​

Q. 정규식에서 기술한 문자열이 주어진 비결정 유한 오토마타에 의해 모두 인식될 수 있음을 직관적으로 설명하시오.

44

45 of 105

정규식 => 비결정 유한 오토마타

  • 정규식을 비결정 유한 오토마타로 변환하는 방법 (아이디어)

45

표기법:

​

정규식 r에 매칭되는 문자열만을 인식하는 유한 오토마타 M(r)

46 of 105

정규식 => 비결정 유한 오토마타

  • 정규식을 비결정 유한 오토마타로 변환하는 방법 (아이디어)

46

cf. lambda λ

=> 아무것도 없는 심볼

=> “”

47 of 105

정규식 => 비결정 유한 오토마타

  • 정규식을 비결정 유한 오토마타로 변환하는 방법 (아이디어)

47

48 of 105

정규식 => 비결정 유한 오토마타

  • 정규식을 비결정 유한 오토마타로 변환하는 방법 (아이디어)

48

49 of 105

정규식 => 비결정 유한 오토마타

  • [연습문제] 정규식을 비결정 유한 오토마타로 변환하는 방법 (아이디어)

49

50 of 105

비결정 => 결정 유한 오토마타(NFA/DFA)

  • 정규식 (a | b)* a b b에 매칭하는 문자열을 인식하는 비결정 유한 오토마타(NFA)와 동일한 문자열을 인식하는 결정 유한 오토마타 (DFA)
  • 상태 머신 = 상태 집합, 상태 전이 규칙, 시작 상태, 최종 상태
  • 상태 집합 : { ds0, ds1, ds2, ds3 }, 시작 상태 : ds0, 최종 상태 : { ds3 }
  • 상태 전이 규칙 : (동일한 상태에서 동일한 입력을 받으면 전이할 상태는 항상 1개)
  • 시작 상태에서 입력 받은 문자열에 따라 전이하여 최종 상태에 도달하면 Yes, 도달하지 못하면 No.

50

51 of 105

비결정 => 결정 유한 오토마타(NFA/DFA)

  • 정규식 (a | b)* a b b에 매칭하는 문자열을 인식하는 비결정 유한 오토마타(NFA)와 동일한 문자열을 인식하는 결정 유한 오토마타 (DFA)
  • 상태 집합 : { ds0, ds1, ds2, ds3 }, 시작 상태 : ds0, 최종 상태 : { ds3 }

Q. 앞 슬라이드의 결정 유한 오토마타의 상태 전이 규칙을 모두 작성하시오.

Q. 앞 슬라이드의결정 유한 오토마타가 주어진 정규식의 문자열을 모두 인식하는지 살펴보시오.

51

52 of 105

비결정 => 결정 유한 오토마타(NFA/DFA)

​

Q. NFA와 DFA가 동일한 문자열 집합을 인식함을 직관적으로 설명하시오.

(힌트: NFA에서 비결정적으로 전이 가능한 상태들의 집합을 DFA의 1개의 상태로 매핑)

​

​

​

​

52

NFA

DFA

(a | b)* a b b

53 of 105

비결정 => 결정 유한 오토마타(NFA/DFA)

  • 비결정(nfa) => 결정 유한 오토마타(dfa)로 변환하는 알고리즘 (아이디어)

- 각 입력에서 nfa에서 이동 후 상태들의 집합을 dfa의 상태로 도입

- 예) Fig 2.14 => Fig. 2.15 (중간 단계) => Fig 2.16 (완성)

53

54 of 105

비결정 => 결정 유한 오토마타(NFA/DFA)

  • 비결정 => 결정 유한 오토마타로 변환하는 알고리즘 (아이디어)

54

55 of 105

비결정 => 결정 유한 오토마타(NFA/DFA)

  • 비결정 => 결정 유한 오토마타로 변환하는 알고리즘 (아이디어)

55

56 of 105

어휘 분석기 도구 설계

  • Lexical Analzyser Generator 설계

- 어휘 분석 명세를 상태 전이 테이블로 변환하고, 유한 오토마타 시뮬레이터를 통해 어휘 부석 수행

56

57 of 105

어휘 분석기 도구 설계

  • Lexical Analzyser의 오토마타 생성

- 프로그램의 패턴 중 어느 하나와 일치하는 lexeme을 인식할 수 있는 하나의 오토마톤이 필요,

- 새로운 시작 상태를 도입하여 NFA들을 하나로 결합

- 이 새로운 시작 상태에서 각각의 패턴 p_i에 대한 NFA (N_i)의 시작 상태로 자동 전이(epsilon transitions)를 추가

57

p_1 { action A1 }

p_2 { action A2 }

…

p_n { action An }

58 of 105

어휘 분석기 도구 설계

  • Lexical Analzyser의 오토마타 생성 예시

-

58

N_1

N_2

N_3

59 of 105

어휘 분석기 도구 설계

  • Lexical Analzyser의 오토마타 생성 예시

- 입력(의 prefixs들)이 여러 패턴에 동시에 매치될 때 (conflicts!)

1) 길이가 긴 prefix를 선택

예) aabbbba 입력에서 p3에 aab, aabb, aabbb, aabbbb 중 aabbbb를 선택

(최대한 많은 b를, 그 이후 a가 나올때 까지)

59

N_1

N_2

N_3

60 of 105

어휘 분석기 도구 설계

  • Lexical Analzyser의 오토마타 생성 예시

- 입력(의 prefixs들)이 여러 패턴에 동시에 매치될 때 (conflicts!)

2) 가장 긴 prefix가 둘 이상 패턴에 매치되면 명세 순서 상 앞의 패턴 선택

예) abba 입력에서 abb가 p2와 p3가 매치되고, 이중 p2를 선택

(명세 순서에서 p2가 p3를 앞에 위치)

60

N_1

N_2

N_3

61 of 105

어휘 분석기 도구 설계

  • NFA 기반 패턴 매칭

- 예) aaba

61

N_1

N_2

N_3

[NFA 기반 패턴 매칭]

1) 각 입력 지점에서 상태 집합을 계산

2) 더이상 다음 상태가 없을 때까지 (상태 집합이 빌 때까지) 진행

3) final states를 포함하는 집합까지 다시 뒤로 돌아감

4) final state가 여러 개인 경우 명세 선언 순서에서 가장 앞에 위치한 패턴을 선택

62 of 105

목차

  • 개요

​

  • 어휘 분석 (lexical analysis)

​

  • 구문 분석 (syntax analysis)

62

63 of 105

구문 분석

  • 구문 분석
  • 입력 : 토큰 시퀀스 (token sequence)
  • 출력 : 구문 트리 (syntax tree)

​

​

​

63

64 of 105

구문 분석

  • 구문 분석
  • 입력 : 토큰 시퀀스 (token sequence)
  • 출력 : 구문 트리 (syntax tree)
  • 구문 분석 명세

production1 { action1 }

production2 { action2 }

…

productionN { actionN }

​

예) E -> E + F 생산 규칙(production) ⇒ 토큰들을 트리로 만드는 방법

​

​

​

64

65 of 105

구문 분석: 어휘 분석

  • 어휘 분석 개요
  • 명세는 작성하기 쉬운 문맥 자유 문법으로, 어휘 분석은 빠른 푸시다운 오토마타를 이용

​

​

​

​

​

​

65

​

명세 작성 방법

명세 구현 방법

어휘 분석기

정규식

유한 오토마타

구문 분석기

문맥자유문법

(Context-free grammar)

푸시다운 오토마타

(Push-down automata)

66 of 105

문법 (Grammar)

  • 언어(Language)
  • 언어 : 문장의 집합 (문장: 문자열!)
  • 문법 : 언어를 정의하는 방법/명세

​

  • 문법 (Grammar) : 시작 기호 S와 생산 규칙들
  • 기호 (symbols) : 단말 (terminal) 기호, 비단말 (nonterminal) 기호
  • 단말 (terminal) 기호 : 다른 기호들로 대체되지 않는 기호 (예: a, b)
  • 비단말 (non-terminal) 기호 : 생산 규칙에 의하여 다른 기호들로 대체되는 기호 (예: S, A, B)
  • 생산 규칙 (production rule) : “왼편 기호들 ---> 오른편 기호들” (예: S -> b S)
  • 예) S -> a S
  • S -> b S
  • S -> a A
  • A -> b B
  • B -> b

​

​

​

​

​

​

66

67 of 105

문법 (Grammar)

  • 문법 (Grammar) : 시작 기호 S와 생산 규칙들
  • 시작 기호 S에서 시작하여 생산 규칙을 반복 적용하여 비단말 기호가 포함되지 않은 문자열에 도달하면 이 문자열을 이 문법으로 기술하는 언어의 문장으로 정의!

​

  • 예) S -> a S
  • S -> b S
  • S -> a A
  • A -> b B
  • B -> b

​

  • 예) S => a S => a b S => a b a A => a b a b B => a b a b b

(a b a b b의 유도 과정 derivation)

​

​

67

68 of 105

문법 (Grammar)

  • 문법 (Grammar) : 시작 기호 S와 생산 규칙들
  • 시작 기호 S에서 시작하여 생산 규칙을 반복 적용하여 비단말 기호가 포함되지 않은 문자열에 도달하면 이 문자열을 이 문법으로 기술하는 언어의 문장으로 정의!

​

  • 예) S -> a S
  • S -> b S
  • S -> a A
  • A -> b B
  • B -> b

​

Q. 위 문법은 정규식 (a | b)* a b b에 매칭되는 모든 문자열들을 유도할 수 있음을 설명하시오. (동일한 언어를 명세하는 점에서 이 문법과 이 정규식은 동치)

​

​

​

​

68

69 of 105

문법 (Grammar)의 종류

  • 4가지 언어 종류 - 촘스키 계층 (Chomsky Hierarchy)
  • 정규 언어(타입3): 정규 문법 (Regular grammar)으로 생성한 언어
  • 문맥 자유 언어(타입2): 문맥 자유 문법 (Context-free grammar)으로 생성한 언어
  • 문맥 민감 언어(타입1): 문맥 민감 문법 (Context-sensitive grammar)으로 생성한 언어
  • 재귀적으로 나열 가능한 언어(타입0): 제한이 없는 문법 (Unrestricted grammar)으로 생성한 언어

​

69

[ 촘스키 계층 (Chomsky Hierarchy) ]

70 of 105

문법 (Grammar)의 종류

  • 4가지 문법 종류
  • 정규 문법 (Regular grammar) : (언어 예: { a^n | n>= 0 } )

왼편(lhs, left-hand side)은 비단말 기호 1개 (예: A -> a A)

오른편(rhs, right-hand side)은 최대 1개의 비단말 기호 사용

  • 문맥 자유 문법 (Context-free grammar) : (언어 예: { a^n b^n | n>= 0 } )

왼편(lhs)은 비단말 기호 오직 1개 (예: A -> a A b)

  • 문맥 민감 문법 (Context-sensitive grammar) : (언어 예: { a^n b^n c^n | n>= 0 } )

생산규칙 x -> y : x, y ∈ (N U T)+ 이고 |x| <= |y|

(N: 넌터미널 기호들의 집합, T: 터미널 기호들의 집합)

(예: x A y -> x a A b y vs. A -> a A b)

  • 제한이 없는 문법 (Unrestricted grammar)

​

​

​

​

​

70

71 of 105

문법 (Grammar)의 종류

  • 정규 문법으로 기술한 언어 예: { a^n | n>= 0 }

S -> A, A -> a A, A -> epsilon (epsilon: 비어있음)

  • 문맥 자유 문법으로 기술한 언어 예: { a^n b^n | n>= 0 } )

S -> A , A -> a A b, A -> epsilon

  • 문맥 민감 문법 (Context-sensitive grammar) : (언어 예: { a^n b^n c^n | n>= 0 } )

S -> a b c | a A b c

A b -> b A

A c -> B b c c

b B -> B b

a B -> a a | a a A

Q. a^2 b^2 c^2을 유도하시오. a^4b^4 c^4을 유도하시오.

​

​

​

71

(*) a^3 b^3 c^3 유도 예시

S => a A b c => a b A c => a b B b c c

=> a B b b c c => a a A b b c c => a a b A b c c

=> a a b b A c c => a a b b B b c c c

=> a a b B b b c c c => a a B b b b c c c

=> a a a b b b c c c

72 of 105

문법 (Grammar)의 종류

  • 4가지 문법 종류와 프로그램 분석 방법과의 연관 관계
  • 정규 문법 (Regular grammar) : 어휘 분석 (lexical analysis)
  • 문맥 자유 문법 (Context-free grammar) : 구문 분석 (syntax analysis)
  • 문맥 민감 문법 (Context-sensitive grammar) : 의미 분석/타입 분석 (type checking)
  • 제한이 없는 문법 (Unrestricted grammar) : 정적/동적 프로그램 분석

​

​

(참고: 타입 분석은 정적 프로그램 분석의 한 가지이기도 함)

​

​

​

​

​

72

73 of 105

문법 자유 문법

  • 문맥 자유 문법(Context-sensitive grammar)와 구문 분석
  • 예) 덧셈보다 곱셈을 우선 계산하는 산술식 : x + y * z, (x + y) * z
  • G: E -> E + T
  • E -> T
  • T -> T * F
  • T -> F
  • F -> ( E )
  • F -> id (id: identifier, 식별자 또는 변수)

​

Q. 시작 기호를 E로 가정하고, 두 문장 x + y * z와 (x + y) * z를 위 문법으로부터 유도하시오.

​

​

​

​

​

73

74 of 105

문법 자유 문법

  • 문맥 자유 문법(Context-sensitive grammar)와 구문 분석
  • 예) 덧셈보다 곱셈을 우선 계산하는 산술식 : x + y * z, (x + y) * z
  • G: E -> E + T
  • E -> T
  • T -> T * F
  • T -> F
  • F -> ( E )
  • F -> id (id: identifier, 식별자 또는 변수)

​

Q. 위 문법을 더 간단하게 아래와 같이 작성하면 어떤 문제가 있나? (모호한 문법: ambiguous grammar)

  • E -> E + E
  • E -> E * E
  • E -> ( E )
  • E -> id

​

​

​

​

​

74

75 of 105

문법 자유 문법

  • 문맥 자유 문법(Context-sensitive grammar)와 구문 분석
  • 예) 덧셈보다 곱셈을 우선 계산하는 산술식 : x + y * z, (x + y) * z
  • G: E -> E + T
  • E -> T
  • T -> T * F
  • T -> F
  • F -> ( E )
  • F -> id (id: identifier, 식별자 또는 변수)

​

  • 문법에 맞는 문자열인지 LR 파싱으로 확인
  • 위 문법 G에 대한 LR 오토마톤 및 파싱 예제 (다음 장)

​

​

​

​

​

75

76 of 105

문법 명세 예시

  • while 프로그래밍언어의 구문 분석을 위한 문법 명세
  • https://github.com/kwanghoon/Lecture_SAV/blob/master/whilelang/app/Parser.hs

​

​

​

76

77 of 105

파싱 개요

  • 파싱 (Parsing)
  • 입력 문자열에서 구문 트리 (파스 트리, Parse tree)를 만드는 방법

​

  • 두 가지 종류

​

​

​

​

​

  • LR 파서 > LL 파서
  • 사실상 모든 프로그래밍언어의 구문을 인식하는 파서를 만들 수 있음

77

파싱 종류

파싱 알고리즘

문법 클래스

Top-down parsing

Recursive-descent parsing

LL(k)

Bottom-up parsing

Shift-Reduce parsing

LR(k)

78 of 105

하향식 파싱 vs. 상향식 파싱

  • 하향식 파싱(Top-down parsing)
  • 시작 심볼에서 시작하여 깊이 우선 순서로 파스 트리의 노드를 만들기
  • 시작 심볼에서 시작하여 맨 왼쪽 넌터미널을 찾아 해당 생산 규칙으로 펼치는 과정을 반복하여 입력 문자열에 도달 (Leftmost derivation)

​

  • 상향식 파싱(Bottom-up parsing)
  • 파스 트리의 leaf 노드들(바닥)에서 시작하여 루트 노드 (시작 심볼)로 향하며 파스 트리의 노드를 만들기
  • 시작 심볼에서 시작하여 맨 오른쪽 넌터미널을 찾아 해당 생산 규칙으로 펼치는 과정을 반복하여 입력 문자열에 도달 (Rightmost derivation) (cf. 이 과정의 역 과정)

​

​

78

79 of 105

하향식 파싱 예 : id * id

​

​

79

80 of 105

상향식 파싱 예 : id * id

​

​

80

81 of 105

Shift-Reduce 파싱

  • 상향식 파싱(Bottom-up parsing) 예시 : id * id

​

​

​

​

​

  • Shift-Reduce 파싱 예시

​

​

81

82 of 105

Shift-Reduce 파싱

  • Shift-Reduce 파싱
  • $ : 입력 문자열의 맨 끝, 스택의 맨 밑바닥

​

  • 시작 스택 상태 : $
  • 시작 입력 상태 : id * id $

​

  • Shift : 다음 입력 (터미널) 심볼을 스택에 push
  • Reduce : 스택 Top의 심볼들(alpha)을 넌터미널 심볼(A)로 대체

(생산 규칙 A -> alpha)

  • Accept : 파싱 종료. 스택 Top에 시작 심볼, 입력 문자열에는 $만 남음
  • Error : Shift나 Reduce를 적용할 수 없음

​

82

83 of 105

LR 파싱

  • LR(k) 파싱
  • 상향식 파서의 가장 널리 사용되고 있는 타입의 파싱
  • “L” : left-to-right scanning of the input
  • “R” : constructing a rightmost derivation in reverse
  • k : the number of input symbols of lookahead that are used in making parsing decisions (shift or reduce)
  • 백트래킹을 하지 않는 shift-reduce 파싱 (빠른 파싱 방법)
  • LR 방법으로 파싱할 수 있는 문법 클래스 LR(k)
  • LR(k)는 LL(k)를 포함
  • 상당히 많은 프로그래밍언어 특징에 대한 구문 분석이 가능하여 널리 사용
  • 별도의 오토마톤을 만드는 과정이 필요함

(LR 파싱 오토마톤을 만드는 알고리즘, 드래곤북 4장 참고)

​

​

83

84 of 105

예) LR(0) 파싱

  • LR(0) 파싱 - 효율적 Shift-Reduce 파싱
  • 덧셈/곱셈 문법에 대한 LR(0) 오토마타 (Dragon book, Fig. 4.31)
  • LR(0) 아이템 A -> X . Y Z : X에서 유도되는 입력 문자열을 지나왔고 앞으로 YZ에서 유도되는 입력 문자열을 기대함
  • LR(0) 오토마톤

상태 : LR(0) 아이템의 집합

전이 : Shift 터미널

Reduce 넌터미널(+ Goto)

  • 스택 필요 (Why?)

예) I11에서 I0, I4, I6으로 갈까?

​

​

​

84

85 of 105

예) LR(0) 파싱

​

​

​

85

86 of 105

LR 파싱

  • LR 파서 상태 = LR 아이템의 집합

- LR 아이템: 예) A -> X Y Z

A -> . X Y Z, A -> X . Y Z, A -> X Y . Z, A -> X Y Z .

예) A ->

A -> .

- 각 LR 아이템은 해당 생산 규칙에서 어디까지 지나왔고, 앞으로 무엇을 기대하는지를 나타냄

예) A -> . X Y Z : 그 다음 입력에서 X Y Z로부터 유도 가능한 문자열을 기대

예) A -> X . Y Z : X에서 유도 가능한 문자열을 바로 전 입력에서 보았고,

Y Z에서 유도 가능한 문자열을 그 다음 입력에서 기대

- LR 아이템의 집합은 어떤 문자열을 바로 전 입력에서 보았을때 이를 수 있는 동일한 위치를 나타내는 LR 아이템들을 모아 놓은 집합

​

​

86

87 of 105

LR 파싱

  • LR 파서 상태 전이: 액션과 스택

- 예) I0 -- E --> I1 E’ -> . E E’ -> E . Goto E

- 예) I0 -- id --> I5 F -> . id F -> id . Shift 5 for id

- E’ -> E . 아이템을 포함하는 I1 상태 Accept

- 예) I11 에서 어디로 돌아갈지? F -> ( E ) . Reduce F -> ( E )

I0 == ( ==> I4 == E ==> I8 == ) ==> I11 이면 I0로 돌아가고,

I7 == ( ==> I4 == E ==> I8 == ) ==> I11 이면 I7로 돌아간다.

어느 방향으로 I11에 도달하였는지 그 궤적을 저장하기 위한 스택이 필요!

​

​

87

88 of 105

예) LR 오토마타 예시

88

0: E' -> E

1: E -> E + T

2: E -> T

3: T -> T * F

4: T -> F

5: F -> ( E )

6: F -> id

​

0 ( Shift 4

0 id Shift 5

1 + Shift 6

1 $ Accept

2 ) Reduce 2

2 * Shift 7

2 + Reduce 2

2 $ Reduce 2

3 ) Reduce 4

3 * Reduce 4

3 + Reduce 4

3 $ Reduce 4

4 ( Shift 4

4 id Shift 5

5 ) Reduce 6

5 * Reduce 6

5 + Reduce 6

5 $ Reduce 6

6 ( Shift 4

6 id Shift 5

7 ( Shift 4

7 id Shift 5

8 ) Shift 11

8 + Shift 6

9 ) Reduce 1

9 * Shift 7

9 + Reduce 1

9 $ Reduce 1

10 ) Reduce 3

10 * Reduce 3

10 + Reduce 3

10 $ Reduce 3

11 ) Reduce 5

11 * Reduce 5

11 + Reduce 5

11 $ Reduce 5

0 E 1

0 T 2

0 F 3

4 E 8

4 T 2

4 F 3

6 T 9

6 F 3

7 F 10

​

생산규칙

액션 테이블

Goto 테이블

89 of 105

LR 파싱

  • LR 파싱 알고리즘
  • 오토마톤 : 번호가 매겨진 생산 규칙, 액션 테이블, Goto 테이블
  • 입력 : 토큰 시퀀스 + EndOfToken ($)
  • 출력 : Accept / Not

​

​

​

​

​

89

90 of 105

LR 파싱

  • LR 파싱 알고리즘
  • 오토마톤 : 번호가 매겨진 생산 규칙, 액션 테이블, Goto 테이블
  • 입력 : 토큰 시퀀스 + EndOfToken ($)
  • 출력 : Accept / Not
  • 현재 상태를 시작 상태 0으로 설정
  • 현재 토큰을 시퀀스의 맨 앞 토큰으로 설정
  • 스택에 현재 상태를 넣기
  • 액션 테이블 [스택 Top의 상태, 현재 토큰]의 액션에 따라 다음을 반복 수행

1) Shift j: 현재 토큰을 스택에 넣고 상태 j를 스택에 넣기

2) Reduce (k: A -> beta): beta 길이 2배 만큼 스택 원소들을 빼고, Goto 테이블 [뺀 다음 스택 top의 상태, A]의 다음 상태 i를 구하고, 스택에 A를 먼저 넣고, 그 다음 상태 i를 넣기

3) Accept: 파서는 입력 토큰 시퀀스를 Accept하고 종료

4) 그 이외의 경우는 파싱 에러!

​

​

​

​

90

91 of 105

LR 파싱

Q. 토큰 시퀀스 id + id * id $ 에 대하여 LR 파싱을 진행해보시오.

  • 0 id (Shift 5)
  • 5 id 0 + (Reduce 6: F -> id) F + id * id
  • 3 F 0 + (Reduce 4: T -> F) T + id * id
  • 2 T 0 + (Reduce 2: E -> T) E + id * id
  • 1 E 0 + (Shift 6)
  • 6 + 1 E 0 id (Shift 5)
  • 5 id 6 + 1 E 0 * (Reduce 6: F -> id) E + F * id
  • 3 F 6 + 1 E 0 * (Reduce 4: T -> F) E + T * id
  • 9 T 6 + 1 E 0 * (Shift 7)
  • 7 * 9 T 6 + 1 E 0 id (Shift 5)
  • 5 id 7 * 9 T 6 + 1 E 0 $ (Reduce 6: F -> id) E + T * F
  • 10 F 7 * 9 T 6 + 1 E 0 $ (Reduce 3: T -> T * F) E + T
  • 9 T 6 + 1 E 0 $ (Reduce 1: E -> E + T) E
  • 1 E 0 $ (Accept)

91

[REMIND] 토큰 시퀀스 id + id * id $는 식 “x + y * z”을 어휘 분석하여 얻은 토큰 시퀀스에 특수 토큰 (EndOfToken $)을 추가한 것으로 id는 토큰 이름, x, y, z는 각 id 토큰의 lexeme들이다.

92 of 105

LR 파싱

Q. 앞서 진행한 LR 파싱의 3번째 컬럼의 유도 과정을 조합하여 얻을 수 있는 구문 트리는 무엇인가?

  • ​

92

id

+

*

id

id

93 of 105

LR 파싱 Reduce 액션과 구문 트리

  • LR 파싱에서 Reduce 액션을 할 때 관련된 생산 규칙에 맞는 구문 트리를 만듬
  • 0: E' -> E { E의 구문 트리를 그대로 왼편 E’의 구문 트리로 전달 }
  • 1: E -> E + T { 왼편 E의 덧셈 노드를 새로 만들고
  • 오른편 E의 구문 트리를 왼쪽 피연산자로
  • T의 구문 트리를 오른쪽 피연산자로 설정 }
  • 2: E -> T { T의 구문 트리를 그대로 왼편 E의 구문 트리로 전달 }
  • 3: T -> T * F { 왼편 T의 곱셈 노드를 새로 만들고
  • 오른편 T의 구문 트리를 왼쪽 피연산자로
  • F의 구문 트리를 오른쪽 피연산자로 설정 }
  • 4: T -> F { F의 구문 트리를 왼편 T의 구문 트리로 전달 }
  • 5: F -> ( E ) { E의 구문 트리를 왼편 F의 구문 트리로 전달 }
  • 6: F -> id { 리프 노드 (leaf node)를 만들어 속성으로 식별자 id를 저장하고
  • 왼편 F로 전달 }

93

94 of 105

LR 파싱 Reduce 액션과 구문 트리

Q. 앞서 구문 트리를 만드는 각 과정을 여러분이 익숙한 프로그래밍언어를 사용하여 구현하시오.

  • 예) “E -> E + T” { $$ = new Add( $E, $T ); }

public class Add extends Tree {

private Tree left, right; // getters are assumed to be available

public Add (Tree left, Tree right) { this.left = left; this.right = right; }

}

  • 예) “E -> T” { $$ = $T }

94

95 of 105

LR 파싱 Reduce 액션과 구문 트리

Q. 5: F -> ( E )에서 괄호를 구문 트리에 따로 저장하지 않았다. 그 이유는 무엇인지 설명하시오.

95

96 of 105

While 언어 문법 : LR(1)

​

  • LR(1) 클래스에 속함! - 더 정확히는 LALR(1) 클래스에도 속함!

​

​

​

96

참고)

​

LALR (Lookahead-LR) :

  • LR(k) 보다 적은 오토마톤 크기로 LR(k)와 동일한 파싱 능력을 갖음

97 of 105

문법 작성하기

  • 왜 어휘 분석과 구문 분석을 분리하는가? 드래곤북 4.3.1
  • 문법 작성하기 (드래곤북 4.3)
  • 모호한 문법을 수정하기 (ambiguous grammars)

:모호한 문법: 주어진 문자열에 대해 두 가지 이상의 구문 트리를 만들 수 있는 문법

​

​

​

  • LL 파싱 (Top-down 파싱)을 위한 Left-recursion elimination과 Left factoring

​

  • 문맥 자유 문법으로 작성하지 못하는 프로그래밍언어 특징

97

98 of 105

실습 : Tree-sitter (깃허브)

98

​

[참고]

https://lazyswamp.blogspot.com/2024/09/how-to-build-rust-implementation-of.html

​

99 of 105

실습 : PMD

  • PMD is a source code analyzer. It finds common programming flaws like unused variables, empty catch blocks, unnecessary object creation, and so forth. It supports many languages. It can be extended with custom rules. It uses JavaCC and Antlr to parse source files into abstract syntax trees (AST) and runs rules against them to find violations. Rules can be written in Java or using a XPath query.
  • ​
  • It supports Java, JavaScript, Salesforce.com Apex and Visualforce, Modelica, PLSQL, Apache Velocity, XML, XSL, Scala.
  • ​
  • Additionally it includes CPD, the copy-paste-detector. CPD finds duplicated code in C/C++, C#, Dart, Fortran, Go, Groovy, Java, JavaScript, JSP, Kotlin, Lua, Matlab, Modelica, Objective-C, Perl, PHP, PLSQL, Python, Ruby, Salesforce.com Apex, Scala, Swift, Visualforce and XML.
  • ​
  • In the future we hope to add support for data/control flow analysis and automatic (quick) fixes where it makes sense.

​

99

100 of 105

실습 : PMD

  • PMD를 설치하고 MySmallBasic (Java 소스 프로그램)을 분석하시오.
  • [PMD 설치하기]
  • https://pmd.sourceforge.io/pmd-6.49.0/pmd_userdocs_installation.html
  • pmd-bin-6.49.0.zip 파일 다운로드
  • unzip해서 디렉토리에 설치하고
  • bin/run.sh 실행 파일 경로 설정 : export PATH=$PATH:/home/khchoi/work/sav/pmd/pmd-bin-6.49.0/bin
  • [분석 대상 MySmallbasic 소스 프로그램 다운로드]
  • https://github.com/kwanghoon/MySmallbasic 에서 MySmallBasic.zip 파일 다운로드 받아 설치하기
  • [PMD로 분석]
  • pmd를 실행하기

run.sh pmd -d MySmallBasic/MySmallBasic/src/com/coducation/smallbasic/ -R rulesets/java/quickstart.xml

​

​

​

100

101 of 105

실습 : PMD

101

khchoi@khchoi-ThinkPad-X1-Carbon-5th:~/work/sav/pmd$ run.sh pmd -d MySmallBasic/MySmallBasic/src/com/coducation/smallbasic/ -R rulesets/java/quickstart.xml

9월 20, 2022 4:03:23 오후 net.sourceforge.pmd.PMD encourageToUseIncrementalAnalysis

경고: This analysis could be faster, please consider using Incremental Analysis: https://pmd.github.io/pmd-6.49.0/pmd_userdocs_incremental_analysis.html

/home/khchoi/work/sav/pmd/MySmallBasic/MySmallBasic/src/com/coducation/smallbasic/ArithExpr.java:21: MethodNamingConventions: The instance method name 'GetOp' doesn't match '[a-z][a-zA-Z0-9]*'

/home/khchoi/work/sav/pmd/MySmallBasic/MySmallBasic/src/com/coducation/smallbasic/ArithExpr.java:25: MethodNamingConventions: The instance method name 'GetOperand' doesn't match '[a-z][a-zA-Z0-9]*'

/home/khchoi/work/sav/pmd/MySmallBasic/MySmallBasic/src/com/coducation/smallbasic/ArithExpr.java:35: LocalVariableNamingConventions: The local variable name 'temp_ex' doesn't match '[a-z][a-zA-Z0-9]*'

/home/khchoi/work/sav/pmd/MySmallBasic/MySmallBasic/src/com/coducation/smallbasic/ArithExpr.java:36: OneDeclarationPerLine: Use one line for each declaration, it enhances code readability.

/home/khchoi/work/sav/pmd/MySmallBasic/MySmallBasic/src/com/coducation/smallbasic/ArithExpr.java:38: LocalVariableNamingConventions: The local variable name 'parsed_float1' doesn't match '[a-z][a-zA-Z0-9]*'

/home/khchoi/work/sav/pmd/MySmallBasic/MySmallBasic/src/com/coducation/smallbasic/ArithExpr.java:38: LocalVariableNamingConventions: The local variable name 'parsed_float2' doesn't match '[a-z][a-zA-Z0-9]*'

​

102 of 105

실습 : SonarQube

  • SonarQube를 설치하고 MySmallBasic (Java 소스 프로그램과 class 파일)을 분석하시오.
  • sonar.sh 웹 서버에서 분석 결과를 웹 GUI로 리포트

sonar-scanner에서 대상 프로그램을 분석하고 웹 서버에 전달

  • [1] sonarqube 설치 (sonar.sh)후 실행

https://www.sonarqube.org/

sonarqube-9.6.1.59531.zip 을 다운받아 같은 이름의 폴더에 풀기

ln -s sonarqube-9.6.1.5953/bin/linux-x86-64 bin

./bin/sonar.sh console

  • [2] http://localhost:9000으로 접속하기

ID/PW: admin/admin

​

102

103 of 105

실습 : SonarQube

  • SonarQube를 설치하고 MySmallBasic (Java 소스 프로그램과 class 파일)을 분석하시오. (계속)
  • [3] sonar-scanner 설치 및 실행 (소스 코드 분석기)

https://docs.sonarqube.org/latest/analysis/scan/sonarscanner/

sonar-scanner-4.7.0.2747-linux.zip 다운받아 같은 이름의 폴더에 풀기

export PATH=$MYHOME:/sonar-scanner-4.7.0.2747-linux/bin:$PATH

sonar-scanner -Dsonar.projectKey=MySmallBasic_Project -Dsonar.sources=./MySmallBasic/src -Dsonar.host.url=http://localhost:9000 -Dsonar.login=sqp_49ec5788961b7f269bd793244e1a27cd89764f87 -Dsonar.java.binaries=./MySmallBasic/bin

기본적으로 Java 소스 프로그램과 바이너리 (클래스) 프로그램이 모두 필요.

바이너리가 없을 때 configuration에서 분석 범위에서 제외

​

103

토큰은 본인 환경에서 새로 생성

(다음 슬라이드 참고)

104 of 105

실습 : SonarQube

104

​

분석할 프로젝트를 새로 만들 때 sonarqube 웹 (http://localhost:9000)에서 이 프로젝트 토큰을 만들고 나중에 분석할 때 옵션으로 이 토큰을 지정하면 분석 결과가 해당 프로젝트로 전달됨.

​

Now that you're logged in to your local SonarQube instance, let's analyze a project:

​

  1. Click the Create new project button.
  2. Give your project a Project key and a Display name and click the Set Up button.
  3. Under Provide a token, select Generate a token. Give your token a name, click the Generate button, and click Continue.
  4. Select your project's main language under Run analysis on your project, and follow the instructions to analyze your project. Here you'll download and execute a Scanner on your code (if you're using Maven or Gradle, the Scanner is automatically downloaded).

​

After successfully analyzing your code, you'll see your first analysis on SonarQube:

​

105 of 105

실습 : SonarQube

105