ISPA가 문법 디버거와 오류 복구 기능을 갖춘 파서 생성기를 공개했다

ISPA는 문법을 정의하면 렉서와 파서를 미리 생성해 완전한 타입의 AST를 만드는 정적 파서·렉서 생성기다. C++23으로 새로 작성됐으며, 생성 결과물은 C++17을 대상으로 하고 Python 출력도 지원한다. 제작자는 벤치마크에서 ISPA가 ANTLR보다 약 12배 빠르다고 설명하지만, 비교 조건에 차이가 있고 flex + bison보다는 느리다고 밝힌다.

저장소와 위키에서 설치, 문법, 생성 API, 알고리즘, 복구, 외부 파서, 패키지, 디버깅 방법을 확인할 수 있다. 저장소에는 사용 데모 영상(usage.mp4)도 안내돼 있다.

생성 방식과 현재 지원 상태

ISPA는 문법을 생성 시점에 DFA 테이블과 일반 코드로 컴파일한다. 실행 중에 코드를 생성·해석·컴파일하지 않는다. 생성된 C++은 parser/stdlibs의 헤더와 core.cpp를 사용하고, Python은 ispa_std를 가져온다. 패키지 내보내기를 이용하면 이 파일들을 빌드 경로나 모듈 경로에 추가할 수 있다.

언어별 코드 생성은 언어에 독립적인 중간 표현인 LangAPI를 거친다. C++17과 Python 생성기가 구현돼 있으며 Python은 현재 LL 방식만 사용한다. 생성 API는 파싱 뒤 별도 처리나 콜백 없이 타입이 지정된 AST를 반환한다. 문법 규칙은 언어 구조를 기술하고 생성된 파서 코드와 연결된다. 점진 생성 기능은 바뀐 부분만 다시 생성하며, 문법 가져오기로 공유 문법을 구성하고 재빌드할 수 있다. 기능을 조건부로 켜는 모듈과 매개변수화 모듈은 로드맵에 남아 있다.

현재 상태는 다음과 같다.

• 컴파일러 프런트엔드와 백엔드는 구현됐으며 Windows와 Linux에서 빌드된다.
• 부트스트랩이 완료됐다. ISPA 자체 문법은 ISPA가 생성한 파서로 파싱하며, 이 파서가 기존 수기 파서를 완전히 대체했다.
• 렉서는 TDFA와 AST를 구성하는 토큰을 지원한다.
• LL 파서는 제품화 대상이며 개발과 테스트가 계속되고 있다. LR 계열 모드는 기능이 적고 실험 단계다. 자세한 내용은 LR 백엔드 상태를 참조한다.
• 점진 생성은 구현돼 변경된 부분만 다시 생성한다. C++17 출력도 구현돼 컴파일과 실행이 가능하다.
• Python 출력은 LL 생성에 구현돼 있으며, 생성 모듈은 대상 런타임의 ispa_std를 사용한다.
• 동적 정규식(이전 캡처의 역참조와 횟수)은 문법으로 읽을 수 있지만 아직 출력 코드로 변환되지 않는다.
• 문법 구문 오류에는 자동 LL 복구와 소스 진단을 제공하며, 구문 오류가 있으면 생성은 중단된다.

백엔드는 문법 구조와 AST 캡처를 C++ 또는 Python으로 변환한다. 고급 액션과 오류 복구 지원은 알고리즘에 따라 다르며, 상세 사항은 LR 백엔드 상태에 정리돼 있다.

생성 파서 디버깅

현재 생성기로 파서를 만들고 빌드한 뒤, 기존 실행 파일을 ispadbg로 실행한다.

./ispadbg --purpose matching --purpose ast -b grammar.isc:12 \

--record parser-trace.json -- ./my-parser input.txt

./ispadbg --replay parser-trace.json

