구문분석(~단순순위 구문분석까지)

구문분석의 종류 

 

블록은 문장들로, 

문장은 식들로

식은 토큰들로 만들어짐 

 

구문구조가 규칙에 잘 맞는지, 맞지 않는지를 검사하는 것을 구문분석 혹은 파싱이라고 함. 

-> 문장 w를 입력받았는데 잘 정의된 문장이라면 파스트리를 생성하고 아니라면 오류메세지를 냄. 

 

이런 일을 '구문분석기' 라는 도구가 담당함. 

유도트리와 모양은 같지만 구문분석기에 의해 생성되는 '파스트리'

 

top-down 방식(좌단유도)과 bottom-up 방식(우단유도-reduce활용)이 있음. 

 

FORTRAN 컴파일러에서 괄호를 쳐서 우선처리 하던 방식에서 좌에서 우로 한 번에 처리하는 방식이 만들어짐. 

 

좌->우 처리방식은 산술식을 좌에서 검사하면서 먼저처리하면 안되는 것은 일시적으로 스택에 쌓아두고, 다음에 읽어들인 연산자와 스택의 TOP에 있는 연산자의 비교에 의해 다음 동작을 결정함. 스택에 있는 연산자와 읽어들인 연산자의 조합에 대해 행렬을 만들어 표현해서 '전이행렬'을 만듦. 이것은 '파싱표'를 의미함.  이러한 방법을 연산자 순위에 따른 구문분석 방법이라 하고 이런 문법을 연산자순위 문법이라고 함. 

 

연산자 순위문법은 보통의 산술식은 표현할 수 있으나 일반적인 프로그램 언어를 다 표현 못함. 

-> 넓은 표현능력을 위해 : 단순순위, 확장순위, 한정순위, 혼합순위, LR(k) 문법들이 제시됨. ex) 현재 실용화된 LR(1)이 있음. 

위의 모든 표현은 bottom-up 방식임. 그 외 top-down 으로는 재귀적 프로시저를 쓰는 recursice-descent 구문분석 방법이 있으나 backbreaking 문제가 있어서 LL(k) 문법이 등장함. 

 

 

 

bottom-up 구문분석 

 

주어진 문자열로 시작해서 reduce로 시작기호를 찾아가는 방법

 

reduce란 aAc -> aBc 로 유도될 때, B가 A로 되는 것임. 이때 B를 핸들이라고 함. 

 

그리고 

 

r1 -> r2 ... rk.. 일때 

1에서 k까지 가는 과정이 우단유도라면 

거꾸로 k에서 1로 가며 reduce를 하는 과정을 handle pruning 이라고 함. 

-> 정의된 문법이 모호하지 않다면 -> 우문장 형태에 대해 단지 하나의 핸들만 있고 && 핸들에 대한 생성규칙이 유일하면

-> 문자열을 결정적으로 구문분석할 수 있다.

 

 

 

 

shift-reduce 구문분석 

-스택/버퍼로 구성됨.

-스택은 핸들을 찾을 때까지 현재 입력기호를 유지하고, 버퍼는 입력된 문자열을 간직함. 

 

- $로 스택의 바닥과 입력의 끝을 표시함. 

 

반복함. 

{

-버퍼의 입력기호를 하나씩 스택으로 옮김 (shift)

-shift 하다가 핸들이 발견되면 핸들에 해당되는 문자열이 생성규칙의 오른쪽에 있는 것을 찾아서 왼쪽 기호로 옮김 (reduece) 

}

-> 핸들이 발견 안되거나 || 입력버퍼가 비어 있는데도 시작기호가 나타나지 않으면 -> 오류메세지 냄

-> 시작기호가 나타나면 구문분석을 멈추고 맞는 문장이라고 평가하고 accept 함. 

 

shift-reduce 구문분석의 문제점 

핸들이 될 수 있는 기호들을 보고서 규칙에 따른 핸들인지 핸들일수도 있으나 규칙에서 벗어난 것인지 애매모호한 문제가 있음. 

