본문 바로가기
C++ 200제/코딩 IT 정보

컴파일러 문제 풀이, 파싱 테이블 LL 파서, 구문 분석 parser 구현

by vicddory 2018. 10. 9.

고급 컴파일러 문제 풀이, 파싱 테이블, LL 파서


4.9 다음 『파서 문법을 생각해보시오


  • lexp ⟶ atom | list
  • atom ⟶ number | identifier
  • list ⟶ (lex-seq)
  • lexp-seq ⟶ lexp, lexp-seq | lexp



컴파일러 문제 풀이, 파싱 테이블 LL 파서, 구문 분석 parser 구현[LL 파서 구문분석 Parser 구현]



a. 이 문법에 대한 좌측 인수 분해한 결과의 파서 문법을 구하시오.


  • lexp ⟶ atom | list
  • atom ⟶ number | identifier
  • list ⟶ (lexp-seq)
  • lexp-seq ⟶ lexp lexp-seq'
  • lexp-seq' ⟶ , lexp-seq | ε



LL파서 parser 구현[LL 파서 구문분석 Parser 구현]


b. 결과 문법의 비단말기호에 대한 First와 Follow 집합을 생성하시오.


  • First(lexp) = { number, identifier, ( }
  • First(atom) = { number, identifier }
  • First(list) = { ( }
  • First(lexp-seq) = { number, identifier, ( }
  • First(lexp-seq') = { ,, ε }
  • Follow(lexp) = {, $, } }
  • Follow(atom) = {, $, } }
  • Follow(list) = {, $, } }
  • Follow(lexp-seq) = {$, } }
  • Follow(lexp-seq') = {$, } }



고급 컴파일러 LL 파서[LL 파서 구문분석 Parser 구현]



c. 결과 파서 문법이 LL(1)임을 보이시오.


다음 (d)의 답안에 보이듯, 테이블 항목들에겐 하나의 선택 사항이 존재한다. (『파싱 테이블 변환 전』)


(여긴 반응형 스킨을 적용한 블로그라 표가 늘어질 수 있으니 되도록이면 데탑에서 보시거나 모바일이라면 가로로 기기를 눕히세요)


 M[N, T]

 number

 identifier

 (

 )

 ,

 $

 Lexp

 lexp→atom

 lexp→atom

 lexp→list

 

 

 

 Atom

 atom→

 number

 atom→

 identifier

 

 

 List

 

 

 list→

 (lexp-seq)

 

 

 

 Lexp-seq

 lexp-seq→

 lexp

 lexp-seq'

 lexp-seq→

 lexp

 lexp-seq'

 lexp-seq→

 lexp

 lexp-seq'

 

 

 

 lexp-seq'

 

 

 

 lexp-seq'→ε

 lexp-seq'→

 lexp-seq

 lexp-seq'→ε



파서 문법 구하기 컴파일러[LL 파서 구문분석 Parser 구현]



d. 결과 문법에 대한 LL(1) 파싱 테이블을 생성하시오.


  • 문제 - (a, (b, (2)), (c))


Parsing Stack

Input String

Action

 $lexp-seq

 (a,(b,(2)),(c))$

 lexp-seq⟶lexp lexp-seq'

 $lexp-seq'lexp

 (a,(b,(2)),(c))$

 lexp⟶list

 $lexp-seq'list

 (a,(b,(2)),(c))$

 list⟶(lexp-seq)

 $lexp-seq')lexp-seq(

 (a,(b,(2)),(c))$

 match

 $lexp-seq')lexp-seq

 a,(b,(2)),(c))$

 lexp-seq⟶lexp lexp-seq'

 $lexp-seq')lexp-seq'lexp

 a,(b,(2)),(c))$

 lexp⟶atom

 $lexp-seq')lexp-seq'atom

 a,(b,(2)),(c))$

 atom⟶identifier

 $lexp-seq')lexp-seq'identifier

 a,(b,(2)),(c))$

 match

 $lexp-seq')lexp-seq'

 ,(b,(2)),(c))$

 lexp-seq'⟶,lexp-seq

 $lexp-seq')lexp-seq ,

 ,(b,(2)),(c))$

 match

 $lexp-seq')lexp-seq

 (b,(2)),(c))$

 lexp-seq⟶lexp lexp-seq'

 $lexp-seq')lexp-seq'lexp

 (b,(2)),(c))$

 lexp⟶list

 $lexp-seq')lexp-seq'list

 (b,(2)),(c))$

 list⟶(lexp-seq)

 $lexp-seq')lexp-seq')lexp-seq(

 (b,(2)),(c))$

 match

 $lexp-seq')lexp-seq')lexp-seq

 b,(2)),(c))$

 lexp-seq⟶lexp lexp-seq'

 $lexp-seq')lexp-seq')lexp-seq'lexp

 b,(2)),(c))$

 lexp⟶atom

 $lexp-seq')lexp-seq')lexp-seq'atom

 b,(2)),(c))$

 atom⟶identifier

 $lexp-seq')lexp-seq')lexp-seq'identifier

 b,(2)),(c))$

 match

 $lexp-seq')lexp-seq')lexp-seq'

 ,(2)),(c))$

 lexp-seq'⟶,lexp-seq

 $lexp-seq')lexp-seq')lexp-seq,

 ,(2)),(c))$

 match

 $lexp-seq')lexp-seq')lexp-seq

 (2)),(c))$

 lexp-seq⟶lexp lexp-seq'

 $lexp-seq')lexp-seq')lexp-seq'lexp

 (2)),(c))$

 lexp⟶list

 $lexp-seq')lexp-seq')lexp-seq'list

 (2)),(c))$

 list⟶(lexp-seq)

 $lexp-seq')lexp-seq')lexp-seq)lexp-seq(

 (2)),(c))$

 match

 $lexp-seq')lexp-seq')lexp-seq)lexp-seq

 2)),(c))$

 lexp-seq⟶lexp lexp-seq'

 $lexp-seq')lexp-seq')lexp-seq)lexp-seq'lexp

 2)),(c))$

 lexp⟶atom

 $lexp-seq')lexp-seq')lexp-seq)lexp-seq'atom

 2)),(c))$

 atom⟶number

 $lexp-seq')lexp-seq')lexp-seq)lexp-seq'number

 2)),(c))$

 match

 $lexp-seq')lexp-seq')lexp-seq)lexp-seq'

 )),(c))$

 lexp-seq'⟶ε

 $lexp-seq')lexp-seq')lexp-seq') )),(c))$ match
 $lexp-seq')lexp-seq')lexp-seq' ),(c))$ lexp-seq'⟶ε
 $lexp-seq')lexp-seq') ),(c))$ match
 $lexp-seq')lexp-seq' ,(c))$ lexp-seq'⟶lexp-seq
 $lexp-seq')lexp-seq, ,(c))$ match
 $lexp-seq')lexp-seq (c))$ lexp-seq⟶lexp lexp-seq'
 $lexp-seq')lexp-seq'lexp (c))$ lexp⟶list
 $lexp-seq')lexp-seq'list (c))$ list⟶(lexp-seq)
 $lexp-seq')lexp-seq')lexp-seq( (c))$ match
 $lexp-seq')lexp-seq')lexp-seq c))$ lexp-seq⟶lexp lexp-seq'
 $lexp-seq')lexp-seq')lexp-seq'lexp c))$ lexp⟶atom
 $lexp-seq')lexp-seq')lexp-seq'atom c))$ atom⟶identifier
 $lexp-seq')lexp-seq')lexp-seq'identifier c))$ match
 $lexp-seq')lexp-seq')lexp-seq' ))$ lexp-seq'⟶ε
 $lexp-seq')lexp-seq') ))$ match
 $lexp-seq')lexp-seq' )$ lexp-seq'⟶ε
 $lexp-seq') )$ match
 $lexp-seq' $ lexp-seq'⟶ε
 $ $ accept