그래픽 화면을 사용하려면 ./ispadbg-gui 또는 설치된 ispadbg-gui를 실행한다. 파서 프로그램을 선택하고 입력 문자열을 입력한 뒤 Run을 누른다. 기본적으로 입력은 examples/main.cpp와 같이 명령줄 인자 하나로 전달된다. 표준 입력을 읽는 파서는 Standard input을 선택한다. 실행을 멈췄을 때 Step, Next, Finish, Continue로 진행할 수 있다. 추적 행을 선택하면 펼칠 수 있는 트리에서 ctx와 AST 값을 비롯한 변수를 살펴볼 수 있다. Open trace와 Save trace는 ispadbg --replay, --record와 같은 JSON 형식을 사용한다. GUI는 Python의 Tkinter를 사용하며 데스크톱 디스플레이가 필요하다.

파서 생성 시 디버그 계측은 기본으로 켜져 있다. ispa에 --no-debug-instrumentation을 전달하면 생성 소스의 체크포인트, 스코프 이벤트, 값 직렬화를 제외한다. 명시적으로 켜려면 --debug-instrumentation을 전달한다.

목적 ID는 matching, failure, ast이며 기본값은 failure다. 디버거는 시작할 때 선택된 ID를 출력한다. 대화형 명령은 s(한 단계 실행), n(다음 단계), f(완료까지 실행), c(계속 실행), b file:line(중단점), p [name](값 확인), ctx, back, forward, live다. 파서가 멈춰 있는 동안 back과 forward로 저장된 스냅샷을 확인할 수 있으며, 실행을 재개하면 현재 멈춤 지점에서 계속한다. 멈추지 않고 기록만 하려면 --no-interactive를 사용한다.

생성된 C++ 코드는 규칙·생산 규칙 스코프, 일치 결과, 타입이 지정된 캡처, 변환된 Python 문장의 소스 체크포인트, 타입이 지정된 AST 스냅샷을 기록한다. Python 대상도 parser/stdlibs/target/ispa_debug.py를 통해 같은 v2 이벤트 프로토콜을 사용한다. 생성된 Python 파서를 실행할 때는 ispa_std.py와 함께 해당 디렉터리를 PYTHONPATH에 넣어야 한다. 추적은 JSON 파일이며 파서가 종료된 뒤에도 재생할 수 있다. 실시간 파서 세션에는 현재 POSIX 파일 디스크립터가 필요하다. Windows용 ispadbg 실행 파일은 오프라인 --replay와 도움말을 지원한다.

부트스트랩과 외부 파서

ISPA는 자기 문법을 스스로 파싱한다. ISPA 입력 언어를 정의하는 .isc 문법을 ISPA가 컴파일해 현재 사용하는 파서를 만들었고, 이 파서는 원래의 수기 파서를 대체했다. Python 부분집합 파서와 작은 모듈 스캐너 파서도 같은 방식으로 생성한다. 부트스트랩 파서는 parser/ispa/bootstrapped_0에 저장소에 포함돼 있으며, 다른 문법을 처리하기 전에 ISPA와 함께 빌드된다.

외부 가져오기는 별도로 생성된 파서를 호출하고 원래 노드 타입을 캡처한다.

import extern python ispa_python as python; expr: @ python.expr {@};

--dep NAME PREFIX로 기존 파서를 지정한다. PREFIX에는 확장자를 쓰지 않는다. ISPA는 내보낸 심벌을 PREFIX.ispa-export에서 읽고, C++ 출력에는 PREFIX.h, Python 출력에는 PREFIX.py를 공개 헤더 또는 모듈로 사용한다. 예를 들면 다음과 같다.

ispa -l cpp -a LL --dir parser/ispa/grammar parser/ispa/entry.isc \

--dep python parser/python/bootstrapped/PyRawParser -o build/Parser

생성된 C++은 <PyRawParser.h>를 포함하고 PyRawParser::Types를 직접 사용한다. 의존성 디렉터리를 컴파일러의 include 경로에 넣고 구현 파일을 정적 또는 공유 라이브러리로 링크해야 한다. 호스트 파서는 가져온 파서의 생산 규칙이나 타입을 복사해 생성하지 않는다. 내보낸 진입점 선언은 의존성 헤더에, 정의는 해당 .cpp 파일에 있다.

