컴파일러6장연습문제

소개글

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

본문내용

간주한다.
(3) 주어진 스트링을 결정적으로 구문 분석할 수 있다는 의미는 무엇인가?
정의된 문법이 모호하지 않다면 모든 우 문장 형태에 대해 단지 한 개의 handle만이 존재하고 이 handle에 적용할 생성 규칙이 유일하면 주어진 스트링을 결정적으로 구문 분석할 수 있다는 것을 의미한다.
(4) Bottom-up 방법에서, AST를 구성하는 방법을 설명하시오.
의미있는 terminal을 shift 할 때 단말 노드를 만들고 의미있는 생성규칙으로 reduce할 때만 지금까지 만든 노드들을 한 데 묶어서 서브트리를 구성한다.
6.3 다음 용어를 간단히 정의하시오.
(1) 확장(expand)
시작 심벌로부터 주어진 스트링을 생성해 나가는 과정을 말함.
즉, A → αβ가 존재할 때, A → αX, X → β 혹은 A → Xβ, X → α로 변환하는 방법
(2) 축약(reduce)
주어진 스트링으로부터 시작 심벌로 도달해 가는 과정을 말함.
즉, S ⇒αβω이고 A → β의 생성규칙이 존재할 때, 문장 형태 αβω에서 β를 A로 대치하는 것.
(3) 핸들(handle)
S ⇒ αAω ⇒ αβω의 유도 과정이 있을 때, β를 문장 형태 αβω의 handle이라 함.
즉, 한 문장 형태에서 reduce 되는 부분을 말한다.
(4) 반복 검조(backtracking)
좌측 유도 과정에서 생성 규칙이 잘못 적용되었으면 그 생성 규칙에서 보았던 스트링을 다시 검조(scanning)하기 위하여 입력으로 보내고 다른 생성 규칙을 갖고 유도를 시도하는 과정을 말함.
6.4 구문 분석에 관한 내용을 다음 순서에 의해 설명하시오
(1) 구분 분석이란 무엇인가?
주어진 입력이 올바른 프로그램인가를 검사하고 다음 단계에서 필요한 정보를 구성하는 과정이다.
(2) 구문 분석 방법에는 어떤 종류가 있으며 각 방법의 특징은 무엇인가?
구문 분석 방법에는 top-down 방식과 bottom-up 방식이 있다. Top-down 방식은 루트 노드로부터 시작하여 단말 노드로 만들어 나가는 반면 bottom-up 방식은 단말 노드로부터 루트 노드를 향하여 위로 만들어 나간다. 이때 입력 스트링은 두 방식 다 한 번에 한 심벌씩 왼쪽부터 오른쪽으로 검조한다.
(3) 구문 분석 방법에 따른 파서는 어떤 종류가 있는가?
좌파스와 우파스 두 가지 종류가 있다.
6.5 다음 문법에 따라 스트링 ababccbaab 의 좌측 유도 과정을 보이고 좌파스를 구하시오.
1. S → aAbA 2. S → aba
3. A → aAb 4. A → bBC 5. A → a
6. B → aBc 7. B → b
8. C → c
S ⇒ aAbA ~ (1)
⇒ abBCbA ` (14)
⇒ abaBcCbA ` (146)
⇒ ababcCbA ~ (1467)
⇒ ababccbA ` (14678)
⇒ ababccbaAb ` (146783)
⇒ ababccbaab . (1467835)
∴ 좌파스 = 1 4 6 7 8 3 5
6.6 다음과 같이 문법이 주어졌을 때, 스트링 (a+a)*a의 우측 유도 과정을

키워드

컴파일러,   컴파일러6장,   컴파일러6장연습문제