구문분석

<구문분석의 종류> 

모든 프로그래밍 언어는 프로그램이 잘 완성될 수 있는 구문구조를 묘사하는 규칙이 있음. 
ex) 파스칼 
구문구조: 블록 <- 문장 <- 식 <- 토큰; 
이러한 구문구조가 규칙에 맞는지 검사하는 것을 구문분석(syntax analysis) or 파싱(parsing)이라고 함. 
즉) 구문분석은 문장 w를 입력받아 w가 정의된 문법의 문장이면 w에 대한 파스트리를 생성하고 w가 정의된 문법의 문장이 아니면 오류메세지를 냄. 


구문구조 규칙을 검사하는 일을 
구문분석기가 함. 

구문분석의 출력으로 생성되는 트리는 유도트리(derivation tree) 와 같은 모양을 갖음. 
-> 유도과정을 나타낼 때는 유도트리 
-> 구문분석기에 의해 생성될 때는 파스트리 라고 부름. 

파스트리를 어떤 순서로 만드냐에 따라 크게 top-down과 bottom-up 방식이 있음. 

top-down: 루트노드에서 시작해 터미널 노드로 만들어 가는 과정 / 시작기호에서 출발해 문법규칙을 적용해 유도에 의한 주어진 문자열을 찾아가는 방법/ 좌단유도

bottom-up: 터미널 노드에서 루트노드로 만들어 나감 / 문자열에서 reduce 에 의해 시작기호를 찾아가는 방법 / 우단유도

 

 

전이행렬로 표현된 파싱표를 참고해 연산자순위에 따른 구문분석 방법을 지원했으나 일반적인 프로그램을 전부 지원할 수 없는 한계에 봉착해서 
단순순위, 확장순위, 한정순위, 혼합순위, LR(k)문법.. 제시됨. (현재는 LR(1)이 실용화됨) ( <- 모두 bottom-up방법)

 

recursive-decent 구문분석 방법은 재귀적 프로시저를 활용하며 top-down 방식임. -> backtracking 문제가 있음. 그래서 LL(k)문법을 사용하게 됨. 

---

<bottom-up 구문분석> 

정의 5-1 요약 
S-> aAc -> abc 로 유도될 경우, b가 A로 대체되는데 이를 reduce 된다고 함. 그리고 이 b를 문장형태 abc의 handle 이라고 함. 한 문장형태에서 reduce 되는 부분을 
handle 이라고 함. 

정의 5-2 요약 
S -> r1 -> r2 -> r3 = w  로 우단유도될 경우, 예를 들어 각 문장 형태 중 r3 에서 r2로 handle을 찾아 reduce 되는 과정을 handle pruning 이라고 함. 


정의된 문법이 모호하지 않으면 모든 우문장 형태에 대해 
1) 단지 한 개의 handle만 존재하고 
2) 이 handle에 적용한 생성규칙이 유일하면 
주어진 문자열을 결정적으로 구문분석할 수 있음을 의미 

---

  
<Shift-reduce 구문분석> 

Shift-reduce 구문분석 방법은 bottom-up 구분분석 방법으로 스택과 버퍼를 이용해 구현함. 
스택은 핸들을 찾을 때까지 현재 입력기호를 유지하고 입력버퍼는 주어진 문자열을 간직함. 

입력버퍼)(+$)
스택(+$)
구동프로그램(+파싱표) - > 출력 



일반적으로 $를 사용해 스택의 바닥(bottom)과 버퍼에서 입력의 끝을 표시함. 그리고 입력문자열을 w라고 하면

초기상태는 
스택 $
입력버퍼 w$

이고 입력버퍼에서 스택으로 입력문자열의 부분인 입력기호를 옮기는 것으로 작동되며, 이를 shift라고 함. shift를 하다가 handle이 발견되면 handle에 해당되는 문자열이 생성규칙의 오른쪽에 있는 것을 찾아서 왼쪽에 있는 기호로 reduece 함. 이런 작업을 반복함 .

이런 작업 중 handle이 발견 안되거나 
입력버퍼가 비어 있는데도 작업의 결과로 시작기호가 나타나지 않으면 오류 메시지(error message)를 띄움. 
or
시작기호가 나타나면 구문분석을 멈추고 구문분석에 의해 주어진 입력문자열은 주어진 문법에 의해 받아들여질 수 있음을 나타냄(accept) 
-> 이렇게 shift와 reduce 가 연속으로 이러우져서 shift-reduce 구문분석이라고 함. 

shift-reduce 구문분석기는 shift, reduce, accept, error 네 가지 행동을 취함. 
shift: 입력기호를 스택의 top에 옮기는 것, 이것은 top에 handle이 나타낼 때까지 반복함. 
reduce: handle이 스택의 top에 나타나면, 스택의 top이 handle의 오른쪽 끝이 되고, handle의 왼쪽 끝을 찾아서 완전한 handle을 찾은 다음, handle에 해당되는 생성규칙의 왼쪽에 있는 기호로 대체하는 것을 의미함. 
accept: 주어진 문자열이 주어진 문법에 맞는 문장임을 나타냄 
error: 현재 보고 있는 입력기호가 그 상태에서 나타낼 수 없기 때문에 틀린 문장임을 나타냄. 

 

문제점

handle을 어떻게 찾고, 
생성규칙이 여러개 존재하면 어떤 걸 적용할 것인가에 대한 문제점이 있음 
-> 이러한 문제점을 해결하기 위해 순위문법이 등장함. 

순위문법은 handle을 생성규칙의 문법기호 상호 간에 순위관계(precedence relation)에 의해서 찾는 방법
그 중 순위관계  > = < (표시에서. 생략) 세 관계로 표시되며, handle은 <와 > 사이에 있게 됨. .. 

 

 

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