2024-10-24 TIL 우테코 2주차 구현, 컴파일러 Syntax analysis

우테코 2주차 구현 시작

1차적으로 함수 구현 완료
✅ class로 구분하여 파일 작성
✅ 함수가 한가지 일만 하도록 구분
✅ 디버거를 통한 디버깅 
✅ 커밋메세지를 기능 구현에 따라 작성 완료
 
🚀 해야 할 일

• MCV 패턴 적용하기
• indent depth가 3이 안 넘는지 확인 후 리팩토링
• 테스트 도구를 사용하여 테스트해보기
• 조건 다시 확인 후 적용 했는지 보기

컴파일러

Lexical Analysis

"Dividing programs into tokens"
Specification: how to specify lexical patterns?

• RE(Regular Expression)
  • longest matching token is selected → highest priority

Recognition: how to recognize the specified patterns?

• DFA(Deterministic finite automata) - NFA(Non-deterministic finite automata) - table
• Accepting state, ε move

Automation: how to generate DFA from RE?

• Automatic generation tool (Lex)
  • Definition section
    • "%{", "%}" 사이에 변수 선언 또는 포함 등등 가능
    • sub-rule에 대한 이름 제공 - RE 여기
  • Rules section - lexical patterns 적기
  • User Func section 
• Thompson's construction (RE → NFA)
• Subset construction (NFA → DFA)
  • ε-closure는 해당 상황에서 ε 을 통해 갈 수 있는 곳
  • Δ(ε-closure, A)는 A를 통해 갈 수 있는 ε-clousure 
  • DFA optimization : non-accepting, accepting state로 나눠서 시작, 계속 set 안에서 서로 구분되면 나눔