-> 핸들을 어떻게 찾을 것인가 : 순위문법 등장 < = > 

 

 

 

 

여러가지 순위문법과 용어 정의 

 

순위문법 = { 연산자순위 문법, 단순순위 문법, 확장순위 문법, 한정순위 문법, 혼합순위 문법 등 .. } 

- 연산자 순위문법에는 앱실론 생성규칙을 갖지 않고, 생성규칙의 오른쪽에 두 개 이상의 논터미널이 연속해서 나올 수 없음.

ex) EE(x), E+E(o)

 

 

아래 표는 정의를 이해하지 않고, 그냥 써봄(이해하면 수정예정 

정의	내용
5-4	연산자 문법에서 연산자순위 관계 =, <, > 관계에서 reduce 되는 순서를 정함. (예시를 봐야함)
5-5	연산자순위 문법은 연산자 문법이면서 두 개 터미널 기호 사이에 많아야 한 개의 연산자순위 관계를 갖는 것이고, 이 문법에 정의된 언어를 연산자순위 언어라고 함.
5-6	Wirth-Weber 순위관계 (예시참고)
5-7	단순순위 문법 = 순위문법,  1) 앱실론 생성규칙이 없음 2) 오른쪽 부분이 같은 생성규칙은 없음  3) 기호 사이에 많아야 한 개의 Wirth-Weber 순위관계를 가짐.
5-8	두 개의 문자열을 알파와 베타라고 하면 두 문자열 사이에 확장순위 관계가 정의됨.
5-9	확장순위 문법 = (m,n) 순위문법  1) 앱실론 생성규칙을 갖지 않음. 2) 오른쪽 부분이 같은 생성규칙은 존재 않음.  3) |x| = m, |y| = n인, 두 문자열 x,y 사이에 많아야 한 개의 확장순위 관계를 가짐.
5-10	이슈비아와 모스가 Wirth-Weber 순위관계 대신 스택 안에서 패턴매칭을 이용해 handle의 head를 찾을 수 있는 한정순위 관계를 제시함.  한정순위 문법은  1) 앱실론 생성규칙을 갖지 않음. 2) 오른쪽 부분이 같은 생성규칙은 존재 않음.  3) 단순순위 문법처럼 기호 사이에 많아야 한 개의 Wirth-Weber 순위관계를 자김. 단 > 관계만 가짐. 한정순위 문법은 > 관계에 따라 핸들의 테일을 찾고 핸들의 해드를 찾기 위해서 생성규칙의 오른쪽 부분을 이용함.
5-11	혼합순위 문법에는 -오른쪽 부분이 있어도 됨. (한정순위문법 과 달리) -핸들을 찾기 위해 한정순위 문법처럼 핸들의 tail을 먼저 찾고, 생성규칙 중에서 오른쪽 부분이 같은 것이 존재하면 생성규칙을 유일하게 선택하기 위해서 이제까지 본 입력 문자열의 local context를 이용함.
5-12	FIRST 는 문자열로부터 유도되어 첫 번째로 나타날 수 있는 터미널 기호들의 집합
5-13	논터미널 기호가 앱실론을 유도할 수 있으면 그 기호를 nullable 하다고 한다.  문자열의 FRIST는 왼쪽기호로부터 유도되는 터미널 기호를 찾는 과정으로 첫 번째 기호가 nullable 하면 그다음 기호의 FIRST도 이 문자열의 FIRST에 속한다.
5-14	Ring sum (+)는  앱실론 is not beloing to A 이면 A(+)B = A 이고  앱실론 is belong to A 이면 A(+)B = (A -{앱실론} ) U B 이다.  FIRST 구할 때 씀.
5-15	FIRST(A1,A2,A3..) =FIRST(A1)(+)FIRST(A2)(+)FIRST(A3)... FIRST 구할 때 씀.

 

 

