regex.tpz
// 정규식 NFA 시각화. 정규식을 톰슨 구성으로 NFA로 바꿔 SVG로 그리고, 시험 문자열의 일치 구간을 표시한다.
// Regex-to-NFA visualizer. Parses a regex, builds a Thompson NFA, draws it as SVG, and highlights
// the matches in a test string. Written in Topaz.
//
// Key identifiers: 범위=codepoint range, 이동=transition, 조각=NFA fragment, 이동표=transition table,
// 새상태=new state, 입실론추가=add epsilon edge, 문자추가=add char edge, 클래스파싱=parse [..] class,
// 이스케이프원자=parse \escape, 원자파싱=parse atom, 반복파싱=parse quantifier, 연결파싱=parse concat,
// 택일파싱=parse alternation, 문자매치=char matches edge, 입실론닫힘=epsilon closure, 가장긴매치=longest
// match, 매치렌더=render matches, 그림=NFA SVG, 화살표=edge arrow, 원=state circle, 이스케이프=HTML escape.
//
// 결정적이다. 같은 (정규식, 문자열)이면 인터프리터와 네이티브/wasm에서 같은 NFA와 같은 표시가 나온다.
// Deterministic. Same (regex, text) yields the same NFA and highlights across interpreter and builds.
// 안 하는 것: 역참조, 룩어라운드, 게으른 수량자, 캡처 그룹 추출, 전체 유니코드 속성(ASCII 클래스만).
// Won't do: backreferences, lookaround, lazy quantifiers, capture extraction, full Unicode (ASCII classes).
// 문자 클래스는 앱 수준 ASCII 범위로 처리한다(컴파일러 변경 없음).
// Character classes are handled as app-level ASCII ranges (no compiler change).
// 매칭에는 작업량 한계가 있다. 아주 길거나 병리적인 입력(긴 문자열에 (a*)*b 등)은 화면을 멈추지
// 않고 너무 복잡하다고 알린다. 시각화 도구라 짧은 예시 문자열을 가정한다.
// Matching has a work budget: very long or pathological input (such as (a*)*b on a long string)
// reports too-complex instead of freezing the page. As a visualizer it assumes short example strings.
type 범위 = { 시작: int, 끝: int }
// 닫힌 전이/수량자 태그. 정규식 문자 자체는 입력 경계라 string으로 둔다.
// Closed transition/quantifier tags. Regex characters themselves stay string at the input boundary.
type 이동종류 = "입실론" | "문자"
type 수량자 = "*" | "+" | "?"
type 이동 = { 종류: 이동종류, 라벨: string, 대상: int, 부정: bool, 범위들: Array<범위> }
type 조각 = { 시작: int, 끝: int, 위치: int }
// 레코드 리터럴은 문자열 리터럴을 넓히므로 전이 생성은 헬퍼로 좁힌다.
// Record literals widen string literals, so transition creation narrows through this helper.
function 이동만들기(종류: 이동종류, 라벨: string, 대상: int, 부정: bool, 범위들: Array<범위>) -> 이동 {
{ 종류: 종류, 라벨: 라벨, 대상: 대상, 부정: 부정, 범위들: 범위들 }
}
function 수량자파싱(글: string) -> Result<수량자, string> {
match 글 {
case "*" => Ok("*")
case "+" => Ok("+")
case "?" => Ok("?")
case _ => Err("수량자가 필요합니다")
}
}
function 입실론인가(종류: 이동종류) -> bool {
match 종류 {
case "입실론" => true
case "문자" => false
}
}
// HTML 이스케이프. 정규식·문자열·전이 라벨은 모두 사용자 입력이라 출력 전에 반드시 이스케이프한다.
// HTML escape. Pattern, text, and every label are user input, so always escape before output.
function 이스케이프(원문: string) -> string {
let mut 결과 = ""
for 글 in 원문.scalars() {
if 글 == "&" { 결과 = 결과 + "&" }
else if 글 == "<" { 결과 = 결과 + "<" }
else if 글 == ">" { 결과 = 결과 + ">" }
else if 글 == "\"" { 결과 = 결과 + """ }
else { 결과 = 결과 + 글 }
}
결과
}
// 이스케이프로 리터럴이 되는 메타문자인가. \. \* 등과 클래스의 \] \- \^ \\ 에 쓴다.
// Is this a metacharacter that a backslash turns into a literal? Used for \. \* and class \] \- \^ \\.
function 메타문자인가(글: string) -> bool {
글 == "." || 글 == "*" || 글 == "+" || 글 == "?" || 글 == "(" || 글 == ")" || 글 == "[" || 글 == "]" || 글 == "{" || 글 == "}" || 글 == "|" || 글 == "^" || 글 == "$" || 글 == "\\" || 글 == "/" || 글 == "-"
}
// 새 상태를 만들어 그 번호를 돌려준다. 이동표는 참조라 호출자에게도 반영된다.
// Allocate a new state and return its index. The table is shared by reference.
function 새상태(이동표: Array<Array<이동>>) -> int {
let mut 표 = 이동표
let mut 빈: Array<이동> = []
표.push(빈)
표.length - 1
}
// 입실론(빈) 전이를 더한다.
// Add an epsilon (empty) transition.
function 입실론추가(이동표: Array<Array<이동>>, 출발: int, 도착: int) {
let mut 표 = 이동표
let mut 비범위: Array<범위> = []
표[출발].push(이동만들기("입실론", "ε", 도착, false, 비범위))
}
// 문자 전이를 더한다. 범위들 안에 코드가 있으면 일치(부정이면 반대).
// Add a character transition: matches when a code is within 범위들 (negated if 부정).
function 문자추가(이동표: Array<Array<이동>>, 출발: int, 도착: int, 라벨: string, 부정: bool, 범위들: Array<범위>) {
let mut 표 = 이동표
표[출발].push(이동만들기("문자", 라벨, 도착, 부정, 범위들))
}
// 문자 클래스 [..]를 파싱한다. 시작위치는 '[' 다음을 가리킨다. a-z 범위, ^ 부정, \d\w\s 약식을 지원한다.
// Parse a [..] class. 시작위치 points just past '['. Supports a-z ranges, ^ negation, \d \w \s.
function 클래스파싱(이동표: Array<Array<이동>>, 시작위치: int, 문자들: Array<string>) -> Result<조각, string> {
let mut 표 = 이동표
let mut 현 = 시작위치
let mut 부정 = false
if 현 < 문자들.length && 문자들[현] == "^" { 부정 = true; 현 = 현 + 1 }
let mut 범위들: Array<범위> = []
let mut 닫힘 = false
let mut 오류 = ""
let mut 계속 = true
while 계속 && 현 < 문자들.length {
let 글 = 문자들[현]
if 글 == "]" { 닫힘 = true; 계속 = false; 현 = 현 + 1 }
else {
let mut 코드 = 0
let mut 진행 = 1
let mut 약식 = false
if 글 == "\\" {
if 현 + 1 >= 문자들.length { 오류 = "역슬래시 뒤에 문자가 필요합니다"; 계속 = false }
else {
let 다 = 문자들[현 + 1]
진행 = 2
if 다 == "d" { 범위들.push({ 시작: 48, 끝: 57 }); 약식 = true }
else if 다 == "w" { 범위들.push({ 시작: 48, 끝: 57 }); 범위들.push({ 시작: 65, 끝: 90 }); 범위들.push({ 시작: 97, 끝: 122 }); 범위들.push({ 시작: 95, 끝: 95 }); 약식 = true }
else if 다 == "s" { 범위들.push({ 시작: 9, 끝: 13 }); 범위들.push({ 시작: 32, 끝: 32 }); 약식 = true }
// 대문자 약식은 여집합 범위로 추가한다(클래스 안에서 \D \W \S 지원).
// Uppercase shorthands add complement ranges so \D \W \S work inside a class.
else if 다 == "D" { 범위들.push({ 시작: 0, 끝: 47 }); 범위들.push({ 시작: 58, 끝: 1114111 }); 약식 = true }
else if 다 == "W" { 범위들.push({ 시작: 0, 끝: 47 }); 범위들.push({ 시작: 58, 끝: 64 }); 범위들.push({ 시작: 91, 끝: 94 }); 범위들.push({ 시작: 96, 끝: 96 }); 범위들.push({ 시작: 123, 끝: 1114111 }); 약식 = true }
else if 다 == "S" { 범위들.push({ 시작: 0, 끝: 8 }); 범위들.push({ 시작: 14, 끝: 31 }); 범위들.push({ 시작: 33, 끝: 1114111 }); 약식 = true }
else if 메타문자인가(다) { 코드 = 다.codePointAt(0) ?? 0 }
else { 오류 = "알 수 없는 이스케이프: \\" + 다; 계속 = false }
}
} else {
코드 = 글.codePointAt(0) ?? 0
}
if 약식 {
현 = 현 + 진행
} else {
// a-z 범위인가: 다음이 '-'이고 그 다음이 ']'가 아니면 범위.
// A range a-z: next is '-' and the char after it is not ']'.
if 현 + 진행 < 문자들.length && 문자들[현 + 진행] == "-"
&& 현 + 진행 + 1 < 문자들.length && 문자들[현 + 진행 + 1] != "]" {
let 끝코드 = 문자들[현 + 진행 + 1].codePointAt(0) ?? 0
if 끝코드 < 코드 { 오류 = "잘못된 문자 범위입니다"; 계속 = false }
else { 범위들.push({ 시작: 코드, 끝: 끝코드 }); 현 = 현 + 진행 + 2 }
} else {
범위들.push({ 시작: 코드, 끝: 코드 }); 현 = 현 + 진행
}
}
}
}
if 오류 != "" { return Err(오류) }
if !닫힘 { return Err("'['에 대응하는 ']'가 없습니다") }
if 범위들.length == 0 { return Err("빈 문자 클래스입니다") }
let 라벨 = 문자들.slice(시작위치 - 1, 현).join("")
let 상태가 = 새상태(표)
let 상태나 = 새상태(표)
문자추가(표, 상태가, 상태나, 라벨, 부정, 범위들)
Ok({ 시작: 상태가, 끝: 상태나, 위치: 현 })
}
// 역슬래시 원자. \d \w \s 약식과 이스케이프된 리터럴(\. \* 등)을 처리한다.
// Backslash atom: \d \w \s shorthands and escaped literals (\. \* and so on).
function 이스케이프원자(이동표: Array<Array<이동>>, 위치: int, 문자들: Array<string>) -> Result<조각, string> {
let mut 표 = 이동표
if 위치 + 1 >= 문자들.length { return Err("역슬래시 뒤에 문자가 필요합니다") }
let 다음 = 문자들[위치 + 1]
let mut 범위들: Array<범위> = []
let mut 부정 = false
let mut 라벨 = ""
if 다음 == "d" { 범위들.push({ 시작: 48, 끝: 57 }); 라벨 = "\\d" }
else if 다음 == "D" { 범위들.push({ 시작: 48, 끝: 57 }); 부정 = true; 라벨 = "\\D" }
else if 다음 == "w" { 범위들.push({ 시작: 48, 끝: 57 }); 범위들.push({ 시작: 65, 끝: 90 }); 범위들.push({ 시작: 97, 끝: 122 }); 범위들.push({ 시작: 95, 끝: 95 }); 라벨 = "\\w" }
else if 다음 == "W" { 범위들.push({ 시작: 48, 끝: 57 }); 범위들.push({ 시작: 65, 끝: 90 }); 범위들.push({ 시작: 97, 끝: 122 }); 범위들.push({ 시작: 95, 끝: 95 }); 부정 = true; 라벨 = "\\W" }
else if 다음 == "s" { 범위들.push({ 시작: 9, 끝: 13 }); 범위들.push({ 시작: 32, 끝: 32 }); 라벨 = "\\s" }
else if 다음 == "S" { 범위들.push({ 시작: 9, 끝: 13 }); 범위들.push({ 시작: 32, 끝: 32 }); 부정 = true; 라벨 = "\\S" }
else if 메타문자인가(다음) { let 코드 = 다음.codePointAt(0) ?? 0; 범위들.push({ 시작: 코드, 끝: 코드 }); 라벨 = "\\" + 다음 }
else { return Err("알 수 없는 이스케이프: \\" + 다음) }
let 상태가 = 새상태(표)
let 상태나 = 새상태(표)
문자추가(표, 상태가, 상태나, 라벨, 부정, 범위들)
Ok({ 시작: 상태가, 끝: 상태나, 위치: 위치 + 2 })
}
// 원자: 리터럴 | . | [클래스] | (택일) | \이스케이프.
// Atom: literal | . | [class] | (alternation) | \escape.
function 원자파싱(이동표: Array<Array<이동>>, 위치: int, 문자들: Array<string>) -> Result<조각, string> {
let mut 표 = 이동표
if 위치 >= 문자들.length { return Err("식이 필요합니다") }
let 글 = 문자들[위치]
if 글 == "(" {
match 택일파싱(표, 위치 + 1, 문자들) {
case Err(메) => Err(메)
case Ok(안) => {
if 안.위치 < 문자들.length && 문자들[안.위치] == ")" {
Ok({ 시작: 안.시작, 끝: 안.끝, 위치: 안.위치 + 1 })
} else { Err("여는 괄호에 대응하는 닫는 괄호가 없습니다") }
}
}
} else if 글 == "[" {
클래스파싱(표, 위치 + 1, 문자들)
} else if 글 == "\\" {
이스케이프원자(표, 위치, 문자들)
} else if 글 == "." {
let mut 범위들: Array<범위> = []
범위들.push({ 시작: 10, 끝: 10 })
let 상태가 = 새상태(표)
let 상태나 = 새상태(표)
문자추가(표, 상태가, 상태나, ".", true, 범위들)
Ok({ 시작: 상태가, 끝: 상태나, 위치: 위치 + 1 })
} else if 글 == ")" || 글 == "|" || 글 == "*" || 글 == "+" || 글 == "?" {
Err("예상치 못한 기호: '" + 글 + "'")
} else {
let 코드 = 글.codePointAt(0) ?? 0
let mut 범위들: Array<범위> = []
범위들.push({ 시작: 코드, 끝: 코드 })
let 상태가 = 새상태(표)
let 상태나 = 새상태(표)
문자추가(표, 상태가, 상태나, 글, false, 범위들)
Ok({ 시작: 상태가, 끝: 상태나, 위치: 위치 + 1 })
}
}
// 수량자: 원자 뒤의 * + ? 를 톰슨 구성으로 감싼다.
// Quantifier: wrap the atom with * + ? using Thompson construction.
function 반복파싱(이동표: Array<Array<이동>>, 위치: int, 문자들: Array<string>) -> Result<조각, string> {
let mut 표 = 이동표
match 원자파싱(표, 위치, 문자들) {
case Err(메) => Err(메)
case Ok(조) => {
let mut 시작 = 조.시작
let mut 끝 = 조.끝
let mut 현 = 조.위치
if 현 < 문자들.length {
let 글 = 문자들[현]
if 글 == "*" || 글 == "+" || 글 == "?" {
let 수 = match 수량자파싱(글) {
case Ok(ㅅ) => ㅅ
case Err(메) => return Err(메)
}
match 수 {
case "*" => {
let 상태가 = 새상태(표); let 상태나 = 새상태(표)
입실론추가(표, 상태가, 시작); 입실론추가(표, 상태가, 상태나)
입실론추가(표, 끝, 시작); 입실론추가(표, 끝, 상태나)
시작 = 상태가; 끝 = 상태나; 현 = 현 + 1
}
case "+" => {
let 상태나 = 새상태(표)
입실론추가(표, 끝, 시작); 입실론추가(표, 끝, 상태나)
끝 = 상태나; 현 = 현 + 1
}
case "?" => {
let 상태가 = 새상태(표); let 상태나 = 새상태(표)
입실론추가(표, 상태가, 시작); 입실론추가(표, 상태가, 상태나); 입실론추가(표, 끝, 상태나)
시작 = 상태가; 끝 = 상태나; 현 = 현 + 1
}
}
}
}
Ok({ 시작: 시작, 끝: 끝, 위치: 현 })
}
}
}
// 연결: 수량자 항을 ε로 잇는다. |, ), 끝에서 멈춘다. 항 없이 만난 수량자는 오류.
// Concatenation: chain quantified terms with epsilon. Stops at |, ), or end. A quantifier with no
// preceding atom is an error. An empty concatenation becomes an epsilon fragment.
function 연결파싱(이동표: Array<Array<이동>>, 위치: int, 문자들: Array<string>) -> Result<조각, string> {
let mut 표 = 이동표
let mut 현 = 위치
let mut 조각있음 = false
let mut 시작 = 0
let mut 끝 = 0
let mut 오류 = ""
let mut 계속 = true
while 계속 && 현 < 문자들.length {
let 글 = 문자들[현]
if 글 == "|" || 글 == ")" {
계속 = false
} else if 글 == "*" || 글 == "+" || 글 == "?" {
오류 = "수량자 앞에 식이 필요합니다"; 계속 = false
} else {
match 반복파싱(표, 현, 문자들) {
case Err(메) => { 오류 = 메; 계속 = false }
case Ok(조) => {
현 = 조.위치
if 조각있음 {
입실론추가(표, 끝, 조.시작)
끝 = 조.끝
} else {
시작 = 조.시작; 끝 = 조.끝; 조각있음 = true
}
}
}
}
}
if 오류 != "" { return Err(오류) }
if 조각있음 {
Ok({ 시작: 시작, 끝: 끝, 위치: 현 })
} else {
let 상태가 = 새상태(표)
let 상태나 = 새상태(표)
입실론추가(표, 상태가, 상태나)
Ok({ 시작: 상태가, 끝: 상태나, 위치: 현 })
}
}
// 택일: 연결을 | 로 잇는다. 새 시작/끝에서 각 가지로 ε를 둔다.
// Alternation: join concatenations with |. A new start/end with epsilon to and from each branch.
function 택일파싱(이동표: Array<Array<이동>>, 위치: int, 문자들: Array<string>) -> Result<조각, string> {
let mut 표 = 이동표
match 연결파싱(표, 위치, 문자들) {
case Err(메) => Err(메)
case Ok(첫) => {
let mut 시작 = 첫.시작
let mut 끝 = 첫.끝
let mut 현 = 첫.위치
let mut 오류 = ""
let mut 계속 = true
while 계속 && 현 < 문자들.length && 문자들[현] == "|" {
match 연결파싱(표, 현 + 1, 문자들) {
case Err(메) => { 오류 = 메; 계속 = false }
case Ok(다음) => {
let 상태가 = 새상태(표)
let 상태나 = 새상태(표)
입실론추가(표, 상태가, 시작); 입실론추가(표, 상태가, 다음.시작)
입실론추가(표, 끝, 상태나); 입실론추가(표, 다음.끝, 상태나)
시작 = 상태가; 끝 = 상태나; 현 = 다음.위치
}
}
}
if 오류 != "" { Err(오류) } else { Ok({ 시작: 시작, 끝: 끝, 위치: 현 }) }
}
}
}
// 코드가 이 문자 전이에 일치하는가.
// Does a code match this character transition?
function 문자매치(이: 이동, 코드: int) -> bool {
match 이.종류 {
case "입실론" => false
case "문자" => {
let mut 안에 = false
for 범 in 이.범위들 { if 코드 >= 범.시작 && 코드 <= 범.끝 { 안에 = true } }
if 이.부정 { !안에 } else { 안에 }
}
}
}
// 입실론 닫힘을 제자리에서 한다. 집합(bool 배열)에 ε로 도달 가능한 상태를 더한다. 스택을 새로
// 만들지 않고 고정점 반복이라 글자마다 할당이 없다. NFA가 작아 빠르다.
// Epsilon closure in place: add the epsilon-reachable states into the bool-array set. Fixpoint
// iteration with no per-call stack allocation, so there is no per-character allocation.
function 닫힘제자리(이동표: Array<Array<이동>>, 집합: Array<bool>, 예산: Array<int>) {
let mut 칸 = 집합
let mut 셈 = 예산
let mut 변함 = true
while 변함 {
변함 = false
let mut s = 0
while s < 이동표.length {
if 칸[s] {
for 이 in 이동표[s] {
셈[0] = 셈[0] + 1
if 입실론인가(이.종류) && !칸[이.대상] { 칸[이.대상] = true; 변함 = true }
}
}
s = s + 1
}
}
}
// 시작위치에서 시작하는 가장 긴 일치 길이. 없으면 -1, 빈 일치면 0.
// Longest match length starting at 시작위치. -1 if none, 0 if a zero-width match.
// 현재/다음 두 bool 배열을 한 번만 만들어 글자마다 재사용한다(참조 교환). 글자당 할당이 없어
// 입실론 순환(예: (a*)*)이 있어도 위치당 O(글자수 * 상태수)로 끝난다.
// Allocate two bool arrays once and reuse them per character by reference swap. No per-character
// allocation, so even epsilon cycles like (a*)* stay O(text * states) per start position.
function 가장긴매치(이동표: Array<Array<이동>>, 시작: int, 끝: int, 코드들: Array<int>, 시작위치: int, 예산: Array<int>) -> int {
let 수 = 이동표.length
let mut 셈 = 예산
let mut 현재: Array<bool> = []
let mut 다음: Array<bool> = []
let mut 자리 = 0
while 자리 < 수 { 현재.push(false); 다음.push(false); 자리 = 자리 + 1 }
현재[시작] = true
닫힘제자리(이동표, 현재, 예산)
let mut 최장 = -1
if 현재[끝] { 최장 = 0 }
let mut 위 = 시작위치
let mut 계속 = true
while 계속 && 위 < 코드들.length {
if 셈[0] > 100000 { return -2 }
let 코 = 코드들[위]
let mut 비움 = 0
while 비움 < 수 { 다음[비움] = false; 비움 = 비움 + 1 }
let mut 있음 = false
let mut s = 0
while s < 수 {
if 현재[s] {
for 이 in 이동표[s] {
셈[0] = 셈[0] + 1
if 문자매치(이, 코) { if !다음[이.대상] { 다음[이.대상] = true; 있음 = true } }
}
}
s = s + 1
}
if !있음 { 계속 = false }
else {
닫힘제자리(이동표, 다음, 예산)
let 임시 = 현재
현재 = 다음
다음 = 임시
위 = 위 + 1
if 현재[끝] { 최장 = 위 - 시작위치 }
}
}
최장
}
// 시험 문자열에서 겹치지 않는 왼쪽 우선·최장 일치를 찾아 강조하고 건수를 알린다.
// Find leftmost-longest non-overlapping matches in the test string, highlight them, report the count.
function 매치렌더(이동표: Array<Array<이동>>, 시작: int, 끝: int, 본문: string) -> string {
let 글자들 = 본문.scalars()
let mut 코드들: Array<int> = []
for 글 in 글자들 { 코드들.push(글.codePointAt(0) ?? 0) }
let mut 예산: Array<int> = []
예산.push(0)
let mut 출력 = ""
let mut 자리 = 0
let mut 매치수 = 0
let mut 빈매치 = false
let mut 초과 = false
while 자리 < 글자들.length && !초과 {
let 길이 = 가장긴매치(이동표, 시작, 끝, 코드들, 자리, 예산)
if 길이 == -2 {
초과 = true
} else if 길이 > 0 {
let mut 조각문 = ""
let mut 안자리 = 자리
while 안자리 < 자리 + 길이 { 조각문 = 조각문 + 이스케이프(글자들[안자리]); 안자리 = 안자리 + 1 }
출력 = 출력 + "<mark style=\"background:#111;color:#fff;padding:0 1px\">" + 조각문 + "</mark>"
자리 = 자리 + 길이
매치수 = 매치수 + 1
} else {
if 길이 == 0 { 빈매치 = true }
출력 = 출력 + 이스케이프(글자들[자리])
자리 = 자리 + 1
}
}
// 작업량이 한계를 넘으면 화면을 멈추지 않도록 멈추고 알린다(문서화된 MVP 경계).
// If the work budget is exceeded, stop and report instead of freezing the page (a documented bound).
if 초과 {
return "<div class=\"err\">시험 문자열이 너무 길거나 패턴이 복잡합니다. 더 짧은 문자열로 시도하세요.</div>"
}
if 가장긴매치(이동표, 시작, 끝, 코드들, 글자들.length, 예산) == 0 { 빈매치 = true }
let mut 머리 = "<div class=\"meta\">일치 {매치수}건"
if 빈매치 { 머리 = 머리 + ", 빈 문자열도 일치합니다" }
머리 = 머리 + "</div>"
if 본문 == "" { 머리 }
else { 머리 + "<div class=\"out\" style=\"white-space:pre-wrap\">" + 출력 + "</div>" }
}
// 한 전이를 화살표로 그린다. 자기 자신이면 위쪽 고리, 아니면 직선. 입실론은 점선.
// Draw one transition as an arrow: a loop above for a self edge, a straight line otherwise. Epsilon dashed.
function 화살표(엑스1: int, 와이1: int, 엑스2: int, 와이2: int, 라벨: string, 입실론: bool) -> string {
let 라 = 이스케이프(라벨)
let mut 점선 = ""
if 입실론 { 점선 = " stroke-dasharray=\"3 2\"" }
let mut 결과 = ""
if 엑스1 == 엑스2 && 와이1 == 와이2 {
결과 = "<path d=\"M {엑스1 - 7} {와이1 - 12} A 11 11 0 1 1 {엑스1 + 7} {와이1 - 12}\" fill=\"none\" stroke=\"#111\"{점선} marker-end=\"url(#화살)\" />"
결과 = 결과 + "<text x=\"{엑스1}\" y=\"{와이1 - 28}\" font-size=\"11\" text-anchor=\"middle\" font-family=\"monospace\" fill=\"#111\">{라}</text>"
} else {
let 가로차 = 엑스2 - 엑스1
let mut 끝엑스 = 엑스2
let mut 끝와이 = 와이2
if 가로차 > 0 { 끝엑스 = 엑스2 - 15 }
else if 가로차 < 0 { 끝엑스 = 엑스2 + 15 }
else if 와이2 > 와이1 { 끝와이 = 와이2 - 15 }
else { 끝와이 = 와이2 + 15 }
let 중엑스 = (엑스1 + 엑스2) / 2
let 중와이 = (와이1 + 와이2) / 2
결과 = "<line x1=\"{엑스1}\" y1=\"{와이1}\" x2=\"{끝엑스}\" y2=\"{끝와이}\" stroke=\"#111\"{점선} marker-end=\"url(#화살)\" />"
결과 = 결과 + "<text x=\"{중엑스}\" y=\"{중와이 - 4}\" font-size=\"11\" text-anchor=\"middle\" font-family=\"monospace\" fill=\"#111\">{라}</text>"
}
결과
}
// 한 상태를 원으로 그린다. 시작은 진입 화살표, 수락은 이중원.
// Draw one state as a circle. Start gets an entry arrow, accept is a double circle.
function 원(엑스: int, 와이: int, 시작인가: bool, 끝인가: bool) -> string {
let mut 결과 = ""
if 끝인가 { 결과 = 결과 + "<circle cx=\"{엑스}\" cy=\"{와이}\" r=\"17\" fill=\"none\" stroke=\"#111\" />" }
결과 = 결과 + "<circle cx=\"{엑스}\" cy=\"{와이}\" r=\"13\" fill=\"#fff\" stroke=\"#111\" />"
if 시작인가 { 결과 = 결과 + "<line x1=\"{엑스 - 32}\" y1=\"{와이}\" x2=\"{엑스 - 15}\" y2=\"{와이}\" stroke=\"#111\" marker-end=\"url(#화살)\" />" }
결과
}
// NFA를 SVG로 그린다. 시작에서 BFS로 레벨을 매겨 왼쪽에서 오른쪽으로 배치한다.
// Draw the NFA as SVG: levels by BFS from the start, laid out left to right.
function 그림(이동표: Array<Array<이동>>, 시작: int, 끝: int) -> string {
let 수 = 이동표.length
let mut 레벨: Array<int> = []
let mut 레벨자리 = 0
while 레벨자리 < 수 { 레벨.push(-1); 레벨자리 = 레벨자리 + 1 }
레벨[시작] = 0
let mut 큐: Array<int> = []
큐.push(시작)
let mut 머리 = 0
while 머리 < 큐.length {
let 현 = 큐[머리]
머리 = 머리 + 1
for 이 in 이동표[현] {
if 레벨[이.대상] == -1 { 레벨[이.대상] = 레벨[현] + 1; 큐.push(이.대상) }
}
}
let mut 정리자리 = 0
while 정리자리 < 수 { if 레벨[정리자리] == -1 { 레벨[정리자리] = 0 }; 정리자리 = 정리자리 + 1 }
let mut 최대레벨 = 0
for 층값 in 레벨 { if 층값 > 최대레벨 { 최대레벨 = 층값 } }
let mut 레벨카운트: Array<int> = []
let mut 카운트자리 = 0
while 카운트자리 <= 최대레벨 { 레벨카운트.push(0); 카운트자리 = 카운트자리 + 1 }
let mut 엑스: Array<int> = []
let mut 와이: Array<int> = []
let mut 좌표자리 = 0
while 좌표자리 < 수 { 엑스.push(0); 와이.push(0); 좌표자리 = 좌표자리 + 1 }
let mut 배치자리 = 0
while 배치자리 < 수 {
let 층 = 레벨[배치자리]
let 순 = 레벨카운트[층]
레벨카운트[층] = 순 + 1
엑스[배치자리] = 55 + 층 * 95
와이[배치자리] = 50 + 순 * 64
배치자리 = 배치자리 + 1
}
let 너비 = 70 + (최대레벨 + 1) * 95
let mut 최대행 = 1
for 칸수 in 레벨카운트 { if 칸수 > 최대행 { 최대행 = 칸수 } }
let 높이 = 60 + 최대행 * 64
let mut 본문 = ""
let mut 출발상태 = 0
while 출발상태 < 수 {
for 이 in 이동표[출발상태] {
본문 = 본문 + 화살표(엑스[출발상태], 와이[출발상태], 엑스[이.대상], 와이[이.대상], 이.라벨, 입실론인가(이.종류))
}
출발상태 = 출발상태 + 1
}
let mut 그릴상태 = 0
while 그릴상태 < 수 {
본문 = 본문 + 원(엑스[그릴상태], 와이[그릴상태], 그릴상태 == 시작, 그릴상태 == 끝)
그릴상태 = 그릴상태 + 1
}
let 머리부 = "<svg viewBox=\"0 0 {너비} {높이}\" width=\"100%\" style=\"border:1px solid #e3e3e3;margin-top:12px;max-width:100%\">"
let 꼬리 = "<defs><marker id=\"화살\" markerWidth=\"8\" markerHeight=\"8\" refX=\"7\" refY=\"3\" orient=\"auto\"><path d=\"M0,0 L7,3 L0,6 Z\" fill=\"#111\" /></marker></defs>"
머리부 + 꼬리 + 본문 + "</svg>"
}
// 첫 줄은 정규식, 나머지 줄은 시험 문자열이다.
// The first line is the regex; the remaining lines are the test string.
function 처리(입력: string) -> string {
let 줄들 = 입력.split("\n")
let 패턴 = if 줄들.length > 0 { 줄들[0] } else { "" }
let mut 본문 = ""
let mut 자리 = 1
while 자리 < 줄들.length {
if 자리 > 1 { 본문 = 본문 + "\n" }
본문 = 본문 + 줄들[자리]
자리 = 자리 + 1
}
if 패턴 == "" {
return "<div class=\"meta\">첫 줄에 정규식, 그 아래 줄에 시험 문자열을 입력하세요.</div>"
}
let mut 이동표: Array<Array<이동>> = []
let 문자들 = 패턴.scalars()
match 택일파싱(이동표, 0, 문자들) {
case Err(메시지) => "<div class=\"err\">정규식 오류: {이스케이프(메시지)}</div>"
case Ok(조) => {
if 조.위치 != 문자들.length {
"<div class=\"err\">정규식 오류: 예상치 못한 기호 '{이스케이프(문자들[조.위치])}'</div>"
} else {
그림(이동표, 조.시작, 조.끝) + 매치렌더(이동표, 조.시작, 조.끝, 본문)
}
}
}
}
print(처리(input()))