과제 3: 어휘/구문 분석기 (Lexer and Parser)

우리가 평소에 작성하는 소스코드(a = 3 + 5)는 컴퓨터 입장에서 보면 그저 무의미한 알파벳 문자들의 나열(String)일 뿐입니다. 어떻게 컴퓨터는 이것이 “덧셈 연산”이라는 의미를 지니고 있다는 것을 알아채는 걸까요?

이번 주차에는 컴파일러의 가장 첫 관문인 어휘 분석기(Lexer)와 구문 분석기(Parser)를 구현하여 문자열 상태의 코드를 논리적인 구조체로 탈바꿈 시킵니다!

1. 인터프리터 언어의 흐름

프로그래밍 언어의 실행 단계는 일반적으로 아래와 같은 선형적 구조를 거칩니다.

흐름도

Tokenizer (Lexer): 소스 코드를 제일 작은 의미 단위인 토큰(Token)으로 잘게 쪼깹니다. (예: 3 + 5 -> INT(3), PLUS, INT(5))
Parser: 쪼개진 1차원 배열 상태의 토큰들을 묶어, 나무 모양의 깊이가 있는 AST(추상 구문 트리) 구조로 재조립합니다.
Interpreter: AST를 밑에서부터 순회하며 실제 계산 연산을 수행합니다 (이번 과제 이후 HW5에서 다룹니다).

어휘 분석 단계(Lexical Analysis)에서는 굳이 복잡한 문법을 따지지 않고 오직 키워드만 찾습니다. OCaml의 ocamllex 툴을 사용하면 정규표현식(Regex)을 이용해 손쉽게 Lexer를 만들 수 있습니다!

우리가 만들 딥러닝 전용 언어(TensorLang)에서는 다차원 텐서를 만들기 위한 구조 표현과 신경망 레이어 키워드가 필요합니다.

let, in, tensor, linear, seq, forward, mse, train 과 같은 핵심 언어 키워드 (Keyword) 파싱
[, ], (, ), ;, , 등의 구두점 식별
문자열 내부를 유연하게 긁어오는 규칙 작성.

src/lexer.mll 내부에 비어있는 정규 표현식 규칙들을 정의하세요!

Lexer가 만든 INT(3) PLUS INT(5) 토큰이 의미가 맞는지(문법적인지) 검증하고 트리를(Tree) 만드는 작업입니다.

파서는 이것이 “무엇을 하는지”에만 관심이 있으며 코드가 예쁘게 적혔는지 띄어쓰기가 몇 개인지에는 큰 관심이 없습니다. 예를 들어 3 + 5 와 5 - 2는 각각 왼쪽과 오른쪽 그림과 같은 트리 형태로 변환됩니다.

`3 + 5` 의 추상 구문 트리 (AST)	`5 - 2` 의 추상 구문 트리 (AST)

저희는 Menhir 라는 파서 생성기(Parser Generator)를 사용해 src/parser.mly 파일에 Context-Free Grammar (CFG) 형태로 문장 생성 규칙(BNF 폼)을 명시합니다.

만약 let m = linear 2 4 in forward m x 와 같은 코드를 작성했다면: expr_list와 텐서 데이터 정의부 tensor [ ... ] 를 어떻게 재귀적으로 묶을지 정의해야 합니다.

TODO 구멍을 찾아 알맞은 정규식과 생성 규칙을 채워 넣으세요:

과제 폴더(전체 프로젝트)를 zip 파일로 압축하여 제출해 주시기 바랍니다. 또한, 터미널에서 dune test를 실행하여 모든 테스트가 통과한 결과 화면을 캡쳐하여 함께 첨부해 주세요.