컴파일러 — SLR Syntax Analyzer

개요

simplified Java의 Context-Free Grammar를 기반으로 한 Bottom-Up SLR 파서 구현
CFG를 설계하고, SLR 파싱 테이블을 구성하여 토큰 시퀀스의 문법적 유효성을 검사
입력이 유효하면 파스 트리를, 유효하지 않으면 에러 리포트를 출력

파일 구성

syntax_analyzer.py   # SLR 파서 메인 실행 파일
slr_table.json       # ACTION/GOTO 테이블 (파서가 참조)
test_OOO.txt         # 입력 테스트 txt
test_OOO_output.txt  # 각 테스트 실행 결과

실행 방법

Python 3 필요. syntax_analyzer.py와 slr_table.json은 반드시 같은 폴더에 존재

python3 syntax_analyzer.py <input_file>

예시:

python3 syntax_analyzer.py test_OOO.txt 

테스트케이스 txt 내부 형식

공백으로 구분된 터미널 토큰이 줄 단위로 작성되어 있습니다.

사용 가능한 터미널: vtype id semi assign literal character boolstr addsub multdiv lparen rparen lbrace rbrace comma if else while return class comp num

예시:

vtype id semi
vtype id assign num semi

출력 형식

Accept 시:

Result: ACCEPT

Parse Tree:
S'
  CODE
    VDECL
      ...

Reject 시:

Result: REJECT
Syntax error at line N: unexpected token 'X'. Expected one of: [...]

CFG 구성

CODE     → VDECL CODE | FDECL CODE | CDECL CODE | ε
VDECL    → vtype id semi | vtype ASSIGN semi
ASSIGN   → id assign RHS
RHS      → EXPR | literal | character | boolstr
EXPR     → EXPR addsub TERM | TERM
TERM     → TERM multdiv FACTOR | FACTOR
FACTOR   → lparen EXPR rparen | id | num
FDECL    → vtype id lparen ARG rparen lbrace BLOCK RETURN rbrace
ARG      → vtype id MOREARGS | ε
MOREARGS → comma vtype id MOREARGS | ε
BLOCK    → STMT BLOCK | ε
STMT     → VDECL | ASSIGN semi
         | if lparen COND rparen lbrace BLOCK rbrace ELSE
         | while lparen COND rparen lbrace BLOCK rbrace
COND     → COND comp BOOLVAL | BOOLVAL
BOOLVAL  → boolstr
ELSE     → else lbrace BLOCK rbrace | ε
RETURN   → return RHS semi
CDECL    → class id lbrace ODECL rbrace
ODECL    → VDECL ODECL | FDECL ODECL | ε

SLR 파싱 테이블

• 총 상태 수: 87
• 충돌: 없음 (conflict-free)
• 전체 테이블은 slr_table.json 참조