고급 컴파일러 문제 풀이, 파싱 테이블, LL 파서
4.9 다음 『파서 문법』을 생각해보시오
- lexp ⟶ atom | list
- atom ⟶ number | identifier
- list ⟶ (lex-seq)
- lexp-seq ⟶ lexp, lexp-seq | lexp
[LL 파서 구문분석 Parser 구현]
a. 이 문법에 대한 좌측 인수 분해한 결과의 파서 문법을 구하시오.
- lexp ⟶ atom | list
- atom ⟶ number | identifier
- list ⟶ (lexp-seq)
- lexp-seq ⟶ lexp lexp-seq'
- lexp-seq' ⟶ , lexp-seq | ε
[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 파서 구문분석 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 파서 구문분석 Parser 구현]
a. 이 파서 문법에 대한 좌측 인수 분해한 결과의 문법을 구하시오.
- decl ⟶ type var-list
- type ⟶ int
- type ⟶ float
- var-list ⟶ identifier B
- B ⟶ , var-list
- 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} = { $ }
[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 파서
댓글