틀딱 답게 C로 작성했엉


https://ideone.com/9vceWI



렉서는 저번에 만들어두어서 

LALR 제네레이터 저번에 만든거 활용겸 해서

파서를 짜는데 

수제작 파서는 손이 너무 많이 간다 ㅠ


솔직히 json은 그냥 재귀하강 더 잘 맞는듯!


회사에서 짠 json라이브러리는 해시테이블, AVLtree , 인덱싱, 더블링크드리스트 까지 적용되어 있는데

파싱은 LL로 함


이거는 그냥 대충 링크드 리스트로 구조만 잡고 끝남 LALR 파서도 버거웠음


...


렉서 최적화는 

아래 링크 참고 많이 했엉

https://nothings.org/computer/lexing.html


요약을 하면 분기문을 최대한 줄이자임


텍스트 파싱할때 , 파싱과정보다. 토큰을 구해내는 스캔 과정이 더 부하가 많이 걸리니까

그쪽으로 최적화를 집중하는 느낌으로!

어떤 json 라이브러리는 SIMD까지 써서 개빠르더라고 ...


내가 최적화한 렉서는  do-while 문에서  분기가 while 조건 딱 하나밖에 없음

그러면 CPU가 분기예측을 항상 성공하고 마지막 탈출조건에서만 실패할테니까


최적화 하려고 적용한 리스트들

1. equal class 를 활용해서  0-9  같은문자가 한번 참조로  '숫자' 라는 하나의 클라스로 분류해낼수 있도록 사전테이블을 일단 둠

2. transition table 을 미리 다 만들어 놓고 상태이동만으로 토큰을 구함

3. 시작, 끝 포인터를 두고  상태에 따라서  시작포인터와, 끝 포인터를 증가시킬 플래그를 상태에 미리 저장

4. equal class 마저도 32비트 안에서 구역을 나누어 할당해서 , 상태에다가 어느부분을 읽어야할지 기록  

5. 시작 포인터를 증가시킬때는 0,1 플래그를 읽고 '길이' 만큼 증가시켜야하는데 

처음에는 곱셈으로 처리했다가. 곱셈도 무거운 연산이라서, 오버플로우랑 비트마스크를 활용함

s += (p - s) & (UINT_MAX + ((state>>9) & 0x1));



최적화 하느라고 코드를 보니까 너무 메모리 침범할 가능성이 많겠더라.. 

자꾸 보면볼수록 코드가 ㅄ같음 ㅠ