--no-dep를 사용하면 ISPA는 지정한 --dir 디렉터리에서 외부 문법 모듈을 찾아 호스트 파서와 나란히 각 의존성을 생성하고, 외부 의존성 이름을 출력 접두사로 쓴다. C++ 의존성은 별도 .h·.cpp 파일로 남으며 빌드 시스템에서 컴파일하고 링크해야 한다. 중첩 의존성은 이를 사용하는 파서보다 먼저 생성되고, 의존성 순환은 진단된다. 명시적인 --dep 연결로 기존 라이브러리를 쓰면서 나머지는 --no-dep로 빌드할 수도 있다.

외부 파서 호출에는 현재 LL 생성과 지연 토큰화가 필요하다. 즉시 토큰화하는 렉서는 외부 호출이 포함된 문법을 AMBIGUOUS 진단과 함께 거부한다. 지연 호출은 가져온 구간을 대상 렉서로 다시 어휘 분석해 토큰 페이로드를 대상 파서에 맞춘 뒤, 반환된 소스 위치에서 호스트 렉서를 재개한다.

Python 대상은 -l python -a LL로 생성한다. ispa_std를 사용할 수 있도록 생성 모듈과 parser/stdlibs/target을 PYTHONPATH에 넣는다.

PYTHONPATH=build:parser/stdlibs/target python3 -c 'import Parser; print(Parser.Parser().parse("input"))'

Python의 외부 가져오기는 생성된 의존성 모듈(예: import Foreign)과 그 모듈의 내보낸 파서 연결을 사용한다. 호스트 파서와 함께 의존성도 PYTHONPATH에 둔다. --dep와 --no-dep의 동작은 위와 같다.

성능과 파서 기능

같은 입력을 대상으로 렉싱과 파싱을 비교했다. 비교 대상은 flex + bison(LALR(1))과 ANTLR(C++ 대상)이며, 낮을수록 빠르다. 상대 배율은 AST를 만들지 않는 flex + bison을 기준으로 한다.

이 결과에서 ISPA는 전체 AST를 만들 때 CST 생성을 비활성화한 ANTLR보다 약 12배 빠르다. 반면 ISPA는 flex + bison보다 느리며, flex + bison이 비슷한 AST를 만들 때는 대략 6~10배 차이가 난다. 이 격차를 줄이는 작업은 진행 중이다. flex + bison 수치는 10회 반복의 정상 상태 측정값이다.

측정 조건은 입력 9.7 MB, Intel Core i5 12450H 노트북, Clang 18과 -O3, GNU Linux(Linux Mint)다. ANTLR은 4.13.2, flex는 2.6.4, bison은 3.8.2를 사용했다. 단일 실행 결과다.

렉서는 캡처와 액션을 하나의 자동자 안에서 처리하는 소형 TDFA(태그가 있는 결정적 유한 오토마톤) 테이블로 토큰을 찾는다. 렉싱 중 AST와 비슷한 토큰을 직접 만들고 필요한 항목만 캡처하며, 토큰 안에서 구조와 캡처 데이터 타입을 보존한 채 다른 토큰을 찾을 수 있다. 렉싱 중 터미널 안의 비단말을 파싱과 별도로 찾는 기능은 아직 구현되지 않았다.

LL은 제품화 대상 파서이며 개발이 계속되고 있다. 대안인 LR 계열 모드는 지원하는 문법 기능이 더 적고 실험 단계다. 파싱 중 완전한 타입의 순회 가능한 AST를 만들며, 후처리 단계나 콜백은 필요하지 않다. 고급 규칙과 fail 블록은 별도의 가이드를 참조한다.

빠른 시작

릴리스에서 ISPA를 설치하고 표준 라이브러리 패키지를 설치한 뒤, 이후 셸에서도 패키지 내보내기를 사용할 수 있도록 설정한다.

ispa-pkg install std

ispa-pkg --export-permanent

새 셸을 연다. 설치된 셸 도우미는 include 경로와 CMake 대상 정보를 제공한다. 현재 셸의 정보를 새로 고치려면 ispa-pkg --export를 실행한다. 그런 다음 grammar.isc를 만든다.

module main -> demo; NUMBER: @ [0-9]+ {@}; main: @ NUMBER {@};

C++ 파서를 생성한다.

ispa -l cpp -a LL grammar.isc -o generated/Parser

