skyjump's blog

일반적인 top-down을 사용하면 backtracking이 생길 경우 느리니까, backtracking하지 않도록 결정적인 파싱 방법이 필요. 그러한 파싱 방법을 LL 파싱.

FIRST
논터미널 A로 부터 유도되어 첫번째로 나타날 수 있는 터미널의 집합.

nullable
논터미널 A가 ε를 유도할 수 있으면 A를 nullable하다. 

FOLLOW
생성규칙이 ε을 유도할 수 있으면 FIRST만 가지고는 생성 규칙을 결정적으로 선택할 수 없다.
논터미널 A 다음에 나오는 심벌에 따라 어느 생성 규칙으로 유도할 것인가를 결정한다. 

LL 조건
논터미널을 대치하기 위한 생성 규칙을 결정적으로 선택하기 위한 조건.
한 논터미널에 2개 이상의 생성규칙이 있을 때,
각 생성규칙의 FIRST가 달라야 하고,
한 생성 규칙이 ε을 유도할 수 있으면, 그 생성규칙의 FOLLOW와 다른 생성규칙의 FIRST가 달라야 한다.

LL방법을 실제로 사용하는 구문분석기
1) Recursive-descent
논터미널에 대한 유도를 각 논터미널별로 구현되어 있는 함수 호출로 처리.
논터미널에 적용할 생성 규칙을 정하기 위해 Lookahead를 조사. Lookahead는 각 생성규칙에서 첫번째로 유도될 수 있는 터미널들의 집합.
2) Predictive 파서
Recursive-descent파서는 생성규칙이 바뀔 때마다 프로그램을 다시 고쳐야 하는 단점이 있다.
Predictive파서는 파싱테이블만 수정하면 된다.
스택의 top과 현재 입력 심벌이 같을 경우 pop, 
expand : 스택의 top이 논터미널일 경우 생성규칙으로 바꿔서 역순으로 넣는다.
accept : 스택의 top과 입력이 모두 $인 경우, 파싱 성공
error

구문 분석의 결과는 파스트리.
파스트리 만드는 순서
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할 때 서브트리를 만든다.