컴파일러 입문 제 2장 연습문제

소개글

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

본문내용

E_ST> | ε
→ \':=\'
→ \'CALL\'
→ \'BEGIN\' \'END\'
→ \';\' |
→ \'IF\' \'THEN\'
→ \'WHILE\' \'DO\'
→
→ \'=\' | \'<>\' | \'<\' | \'>\' | ‘<=’ | ‘>=’
→ \'+\' | \'-\' |
→ \'*\' | \'/\' |
→ \'-\' | | | \'(\' \')\'
참고 위 문법에서 <와 > 사이의 심벌은 nonterminal이고, terminal 심벌은 ‘와 ’ 사이에 표시했다. 문법 표현에서 오직 생성 규칙만을 명시했을 때, nonterminal 심벌은 생성 규칙의 왼쪽에 나타나는 심벌들이며 그 이외의 심벌은 terminal 심벌이다. 시작 심벌은 보통 첫 번째 생성 규칙의 왼쪽에 있는 nonterminal 심벌이다.
VARna; nb; num; div; sum
CONST limit = 500
na := 2// 2n-1
nb := 3// 2n-1
num := 6// 2n-1 * (2n-1)
while num < limit do
BEGIN
div := 2
sum := 1
while div <= nb do
BEGIN
if num % div = 0 then
sum := sum + div
div := div + 1
END
if num == sum then
print \"완전수 : \" num
na := na * 2// 2n-1
nb := na * 2 - 1// 2n-1
num := na * nb// 2n-1 * (2n-1)
END
.// end of program
2.20 다음은 Mini Language(by Edgar W. Dijkstra)의 문장에 해당하는 핵심 문법이다. 500 이하의 완전수를 구하는 프로그램을 작성하시오.
::= | \':=\' | \'if\' \'then\' \'else\' \'fi\'| \'while\' \'do\' \'od\'| \'skip\'
참고 생성 규칙에서 lhs와 rhs를 구분하는 기호를 → 대신에 BNF(Backus-Naur Form) 표기법에서는 ::=을 사용한다.
na := 2// 2n-1
nb := 3// 2n-1
num := 6// 2n-1 * (2n-1)
while num < 500 do
div := 2
sum := 1
while div <= nb do
if num % div == 0 then
sum := sum + div
fi
div := div + 1
od
if num == sum then
print \"완전수 : \" num
fi
na := na * 2// 2n-1
nb := na * 2 - 1// 2n-1
num := na * nb// 2n-1 * (2n-1)
od
완전수http://ko.wikipedia.org/
수론에서 완전수(完全數)는 자기 자신을 제외한 양의 약수를 더했을 때 자기 자신이 되는 양의 정수를 말한다.
최초 네 개의 완전수는 6, 28, 496, 8128이다.
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064
또, 완전수는 항상 연속되는 자연수의 합으로 표현할 수 있다.
6 = 1 + 2 + 3
28 = 1 + 2 + 3 + 4 + 5 + 6 + 7
496 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + . . . + 30 + 31
8128 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + . . . + 126 + 127
짝수 완전수
고대 그리스인들은 이들 네 개의 완전수 밖에는 알지 못했다. 유클리드는 이들을 2n1(2n 1) 에 알맞은 수를 대입해 구할 수 있다는 것을 발견했다.
n = 2 일때: 21(22 1) = 6
n = 3 일때: 22(23 1) = 28
n = 5 일때: 24(25 1) = 496
n = 7 일때: 26(27 1) = 8128
유클리드는 여기서 2n 1이 언제나 소수라는 점에 착안하여 2n 1가 소수일 때 2n-1(2n 1)는 완전수라는 것을 증명했다. 이때 n은 언제나 소수이지만 n이 소수라고 2n 1도 꼭 소수가 되지는 않는다. 2n 1이 소수일 때는 이를 메르센 소수라고 부른다. 마랭 메르센은 17세기에 정수론과 완전수를 연구한 수도승이었다.
유클리드 이후 2천년이 지나, 레온하르트 오일러는 모든 짝수 완전수는 2n-1(2n 1)의 형태라는 것을 증명했다. 즉 짝수 완전수와 메르센 소수 사이에는 일대일 대응이 있다는 것이 밝혀졌다. 메르센 소수의 수가 유한한지 무한한지는 알려져 있지 않다. 그러므로 완전수의 수가 무한한지도 알려져 있지 않다.
홀수 완전수
홀수 완전수가 존재하는 지는 아직 알려져 있지 않다. 적어도 10300 까지의 정수 중에는 없다는 것이 확인된 바 있다.
완전수와 더불어, 진약수를 더해서 자기 자신보다 적은 수를 부족수, 많은 수를 과잉수라 부른다. 서로의 진약수를 더하면 상대편이 되는 두 수는 친화수라 부른다.

키워드

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