애플리케이션에서 생성된 파서를 사용하고 CMake를 통해 설치된 대상을 링크한다. CMakeLists.txt에는 다음을 넣는다.

cmake_minimum_required(VERSION 3.20)

project(demo LANGUAGES CXX)

include("$ENV{ISPA_TARGETS_CMAKE}")

add_executable(demo main.cpp generated/Parser.cpp)

target_link_libraries(demo PRIVATE ISPA::Targets)

이 대상은 설치된 ISPA 헤더와 런타임 라이브러리를 제공한다. Python 출력까지 포함한 설치 사용자용 전체 안내는 시작하기 위키에 있다.

로드맵과 설치

향후 계획에는 생성 코드의 렉서·LR 액션과 동적 정규식, LL 복구를 포함한 문법 진단의 추가 개선이 있다. LL 파서에서 좌재귀를 해결하면서 LR 파서와 구조적 동등성을 유지하도록 사용자 정의 예측 LL 알고리즘인 PLL을 완성하는 작업도 계획돼 있다. Python용 다중 대상 코드 생성기, LR(1)·LALR 등 전체 LR 파서의 안정화, 기능 조건부 모듈과 disable feature X 및 매개변수화 모듈도 로드맵에 포함된다. JSON, XML, 수학식, C 계열 문장을 위한 문법 표준 라이브러리와 concepts/에 기술된 기능도 계획돼 있다.

ISPA는 Linux x86_64, Windows x64, macOS Apple Silicon(ARM64)용 사전 빌드 GitHub Release 아카이브를 제공한다. macOS Intel은 해당 릴리스 아카이브가 있을 때 설치 프로그램으로 지원된다. 모든 명령은 관리자 권한 없이 현재 사용자용으로 설치한다.

릴리스 설치 프로그램에는 ispa와 함께 ispa-pkg, ispadbg가 제공된다. 소스 체크아웃에서는 Python 3.9 이상과 PyYAML이 필요하며 다음 명령으로 두 Python CLI를 설치한다.

python3 -m pip install .

태그가 지정된 릴리스는 지원되는 Linux·Windows·macOS 네 가지 대상으로 Nuitka 독립 실행 파일도 배포한다. 파일 이름은 ispa-pkg-<platform>과 ispadbg-<platform>이며, Windows에서는 .zip, 그 밖에는 .tar.gz 형식이다. ISPA 플랫폼 아카이브에는 두 실행 파일이 포함되며 설치 프로그램과 업데이트 프로그램이 이를 활성화한다.

CLI 코드는 cli/pkg에 있다. 기본 라이브러리 설치 위치는 Linux와 macOS에서 ~/.local/share/ispa/libraries이며, 릴리스 설치본에서 실행하면 ISPA 설치 디렉터리 아래에 둔다. 두 명령의 위치를 바꾸려면 ISPA_PKG_ROOT를 지정한다. ispa-pkg --root는 패키지 명령의 위치만 바꾼다. ispa는 일치하는 디렉터리에서 문법 라이브러리와 import py 라이브러리를 자동으로 찾는다. 알고리즘과 변환기 플러그인은 실행 파일 옆에 번들로 제공된다. 설치 패키지에는 ispalib/grammar, ispalib/python, ispatarget/<language>, ispaalgorithm 디렉터리가 있다. 생성 대상 코드를 컴파일할 때는 해당 ispatarget/<language> 디렉터리를 컴파일러나 인터프리터 검색 경로에 추가한다.

설치된 외부 파서 매니페스트(NAME.h 또는 NAME.py 옆의 NAME.ispa-export)도 --dep 연결을 자동으로 제공한다. 매니페스트가 하나인 패키지는 패키지 이름으로 참조할 수 있으며, 명시적인 --dep가 우선한다.

ispa-pkg install std

ispa-pkg install owner/repository --ref v1.2.0

ispa-pkg install https://example.org/mylib.tar.gz --name mylib

ispa-pkg update

ispa-pkg list

ispa-pkg catalog update

ispa-pkg catalog list

