slow.monster

STUDIO HAZE · jeniapp

Topaz source

Open by house policy. Topaz is our own language.

Topaz 5.20.2 · 63 files

apps/regex/regex.tpz

Topaz · 23692 B · Original file

1// 정규식 NFA. 정규식을 톰슨 구성으로 NFA 로 바꿔 SVG 로 그리고 시험 문자열의 일치 구간을 표시합니다.
2// 입력 첫 줄은 정규식이고 나머지 줄은 시험 문자열입니다. 출력은 NFA 그림과 일치 건수, 강조한 시험 문자열을 담은 HTML 조각이거나 오류 한 줄입니다.
3// 같은 입력이면 인터프리터와 웹 빌드에서 바이트까지 같은 출력을 냅니다. 일치는 겹치지 않는 왼쪽 우선 최장 일치이고, 작업량이 한계를 넘으면 멈추고 알립니다.
4// 역참조, 룩어라운드, 게으른 수량자, 캡처 추출, 앵커, 횟수 반복은 하지 않습니다. ^ $ { } 는 글자 그대로 맞추고, 약식과 문자 클래스는 ASCII 범위입니다.
5// Regex NFA: builds a Thompson NFA from a regex, draws it as SVG and highlights leftmost-longest matches in a test string.
7record 범위 { 시작: int, 끝: int }
8enum 전이종류 { 입실론, 문자(bool, Array<범위>) }
9record 전이 { 라벨: string, 대상: int, 종류: 전이종류 }
10type 수량자 = "*" | "+" | "?"
11// 괄호 묶음은 남기지 않습니다. 택일과 연결은 가지나 항이 하나여도 그대로 두고 엮을 때 풉니다.
12enum 식 { 한글자(string, bool, Array<범위>), 반복(식, 수량자), 연결(Array<식>), 택일(Array<식>) }
13record 읽은식 { 값: 식, 다음: int }
14record 읽은범위 { 범위들: Array<범위>, 다음: int }
15enum 풀린이스케이프 { 약식(Array<범위>), 낱글자(int) }
16record 간선 { 출발: int, 이동: 전이 }
17record 조각 { 시작: int, 끝: int, 간선들: Array<간선>, 상태수: int }
18record NFA { 전이표: Array<Array<전이>>, 시작: int, 끝: int }
19record 진행 { 켜진상태: Array<bool>, 작업량: int }
20enum 일치 { 없음, 길이(int), 초과 }
21record 시도 { 결과: 일치, 작업량: int }
22record 점 { x: int, y: int }
24// 시험 문자열 하나에서 훑는 전이 수의 한계입니다. 긴 문자열에 (a*)*b 같은 병리적 패턴을 넣어도 화면이 멈추지 않습니다.
25let 작업한계 = 100000
26let 메타문자집합 = Set.of(".", "*", "+", "?", "(", ")", "[", "]", "\{", "\}", "|", "^", "$", "\\", "/", "-")
27let 빈패턴안내 = "<div class=\"meta\">첫 줄에 정규식, 그 아래 줄에 시험 문자열을 입력하세요.</div>"
28let 복잡함안내 = "시험 문자열이 너무 길거나 패턴이 복잡합니다. 더 짧은 문자열로 시도하세요."
29let 강조여는표시 = "<mark style=\"background:#111;color:#fff;padding:0 1px\">"
31// 공용 도우미 시작 (이스케이프 오류알림 글자인가 결과풀기)
32// 여러 도구가 같은 원본을 씁니다. 여기서 고치지 않고 원본에서 고친 뒤 다시 생성합니다.
34// 사용자 입력을 HTML 에 넣기 전에 반드시 거칩니다.
35function 이스케이프(원문: string) -> string {
36 원문.replace("&", "&amp;").replace("<", "&lt;").replace(">", "&gt;").replace("\"", "&quot;")
39// 문구는 고정 문장이거나 이미 이스케이프한 값이어야 합니다.
40function 오류알림(문구: string) -> string {
41 "<div class=\"err\">{문구}</div>"
44// 위치가 글자들 끝을 넘으면 거짓입니다.
45function 글자인가(글자들: Array<string>, 위치: int, 글자: string) -> bool {
46 위치 < 글자들.length && 글자들[위치] == 글자
49// 성공 값과 안내가 모두 바로 보여 줄 HTML 조각일 때 진입점에서 한 번 풉니다. 토파즈 과제 'Result 오류 쪽 변환과 풀기' 의 우회입니다.
50function 결과풀기(값: Result<string, string>) -> string {
51 match 값 {
52 case Ok(결과) => 결과
53 case Err(안내) => 안내
54 }
57// 공용 도우미 끝
59function 코드값(글자: string) -> int {
60 글자.codePointAt(0) ?? 0
63// 대문자 약식은 여집합 범위로 둡니다. 클래스의 부정은 클래스 전체에 하나뿐이라 [^\D] 같은 조합도 이렇게 맞습니다. 1114111 은 U+10FFFF 이고 16진 리터럴이 없어 10진으로 씁니다. 토파즈 과제 '16진 정수 리터럴' 의 우회입니다.
64function 약식범위(표지: string) -> Option<Array<범위>> {
65 match 표지 {
66 case "d" => Some([범위 { 시작: 48, 끝: 57 }])
67 case "w" => Some([범위 { 시작: 48, 끝: 57 }, 범위 { 시작: 65, 끝: 90 }, 범위 { 시작: 97, 끝: 122 }, 범위 { 시작: 95, 끝: 95 }])
68 case "s" => Some([범위 { 시작: 9, 끝: 13 }, 범위 { 시작: 32, 끝: 32 }])
69 case "D" => Some([범위 { 시작: 0, 끝: 47 }, 범위 { 시작: 58, 끝: 1114111 }])
70 case "W" => Some([
71 범위 { 시작: 0, 끝: 47 },
72 범위 { 시작: 58, 끝: 64 },
73 범위 { 시작: 91, 끝: 94 },
74 범위 { 시작: 96, 끝: 96 },
75 범위 { 시작: 123, 끝: 1114111 },
76 ])
77 case "S" => Some([범위 { 시작: 0, 끝: 8 }, 범위 { 시작: 14, 끝: 31 }, 범위 { 시작: 33, 끝: 1114111 }])
78 case _ => None
79 }
82// 위치는 역슬래시를 가리킵니다.
83function 이스케이프풀기(글자들: Array<string>, 위치: int) -> Result<풀린이스케이프, string> {
84 if 위치 + 1 >= 글자들.length { return Err("역슬래시 뒤에 문자가 필요합니다") }
85 let 표지 = 글자들[위치 + 1]
86 match 약식범위(표지) {
87 case Some(범위들) => Ok(풀린이스케이프.약식(범위들))
88 case None => {
89 if 표지 in 메타문자집합 { Ok(풀린이스케이프.낱글자(코드값(표지))) } else { Err("알 수 없는 이스케이프: \\" + 표지) }
90 }
91 }
94// 위치는 시작 글자 바로 뒤입니다. 붙임표 뒤가 ']' 이면 붙임표는 글자이고, 범위 끝 글자는 이스케이프를 풀지 않습니다.
95function 범위읽기(글자들: Array<string>, 시작코드: int, 위치: int) -> Result<읽은범위, string> {
96 if !글자인가(글자들, 위치, "-") || 위치 + 1 >= 글자들.length || 글자들[위치 + 1] == "]" {
97 return Ok(읽은범위 { 범위들: [범위 { 시작: 시작코드, 끝: 시작코드 }], 다음: 위치 })
98 }
99 let 끝코드 = 코드값(글자들[위치 + 1])
100 if 끝코드 < 시작코드 { return Err("잘못된 문자 범위입니다") }
101 Ok(읽은범위 { 범위들: [범위 { 시작: 시작코드, 끝: 끝코드 }], 다음: 위치 + 2 })
104function 클래스항목읽기(글자들: Array<string>, 위치: int) -> Result<읽은범위, string> {
105 if 글자들[위치] != "\\" { return 범위읽기(글자들, 코드값(글자들[위치]), 위치 + 1) }
106 match 이스케이프풀기(글자들, 위치)? {
107 case 약식(범위들) => Ok(읽은범위 { 범위들: 범위들, 다음: 위치 + 2 })
108 case 낱글자(코드) => 범위읽기(글자들, 코드, 위치 + 2)
109 }
112// 위치는 '[' 바로 뒤입니다. 라벨은 괄호까지 포함한 원문입니다.
113function 클래스읽기(글자들: Array<string>, 위치: int) -> Result<읽은식, string> {
114 let 부정 = 글자인가(글자들, 위치, "^")
115 let mut 범위들: Array<범위> = []
116 let mut i = if 부정 { 위치 + 1 } else { 위치 }
117 while i < 글자들.length && 글자들[i] != "]" {
118 let 항목 = 클래스항목읽기(글자들, i)?
119 for 항목범위 in 항목.범위들 { 범위들.push(항목범위) }
120 i = 항목.다음
121 }
122 if i >= 글자들.length { return Err("'['에 대응하는 ']'가 없습니다") }
123 if 범위들.length == 0 { return Err("빈 문자 클래스입니다") }
124 let 라벨 = 글자들.slice(위치 - 1, i + 1).join("")
125 Ok(읽은식 { 값: 식.한글자(라벨, 부정, 범위들), 다음: i + 1 })
128// 연결읽기가 입력 끝과 | ) 수량자를 먼저 걸러 내므로 여기서는 원자가 늘 있습니다.
129function 원자읽기(글자들: Array<string>, 위치: int) -> Result<읽은식, string> {
130 let 글자 = 글자들[위치]
131 match 글자 {
132 case "(" => {
133 let 안 = 택일읽기(글자들, 위치 + 1)?
134 if 글자인가(글자들, 안.다음, ")") {
135 Ok(읽은식 { 값: 안.값, 다음: 안.다음 + 1 })
136 } else {
137 Err("여는 괄호에 대응하는 닫는 괄호가 없습니다")
138 }
139 }
140 case "[" => 클래스읽기(글자들, 위치 + 1)
141 case "\\" => {
142 let 범위들 = match 이스케이프풀기(글자들, 위치)? {
143 case 약식(약식범위들) => 약식범위들
144 case 낱글자(코드) => [범위 { 시작: 코드, 끝: 코드 }]
145 }
146 Ok(읽은식 { 값: 식.한글자("\\" + 글자들[위치 + 1], false, 범위들), 다음: 위치 + 2 })
147 }
148 // 점은 줄바꿈만 빼고 맞춥니다.
149 case "." => Ok(읽은식 { 값: 식.한글자(".", true, [범위 { 시작: 10, 끝: 10 }]), 다음: 위치 + 1 })
150 case _ => {
151 let 코드 = 코드값(글자)
152 Ok(읽은식 { 값: 식.한글자(글자, false, [범위 { 시작: 코드, 끝: 코드 }]), 다음: 위치 + 1 })
153 }
154 }
157function 수량자읽기(글자들: Array<string>, 위치: int) -> Option<수량자> {
158 if 위치 >= 글자들.length { return None }
159 match 글자들[위치] {
160 case "*" => Some("*")
161 case "+" => Some("+")
162 case "?" => Some("?")
163 case _ => None
164 }
167// 수량자는 원자 하나에 하나만 붙습니다. a** 의 두 번째 * 는 연결읽기에서 오류가 됩니다.
168function 반복읽기(글자들: Array<string>, 위치: int) -> Result<읽은식, string> {
169 let 원자 = 원자읽기(글자들, 위치)?
170 match 수량자읽기(글자들, 원자.다음) {
171 case Some(종류) => Ok(읽은식 { 값: 식.반복(원자.값, 종류), 다음: 원자.다음 + 1 })
172 case None => Ok(원자)
173 }
176function 연결읽기(글자들: Array<string>, 위치: int) -> Result<읽은식, string> {
177 let mut 항들: Array<식> = []
178 let mut i = 위치
179 while i < 글자들.length {
180 match 글자들[i] {
181 case "|" | ")" => { break }
182 case "*" | "+" | "?" => { return Err("수량자 앞에 식이 필요합니다") }
183 case _ => {
184 let 항 = 반복읽기(글자들, i)?
185 항들.push(항.값)
186 i = 항.다음
187 }
188 }
189 }
190 Ok(읽은식 { 값: 식.연결(항들), 다음: i })
193function 택일읽기(글자들: Array<string>, 위치: int) -> Result<읽은식, string> {
194 let 첫 = 연결읽기(글자들, 위치)?
195 let mut 가지들 = [첫.값]
196 let mut i = 첫.다음
197 while 글자인가(글자들, i, "|") {
198 let 가지 = 연결읽기(글자들, i + 1)?
199 가지들.push(가지.값)
200 i = 가지.다음
201 }
202 Ok(읽은식 { 값: 식.택일(가지들), 다음: i })
205// 택일읽기는 짝 없는 ')' 에서만 입력 끝 전에 멈춥니다.
206function 식읽기(글자들: Array<string>) -> Result<식, string> {
207 let 읽음 = 택일읽기(글자들, 0)?
208 if 읽음.다음 < 글자들.length { return Err("예상치 못한 기호 '{글자들[읽음.다음]}'") }
209 Ok(읽음.값)
212function 입실론간선(출발: int, 도착: int) -> 간선 {
213 간선 { 출발: 출발, 이동: 전이 { 라벨: "ε", 대상: 도착, 종류: 전이종류.입실론 } }
216function 펼치기(묶음들: Array<Array<간선>>) -> Array<간선> {
217 [for 묶음 in 묶음들 for 하나 in 묶음 => 하나]
220// 상태 번호와 상태마다의 간선 순서는 그림의 배치와 작업량 셈을 정하므로, 자식을 먼저 엮고 새 상태와 간선을 뒤에 붙이는 순서를 지킵니다.
221function 엮기(값: 식, 상태수: int) -> 조각 {
222 match 값 {
223 case 한글자(라벨, 부정, 범위들) => {
224 let 문자전이 = 전이 { 라벨: 라벨, 대상: 상태수 + 1, 종류: 전이종류.문자(부정, 범위들) }
225 조각 { 시작: 상태수, 끝: 상태수 + 1, 간선들: [간선 { 출발: 상태수, 이동: 문자전이 }], 상태수: 상태수 + 2 }
226 }
227 case 반복(안, 종류) => 반복엮기(엮기(안, 상태수), 종류)
228 case 연결(항들) => 연결엮기(항들, 상태수)
229 case 택일(가지들) => 택일엮기(가지들, 상태수)
230 }
233function 반복엮기(속: 조각, 종류: 수량자) -> 조각 {
234 let 새시작 = 속.상태수
235 let 새끝 = 속.상태수 + 1
236 match 종류 {
237 case "*" => {
238 let 잇기 = [입실론간선(새시작, 속.시작), 입실론간선(새시작, 새끝), 입실론간선(속.끝, 속.시작), 입실론간선(속.끝, 새끝)]
239 조각 { 시작: 새시작, 끝: 새끝, 간선들: 펼치기([속.간선들, 잇기]), 상태수: 새끝 + 1 }
240 }
241 // + 는 원자의 시작을 그대로 쓰므로 새 상태가 끝 하나뿐입니다.
242 case "+" => {
243 let 잇기 = [입실론간선(속.끝, 속.시작), 입실론간선(속.끝, 새시작)]
244 조각 { 시작: 속.시작, 끝: 새시작, 간선들: 펼치기([속.간선들, 잇기]), 상태수: 새시작 + 1 }
245 }
246 case "?" => {
247 let 잇기 = [입실론간선(새시작, 속.시작), 입실론간선(새시작, 새끝), 입실론간선(속.끝, 새끝)]
248 조각 { 시작: 새시작, 끝: 새끝, 간선들: 펼치기([속.간선들, 잇기]), 상태수: 새끝 + 1 }
249 }
250 }
253function 연결엮기(항들: Array<식>, 상태수: int) -> 조각 {
254 if 항들.length == 0 {
255 return 조각 { 시작: 상태수, 끝: 상태수 + 1, 간선들: [입실론간선(상태수, 상태수 + 1)], 상태수: 상태수 + 2 }
256 }
257 let 첫 = 엮기(항들[0], 상태수)
258 let mut 끝 = 첫.끝
259 let mut 다음상태 = 첫.상태수
260 let mut 묶음들 = [첫.간선들]
261 for 항 in 항들.slice(1, 항들.length) {
262 let 엮음 = 엮기(항, 다음상태)
263 묶음들.push(엮음.간선들)
264 묶음들.push([입실론간선(끝, 엮음.시작)])
265 끝 = 엮음.끝
266 다음상태 = 엮음.상태수
267 }
268 조각 { 시작: 첫.시작, 끝: 끝, 간선들: 펼치기(묶음들), 상태수: 다음상태 }
271// 가지가 셋 이상이면 앞 가지들을 묶은 조각을 다시 새 시작과 새 끝으로 감쌉니다.
272function 택일엮기(가지들: Array<식>, 상태수: int) -> 조각 {
273 let 첫 = 엮기(가지들[0], 상태수)
274 let mut 시작 = 첫.시작
275 let mut 끝 = 첫.끝
276 let mut 다음상태 = 첫.상태수
277 let mut 묶음들 = [첫.간선들]
278 for 가지 in 가지들.slice(1, 가지들.length) {
279 let 엮음 = 엮기(가지, 다음상태)
280 let 새시작 = 엮음.상태수
281 let 새끝 = 엮음.상태수 + 1
282 묶음들.push(엮음.간선들)
283 묶음들.push([입실론간선(새시작, 시작), 입실론간선(새시작, 엮음.시작), 입실론간선(끝, 새끝), 입실론간선(엮음.끝, 새끝)])
284 시작 = 새시작
285 끝 = 새끝
286 다음상태 = 새끝 + 1
287 }
288 조각 { 시작: 시작, 끝: 끝, 간선들: 펼치기(묶음들), 상태수: 다음상태 }
291function NFA만들기(값: 식) -> NFA {
292 let 엮음 = 엮기(값, 0)
293 let mut 전이표: Array<Array<전이>> = [for i in 0..<엮음.상태수 => []]
294 for 하나 in 엮음.간선들 { 전이표[하나.출발].push(하나.이동) }
295 NFA { 전이표: 전이표, 시작: 엮음.시작, 끝: 엮음.끝 }
298function 입실론인가(종류: 전이종류) -> bool {
299 match 종류 {
300 case 입실론 => true
301 case 문자(_, _) => false
302 }
305function 문자일치인가(이동: 전이, 코드: int) -> bool {
306 match 이동.종류 {
307 case 입실론 => false
308 case 문자(부정, 범위들) => {
309 let 안에있음 = 범위들.reduce(false, (있음, 구간) => 있음 || (코드 >= 구간.시작 && 코드 <= 구간.끝))
310 if 부정 { !안에있음 } else { 안에있음 }
311 }
312 }
315// 작업량은 켜진 상태에서 훑은 전이마다 하나씩 셉니다. 상태 번호 순서로 한 바퀴 돌며 바로 켜는 고정점 반복이라 바퀴 수도 이 순서를 따릅니다.
316function 입실론닫힘(전이표: Array<Array<전이>>, 앞: 진행) -> 진행 {
317 let mut 켜짐 = 앞.켜진상태.slice(0, 앞.켜진상태.length)
318 let mut 작업량 = 앞.작업량
319 let mut 바뀜 = true
320 while 바뀜 {
321 바뀜 = false
322 for 상태 in 0..<전이표.length {
323 if 켜짐[상태] {
324 for 이동 in 전이표[상태] {
325 작업량 += 1
326 if 입실론인가(이동.종류) && !켜짐[이동.대상] {
327 켜짐[이동.대상] = true
328 바뀜 = true
329 }
330 }
331 }
332 }
333 }
334 진행 { 켜진상태: 켜짐, 작업량: 작업량 }
337function 글자건너기(전이표: Array<Array<전이>>, 앞: 진행, 코드: int) -> 진행 {
338 let mut 켜짐 = [for i in 0..<전이표.length => false]
339 let mut 작업량 = 앞.작업량
340 for 상태 in 0..<전이표.length {
341 if 앞.켜진상태[상태] {
342 for 이동 in 전이표[상태] {
343 작업량 += 1
344 if 문자일치인가(이동, 코드) { 켜짐[이동.대상] = true }
345 }
346 }
347 }
348 진행 { 켜진상태: 켜짐, 작업량: 작업량 }
351// 작업량은 한 시험 문자열의 모든 시작 위치에 걸쳐 누적하고, 한계는 글자를 하나 읽기 전에만 봅니다.
352// 켜진 상태가 없으면 더 읽어도 일치가 늘지 않으므로 거기서 멈춥니다.
353function 가장긴일치(기계: NFA, 코드들: Array<int>, 시작위치: int, 작업량: int) -> 시도 {
354 let 처음 = 진행 { 켜진상태: [for 상태 in 0..<기계.전이표.length => 상태 == 기계.시작], 작업량: 작업량 }
355 let mut 현재 = 입실론닫힘(기계.전이표, 처음)
356 let mut 결과 = if 현재.켜진상태[기계.끝] { 일치.길이(0) } else { 일치.없음 }
357 let mut 위치 = 시작위치
358 while 위치 < 코드들.length && (true in 현재.켜진상태) {
359 if 현재.작업량 > 작업한계 { return 시도 { 결과: 일치.초과, 작업량: 현재.작업량 } }
360 현재 = 입실론닫힘(기계.전이표, 글자건너기(기계.전이표, 현재, 코드들[위치]))
361 위치 += 1
362 if 현재.켜진상태[기계.끝] { 결과 = 일치.길이(위치 - 시작위치) }
363 }
364 시도 { 결과: 결과, 작업량: 현재.작업량 }
367function 빈일치인가(결과: 일치) -> bool {
368 match 결과 {
369 case 길이(n) => n == 0
370 case 없음 | 초과 => false
371 }
374// 빈 일치는 강조하지 않고 한 글자를 넘긴 뒤 건수 줄에서 따로 알립니다. 문자열 끝 위치의 빈 일치도 셉니다.
375function 일치표시(기계: NFA, 본문: string) -> string {
376 let 글자들 = 본문.scalars()
377 let 코드들 = 글자들.map(코드값)
378 let mut 조각들: Array<string> = []
379 let mut 자리 = 0
380 let mut 작업량 = 0
381 let mut 일치수 = 0
382 let mut 빈일치 = false
383 while 자리 < 글자들.length {
384 let 이번 = 가장긴일치(기계, 코드들, 자리, 작업량)
385 작업량 = 이번.작업량
386 let 일치길이 = match 이번.결과 {
387 case 초과 => return 오류알림(복잡함안내)
388 case 길이(n) => n
389 case 없음 => 0
390 }
391 빈일치 = 빈일치 || 빈일치인가(이번.결과)
392 if 일치길이 > 0 {
393 조각들.push(강조여는표시 + 이스케이프(글자들.slice(자리, 자리 + 일치길이).join("")) + "</mark>")
394 자리 += 일치길이
395 일치수 += 1
396 } else {
397 조각들.push(이스케이프(글자들[자리]))
398 자리 += 1
399 }
400 }
401 빈일치 = 빈일치 || 빈일치인가(가장긴일치(기계, 코드들, 글자들.length, 작업량).결과)
402 let 빈일치안내 = if 빈일치 { ", 빈 문자열도 일치합니다" } else { "" }
403 let 머리 = "<div class=\"meta\">일치 {일치수}건{빈일치안내}</div>"
404 if 본문 == "" { 머리 } else { 머리 + "<div class=\"out\" style=\"white-space:pre-wrap\">" + 조각들.join("") + "</div>" }
407// 시작에서 너비 우선으로 층을 매깁니다. 닿지 않는 상태는 0층에 둡니다.
408function 층매기기(전이표: Array<Array<전이>>, 시작: int) -> Array<int> {
409 let mut 층들 = [for i in 0..<전이표.length => -1]
410 층들[시작] = 0
411 let mut 대기열 = [시작]
412 let mut 머리 = 0
413 while 머리 < 대기열.length {
414 let 현재 = 대기열[머리]
415 머리 += 1
416 for 이동 in 전이표[현재] {
417 if 층들[이동.대상] == -1 {
418 층들[이동.대상] = 층들[현재] + 1
419 대기열.push(이동.대상)
420 }
421 }
422 }
423 층들.map(층 => 층.atLeast(0))
426// 화살촉이 원 테두리에 닿도록 선 끝을 반지름 15 만큼 당깁니다. 톰슨 구성은 자기 자신으로 가는 전이를 만들지 않아 고리는 그리지 않습니다.
427function 전이그리기(출발: 점, 도착: 점, 라벨: string, 점선인가: bool) -> string {
428 let 점선 = if 점선인가 { " stroke-dasharray=\"3 2\"" } else { "" }
429 let 가로차 = 도착.x - 출발.x
430 let 끝x = if 가로차 > 0 { 도착.x - 15 } else if 가로차 < 0 { 도착.x + 15 } else { 도착.x }
431 let 끝y = if 가로차 != 0 { 도착.y } else if 도착.y > 출발.y { 도착.y - 15 } else { 도착.y + 15 }
432 let 가운데x = (출발.x + 도착.x) / 2
433 let 가운데y = (출발.y + 도착.y) / 2
434 [
435 "<line x1=\"{출발.x}\" y1=\"{출발.y}\" x2=\"{끝x}\" y2=\"{끝y}\" stroke=\"#111\"{점선} marker-end=\"url(#화살)\" />",
436 "<text x=\"{가운데x}\" y=\"{가운데y - 4}\" font-size=\"11\" text-anchor=\"middle\" font-family=\"monospace\" fill=\"#111\">{이스케이프(라벨)}</text>",
437 ].join("")
440// 시작 상태에는 들어오는 화살표를, 수락 상태에는 바깥 원을 더합니다.
441function 상태그리기(중심: 점, 시작인가: bool, 끝인가: bool) -> string {
442 [
443 if 끝인가 { "<circle cx=\"{중심.x}\" cy=\"{중심.y}\" r=\"17\" fill=\"none\" stroke=\"#111\" />" } else { "" },
444 "<circle cx=\"{중심.x}\" cy=\"{중심.y}\" r=\"13\" fill=\"#fff\" stroke=\"#111\" />",
445 if 시작인가 { "<line x1=\"{중심.x - 32}\" y1=\"{중심.y}\" x2=\"{중심.x - 15}\" y2=\"{중심.y}\" stroke=\"#111\" marker-end=\"url(#화살)\" />" } else { "" },
446 ].join("")
449// 층마다 가로 95, 층 안의 상태마다 세로 64 이고 층 안의 순서는 상태 번호 순입니다.
450function NFA그리기(기계: NFA) -> string {
451 let 상태수 = 기계.전이표.length
452 let 층들 = 층매기기(기계.전이표, 기계.시작)
453 let 층수 = 층들.reduce(0, (최대, 층) => 최대.atLeast(층)) + 1
454 let mut 층별개수 = [for i in 0..<층수 => 0]
455 let mut 점들: Array<점> = []
456 for 층 in 층들 {
457 점들.push(점 { x: 55 + 층 * 95, y: 50 + 층별개수[층] * 64 })
458 층별개수[층] += 1
459 }
460 let 너비 = 70 + 층수 * 95
461 let 높이 = 60 + 층별개수.reduce(1, (최대, 개수) => 최대.atLeast(개수)) * 64
462 let 전이들 = [for 상태 in 0..<상태수 for 이동 in 기계.전이표[상태] => 전이그리기(점들[상태], 점들[이동.대상], 이동.라벨, 입실론인가(이동.종류))]
463 let 상태들 = [for 상태 in 0..<상태수 => 상태그리기(점들[상태], 상태 == 기계.시작, 상태 == 기계.끝)]
464 [
465 "<svg viewBox=\"0 0 {너비} {높이}\" width=\"100%\" style=\"border:1px solid #e3e3e3;margin-top:12px;max-width:100%\">",
466 "<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>",
467 전이들.join(""),
468 상태들.join(""),
469 "</svg>",
470 ].join("")
473function 정규식보기(입력: string) -> Result<string, string> {
474 let 줄들 = 입력.split("\n")
475 let 패턴 = 줄들[0]
476 if 패턴 == "" { return Err(빈패턴안내) }
477 let 기계 = match 식읽기(패턴.scalars()) {
478 case Ok(읽은값) => NFA만들기(읽은값)
479 case Err(메시지) => return Err(오류알림("정규식 오류: {이스케이프(메시지)}"))
480 }
481 let 본문 = 줄들.slice(1, 줄들.length).join("\n")
482 Ok(NFA그리기(기계) + 일치표시(기계, 본문))
485input() |> 정규식보기 |> 결과풀기 |> print

SHA256 62f94966fbb043279804eceb61f961a0da12d4b0c3ad4a16afa24b8ff0481972