공부/컴파일러2011. 8. 22. 15:37


구문 분석의 결과는 파스트리.
파스트리 만드는 순서
1) top-down, 2) bottom-up
top-down은 시작 심벌로부터 생성 규칙을 적용하여 좌측 유도해 나가는 방법.
bottom-up은 주어진 스트링으로부터 시작 심벌로 축약되어 가는 과정. 우측 유도에서 적용된 생성 규칙 번호의 역순.

파스트리의 루트노드는 시작 심벌이고, 중간 노드는 비단말 심벌, 단말 노드는 단말 심벌.
top-down 방식은 루드노드부터 만들어 나가고, bottom-up 방식은 단말 노드부터 시작하여 서브트리를 만들어 나간다.

추상구문트리(Abstract Syntax Tree) : 파스 트리에서 꼭 필요한 의미 정보만을 갖는 트리.

Backtracking
top-down 시작 심벌로부터 좌측유도 하다가 생성 규칙이 잘못 적용되었으면 그 생성 규칙에서 보았던 스트링을 다시 입력으로 보내고 다른 생성 규칙을 적용하여 유도를 해본다.

top-down 할 때 left-recursion이 있으면 무한루프에 빠진다.

direct left-recursion 없애기.
A->Aα|β, it means A= βα*
it equals
A-> βA'
A' ->αA'|ε  

indirect left-recursion 없애기
direct left-recursion으로 만든다음 없앤다.
direct left-recursion으로 만드는 알고리즘 :
논터미널에 순서를 매기고
논터미널의 생성규칙에 앞선 논터미널이 있으면 앞선 논터미널의 생성규칙을 대입한다.  

left-factoring
같은 심벌들을 prefix로 갖는 두 개 이상의 생성 규칙이 있으면 어떤 생성 규칙을 적용해야 할지 결정 할 수 없다.
공통된 앞부분을 새로운 논터미날을 이용해서 표현한다.
A->αβ|αγ <=> A->α(β|γ) <=> A->αA', A'->β|γ

bottom-up의 reduce
구문 분석 중에 나타나는 문장 형태의 일부분이 정의된 생성 규칙의 rhs와 같을 때, 이 생성규칙의 lhs로 대체하는 것.
reduce되는 부분을 handle이라고 한다.

shift-reduce 구문 분석
bottom-up의 일종.
스택과 입력 버퍼가 있다. 스택에 handle을 찾을 때까지 문법 심벌들을 유지하고, 입력 버퍼는 주어진 스트링을 가지고 있다.
shift는 입력 심벌을 스택으로 이동하는 것. reduce는 스택 top의 핸들을 생성규칙으로 축약하는 것.
accept는 주어진 스트링이 문법적으로 맞다는 것.

트리생성
파싱하면서 트리 만들 수 있다.
시프트할때 단말 노드를 만들고 reduce할 때 서브트리를 만든다.

'공부 > 컴파일러' 카테고리의 다른 글

LR 구문 분석  (0) 2011.08.24
LL 구문 분석  (0) 2011.08.22
context-free grammar  (0) 2011.08.20
regular language  (0) 2011.08.20
formal language  (0) 2011.08.20


Posted by skyjumps