예전에 컴파일러 수업들으면서 만들었던거

예제: https://gall.dcinside.com/board/view/?id=programming&no=1355550

정규표현식 NFA, DFA 시각화 도구

[],|,+,?,*,() 연산 지원

a|(a|b)? 와 같이 or 중첩시 a|((a|b)?) 로 바꿔야 동작함



스캐너 제너레이터와 스캐너

왼쪽 상단 Lexer Definition에서 규칙 추가가능

제일 윗 줄이 가장 높은 우선순위 가짐

왼쪽 하단에 텍스트 넣으면 시험할 수 있음






SLR, LALF from LR(0), LALR from LR(1), LR(1) 파서 제너레이터, Shift-Reduce Parser 지원

bison 문법 일부 지원



LR(1) 와 LALR 비교



파스트리 출력 기능



간단한 L-Attributed 기능


디펜던시: https://graphviz.gitlab.io/_pages/Download/Download_windows.html

소스코드: https://github.com/koikatsu-user/65d4bx96c5v4b9s87gdf9nbs87gnf98sg

바이너리: https://github.com/koikatsu-user/65d4bx96c5v4b9s87gdf9nbs87gnf98sg/releases/download/z645cxv065z4xc6v54a65s4d0vas/4dfg5sdf4gs0df65b4xz65b0.zip

기반 코드로 만든 json parser: https://github.com/xxx1720/json-parser


여기다가는 올린적 없어서 생각난김에 올려봄

오래전에 만든거긴하지만

틈날 때마다 오류들 수정 많이해서 regex 괄호버그 빼고는 다른 버그는 없을꺼임 (조만간 고칠꺼)

심심할때 써보센










소스코드분석

코드 전부 다 이해하려면 stack, queue, automata, bfs, dfs, scc 정도는 알아야함

1. 정규표현식 분석기


cc/ScannerGenerator.cs에있는 SimpleRegex 클래스

정규표현식 스트링을 DFA로 바꿔줌

build함수는 make_nfa -> opt_nfa -> nfa2dfa -> opt_dfa 순서대로 호출함

make_nfa: 정규표현식 패턴을 NFA로 바꿈

opt_nfa: 엡실론들을 가능한 삭제해버리는 엡실론 클로져 연산 수행

nfa2dfa: dfa transition 테이블을 이용해 NFA 그래프를 DFA로 바꿈 (그냥 구글에 nfa2dfa치면나오는 알고리즘이랑 똑같은거 씀

opt_dfa: hopcroft알고리즘으로 DFA 축약


이론이나 구현에 관한 자세한건 소스코드랑

https://talkingaboutme.tistory.com/category/About%20Study/Compiler?page=2 참고


2. 스캐너 제너레이터

SimpleRegex가 만든 DFA를 이용해서 스캐너를 만들어냄

드래곤책 3.8.3. DFA's for Lexical Analyzers 파트랑 Engineering A compiler 2.5 Scanner Implementaion 참고해서 만듬

둘 다 설명 빈약한테 서로 빈약한곳 알려줘서 둘 다 읽어보면 만들 수 있을 꺼임

간단하게 설명하면 모든 DFA를 하나의 input state에 전부다 연결시키고 그걸 통채로 dfa로 바꿔버린다는 아이디어임

소스코드에 주석들 있으니깐 읽어보셈


3. 스캐너

스캐너 제너레이터에서 Generate후 CreateScannerInstance로 Scanner 클래스 인스턴스를 얻을 수 있음


4. 파서 제너레이터

소스코드는 cc/ParserGenerator.cs에 ParserGenerator 클래스에 있음

FIRST, FOLLOW, SLR, CLR, LR(1), LALR 관련 함수들이 있는 클래스임

Generate: SLR 파싱테이블을 만들어줌, Shift-Reduce Complict가 발생하면 오류남

GenerateLR1: LR(1) 파싱테이블을 만들어줌

GenerateLALR: 같은 LR(1) DFA 노드들을 합쳐서 lookahead를 계산해 LALR 파싱테이블을 만들어줌

GenerateLALR2: LR(0) 노드에서 lookahead를 채워서 LALR 파싱테이블을 만들어줌

Generate가 끝나면 CreateExtendedShiftReduceParserInstance로 파서 인스턴스를 만들 수 있음


4.1. SLR Generate

다른 Generate함수들이랑 다른점은 Shift Reduce Conflict를 해결하는 부분이 존재하지 않다는 거임

다른 Generate함수들은 SLR Generate의 전체를 전부다 사용하고 거기에 Shift Reduce Conflict를 해결하는 모듈을 붙이는 방식으로 개발됨

https://lesslate.github.io/compiler/SLR-%ED%8C%8C%EC%8B%B1-%ED%85%8C%EC%9D%B4%EB%B8%94-%EA%B5%AC%EC%84%B1-%EB%B0%A9%EB%B2%95/

이 방법이랑 완전히 같음. Action이랑 GOTO 테이블을 만들어냄


4.2. LR1 Generate

SLR에서 사용한 first_nonterminals와는 달리 first_with_lookahead라는 함수를 사용함

이 함수는 LR(0)의 State 아이템과 lookahead를 동시에 계산해줌


4.3. LALR Generate

LR1 Generate에서 Merge하는 부분을 추가한 것


4.4. LALR2 Generate

SLR에서 만든 LR(0) State아이템에 Lookahead를 추가해주는 방식

fill_lookahead가 핵심함수임


ㅇㅇ