FOLLOW follow 연산도 first와 마찬가지로 여러가지 룰이 적용된다. 먼저 정의이자 룰은, 1. FOLLOW란 해당 터미널/논터미널 바로 뒤에 따라오는 요소를 말한다. first는 해당 논터미널이 전개되었을때 가장 앞에 오는 요소라면, follow는 해당 논터미널 뒤에 가장 근접한 요소를 찾는다. S -> aAtB 일때, A의 follow는 t가 되는것이다. 2. S -> AB에서, B가 epsilon이 아닐때 First(B)는 Follow(A)와 같다. 이는 AB가 있을때 A의 Follow는 B의 가장 앞쪽과 같기 때문에 이가 성립된다 3. S -> aB에서, Follow(B)는 Follow(S)와 같다. B뒤에 뭐가 없는 상황일때, S의 마지막과 B의 마지막이 동일하기 때문에 부분집합으로 ..

LL Parsing은 Left to Right 왼쪽에서 부터 오른쪽으로 스캔한다는 의미의 L과 Left-most derivation의 L을 합쳐 LL Parsing 이라고 한다. LL 파싱에는 FIRST와 FOLLOW라는 연산자가 있는데, 이번엔 LL파싱을 알기 전 알아야 할 정의와 FIRST연산에 대한 개념을 정리 할 것이다. Nullable Set nullable set은 epsilon을 통해 null 이 될 수 있는 집합을 말한다. B -> epsilon 은 nullable set이며, S -> aBA | BB | ABc와 같은 경우도 B가 epsilon이기 때문에 B가 둘다 epsilon일 수 있어서 Nullable Set으로 판정된다. 한가지의 경우라도 Null이 나올 수 있으면 Nullable..

Bottom-up Parsing은 string 에서 식을 조합하여 스타팅 포인트로 가는 방법이다. S -> aAcBe A -> Ab A -> b B -> d 이러한 식이 있고, abbcde 라는 string 이 주어졌을때, 치환하면서 스타팅 포인트로 갈 수 있다. 먼저 b를 non-terminal A로 치환하면, aAbcde가 된다. 여기서 Ab를 A로 치환하면 aAcde가 되고, d를 B로 치환하면 aAcBe가 된다. 이는 스타팅 포인트 이므로 결론에 도달하였으니 올바르게 선언된 string이라고 볼 수 있다. Shift-Reduce 개념 E -> E + T E -> T T -> T * F T -> F F -> a 이 식의 + *는 터미널의 이름일 뿐이고, 연산자가 아니다. SHIFT는 왼쪽부터 Syn..

Indirect Left-Recursion이란 간접적으로 Left-Recursion을 만들어 무한루프에 빠지게 만드는 상황을 말한다. S -> Aa|b A -> Ac|Sd|e 이와 같은 식이 있을 때, S가 A를 가리키고 진행중인데 A가 다시 S를 호출하는 상황이 나오게 된다. 이렇게 되면 무한루프에 빠질 수 있게되고 top-down에서 나올 수 없는 역방향 참조가 나타난다. 그리고, A -> Ac에서 Direct Left-Recursion이 나타나고 있다. Indirect Left-Recursion 제거 위 식 A -> Sd 부분을 치환하여 A -> Aad|bd로 바꾼다. S 가 Aa|b 이므로 치환법칙을 이용한 것이다. 이렇게 되면 A -> Ac | Aad | bd | e 가 되고 Direct Lef..

탑다운 파싱을 하다보면 Left-Recursion이라는 문제가 생길 수 있다. Left-Recirsion이란, A -> Ab와 같은 식에서 점진적으로 진행을 할때, b가 나올때 까지 계속 포인터가 진행하게 되어 무한 루프에 빠질 수 있는 위험을 말한다. 그래서 탑다운 파싱을 쓰기 위해서는 Left-Recursion을 제거해야만 하는데 이를 피할 수 있는 방식이 Left-Recursion을 Right-Recursion으로 바꾸어 검증 가능하도록 만드는 것이다. Left-Recursion 변환 A -> Aa | b 가 있다. 이 식은 최종적으로 ba*를 만들지만 A 가 Aa를 만드므로 A를 검사하지 못해 무한 루프가 돈다. 이를 Right Recursion으로 변환하면 A -> bB B -> aB 이렇게 된..

저번에 알아봤던 탑다운 파싱에 대해 자세히 알아보자 탑다운 형식에서 만들어진 파싱 트리는 스타팅 노드에서 밑으로 내려가는데, 어휘가 서술 가능할 경우 그냥 내려가면 끝이지만, 불가능하게 노드가 끝날 경우 되는 경우를 찾기 위하여 다시 윗 노드로 올라가야 하는데 이를 백트래킹이라고 한다. 이 백트래킹은 중복되고 시간이 오래걸리기 때문에 최소화 하는 방법을 알아야 한다. S -> aAd S -> aB A -> b A -> c B -> ccd 이와 같은 식이 주어졌다고 했을 때, input : accd가 올바른 구문인지 검증을 top-down 방식으로 진행해보자 1. S -> aAd pointer : (a)ccd aAd에서, 포인터인 a가 적절한지 검사한다. 일단 첫 a가 동일하므로 a까지는 적합한 문구라고 ..