프로그래밍 언어 개념 연습문제 5장

01. 다음 약어에 대한 원어를 쓰시오.
(1) PGS
(2) YACC
(3) PQCC, TCOL
(4) ACK, EM
(5) JIT

02. 컴파일러의 일반적인 구조를 어휘 분석기, 구문 분석기, 중간 언어 생성기, 코드 최적화기, 그리고 목적 코드 생성기로 나누어 설명하고 특히, 각 단계의 입력과 출력을 설명하시오.

03. 코드 최적화는 관점에 따라 지역 최적화와 전역 최적화로 구분할 수 있다. 지역 최적화(핍홀 최적화)에 의해 얻을 수 있는 효과를 열거하시오.

04. 렉스와 YACC의 기능을 간단히 설명하시오. 그리고 렉스와 YACC를 이용하여 컴파일러의 전단부를 구현하는 방법을 설명하시오.

05. 컴파일 과정을 어휘 분석, 구문 분석, 중간 코드 생성, 코드 최적화, 목적 코드 생성 단계로 나누어 설명하고 각 단계를 자동적으로 구성하기 위한 컴파일러 제작 도구에 관하여 논하시오.

 

06. 다음 괄호에 알맞은 용어를 쓰시오.
(1) 어휘 분석기를 간단히 (    ) 또는 lexer라 부른다.
(2) 특수 형태의 토큰에는 keyword, operator symbol, 그리고 (    )가 있다.
(3) 일반 형태(general form)의 토큰은 프로그래머가 프로그램을 작성할 때 사용하는 명칭과 상수들이며 그 구조는 ( )에 의해 결정된다.
(4) 토큰들은 효율적인 처리를 위해서 고유의 내부번호를 갖는데 이것을 (    )라 부른다.
(5) 스캐너가 파서에게 넘겨주는 토큰의 정보는 일반적으로 토큰 번호와 (    )이다.
(6) 어휘 분석 과정에서 심벌 테이블을 운영하는 경우에, 명칭에 대한 토큰 값으로 스트링 값 대신에 그에 해당하는 심벌 테이블의 (    )를 사용하여 구문 분석기에 전달할 수 있다.
(7) 구현상으로 스캐너는 파서가 토큰이 필요할 때 호출하는 (    )이다.

(8) 컴파일러를 위한 어휘 분석기는 주어진 입력을 (    ) 내에 처리해야 하기 때문에 반드시 결정적 유한 오토마타로 구현해야 한다.
(9) 문법 표현으로부터 PGS가 terminal 심벌을 가려내 주고 그 내부 번호를 지정해준다. 이 내부 번호가 토큰 번호이며 (    )과 밀접한 관계를 갖고 있다.

(10) 어휘 분석기를 작성하는 방법은 크게 두 가지로 나눌 수 있다. 범용 프로그래밍 언어를 사용하여 작성하거나 또는 (    )로부터 얻을 수 있다.
(11) 읽어들인 문자가 더 이상 그 토큰에 속하지 않는 경우 다음 번의 토큰을 인식할 때 다시 처리되기 위하여 입력으로 되돌려지는 것을 (    )라 말한다.
(12) 렉스의 입력은 세 부분으로 구성되는데 각 부분을 구분하는 구분자는 (    )이다.

(13) 렉스의 출력 파일 이름은 (    )이며, C 컴파일러를 불러 컴파일해야 한다.

(14) 렉스의 정규표현에서 문자들의 종류를 정의하는데 [와 ]를 사용한다. [] 내에 사용된 대부분의 연산자 문자는 의미를 상실하며 단지 ( ). ^. ₩만이 특수한 의미를 가진다.
(15) 렉스 입력에서, 파일의 끝(end of file)을 만났을 때 부르는 함수는 (    ) 이며 일반적으로 이는 사용자가 제공해야 한다.

07. 다음을 간략히 설명하시오.
(1) 스캐너(scanner)와 파서(parser)의 관계를 그림으로 설명하시오.

(2) 스캐너를 작성하는 두 가지 방법을 비교 설명하시오.

08. 다음과 같은 조건을 만족하는 정수 상수의 형태를 상태 전이도로 고안하시오. 그리고 정규 표현을 구하여 확인하시오.
(1) 정수 상수의 종류는 10진수, 8진수, 2진수, 16진수로 구분된다.
(2) 10진수는 0이 아닌 수로 시작하여 decimal digit이 반복되는 형태이다.

(3) 8진수는 0으로 시작하여 octal digit이 반복하여 나오는 형태이다.
(4) 2진수는 OB로 시작하여 binary digit이 반복하여 나오는 형태이다.
(5) 16진수는 0X로 시작하여 hexa-digit이 반복하여 나오는 형태이다.

09. 고정 소수점(fixed-point) 형태의 실수가 0. 또는 .0 또는 0.0 등이 가능한 구조(단, (decimal point)만은 인식할 수 없음)일 때, 고정 소수점 실수를 인식하는
(1) 상태 전이도를 설계하고
(2) 정규 표현을 구하여 확인하시오.

 

10. 다음 괄호에 알맞은 말을 쓰시오.
(1) 문법적인 검사를 행하는 syntax analyzer를 간단히 (    )라 부른다.

(2) 구문 분석기의 출력은 파스, 파스 트리, 또는 (    )가 될 수 있다.
(3) 구문 분석기의 출력인 구문 분석 정보는 (    )의 입력이 된다.