왜 FIRST와 FOLLOW를 찾아야 하는가? 

 

 

FIRST(X)를 찾는 법 

1. 만일 X가 하나의 터미널이면 {X}는 FIRST (X)에 속한다. 
2. 만일 X가 하나의 논터미널이면 X -> ab의 생성규칙이 존재하면, 터미널 기호인 {a}는 FIRST(X)에 속한다.
   또한 X -> 앱실론의 생성규칙이 존재하면 {앱실론} 도 FIRST(X)에 속한다. 
3. 만일 X ->Y1Y2Y3Y4...의 생성규칙이 존재하면, 
   FIRST(X)=FIRST(X) U FIRST(Y1Y2Y3Y4..)임. 

예시는 p177 ~p178 에 자세히 나옴. 

 

<요령>

문법규칙의 왼쪽부분 기호를 취해서 유도되는 오른쪽 부분의 기호 중에 제일 앞에 있는 기호에 터미널 기호가  있으면

이 터미널 기호들이 FIRST가 됨 혹은 앱실론도 있으면 FIRST가 됨.  

 

문법규칙의 왼쪽부분 기호를 취해서 유도되는 기호에 터미널 기호가 없으면 좌단유도를 해서 왼쪽에 터미널 기호가 보이면 그게 FIRST가 됨. 

 

FOLLOW는 오른쪽 부분을 보고서 기호 뒤에 있는 부분을 보고 계산을 했는데, FIRST는 다름.  

 

 

5-16	문법 G가 context-free 문법일 때, 논터미널 A의 FOLLOW(A)는 어떤 문장형태에서 S -> aAbCd 일때 논터미널 A 기호 다음에 오는 터미널 기호들의 집합..

 

 

FOLLOW(A)를 찾는 법 

1. 만일 A가 시작기호이면 $는 FOLLOW(A)에 속한다. 
2. B-> aAc, c != 앱실론인 생성규칙이 존재하면, A의 FOLLOW에 앱실론을 제외한 FIRST(c)를 첨가한다.  여기서 앱실론은 뺀다.
3. B -> aA 이거나 B -> aAb에서 b -*- > 앱실론이면, B의 FOLLOW 전체를 A의  FOLLOW에 첨가한다. 

 

 p179~180 에 자세히 나옴. 

 

<요령>

 

문법규칙에서 오른쪽에 있는 기호를 취해서 그 뒤를 보고 판단한다. 만약 뒤에 앱실론이 있거나 아무것도 없으면 왼쪽부분 기호의 FOLLOW는 원래 취하고자 하는 기호의 FOLLOW에 모두 속한다. 

 

문법규칙에서 오른쪽에 있는 기호를 취해서 그 뒤를 보고 판단할 때, 만약 뒤에 터미널 기호가 있으면 그게 FOLLOW다. 

 

문법규칙에서 오른쪽에 있는 기호를 취해서 그 뒤를 보고 판단할 때, 만약 뒤에 논 터미널 기호가 있으며 그 논터미널 기호의 FIRST를 취한다. 그리고 그렇게 구한 FIRST는 원래 취하고자 하는 기호의 FOLLOW에 모두 속한다. 

 

 

FIRST나 FOLLOW 모두 앱실론으로 공식 안에 원래 보이는 공식의 모양새 외에 다른 모양새가 보이면 모두 구한다. 

보통 원래 앞서 구한 FOLLOW를 이후의 FOLLOW가 포함하는 경우가 있기 때문에 문제를 풀 때는 순차적으로 잘 적고 풀면 된다.  FIRST는 앱실론을 포함할 수 있고, FOLLOW는 $ 를 포함할 수 있다. 

 

---

 

단순순위 구문분석 

 

논터미널과 터미널 

논터미널과 논터미널

사이에 순위관계 부여해서 구문분석이 이뤄지게 함. 

-> 

단순순위 파싱표 

단순순위 함수 

 

 

출처: 방송대 컴파일러 구성