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의 마지막이 동일하기 때문에 부분집합으로 ..

드디어 컴파일러 개발 착공을 시작하게 되었다. 컴파일러 개발 언어는 제일 익숙한 c#으로 하기로 했다. 새로 만들 언어 이름은 nasigo-language, 유일하게 자신있는 요리이자 내가 좋아하는 음식이다. 첫번째로, 코드를 불러올 Parsing에 관한 라이브러리를 만들기로 하였다. Parsing Data라는 class를 통해 데이터를 주고 받도록 설계되어 있으며, 메서드 클래스와 데이터 타입 클래스로 나누어져 있다. Parsing Data는 String과 List를 통해 접근할 수 있으며, 추가는 클래스 내 Add 함수만을 통해 할 수 있다. Parser는 Nasigolang Main에서 Singleton을 통해 접근할 수 있고, 클라이언트 역할인 DoParse와 실제 구현부인 ParsingLine으..

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 이렇게 된..