(4) Top-down 방법으로 구문 분석을 수행하는 구문 분석기의 종류에는 recursive-descent 파서와 (    )가 있으며 bottom-up 방법으로 구문 분석을 수행하는 구문 분석기의 종류에는 precedence 파서와 (    )가 있다.
(5) 의미있는 생성규칙과 의미있는 terminal 심벌은 모두 (    )가 결정한다.

(6) 일반적인 top-down 방법에서, 생성규칙을 잘못 적용하여 그 생성규칙에서 보았던 스트링을 다시 입력으로 되돌려 주어진 스트링을 반복적으로 스캐닝(scanning) 하는 작업을 (    )이라 한다.
(7) 간접 left-recursion을 직접 left-recursion으로 바꿀 때 사용하는 문법 변환 기법(grammar transformation technique)은 (    )이다.
(8) Top-Down 구문 분석에서 정의된 문법이 어떤 조건을 만족하면 주어진 문장을 결정적으로 구문 분석할 수 있는데 이를 (    )조건이라 한다.
(9) SaB이고 A→ B의 생성규칙이 존재할 때, 문장 형태 aB에서 B를 A로대치하는 것을 (    )라고 말한다.
(10) Bottom-up 방법에서, reduce sequence는 (    )와 같다.

11. 다음을 간략하게 한 문장으로 답하시오.
(1) 컴파일러의 전단부인 scanner, parser, intermediate code generator의 관계를 그림으로 표현하고 특히 각 단계의 입출력을 설명하시오.
(2) 일반적인 top-down 파싱 방법에서 어느 경우에 틀린 문장으로 간주하는가?
(3) 주어진 스트링을 결정적으로 구문 분석할 수 있다는 의미는 무엇인가?

12. 다음 용어를 간단히 정의하시오.
(1) 축약(reduce)
(2) 핸들(handle)
(3) 반복 검조(backtracking)

13. 구문 분석에 관한 내용을 다음 순서에 의해 설명하시오.
(1) 구문 분석이란 무엇인가?
(2) 구문 분석 방법에는 어떤 종류가 있으며 각 방법의 특징은 무엇인가?

(3) 구문 분석 방법에 따른 파서는 어떤 종류가 있는가?

 

14. 다음 문법에 따라 스트링 ababccbaab 의 좌측 유도 과정을 보이고 좌파스를 구하시오

5. S → aAbA		2. S → aba
3. A → aAb		5. A → bBC		5. A → a
5. B → aBc		5. B → b
5. C → c

15. 다음과 같이 문법이 주어졌을 때, 스트링 (ata)*a의 우측 유도 과정을 보이고 우파
스를 구하시오.

5. E → T + E		2. E → T
3. T → F * T		5. T → F
5. F → (E)		5. F → a

16. 다음과 같이 문법과 스트링이 주어졌을 때, 일반적인 top-down 구문 분석 방법을 이용하여 구문 분석하는 과정을 보이시오.

   (1)	S → (L)	   ω:(a, (a, a))	   (2)	S → aSa	   ω:abba
	S → a					S → bsb
	L → S,L					S → ε
	L → S

17. 다음 괄호에 알맞은 용어를 쓰시오.
(1) 시작 심벌로부터 시작하여 주어진 스트링과 같은 스트링을 유도해 나가는 파싱 방법을 (    )이라 부른다.
(2) LL이란 용어에서 두 번째 L자는(    )의 약자이다.
(3) ring sum(⨁)의 정의에서 A가 ε을 포함하고 있다면, A ⨁ B는 (    )이다.
(4) FOLLOW 계산 과정에서 A → αB이거나 A→αBβ에서 FIRST(β)에 ε이 속하는 경우, (    )의 FOLLOW 전체를 (    )의 FOLLOW에 추가한다.

(5) 일련의 프로시저 호출로 파싱을 행하는 파서를(    )라 한다.
(6) Predictive 구문 분석이란 문법-의존적인 (    )과 문법-독립적인 (    )으로 나누어 처리하는 방법이다.
(7) Predictive 파서의 4가지 행동은 pop, (    ), accept, error 이다.

(8) Predictive 파싱 테이블의 크기는 (    )이 된다.

(9) 주어진 문법으로부터 predictive 파싱 테이블을 만들었을 때, 중복된 엔트리를 갖지 않으면 그 문법을(    ) 문법이라 말한다.
(10) 일반적으로 LL(k)가 strong LL(k)보다 (    )의 정보가 더 있기 때문에 더 큰 종류의 언어를 인식할 수 있다.

 

18. 다음 괄호에 알맞은 말을 쓰시오.
(1) LR은 입력 스트링을 왼쪽에서 오른쪽으로 읽어가며(Left to right scanning) 출력으로 (    )를 생성하기 때문에 붙여진 이름이다.
(2) LR 파싱 테이블은 2차원 배열로 가로는 문법 심벌로, 세로는 (    )들로 구성되어 있다.
(3) LR 파서의 4가지 행동은 (    )파서 (    )와 의미가 모두 같다.
(4) 한 상태에서 입력 심벌을 본 행동이 error라면 입력 스트링이 틀린 스트링이라는 의미이며 그에 따른 작업을 하게 된다. 일반적으로 (    )을 불러 처리한다.