컴파일러 입문 5장

소개글

컴파일러 입문 5장에 대한 보고서 자료입니다.

본문내용

a, Z ) = { ( q0, 0Z )}δ( q0, b, Z ) = { ( q0, 1Z )}
δ( q0, a, 0 ) = { ( q0, 00 )}δ( q0, b, 0 ) = { ( q0, ε )}
δ( q0, a, 1 ) = { ( q0, ε )}δ( q0, b, 1 ) = { ( q0, 11 )}
δ( q0, ε, Z ) = { ( qf, Z )}
스택이 초기 상태(Z)에서 입력 a 는 스택에 0을 넣고, 입력 b 는 스택에 1을 넣는다.
스택에 0이 있을 때 입력 a 는 스택에 0을 삽입하고, 입력 b 는 스택에서 0을 제거한다.
스택에 1이 있을 때 입력 a 는 스택에서 1을 제거하고, 입력 b 는 스택에 1을 삽입한다.
입력을 전부 처리하고 스택이 비었으면(Z) 종결상태(qf)로 입력 스트링은 인식된다.
집합 L(P) = { (a + b)* | Na = Nb, Na와 Nb는 스트링에 있는 a와 b의 수 }
5.25 다음 PDA P가 인식하는 언어 Le(P)는 무엇인가? 집합 표현으로 나타내시오.
P = ( {q1, q2}. {0, 1, c}, {R, B, G}, δ, q1, R, φ ),
δ( q1, 0, R ) = { ( q1, BR )}δ( q1, 1, R ) = { ( q1, GR )}
δ( q1, 0, B ) = { ( q1, BB )}δ( q1, 1, B ) = { ( q1, GB )}
δ( q1, 0, G ) = { ( q1, BG )}δ( q1, 1, G ) = { ( q1, GG )}
δ( q1, c, R ) = { ( q2, R )}δ( q1, c, B ) = { ( q2, B )}
δ( q1, c, G ) = { ( q2, G )}
δ( q2, 0, B ) = { ( q2, ε )}δ( q2, 1, G ) = { ( q2, ε )}
δ( q1, ε, R ) = { ( q2, ε )}
5.26 다음 context-free 문법 G를 보고 물음에 답하시오.
S → (S)S | ε
① L(G)를 인식하는 PDA P를 top-down 방법으로 구성하시오.
P = ( {q}. { ( , ) }, {S , ( , ) }, δ, q, S, φ ),
δ( q, ε, S ) = { ( q, (S)S ), ( q, ε ) }
δ( q, x, x ) = { ( q, ε ) }, 여기서 x ∈ { ( , ) }
② P에 의해서 스트링 ()(()())를 인식하는 과정을 보이시오.
( q, ()(()()), S ) ( q, ()(()()), (S)S )
( q, )(()()), S)S )
( q, )(()()), )S )
( q, (()()), S )
( q, (()()), (S)S)
( q, ()()), S)S)
( q, ()()), (S)S)S)
( q, )()), S)S)S)
( q, )()), )S)S)
( q, ()), S)S)
( q, ()), (S)S)S)
( q, )), S)S)S)
( q, )), )S)S)
( q, ), S)S)
( q, ), )S)
( q, ε, S)
( q, ε, ε)
③ L(G)를 인식하는 PDA R을 bottom-up 방법으로 구성하시오.
확장된 PDA R에 의하여
R = ( {q, r}. { ( , ) }, {S , ( , ) }, δ, q, $, { r } ),
δ( q, x, ε ) = { ( q, xS ) }, 여기서 x ∈ { ( , ) }
δ( q, ε, (S)S ) = { ( q, S ) }
δ( q, ε, ε ) = { ( q, S ) }
④ R에 의해서 스트링 ()(()())를 인식하는 과정을 보이시오.
( q, ()(()()), $ ) ( q, )(()()), $(S )
( q, (()()), $(S)S )
( q, (()()), $S )
( q, (()()), $ε )
( q, ()()), $(S )
( q, )()), $(S(S )
( q, ()), $(S(S)S )
( q, ()), $(SS )
( q, ()), $(Sε )
( q, )), $(S(S )
( q, ), $(S(S)S )
( q, ), $(SS )
( q, ), $(Sε )
( q, ε, $(S)S )
( q, ε, $S )
( r, ε, ε )
5.27 다음 context-free 언어를 보고 물음에 답하시오.
L = { ωcωR | ω∈{a,b}* }
① L을 인식하는 PDA P를 top-down 방법으로 구성하시오.
② P에 의해서 스트링 abbcbba를 인식하는 과정을 보이시오.
③ L을 인식하는 PDA R을 bottom-up 방법으로 구성하시오.
④ R에 의해서 스트링 abbcbba를 인식하는 과정을 보이시오.
5.28 다음 언어 ( ∑ = {a, b, c} )를 인식하는 PDA를 구성하시오.
① L = { anb2n | n≥0 }
② L = { ω | na(ω) = nb(ω) }
③ L = { ω | na(ω) + nb(ω) = nc(ω) }
5.29 다음을 CFG로 고안하고 주어진 스트링에 대한 유도 트리를 그리시오.
① list structure :
△ λ는 null을 나타내고 a는 atom을 나타내는 리스트 구조이다. 그리고 ℓ1, ℓ2, …, ℓk 가 리스트 구조이면, (ℓ1, ℓ2, …, ℓk)도 역시 리스트 구조이다.
△ (((a,a),λ,(a)),a)
② nested parenthesis structure :
△ 괄호의 종류는 () 과 [] 의 두 가지이며, 항상 균형을 이룬다. 그러나 상식적으로 ([])와 ([[]])는 가능한 구조이나 ([)나 (])은 틀린 형태이다.
△ ([][])[()]
5.30 다음은 Tiny C (by Ian Kaplan) 문법을 EBNF로 기술한 것이다. 2개의 정수를 매개 변수로 받아 최대 공약수(GCD: Greatest Common Divisor)를 구하는 함수 gcd()를 작성하시오.
5.31 다음은 SPL (Simple Programming Language)의 문법을 EBNF로 기술한 것이다. N개의 정수 자료를 읽어 최소 값과 최대 값을 찾아 출력하는 SPL 프로그램을 작성하시오. 첫 번째 읽은 값이 자료의 개수이다.

키워드

컴파일러,   컴파일러 입문,   컴파일러 입문 5장,   오세만