컴파일러 입문

소개글

컴파일러 입문 (정익사) 2장 전체 연습 문제 입니다.

목차

2.1 다음 괄호에 알맞은 말을 쓰시오.
2.2 다음 괄호에 알맞은 용어를 쓰시오.
2.3 다음 용어에 대한 정의를 쓰시오.
2.4 다음 질문에 대하여 간략히 답 하시오
2.5 다음 문법을 보고 물음에 답하시오.
2.6 만일 L(G1) = L(G2)이면, 두 개의 문법 G1과 G2가 동등하다고 말한다. 다음 문법과 동등한 문법을 하나만 적어보시오.
2.7 다음 정규 문법이 생성하는 언어는 각각 무엇인가?
2.8 다음 언어를 생성하는 정규 문법은 무엇인가?
2.9 다음 context-free 문법이 생성하는 언어는 각각 무엇인가?
2.10 다음 CFG가 나타내는 언어의 형태를 설명하시오.
2.11 다음 언어를 생성하는 context-free 문법은 각각 무엇인가?
2.13 다음 언어를 생성하는 context-sensitive 문법은 각각 무엇인가?
2.14 다음 언어를 생성하는 문법을 구하시오.
2.15 다음 언어를 생성하는 문법을 고안하시오.
2.16 VT = {a,b}이고 ηa(ω)와 ηb(ω)가 각각 스트링 ω에 있는 a와 b의 개수라 할 때, 다음 언어를 생성하는 context-free 문법을 고안하시오.
2.17다음과 같은 프로그래밍 언어의 구조를 나타내는 context-free 문법을 고안하시오.
2.18 G1 = (VN1, VT1, P1, S1) 과 G2 = (VN2, VT2, P2, S2)를 임의의 형태의 문법이라 하자. 문법 G1 과 G2 로부터 각각의 문법 형태에 대하여 다음을 구성하는 방법을 보이시오.
2.19 다음은 PL/0 문법이다. PL/0 언어를 이용하여 다음을 프로그래밍 하시오. 500 이하의 완전수(perfect number)를 구하시오. 완전수란 자신을 제외한 약수의 합과 같은 양의 정수를 말한다.
2.20 다음은 Mini Language(by Edgar W. Dijkstra)의 문장에 해당하는 핵심 문법이다. 500 이하의 완전수를 구하는 프로그램을 작성하시오.

본문내용

2.1 다음 괄호에 알맞은 말을 쓰시오.
⑴ u와 v가 스트링일 때 |uv| = ( |u| + |v| )이다.
⑵ ωR은 스트링 ω의 ( 역순 )인 스트링을 나타낸다.
⑶ 알파벳 T에 대하여 언어 L은 ( T* )의 부분 집합이다.
⑷ 무한 언어를 유한 표현으로 나타내는 방법에는 세 가지가 있는데, ① 집합으로 조건 제시법, ② 언어 생성 시스템인 문법, ③ 언어의 ( 인식기 ) 등이다.
⑸ ( nonterminal 심벌 )은 문법에서 스트링을 생성하는데 사용되는 중간 과정의 심벌로 언어의 구조를 정의하는데 사용된다.
⑹ terminal 심벌과 nonterminal 심벌을 합해서 ( grammar symbol / 문법심볼 )이라하며 보통 V(vocabulary)로 나타낸다.
⑺ 생성 규칙의 형태가 A → αAβ 와 같은 생성 규칙을 ( 유도과정에서 대치할 수 있다 )라 부른다.
⑻ 형식 언어 이론에서 주로 사용하는 증명 방법에는 ( 귀납 증명법 )과 모순 증명법이 있다.
⑼ 문법을 생성 규칙에 따라 4가지로 분류한 사람은 ( Noam Chomsky )이다.
⑽ ( 유한 ) 언어란 그 언어에 속하는 스트링을 일정한 순서로 열거할 수 있는 알고리즘을 갖는 언어를 말한다.
⑾ type 0 언어를 인식할 수 있는 인식기는 ( Turing Machine )이다.
⑿ 회문 언어(palindromic language)의 형태는 ( ωωR )이다.

참고 자료

컴파일러 입문