ispa-pkg --export-permanent를 한 번 실행하고 새 bash, zsh 또는 PowerShell 세션을 연다. 이 명령은 작은 셸 함수를 설치하고 시작 시 내보내기 경로를 불러온다. 해당 셸에서 ispa-pkg --export를 실행하면 eval 없이 현재 세션의 경로를 새로 고친다. 셸 함수가 로드되지 않은 상태에서 독립 실행 파일을 실행하면 부모 셸의 환경을 바꿀 수 없으므로 셸 코드를 출력한다.

내보내기 경로에는 C++ 헤더와 라이브러리 디렉터리, 공유 라이브러리용 런타임 로더 경로, Python 대상 디렉터리가 추가된다. 기존 검색 경로는 보존한다. 생성된 ISPA_TARGETS_CMAKE 파일은 설치된 헤더와 라이브러리를 포함하는 ISPA::Targets를 정의한다. 설치 과정에서 ispa-pkg는 각 패키지의 ispatarget/cpp/**/*.cpp 파일을 C++17로 컴파일하고 ispatarget/cpp/lib에 보관한다. 파일 이름은 lib<name>.a이며 MSVC에서는 <name>.lib다. 이를 위해 C++ 컴파일러와 아카이버가 필요하다. 도구 체인을 지정하려면 CXX, CXXFLAGS, AR을 설정한다. 내보내기는 이전 설치에서 빠진 아카이브도 빌드한다. 아카이브 디렉터리는 LIBRARY_PATH(Windows에서는 LIB)에 추가되고, 아카이브 경로는 ISPA_CPP_LIBRARIES와 ISPA_TARGETS_CMAKE에 포함된다.

GCC와 Clang에서 C++ 헤더 검색 경로 변수는 CPATH와 CPLUS_INCLUDE_PATH다. CPLUSPLUS_PATH는 인식되지 않는다. 생성 C++ 코드와 대상 런타임은 C++17로 빌드된다. 내보내기 경로를 불러온 뒤에는 예를 들어 다음처럼 컴파일할 수 있다.

clang++ -std=c++17 -c Parser.cpp

이미 설치된 ispa-pkg 실행 파일과 std 라이브러리 패키지를 사용 중이라면 이 소스 체크아웃에서 변경된 내용을 받기 위해 둘을 업데이트해야 한다.

카탈로그는 저장소 루트의 ispa-libraries.yaml이다. catalog update는 현재 파일을 GitHub에서 로컬 패키지 루트로 가져온다. --catalog FILE은 다른 YAML 카탈로그를 지정한다. 카탈로그 항목은 선택적 ref가 붙은 github: owner/repository 또는 archive: URL을 지정한다. 설치된 GitHub 패키지는 커밋이 바뀌면 업데이트된다. 아카이브와 로컬 디렉터리는 내용이 바뀌면 업데이트된다. --force는 패키지를 다시 설치한다.

라이브러리 저장소는 루트에 ispa-package.yaml을 둘 수 있다. 이 저장소의 ispa-package.yaml은 표준 라이브러리 패키지의 예다. 소스는 parser/stdlibs이며 이름이 바뀐 폴더는 표준 목적지에 연결된다. 설정 파일이 없으면 ispalib/grammar, ispalib/python, ispatarget/cpp, ispatarget/python, ispaalgorithm에서 패키지 소스를 읽는다. 설정은 layout.root로 release 디렉터리를 지정하거나, archive: release/library.zip으로 레이아웃을 적용하기 전에 저장소 안의 아카이브를 풀 수 있다. install 목록에 저장소 기준 .py 또는 셸 스크립트 경로를 넣으면 파일 복사 뒤 실행하며, 스크립트에는 스테이징된 목적지 경로가 첫 번째 인자로 전달된다. 스크립트를 선언한 패키지를 설치하거나 업데이트하려면 --allow-scripts를 전달한다. layout.files를 사용하면 target/ispa_std.py 같은 개별 파일을 매핑할 수 있다. LL과 LR 알고리즘 플러그인은 ISPA에 포함되며 std에는 들어 있지 않다.

운영체제별 설치와 업데이트

Linux와 macOS에서는 설치 스크립트 scripts/install.sh를 먼저 검토한 뒤 실행한다.

curl -fsSL https://raw.githubusercontent.com/Sinfolke/ispa-parser-generator/main/scripts/install.sh | sh