4.10 단순화된 다음 C 선언문에 대한 문법을 생각해보시오


  • declaration ⟶ type var-list
  • type ⟶ int | float
  • var-list ⟶ identifier, var-list | identifier



컴파일러 파싱 테이블 ll 파서[LL 파서 구문분석 Parser 구현]



a. 이 파서 문법에 대한 좌측 인수 분해한 결과의 문법을 구하시오.


  1. decl ⟶ type var-list
  2. type ⟶ int
  3. type ⟶ float
  4. var-list ⟶ identifier B
  5. B ⟶ , var-list
  6. B ⟶ ε



컴파일러 파싱 테이블 구현[LL 파서 구문분석 Parser 구현]



b. 결과 파서 문법의 비단말기호에 대한 First와 Follow 집합을 생성하시오.


  • First(decl) = First(type) = {int, float}
  • First(type) = First(int) ∪ First(float) = {int, float}
  • First(var-list) = First(identifier) = {identifier}
  • First(B) = First(,) ∪ First(ε) = {, ε}
  • Follow(decl) = { $ }
  • Follow(type) = First(var-list) = {identifier}
  • Follow(var-list) = Follow(decl) = { $ }
  • Follow(B) = Follow{var-list} = { $ }



고급 컴파일러 parser 구현[LL 파서 구문분석 Parser 구현]



c. 결과 문법이 LL(1)임을 보이시오.


1. First(int) ∩ First(float) = ∅

First(,) ∩ First(ε) = ∅


2. ε ∈ First(B)

First(B) ∩ Follow(B) = ∅


d. 결과 문법에 대한 LL(1) 파싱 테이블을 생성하시오.


M[N,T]

 int

 float

 identifier

 ,

 $

 decl

 1

 1

 

 

 

 type

 2

 3

 

 

 

 var-list

 

 

 4

 

 

 B

 

 

 

 5

 6



컴파일러 파싱 테이블[LL 파서 구문분석 Parser 구현]



e. 아래에 주어진 입력문장에서, LL(1) 파서의 동작을 보이시오.


문제 - int x, y, z.


Parsing Stack

Input

Action

 $ decl

 int x, y, z$

 decl⟶type var-list

 $ var-list type

 int x, y, z$

 type⟶int

 $ var-list int

 int x, y, z$

 match int

 $ var-list 

 x, y, z$

 var-list⟶identifier B

 $ B identifier

 x, y, z$

 match identifier w/x

 $ B

 , y, z$

 B⟶, var-list

 $ var-list ,

 , y, z$

 match ,

 $ var-list 

 y, z$

 var-list⟶identifier B

 $ B identifier

 y, z$

 match identifier w/y

 $ B

 , z$

 B⟶, var-list

 $ var-list ,

 , z$

 match ,

 $ var-list 

 z$

 var-list⟶identifier B

 $ B identifier

 z$

 match identifier w/z

 $ B

 $

 B⟶ε

 $

 $

 Accept



고급 컴파일러 문제 풀이, 파싱 테이블, LL 파서

댓글