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

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

어휘 분석을 마치고 구문 분석을 이야기한다. Syntax Analysis란? - 한줄 한줄 입력된 코드가 유효한지 검사한다. - 전체를 파싱하여 트리로 만들어 낸다. - 크게 탑다운 파싱과 바텀업 파싱으로 나뉜다. Syntax 1) S -> XY 2) X -> aX 3) X -> b 4) Y -> aY 5) Y -> c Top-down Parsing 탑다운 파싱은 루트 노드부터 터미널 노드까지 파싱하는 방법이다. 파싱 순서는 1 -> 2 -> 3 -> 4 -> 5 순으로 되며, 스타트 지점인 S 부터 하나씩 풀어 나간다. Bottom-up Parsing 바텀업은 터미널 노드로 부터 루트 노드까지 파싱하는 방법이다. 파싱 순서는 3 -> 2 -> 5 -> 4 -> 1 터미널인 a b a c로 부터 non-..

이번엔, analyzer를 통해 정제된 데이터중 ID를 Finite Automata로 변환해 보자. ID (변수명)은 첫번째가 letter이여야 하고 그 이후에는 Digit 또는 letter이여야 한다. ID to Automata 이를 오토마타로 바꾸면, 가 된다. 식으로 나타내기 위해 편의상 letter는 l로 digit은 d로 표기하도록 하자 S = lA A = lA + dA + epsilon 이 된다. A로 묶으면 A = (l + d)A + epsilon이 되고, 정리하면 A = (l + d)* 가 된다. A를 S식에 대입하면 최종으로 S = l(l + d)* 이 된다. 해석해보면 처음엔 letter, 그 이후로는 l 또는 d가 무작위로 나올 수 있다는 뜻이다. Integer to Automata ..