이 명령은 운영체제와 아키텍처에 맞는 최신 GitHub Release를 내려받는다. 바이너리는 ~/.local/bin/ispa에 연결된다. ~/.local/bin이 PATH에 있는지 확인한 다음 실행한다.

ispa --help

특정 버전을 설치하려면 다음을 실행한다.

ISPA_VERSION=v1.1.0 sh -c "$(curl -fsSL https://raw.githubusercontent.com/Sinfolke/ispa-parser-generator/main/scripts/install.sh)"

Windows PowerShell에서는 설치 스크립트 scripts/install.ps1를 먼저 검토한 뒤 실행한다.

irm https://raw.githubusercontent.com/Sinfolke/ispa-parser-generator/main/scripts/install.ps1 | iex

새 터미널을 열고 ispa --help를 실행한다. 설치 프로그램은 %LOCALAPPDATA%\\Programs\\ISPA\\bin\\ispa.cmd를 만들고 해당 디렉터리를 사용자 PATH에 추가한다. 특정 공개 태그를 설치하려면 다음처럼 실행한다.

$env:ISPA_VERSION = 'v1.1.0'

irm https://raw.githubusercontent.com/Sinfolke/ispa-parser-generator/main/scripts/install.ps1 | iex

설치 위치를 바꾸려면 Linux와 macOS에서는 설치 스크립트 실행 전에 ISPA_INSTALL_DIR 및/또는 ISPA_BIN_DIR을 설정한다. Windows에서는 PowerShell에서 스크립트를 실행하기 전에 같은 환경 변수를 설정한다.

업데이트는 다음 명령으로 수행한다.

ispa-update

Linux와 macOS에서 기본 경로를 사용하는 ISPA를 제거하려면 다음을 실행한다.

rm -f "$HOME/.local/bin/ispa"

rm -rf "${XDG_DATA_HOME:-$HOME/.local/share}/ispa"

Windows에서 기본 경로를 사용하는 경우 %LOCALAPPDATA%\\Programs\\ISPA를 삭제하고, 사용자 PATH에서 해당 폴더의 bin 항목도 제거한다.

빌드 요구사항

최신 Ubuntu에서는 libc++가 포함된 Clang을 사용한다. Windows에서는 MSVC clang-cl을 사용하며, CMake 4.5.0-rc1과 vcpkg.json에 지정된 의존성이 필요하다. 현재 GCC로는 ISPA를 빌드할 수 없다. Windows의 Clang 빌드는 테스트되지 않았다.

Ubuntu에서 빌드할 때 ISPA_SOURCE_DIR을 로컬 경로로 바꾸고 다음과 같이 설정한다.

export ISPA_SOURCE_DIR=/path/to/ispa-parser

export CC=clang-20

export CXX=clang++-20

export CFLAGS="-stdlib=libc++"

export CXXFLAGS="-stdlib=libc++"

export LDFLAGS="-stdlib=libc++"

cmake -B cmake-build-release \

-DCMAKE_BUILD_TYPE=Release \

-DCMAKE_TOOLCHAIN_FILE=~/vcpkg/scripts/buildsystems/vcpkg.cmake \

-DVCPKG_CHAINLOAD_TOOLCHAIN_FILE=$ISPA_SOURCE_DIR/cmake/toolchains/clang-libcxx.cmake \

-DVCPKG_TARGET_TRIPLET=x64-linux-libcxx \

-DVCPKG_OVERLAY_TRIPLETS=$ISPA_SOURCE_DIR/cmake/triplets

그런 다음 빌드한다.

cmake --build cmake-build-release

Windows에서 빌드할 때 설정이 작동하지 않으면 CMAKE_TOOLCHAIN_FILE을 vcpkg 설치 경로로 바꾼다. CMAKE_CXX_COMPILER를 cl.exe로 설정하거나 MSVC에 필요한 다른 변수를 지정해야 할 수도 있다.

cmake -B cmake-build-release -G Ninja -DCMAKE_BUILD_TYPE=Release -DCMAKE_TOOLCHAIN_FILE="%VCPKG_INSTALLATION_ROOT%/scripts/buildsystems/vcpkg.cmake"

cmake --build cmake-build-release