컴파일러 5장 연습 문제

소개글

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

목차

5.1 다음 괄호에 알맞은 단어를 쓰시오.
5.2 다음 약어에 대한 원어(full name)를 쓰시오.
5.3 다음을 간략히 정의하시오.
5.4 다음을 간단히 설명하시오
5.5 Mini C 언어에 대한 다음 구조를 문법 흐름도로 그리시오.
5.6 다음과 같은 문법이 주어졌을 때, 문장 begin d;s;s end 에 대한 좌측 유도와 우측 유도 과정을 보이시오.
5.7 생성 규칙이 다음과 같은 문법이 있다.
중략..

본문내용

()), $LSLS )
┣ {q, ()), $LSLSRS)
┣ {q, ()), $LSS )
┣ {q, ()), $LS )
┣ {q, )), $LSLS )
┣ {q, ), $LSLSRS)
┣ {q, ), $LSS )
┣ {q, ), $LS )
┣ {q, ε, $LSRS )
┣ {q, ε, $S )
┣ {q, ε, ε )
5.27 다음 context-free 언어를 보고 물음에 답하시오.
L = { ωcωR | ω∈{a,b}* }
① L을 인식하는 PDA P를 top-down 방법으로 구성하시오.
G : S → aSa | bSb | c
① 다른 방법
P = 동일하고 전이함수만 변경함
δ(q1, a, S) = (q1, Sa)
δ(q1, b, S) = (q1, Sb)
δ(q1, c, S) = (q2, ε)
δ(q2, a, a) = (q2, ε)
δ(q2, b, b) = (q2, ε)
δ(q2, ε, R) = (q2, ε)
② 인식과정
(q1, abbcbba, SR)
┣ (q1, bbcbba, SaR)
┣ (q1, bcbba, SbaR)
┣ (q1, cbba, SbbaR)
┣ (q2, bba, bbaR)
┣ (q2, ba, baR)
┣ (q2, a, aR)
┣ (q2, ε, R)
┣ (q2, ε, ε)
P = ( {q1, q2}. {a, b, c}, {a, b, S, R}, δ, q1, SR, {q2} ),
δ(q1, ε, S) = { (q1, aSa) , (q1, bSb) }
δ(q1, a, aS) = (q1, S) δ(q1, b, bS) = (q1, S)
δ(q1, c, S) = (q2, ε)
δ(q2, a, a) = (q2, ε)δ(q2, b, b) = (q2, ε)
δ(q2, ε, R) = δ(q2, ε)
② P에 의해서 스트링 abbcbba를 인식하는 과정을 보이시오.
(q1, abbcbba, SR)┣ (q1, abbcbba, aSaR)
┣ (q1, bbcbba, SaR)
┣ (q1, bbcbba, bSbaR)
┣ (q1, bcbba, SbaR)
┣ (q1, bcbba, bSbbaR)
┣ (q1, cbba, SbbaR)
┣ (q2, bba, bbaR)
┣ (q2, ba, baR)
┣ (q2, a, aR)
┣ (q2, ε, R)
┣ (q2, ε, ε)
③ L을 인식하는 PDA R을 bottom-up 방법으로 구성하시오.
P = ( {q1, q2}. {a, b, c}, {a, b, $}, δ, q1, $, {q2} ),<참조 ex27>
δ(q1, a, ε ) = (q1, a)δ(q1, b, ε ) = (q1, b)
δ(q1, c, ε ) = (q2, ε)
δ(q2, a, a ) = {(q2, ε)}δ(q2, b, b ) = {(q2, ε)}
δ(q2, ε, $ ) = {(q2, ε)}
④ R에 의해서 스트링 abbcbba를 인식하는 과정을 보이시오.
(q1, abbcbba, $)┣ (q1, bbcbba, $a)
┣ (q1, bcbba, $ab)
┣ (q1, cbba, $abb)
┣ (q2, bba, $abb)
┣ (q2, ba, $ab)
┣ (q2, a, $a)
┣ (q2, ε, $)
┣ (q2, ε, ε)
5.28 다음 언어 ( ∑ = {a, b, c} )를 인식하는 PDA를 구성하시오.
① L = { anb2n | n≥0 }
G :S → aSbb | ε
P = ( {q, r}, {a, b}, {a, b, S}, δ, q, S, {r} ),
δ(q, ε, S) = { (q, aSbb), (r, ε) }
δ(q, a, aS) = (q, S)
δ(q, b, Sb) = (r, ε)
δ(r, b, b) = (r, ε)
② L = { ω | na(ω) = nb(ω) }
G :S → aSb | bSa
P = ( {q}, {a, b}, {a, b, $}, δ, q, $, φ ),
δ(q, a, a) = (q, aa)
δ(q, a, b) = (q, ε)
δ(q, b, b) = (q, bb)
δ(q, b, a) = (q, ε)
δ(q, ε, $) = (q, ε)
③ L = { ω | na(ω) + nb(ω) = nc(ω) }
PDA P = ( { q }, { a, b, c }, { a, b, c, $ }, δ, q, $, φ ),
δ(q, a, $) = (q, a$)δ(q, b, $) = (q, b$)δ(q, c, $) = (q, c$)
δ(q, a, a) = (q, c)δ(q, b, a) = (q, c)δ(q, c, a) = (q, ac)
δ(q, a, b) = (q, c)δ(q, b, b) = (q, c)δ(q, c, b) = (q, bc)
δ(q, a, c) = (q, ac)δ(q, b, c) = (q, bc)δ(q, c, c) = (q, ε)
δ(q, ε, $) = {q, ε)
5.29 다음을 CFG로 고안하고 주어진 스트링에 대한 유도 트리를 그리시오.
① list structure :
▷ λ는 null을 나타내고 a는 atom을 나타내는 리스트 구조이다. 그리고 ℓ1, ℓ2, …, ℓk 가 리스트 구조이면, (ℓ1, ℓ2, …, ℓk)도 역시 리스트 구조이다.
▷ (((a,a),λ,(a)),a)
② nested parenthesis structure :
△ 괄호의 종류는 () 과 [] 의 두 가지이며, 항상 균형을 이룬다. 그러나 상식적으로 ([])와 ([[]])는 가능한 구조이나 ([)나 (])은 틀린 형태이다.
△ ([][])[()]
G : S → (S)S | [S]S | ε
유도과정 :
S ⇒ (S)S ⇒ ([S]S)S ⇒ ([S][S]S)S ⇒ ([S][S]S)[S]S ⇒ ([S][S]S)[(S)S]S
5.30 다음은 Tiny C (by Ian Kaplan) 문법을 EBNF로 기술한 것이다. 2개의 정수를 매개 변수로 받아 최대 공약수(GCD: Greatest Common Divisor)를 구하는 함수 gcd()를 작성하시오.
5.31 다음은 SPL (Simple Programming Language)의 문법을 EBNF로 기술한 것이다. N개의 정수 자료를 읽어 최소 값과 최대 값을 찾아 출력하는 SPL 프로그램을 작성하시오. 첫 번째 읽은 값이 자료의 개수이다.

키워드

컴파일러,   컴파일러 입문,   연습문제