HTML을 μ •κ·œ ν‘œν˜„μ‹λ§ŒμœΌλ‘œ νŒŒμ‹±ν•  수 μžˆμ„κΉŒ?

    HTML을 μ •κ·œ ν‘œν˜„μ‹λ§ŒμœΌλ‘œ νŒŒμ‹±ν•  수 μžˆμ„κΉŒ?


    이번 ν¬μŠ€νŒ…μ—μ„œλŠ” μ΄λ¦„λ§Œ 듀어도 땀이 λ‚˜κΈ° μ‹œμž‘ν•˜λŠ” λ§ˆμ„±μ˜ κ·Έ 녀석, μ •κ·œ ν‘œν˜„μ‹μ— λŒ€ν•œ μ„Έ 번째 이야기λ₯Ό 해보렀고 ν•œλ‹€.

    ν•„μžλ„ μ•Œκ³  μ—¬λŸ¬λΆ„λ„ μ•Œκ³  세상 λͺ¨λ‘κ°€ λ‹€ μ•Œλ‹€μ‹œν”Ό μ •κ·œ ν‘œν˜„μ‹μ€ ν‰μ†Œ μ•…λž„ν•œ λ¬Έλ²•μœΌλ‘œ 유λͺ…ν•œ 녀석이기 λ•Œλ¬Έμ—, μ§€λ‚œ 번 ν•„μžκ°€ 썼던 λΆˆκ·œμΉ™ μ†μ—μ„œ κ·œμΉ™μ„ μ°Ύμ•„λ‚΄λŠ” μ •κ·œ ν‘œν˜„μ‹ ν¬μŠ€νŒ…μ²˜λŸΌ μ •κ·œ ν‘œν˜„μ‹μ˜ 문법을 λΆ„μ„ν•˜κ³  μ‚¬μš©λ²•μ„ μ•Œλ €μ£ΌλŠ” ν¬μŠ€νŒ…λ“€ λ˜ν•œ ꡉμž₯히 λ§Žλ‹€.

    반면 κ·Έ μ•…λž„ν•œ 문법에 μ΅μˆ™ν•΄μ§€κ³  λ‚˜λ©΄ λ¬Έμžμ—΄κ³Ό κ΄€λ ¨λœ ꡉμž₯히 λ‹€μ–‘ν•œ 문제λ₯Ό 짧은 μ •κ·œ ν‘œν˜„μ‹λ§ŒμœΌλ‘œ λΉ λ₯΄κ²Œ ν•΄κ²°ν•  수 있기 λ•Œλ¬Έμ—, κ°œλ°œμžλ“€μ—κ²ŒλŠ” μƒλ‹Ήν•œ μ• μ¦μ˜ λŒ€μƒμ΄λΌκ³  ν•  수 μžˆλ‹€. (ν•„μž μ£Όλ³€ κ°œλ°œμžλ“€λ„ λŒ€λΆ€λΆ„ μ •κ·œμ‹ λ³„λ‘œ μ•ˆ μ’‹μ•„ν•œλ‹€β€¦)

    κ·Έλž˜μ„œ μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ μ–΄λ–€ 문제λ₯Ό ν•΄κ²°ν•  λ•Œ, ꡬ글링을 톡해 찾은 μ •κ·œ ν‘œν˜„μ‹μ„ λ³΅λΆ™ν•˜κ±°λ‚˜ regexr 같은 μ‚¬μ΄νŠΈμ—μ„œ μ‚½μ§ˆμ„ ν•˜λ©° ν•΄κ²°ν•˜λŠ” κ²½μš°κ°€ λ§Žμ€λ°, 이 κ³Όμ •μ—μ„œ 잘λͺ»λœ μ •κ·œ ν‘œν˜„μ‹μ„ 아무 검증없이 μ‚¬μš©ν•˜μ—¬ ν”Όλ₯Ό λ³΄λŠ” μΌ€μ΄μŠ€κ°€ μ™•μ™• μ‘΄μž¬ν•œλ‹€.

    λ¬Όλ‘  μ–΄λ–€ μ •κ·œ ν‘œν˜„μ‹μ„ 보고 이게 μ˜¬λ°”λ₯Έ μ •κ·œ ν‘œν˜„μΈμ§€ μ•„λ‹Œμ§€λ₯Ό νŒŒμ•…ν•˜λŠ” 것은 쉽지 μ•Šλ‹€. ν•˜μ§€λ§Œ μ •κ·œ ν‘œν˜„μ‹μ΄λΌλŠ” 것이 μ™œ 세상에 λ‚˜μ˜€κ²Œ λ˜μ—ˆλŠ”μ§€, μ–΄λ–€ ν™˜κ²½μ—μ„œ κ΅¬λ™λ˜λŠ” 것을 μ „μ œλ‘œ λ§Œλ“€μ–΄μ§„ 것인지뢀터 μ•Œκ³  λ‚˜λ©΄ μžμ—°μŠ€λŸ½κ²Œ μ •κ·œ ν‘œν˜„μ‹μ˜ ν•œκ³„μ λ„ 이해할 수 있게 λœλ‹€.

    이번 ν¬μŠ€νŒ…μ—μ„œλŠ” ν•„μžμ™€ 같은 ν”„λ‘ νŠΈμ—”λ“œ κ°œλ°œμžμ—κ²ŒλŠ” λ„ˆλ¬΄λ‚˜λ„ μ΅μˆ™ν•œ HTMLμ΄λΌλŠ” μ–Έμ–΄λ₯Ό μ •κ·œ ν‘œν˜„μ‹λ§ŒμœΌλ‘œ νŒŒμ‹±ν•  수 μžˆλŠ”κ°€λΌλŠ” μ§ˆλ¬Έμ„ 톡해 μ •κ·œ ν‘œν˜„μ‹μ΄ 개발된 λͺ©μ κ³Ό ν•œκ³„μ— λŒ€ν•΄μ„œ 이야기 해보렀고 ν•œλ‹€.

    잘λͺ»λœ μ •κ·œ ν‘œν˜„μ‹μ΄ λ§Œλ“œλŠ” μ•Όκ·Ό 상황

    본격적인 μ„€λͺ…에 듀어가기에 μ•žμ„œ, 잘λͺ» μž‘μ„±λœ μ •κ·œ ν‘œν˜„μ‹μ΄ μ–΄λ–€ 상황을 뢈러올 수 μžˆλŠ”μ§€λΆ€ν„° ν•¨κ»˜ μ‚΄νŽ΄λ³΄μž.

    ν•„μžκ°€ 이 ν¬μŠ€νŒ…μ—μ„œ μ΄μ•ΌκΈ°ν•˜λŠ” 잘λͺ» μž‘μ„±λœ μ •κ·œ ν‘œν˜„μ‹μ€ β€œμ •κ·œ ν‘œν˜„μ‹μ΄ aλ₯Ό μ°Ύμ•„μ•Ό ν•˜λŠ”λ°, bλ₯Ό μ°Ύμ•˜μ–΄β€μ™€ 같은 λŠλ‚Œμ€ μ•„λ‹ˆλ‹€. 사싀 이런 λ¬Έμ œλŠ” κ·Έλƒ₯ μ •κ·œ ν‘œν˜„μ‹ 문법이 μ΅μˆ™ν•˜μ§€ μ•Šμ•„μ„œ μ‹€μˆ˜ν•œ 것이기 λ•Œλ¬Έμ—, μ‹œκ°„μ„ κ°€μ§€κ³  μ •κ·œ ν‘œν˜„μ‹μ„ 쑰금만 μžμ„Ένžˆ λ“€μ—¬λ‹€ 보면 λˆ„κ΅¬λ“ μ§€ 잘λͺ» μž‘μ„±ν•œ ν‘œν˜„μ„ μ°Ύμ•„λ‚Ό 수 μžˆλ‹€.

    ν•„μžκ°€ μ΄μ•ΌκΈ°ν•˜κ³  싢은 것은 μ •κ·œ ν‘œν˜„μ‹μ΄ μž‘λ™ν•˜λŠ” 원리λ₯Ό 잘 λͺ¨λ₯΄κ³  μ‚¬μš©ν–ˆμ„ λ•Œ λ°œμƒν•  수 μžˆλŠ” 퍼포먼슀 μ΄μŠˆλ‚˜, ν˜Ήμ€ μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œλŠ” μ•„μ˜ˆ 해결이 λΆˆκ°€λŠ₯ν•œ 문제λ₯Ό μ–΄λ–»κ²Œλ“  ν•΄κ²°ν•˜λ €κ³  λΆ™μž‘κ³  μžˆλŠ” μŠ¬ν”ˆ 상황듀이닀.

    λ¬Όλ‘  κ°œλ°œμžλ“€μ΄ 이런 원리 같은 건 λͺ°λΌλ„ μ •κ·œ ν‘œν˜„μ‹μ„ μ‚¬μš©ν•  수 μžˆλ„λ‘ μ •κ·œ ν‘œν˜„μ‹ μ—”μ§„μ΄λΌλŠ” 좔상화 계측이 μ‘΄μž¬ν•˜λŠ” κ²ƒμ΄κΈ°λŠ” ν•˜μ§€λ§Œ, κ·Έλ ‡λ‹€κ³  λ„ˆλ¬΄ μ—”μ§„λ§Œ λ―Ώκ³  μžˆλ‹€κ°€λŠ” λ―Ώμ—ˆλ˜ μ •κ·œ ν‘œν˜„μ‹ν•œν…Œ λ’·ν†΅μˆ˜λ₯Ό μ–»μ–΄λ§žλŠ” 상황이 μ–Όλ§ˆλ“ μ§€ λ°œμƒν•  수 μžˆλ‹€.

    μ˜μ›νžˆ λλ‚˜μ§€ μ•ŠλŠ” μ •κ·œ ν‘œν˜„μ‹

    첫 번째 λ’·ν†΅μˆ˜ 상황은 μ •κ·œ ν‘œν˜„μ‹μ΄ νŒ¨ν„΄μ„ λ§€μΉ­ν•˜λŠ” 과정을 잘 λͺ¨λ₯΄κ³  μ‚¬μš©ν–ˆμ„ λ•Œ λ°œμƒν•  수 μžˆλŠ” 퍼포먼슀 μ΄μŠˆμ΄λ‹€.

    μ •κ·œ ν‘œν˜„μ‹μ€ DFS(깊이 μš°μ„  탐색) μ•Œκ³ λ¦¬μ¦˜μ„ 기반으둜 ν•˜λŠ” λ°±νŠΈλž˜ν‚Ή μ•Œκ³ λ¦¬μ¦˜μ„ μ‚¬μš©ν•˜μ—¬ λ¬Έμžμ—΄μ˜ νŒ¨ν„΄μ„ λ§€μΉ­ν•œλ‹€. 즉, μ–΄λ–€ λ…Έλ“œλ₯Ό μ–΄λ–€ 쑰건으둜 νƒμƒ‰ν•˜λƒμ— λ”°λΌμ„œ νŒ¨ν„΄μ„ λ§€μΉ­ν•˜λŠ” μ‹œκ°„μ΄ 생각보닀 많이 κΈΈμ–΄μ§ˆ μˆ˜λ„ μžˆλ‹€λŠ” 것이닀.

    특히 μžλ°”μŠ€ν¬λ¦½νŠΈ 엔진에 ν¬ν•¨λ˜μ–΄μžˆλŠ” μ •κ·œ ν‘œν˜„μ‹ 엔진은 비동기가 μ•„λ‹Œ λ™κΈ°μ‹μœΌλ‘œ μž‘λ™ν•˜κΈ° λ•Œλ¬Έμ— μ •κ·œ ν‘œν˜„μ‹μ΄ νŒ¨ν„΄ λ§€μΉ­ν•˜λŠλΌ μ‹œκ°„μ„ 였래 μž‘μ•„λ¨ΉλŠ”λ‹€λ©΄, κ·Έ μ‹œκ°„ λ™μ•ˆ λ‹€λ₯Έ 일을 μ „ν˜€ μˆ˜ν–‰ν•  수 μ—†λŠ” λˆˆλ¬Όλ‚˜λŠ” 상황이 λ°œμƒν•  μˆ˜λ„ μžˆλ‹€.

    이게 μ–΄λ–€ 상황인지 이해가 λ˜μ§€ μ•ŠλŠ”λ‹€λ©΄ λΈŒλΌμš°μ €μ—μ„œ μƒˆ 탭을 μ—΄κ³  μ•„λž˜ μ½”λ“œλ₯Ό μ½˜μ†”μ—μ„œ 싀행해보도둝 ν•˜μž. (이 νƒ­μ—μ„œ ν•˜λ©΄ 글을 λͺ» μ½μ„ν…Œλ‹ˆ λ‹€λ₯Έ νƒ­μ—μ„œ ν•˜μžβ€¦)

    // λ¬Έμžμ—΄ 길이와 상관없이 무쑰건 탐색 8회
    /^(\d+)*$/.test('123123123123123123');
    // 탐색 26회
    // 이 μ •λ„λŠ” 금방 λλ‚œλ‹€
    /^(\d+)*$/.test('123!');
    
    // 탐색 98,306회
    /^(\d+)*$/.test('123123123123123!'); 
    
    // μ–΄...? 연산이 μ•ˆ λλ‚œλ‹€....
    /^(\d+)*$/.test('123123123123123123123123123123123123123123!'); 

    첫 번째 μ˜ˆμ‹œλŠ” λ¬Έμžμ—΄ 길이와 상관없이 무쑰건 8회의 νƒμƒ‰λ§ŒμœΌλ‘œ λΉ λ₯΄κ²Œ νŒ¨ν„΄μ„ λ§€μΉ­ν•˜κ³  κ²°κ³Όλ₯Ό λ°˜ν™˜ν•˜μ§€λ§Œ 두 번째 μ˜ˆμ‹œλ₯Ό 보면 λ¬Έμžμ—΄ 끝에 νŠΉμˆ˜λ¬Έμžκ°€ ν•˜λ‚˜ λΆ™μ—ˆμ„ 뿐인데 μ—°μ‚° νšŸμˆ˜κ°€ κΈ°ν•˜κΈ‰μˆ˜μ μœΌλ‘œ λŠ˜μ–΄λ‚˜λ”λ‹ˆ, κΈ‰κΈ°μ•Ό 연산이 λλ‚˜μ§€ μ•ŠλŠ” μˆ˜μ€€κΉŒμ§€ λ„λ‹¬ν•œλ‹€.

    λ§Œμ•½ 이런 상황이 μ‹€μ œ λΉ„μ¦ˆλ‹ˆμŠ€ μ–΄ν”Œλ¦¬μΌ€μ΄μ…˜μ—μ„œ λ°œμƒν–ˆλ‹€λ©΄ μœ μ €λŠ” μ–΄λ– ν•œ UI μš”μ†Œμ™€λ„ μƒν˜Έ μž‘μš©μ„ ν•˜μ§€ λͺ»ν•˜κ³  λ©ˆμΆ°λ²„λ¦° ν™”λ©΄λ§Œ 보고 있게 될 것이닀. 심지어 이런 μ •κ·œ ν‘œν˜„μ‹μ˜ μž‘λ™μ›λ¦¬λ₯Ό μ•…μš©ν•˜μ—¬ μ‹œμŠ€ν…œμ„ λ©ˆμΆ”κ²Œ ν•˜λŠ” ReDoSλΌλŠ” 곡격 방식도 μ‘΄μž¬ν•œλ‹€.

    λ°”λ‘œ 이런 κ²½μš°κ°€ μ •κ·œ ν‘œν˜„μ‹μ˜ μž‘λ™ 원리λ₯Ό μ œλŒ€λ‘œ μ•Œμ§€ λͺ»ν•˜κ³  μ‚¬μš©ν•˜κ²Œ 되면 가끔 λ§› λ³Ό μˆ˜μžˆλŠ” μ•Όκ·Ό 상황이닀.

    더 ν™”λ”±μ§€κ°€ λ‚˜λŠ” 건 μ €λŸ° μ •κ·œ ν‘œν˜„μ‹μ„ μž‘μ„±ν•΄λ„ κ·Έμ € μˆ˜ν–‰ μ‹œκ°„λ§Œ κΈ°ν•˜κΈ‰μˆ˜μ μœΌλ‘œ λŠ˜μ–΄λ‚  뿐 μ—λŸ¬λŠ” μ•„λ‹ˆλΌλŠ” 것이닀. κ·Έλž˜μ„œ λ―Ώμ—ˆλ˜ μ •κ·œ ν‘œν˜„μ‹ν•œν…Œ λ’·ν†΅μˆ˜ λ§žκΈ°κ°€ 더 μ‰¬μš΄ 상황이닀. κ²Œλ‹€κ°€ 이런 μ’…λ₯˜μ˜ μ—λŸ¬λŠ” μ§„μ§œ 찾기도 νž˜λ“€λ‹€. (μ–΄μ°Œμ–΄μ°Œ μ°Ύμ•˜μ•„λ„ μ •κ·œ ν‘œν˜„μ‹μ΄ μ›μΈμ΄λž€ κ±Έ μ•Œλ©΄ λˆˆμ•žμ΄ 막막해진닀…)

    noway 내 야근이 잘못 작성한 정규 표현식 한 줄 때문이란 것을 알았을 때의 표정.jpg

    μ΄λ ‡κ²Œ λ°±νŠΈλž˜ν‚Ή μ•Œκ³ λ¦¬μ¦˜μ„ μ‚¬μš©ν•˜λŠ” μ •κ·œ ν‘œν˜„μ‹μ˜ νŠΉμ„± 상 μ–΄λ–€ 탐색 과정을 κ±°μΉ˜λƒμ— λ”°λΌμ„œ νΌν¬λ¨ΌμŠ€κ°€ 많이 λ–¨μ–΄μ§ˆ μˆ˜λ„ 있기 λ•Œλ¬Έμ—, μ •κ·œ ν‘œν˜„μ‹μ„ μ‚¬μš©ν•  λ•ŒλŠ” 이런 λœ»ν•˜μ§€ μ•Šμ€ 상황이 λ°œμƒν•  μˆ˜λ„ μžˆλ‹€λŠ” 것을 항상 염두에 λ‘¬μ•Όν•œλ‹€.

    μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œλŠ” ν•΄κ²°ν•  수 μ—†λŠ” 문제

    그리고 두 번째 λ’·ν†΅μˆ˜ 상황은 μ •κ·œ ν‘œν˜„μ‹λ§ŒμœΌλ‘œλŠ” μ ˆλŒ€ ν•΄κ²°ν•  수 μ—†λŠ” 문제λ₯Ό μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ ν•΄κ²°ν•˜λ €κ³  ν•˜λŠ” 상황이닀.

    첫 번째 상황은 퍼포먼슀 λͺ¨λ‹ˆν„°λ§μ„ 톡해 β€œμ •κ·œ ν‘œν˜„μ‹μ΄ μ΄μƒν•œλ°?β€λΌλŠ” λ¬Έμ œλΌλ„ μ•Œμ•„λ‚Ό 수 μžˆμ§€λ§Œ, 이 두 번째 상황은 μ •κ·œ ν‘œν˜„μ‹μ˜ 원리와 ν•œκ³„λ₯Ό λͺ¨λ₯Έλ‹€λ©΄ μ§„μ§œ 일주일 λ‚΄λ‚΄ μ‚½μ§ˆλ§Œ ν•˜λ©° μ‹œκ°„λ§Œ 날릴 μˆ˜λ„ μžˆλŠ” 상황이기 λ•Œλ¬Έμ— κ°œμΈμ μœΌλ‘œλŠ” 이 두 번째 상황이 쑰금 더 μŠ¬ν”ˆ 상황이라고 μƒκ°ν•œλ‹€.

    μ•„λž˜μ—μ„œ λ‹€μ‹œ ν›„μˆ ν•˜κ² μ§€λ§Œ, 사싀 μ •κ·œ ν‘œν˜„μ‹μ€ 세상 λͺ¨λ“  λ¬Έμžμ—΄μ˜ νŒ¨ν„΄μ„ μ°Ύμ•„λ‚Ό 수 μžˆλŠ” 만λŠ₯ μ—΄μ‡ κ°€ μ•„λ‹ˆλΌ 였히렀 μ—„κ²©ν•œ ν•œκ³„κ°€ μ‘΄μž¬ν•˜λŠ” 도ꡬ이닀.

    λŒ€ν‘œμ μœΌλ‘œ HTML, CSS와 같이 λ¬΄ν•œν•˜κ²Œ 열릴 수 μžˆλŠ” νƒœκ·Έλ‚˜ κ΄„ν˜Έκ°€ μ‘΄μž¬ν•˜λŠ” μ–Έμ–΄λŠ” μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ 검증이 λΆˆκ°€λŠ₯ν•˜λ‹€. κ·Έλž˜μ„œ 이 ν¬μŠ€νŒ…μ˜ 제λͺ©μ΄μ—ˆλ˜ β€œHTML을 μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ νŒŒμ‹±ν•  수 μžˆμ„κΉŒ?β€λΌλŠ” μ§ˆλ¬Έμ— λŒ€ν•œ λŒ€λ‹΅μ€ λ°”λ‘œ

    .
    .
    .
    x "No" 이다.

    λ§Œμ•½ μ—¬λŸ¬λΆ„μ΄ HTML을 μ •κ·œ ν‘œν˜„μ‹λ§ŒμœΌλ‘œ νŒŒμ‹±ν•˜λŠ” 것은 λΆˆκ°€λŠ₯ν•˜λ‹€λŠ” 사싀을 λͺ¨λ₯΄κ³  μžˆμ—ˆλ‹€λ©΄, μ ˆλŒ€ ν•΄κ²°ν•  수 μ—†λŠ” 문제λ₯Ό ν•΄κ²°ν•˜κΈ° μœ„ν•΄ λ§Žμ€ μ‹œκ°„μ„ 날렀먹을 μˆ˜λ„ μžˆλ‹€λŠ” 것이닀.

    그런데 ν•„μžλ₯Ό ν¬ν•¨ν•œ λ§Žμ€ 뢄듀이 ν‰μ†Œμ— μ •κ·œ ν‘œν˜„μ‹μ„ μ‚¬μš©ν•˜μ—¬ HTML νƒœκ·Έκ°€ μ˜¬λ°”λ₯΄κ²Œ 열리고 λ‹«ν˜”λŠ”μ§€λ₯Ό 검사해본 κ²½ν—˜μ΄ μžˆλŠ”λ°, μ™œ ν•„μžλŠ” μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ HTML을 νŒŒμ‹±ν•  수 μ—†λ‹€κ³  μ΄μ•ΌκΈ°ν•˜λŠ” κ²ƒμΌκΉŒ?

    κ·Έ 이유λ₯Ό μ•ŒκΈ° μœ„ν•΄μ„œλŠ” μ •κ·œ ν‘œν˜„μ‹μ΄λΌλŠ” 도ꡬ가 μ–΄λ–€ λ§₯λ½μ—μ„œ 개발된 것인지, μ–΄λ–€ ν™˜κ²½μ—μ„œ κ΅¬λ™λ˜λŠ” 것을 μ „μ œλ‘œ ν•˜κ³  μžˆλŠ” 것인지λ₯Ό μ‚΄νŽ΄λ³΄λ©° μ •κ·œ ν‘œν˜„μ‹μ΄ κ°€μ§€κ³  μžˆλŠ” ν•œκ³„κ°€ 무엇인지 μ•Œμ•„λ΄μ•Ό ν•  ν•„μš”κ°€ μžˆλ‹€.

    μ •κ·œ ν‘œν˜„μ‹μ€ μ™œ λ§Œλ“€μ–΄μ§„ κ²ƒμΌκΉŒ?

    κ°œλ°œμžλ“€μ—κ²Œ μ •κ·œ ν‘œν˜„μ‹μ΄λΌλŠ” λ‹¨μ–΄λŠ” 이미 μ΅μˆ™ν•˜λ‹€. κ°œλ°œμžλ“€ μ‚¬μ΄μ—μ„œ μ •κ·œ ν‘œν˜„μ‹μ˜ μ€„μž„λ§μΈ μ •κ·œμ‹μ„ κ·œμ‹μ΄ν˜•μ²˜λŸΌ λ³€ν˜•ν•΄μ„œ λΆ€λ₯΄λŠ” 것이 밈이 될 정도이기도 ν•˜λ‹ˆ 말이닀.

    ν•˜μ§€λ§Œ μ •κ·œ ν‘œν˜„μ‹μ΄ μ™œ β€œμ •κ·œ ν‘œν˜„μ‹β€μ΄λΌλŠ” μš”μƒν•œ μ΄λ¦„μœΌλ‘œ λΆˆλ¦¬λŠ” μ§€λ₯Ό κΆκΈˆν•΄ ν•˜λŠ” μ‚¬λžŒμ€ κ·Έλ ‡κ²Œ λ§Žμ§€ μ•Šλ‹€. κ·ΈλŸ¬λ‹ˆ μ •κ·œ ν‘œν˜„μ‹μ΄ μ •ν™•νžˆ μ–΄λ–€ 역할을 ν•˜λŠ” 도ꡬ인지λ₯Ό μ•ŒκΈ° μœ„ν•œ 첫 걸음으둜 μš°λ¦¬μ—κ²Œ 이미 μ΅μˆ™ν•œ 이 β€œμ •κ·œ ν‘œν˜„μ‹β€μ΄λΌλŠ” μ΄λ¦„μ˜ μ˜λ―ΈλΆ€ν„° ν•œλ²ˆ 생각해보도둝 ν•˜μž.

    μ •κ·œ(正規)λΌλŠ” λ‹¨μ–΄μ˜ μ˜λ―ΈλŠ” κ·œμΉ™μ μΈ 무언가, νŒ¨ν„΄μ΄λ‹€. 즉, μ •κ·œ ν‘œν˜„μ΄λΌλŠ” 것은 κ²°κ΅­ 말 κ·ΈλŒ€λ‘œ κ·œμΉ™μ μΈ νŒ¨ν„΄μ„ ν‘œν˜„ν•˜κ³  μžˆλ‹€λŠ” 의미이기 λ•Œλ¬Έμ— μš°λ¦¬λŠ” 일반적으둜 μ •κ·œ ν‘œν˜„μ‹μ΄ λ¬Έμžμ—΄μ—μ„œ λ‚΄κ°€ μ›ν•˜λŠ” νŒ¨ν„΄μ„ λ§€μΉ­ν•˜λŠ” 도ꡬ라고 μ•Œκ³  μžˆλ‹€.

    이 νŒ¨ν„΄μ΄λΌλŠ” λ‹¨μ–΄λŠ” 12121212처럼 λ‹¨μˆœνžˆ λ°˜λ³΅λ˜λŠ” κ·œμΉ™λ§Œμ„ μ˜λ―Έν•˜λŠ” 것이 μ•„λ‹ˆλΌ, μš°λ¦¬κ°€ μ •κ·œ ν‘œν˜„μ‹μ„ μ‚¬μš©ν•  λ•Œ μ •μ˜ν•˜λŠ” κ·œμΉ™μ²˜λŸΌ β€œaκ°€ 2번 λ‚˜μ˜€κ³  κ·Έ 뒀에 λ°”λ‘œ bκ°€ λ‚˜νƒ€λ‚œλ‹€β€μ™€ 같이 μ‚¬μš©μžκ°€ μ •μ˜ν•˜λŠ” λͺ¨λ“  κ·œμΉ™κΉŒμ§€ ν¬ν•¨ν•˜λŠ” μ˜λ―Έμ΄λ‹€.

    이처럼 μ •κ·œ ν‘œν˜„μ‹μ˜ κ°€μž₯ 기본적인 μš©λ„λŠ” λ¬Έμžμ—΄ μ†μ—μ„œ νŒ¨ν„΄μ„ μ°ΎλŠ” κ²ƒμ΄μ§€λ§Œ, 사싀 μ •κ·œ ν‘œν˜„μ‹μ€ λ‹¨μˆœνžˆ λ¬Έμžμ—΄μ˜ νŒ¨ν„΄μ„ 찾을 수 μžˆλ‹€λŠ” λ‹ˆμ¦ˆλ§Œμ„ μœ„ν•΄μ„œ λ§Œλ“€μ–΄μ§„ 것이 μ•„λ‹ˆλ‹€. κ·Έλ ‡λ‹€λ©΄ μ •κ·œ ν‘œν˜„μ‹μ€ λ„λŒ€μ²΄ 무엇을 μœ„ν•œ νŒ¨ν„΄μ„ ν‘œν˜„ν•˜κ³  μžˆλŠ” κ²ƒμΌκΉŒ?

    기계가 μ•Œμ•„λ“€μ„ 수 μžˆλŠ” μ–Έμ–΄λ₯Ό ν‘œν˜„ν•΄λ³΄μž

    μ•žμ„œ μ΄μ•ΌκΈ°ν–ˆλ“―μ΄ μ •κ·œ ν‘œν˜„μ‹μ€ μ–΄λ–€ νŒ¨ν„΄μ„ ν‘œν˜„ν•˜κΈ° μœ„ν•΄ νƒœμ–΄λ‚œ λ„κ΅¬μ΄μ§€λ§Œ, 사싀 μ •κ·œ ν‘œν˜„μ‹μ˜ 탄생 배경을 μ΄ν•΄ν•˜λ €λ©΄ β€œμ™œ λ¬Έμžμ—΄ λ‚΄μ—μ„œ νŒ¨ν„΄μ„ 찾으렀고 ν–ˆλŠ”μ§€β€λ₯Ό μ•„λŠ” 것이 더 μ€‘μš”ν•˜λ‹€.

    κ²°λ‘ λΆ€ν„° μ΄μ•ΌκΈ°ν•˜μžλ©΄ μ •κ·œ ν‘œν˜„μ‹μ˜ μ‹œμž‘μ€ λ°”λ‘œ 기계가 μ•Œμ•„λ“€μ„ 수 μžˆλŠ” μ–Έμ–΄λ₯Ό ν‘œν˜„ν•˜κΈ° μœ„ν•œ κ³ λ―Όμ—μ„œλΆ€ν„° μΆœλ°œν–ˆλ‹€. 즉, 기계가 μ–Έμ–΄λΌλŠ” κ°œλ…μ„ 인지할 수 μžˆλ„λ‘ μ–Έμ–΄λ₯Ό μˆ˜ν•™μ μœΌλ‘œ ν‘œν˜„ν•˜κΈ° μœ„ν•΄ νƒœμ–΄λ‚œ κ°œλ…μ΄λΌλŠ” 것이닀.

    1951년, 처음으로 정규 집합을 사용하여 언어를 수학적으로 기술한 클레이니 형

    단, 이 μ‹œμ ˆμ— μ΄μ•ΌκΈ°ν•˜λŠ” 기계가 μ•Œμ•„λ“€μ„ 수 μžˆλŠ” μ–Έμ–΄λΌλŠ” 것은 였늘 λ‚  μ—°κ΅¬ν•˜κ³  μžˆλŠ” κ²ƒμ²˜λŸΌ μ‚¬λžŒμ΄ μ‚¬μš©ν•˜λŠ” μžμ—°μ–΄ 같은 κ³ μˆ˜μ€€μ˜ μ–Έμ–΄λ₯Ό μ˜λ―Έν•˜λŠ” 것은 λ‹Ήμ—°νžˆ μ•„λ‹ˆλ‹€.

    μ—¬κΈ°μ„œ 언어라고 ν•˜λŠ” 것은 ν•œκ΅­μ–΄λ‚˜ μ˜μ–΄ 같은 μžμ—°μ–΄κ°€ μ•„λ‹ˆλΌ 쑰금 더 좔상적인 μ˜λ―Έμ΄λ‹€. ν‰μ†Œμ— μš°λ¦¬κ°€ μ‚¬μš©ν•˜λŠ” ν”„λ‘œκ·Έλž˜λ° 언어도 β€œμ–Έμ–΄(Language)β€œλΌκ³  λΆ€λ₯΄λŠ” κ²ƒμ²˜λŸΌ 컴퓨터 κ³Όν•™κ³Ό μˆ˜ν•™μ˜ μ„Έκ³„μ—μ„œ μ–Έμ–΄λΌλŠ” 것은 λ‹¨μˆœνžˆ μ–΄λ–€ νŠΉμ •ν•œ κ·œμΉ™μ„ κ°€μ§„ λ¬Έμžμ—΄μ˜ 집합을 μ˜λ―Έν•˜κΈ° λ•Œλ¬Έμ΄λ‹€.

    μˆ˜ν•™μ μœΌλ‘œ μ •μ˜λœ μ–Έμ–΄μ˜ 의미

    μš°λ¦¬λŠ” 언어라고 ν•˜λŠ” 것이 무엇인지 λŠλ‚Œμ μœΌλ‘œλŠ” μ•Œκ³  μžˆμ§€λ§Œ μ •ν™•νžˆ 이게 무엇이라고 κ³ λ―Όν•΄λ³Έ 적은 많이 없을 것이닀.

    ν•˜μ§€λ§Œ 컴퓨터 κ³Όν•™μ΄λ‚˜ μˆ˜ν•™μ˜ μ„Έκ³„μ—μ„œλŠ” 이런 λŠλ‚Œμ μΈ 지식을 μ ˆλŒ€ ν—ˆμš©ν•˜μ§€ μ•ŠκΈ° λ•Œλ¬Έμ—, μ–Έμ–΄λΌλŠ” κ°œλ…μ„ 이 μ„Έκ³„μ—μ„œ μ‚¬μš©ν•˜κ³  μ‹Άλ‹€λ©΄ μ–Έμ–΄κ°€ μ •ν™•νžˆ μ–΄λ–€ 것이라고 μ •μ˜ν•˜λŠ” 과정이 λ°˜λ“œμ‹œ ν•„μš”ν•˜λ‹€.

    사싀 μˆ˜ν•™κ³Ό 컴퓨터 κ³Όν•™μ—μ„œ μ •μ˜ν•˜λŠ” μ–Έμ–΄λΌλŠ” 것은 λ‹¨μˆœν•˜κ²Œ μ–΄λ–€ λ¬Έμžμ—΄λ“€μ˜ 집합을 μ˜λ―Έν•˜λŠ” 것 κ·Έ 이상 κ·Έ μ΄ν•˜λ„ μ•„λ‹ˆλ‹€.

    자바스크립트는 대충 이런 문자열들이 모인 집합이지 않을까

    ν•˜μ§€λ§Œ λ‹Ήμ—°ν•˜κ²Œλ„ 아무 λ¬Έμžμ—΄μ΄λ‚˜ 막 집어넣은 집합을 μ˜λ―Έν•˜λŠ” 것은 μ•„λ‹ˆκΈ° λ•Œλ¬Έμ—, μ–Έμ–΄λ₯Ό κ΅¬μ„±ν•˜λŠ” λ¬Έμžμ—΄μ˜ 집합은 λ°˜λ“œμ‹œ λ‹€μŒ 3κ°€μ§€ 쑰건을 λ§Œμ‘±ν•΄μ•Όν•œλ‹€.

    1. μœ ν•œν•œ 길이의 κΈ°ν˜Έλ“€μ˜ μ§‘ν•© Sκ°€ λ°˜λ“œμ‹œ μ‘΄μž¬ν•œλ‹€
    2. S의 μ›μ†Œλ“€λ‘œ λ§Œλ“  λ¬Έμžμ—΄μ˜ 집합인 S*λ₯Ό ν˜•μ„±ν•˜λŠ” κ·œμΉ™μ΄ λ°˜λ“œμ‹œ μ‘΄μž¬ν•œλ‹€
    3. κ·œμΉ™μ— 맞게 λ§Œλ“€μ–΄μ§„ λ¬Έμžμ—΄λ“€μ΄ μ–΄λ–€ 의미λ₯Ό κ°€μ§€λŠ”μ§€ κ²°μ •ν•  수 μžˆλ‹€

    즉, 이 3κ°€μ§€ 쑰건을 λ§Œμ‘±ν•˜λŠ” λ¬Έμžμ—΄μ˜ 집합은 μ •λ§λ‘œ 기초적인 언어라고 λΆ€λ₯Όλ§Œν•œ 자격이 λ˜λŠ” 것이닀. 이제 μ–Έμ–΄μ˜ μ •μ˜μ— λŒ€ν•΄ μ•Œμ•˜μœΌλ‹ˆ 이제 1λ²ˆλΆ€ν„° ν•˜λ‚˜ν•˜λ‚˜ λ§Œμ‘±μ‹œμΌœλ³΄λ©΄μ„œ μ–Έμ–΄λ₯Ό λ§Œλ“€μ–΄λ³΄λ„λ‘ ν•˜μž.

    μš°μ„  첫 번째 쑰건인 κΈ°ν˜Έλ“€μ˜ μ§‘ν•© SλŠ” 무엇을 μ˜λ―Έν•˜λŠ” 걸까?

    잘 생각해보면 지ꡬ 상에 μ‘΄μž¬ν•˜λŠ” λͺ¨λ“  언어듀은 κ·Έ μ–Έμ–΄μ—μ„œ μ‚¬μš©λ˜λŠ” κΈ°ν˜Έλ“€μ„ κ°€μ§€κ³  μžˆλ‹€. ν•œκΈ€μ€ γ„±, γ„΄, γ„·κ³Ό 같은 자음과 ㅏ, γ…‘, γ…“ 같은 λͺ¨μŒμ„ λ‚˜νƒ€λ‚΄λŠ” κΈ°ν˜Έλ“€, 그리고 μ˜μ–΄λŠ” a, b, c와 같은 κΈ°ν˜Έλ“€μ„ κ°€μ§€κ³  μžˆλŠ” 것 처럼 말이닀. μš°λ¦¬λŠ” 이런 κΈ°ν˜Έλ“€μ˜ λͺ¨μŒμ„ β€œμ•ŒνŒŒλ²³β€μ΄λΌκ³  λΆ€λ₯΄κ³ , λ°”λ‘œ 이 μ•ŒνŒŒλ²³μ΄ μ–Έμ–΄μ˜ 첫 번째 쑰건인 κΈ°ν˜Έλ“€μ˜ μ§‘ν•© S이닀.

    그럼 ν•œλ²ˆ μ•ŒνŒŒλ²³μ„ 정해보도둝 ν•˜μž. ν•„μžλŠ” 이 μ˜ˆμ‹œμ—μ„œ κ·Έλƒ₯ μ†Œλ°•ν•˜κ²Œ a, bλΌλŠ” κ°„λ‹¨ν•œ 기호 2개둜만 μ•ŒνŒŒλ²³μ„ κ΅¬μ„±ν•˜λ €κ³  ν•œλ‹€.

    S = ['a', 'b']

    자 이제 μ–Έμ–΄μ˜ 첫 번째 쑰건인 β€œμœ ν•œν•œ 길이의 κΈ°ν˜Έλ“€μ˜ μ§‘ν•© Sβ€œλ₯Ό λ§Œλ“€μ—ˆλ‹€. λ‹€μŒμœΌλ‘œλŠ” ”S의 μ›μ†Œλ“€λ‘œ λ§Œλ“  λ¬Έμžμ—΄μ˜ 집합인 S*β€œλ₯Ό λ§Œλ“€ 차둀이닀. 두 번째 쑰건을 보면 이 λ¬Έμžμ—΄μ˜ 집합을 ν˜•μ„±ν•˜κΈ° μœ„ν•΄μ„œλŠ” μ–΄λ– ν•œ κ·œμΉ™μ΄ ν•„μš”ν•˜λ‹€κ³  ν•œλ‹€.

    그리고 이 κ·œμΉ™μ΄ λ°”λ‘œ 이 μ–Έμ–΄μ˜ 문법(Syntax)λ₯Ό μ˜λ―Έν•œλ‹€. 지ꡬ μƒμ—λŠ” 같은 μ•ŒνŒŒλ²³μ„ μ‚¬μš©ν•˜λŠ” μ–Έμ–΄κ°€ ν•œ λ‘κ°œκ°€ μ•„λ‹ˆκΈ° λ•Œλ¬Έμ—, 이 두 번째 κ·œμΉ™, 즉 문법이 이 μ–Έμ–΄μ˜ νŠΉμƒ‰μ„ λ§Œλ“€μ–΄λ‚Έλ‹€.

    [같은 라틴 μ•ŒνŒŒλ²³μ„ μ“°μ§€λ§Œ λ¬Έμžμ—΄μ„ μ‘°ν•©ν•˜λŠ” κ·œμΉ™μ΄ 닀름]
    
    μ˜μ–΄: I love you
    ν”„λž‘μŠ€μ–΄: je t'aime
    μ΄νƒˆλ¦¬μ•„μ–΄: ti amo

    μœ„ μ˜ˆμ‹œμ—μ„œ λ³Ό 수 μžˆλ“―μ΄ μ˜μ–΄μ—μ„œ μ‚¬μš©λ˜λŠ” 라틴 μ•ŒνŒŒλ²³μ€ ν”„λž‘μŠ€μ–΄λ‚˜ μ΄νƒˆλ¦¬μ•„μ–΄μ—μ„œλ„ λŒ€λΆ€λΆ„ μ‚¬μš©λ˜κ³  μžˆλ‹€. λ˜‘κ°™μ΄ β€œμ‚¬λž‘β€μ΄λΌλŠ” 의미λ₯Ό κ°€μ§„ 단어라고 해도 μ˜μ–΄λŠ” loveλΌλŠ” 4개의 μ•ŒνŒŒλ²³μ΄ μ‘°ν•©λœ λ¬Έμžμ—΄λ‘œ ν‘œν˜„ν•˜κ³ , ν”„λž‘μŠ€μ–΄λŠ” l'amourλΌλŠ” 'λ₯Ό ν¬ν•¨ν•˜μ—¬ 7개의 μ•ŒνŒŒλ²³μ΄ μ‘°ν•©λœ λ¬Έμžμ—΄λ‘œ ν‘œν˜„ν•  수 μžˆλŠ” 것을 생각해보면 λœλ‹€.

    κ·Έλž˜μ„œ μ•ŒνŒŒλ²³λ§Œ μ •μ˜ν•œλ‹€κ³  ν•΄μ„œ μ–΄λ–€ μ–Έμ–΄λ₯Ό μ •μ˜ν–ˆλ‹€κ³  λ§ν•˜κΈ°κ°€ μ–΄λ ΅λ‹€λŠ” 것이닀. ν•„μžλŠ” 이 λ¬Έμžμ—΄μ˜ μ§‘ν•© S*의 κ·œμΉ™μ„ β€œμ•ŒνŒŒλ²³ a와 b둜 λ§Œλ“€ 수 μžˆλŠ” λͺ¨λ“  3자리 μ΄ν•˜μ˜ κΈ€μžβ€λΌκ³  μ •ν•˜λ„λ‘ ν•˜κ² λ‹€. 그럼 ν•„μžκ°€ λ§Œλ“€κ³  μžˆλŠ” 이 μ–Έμ–΄λ₯Ό κ΅¬μ„±ν•˜λŠ” λ¬Έμžμ—΄μ˜ μ§‘ν•© S*λŠ” 이런 λͺ¨μ–‘이 될 것이닀.

    S* = [
      "",
      "a", "b",
      "aa", "ab", "ba", "bb",
      "aaa", "aab", "aba", "abb",
      "baa", "bab", "bba", "bbb",
    ]

    이제 두 번째 쑰건인 ”S의 μ›μ†Œλ“€λ‘œ λ§Œλ“  λ¬Έμžμ—΄μ˜ 집합인 S*λ₯Ό ν˜•μ„±ν•˜λŠ” κ·œμΉ™β€λ„ μ •μ˜ν•˜κ³ λ‚˜λ‹ˆ ν•„μžμ˜ μ–Έμ–΄κ°€ μ–΄λ–€ λ¬Έμžμ—΄λ“€μ„ ν¬ν•¨ν•˜κ³  μžˆλŠ” 집합인지 μ•Œ 수 있게 λ˜μ—ˆλ‹€. μ—¬κΈ°κΉŒμ§€ μ˜€κ³ λ‚˜λ©΄ 사싀 λ§ˆμ§€λ§‰ 쑰건은 μžλ™μœΌλ‘œ μΆ©μ‘±λœλ‹€.

    ν•„μžκ°€ S*의 κ·œμΉ™μœΌλ‘œ μ •μ˜ν•œ 쑰건인 β€œμ•ŒνŒŒλ²³ a와 b둜 λ§Œλ“€ 수 μžˆλŠ” λͺ¨λ“  3자리 μ΄ν•˜μ˜ κΈ€μžβ€λŠ” μœ ν•œν•œ 개수의 λ¬Έμžμ—΄μ˜ μ›μ†Œλ§Œ λ§Œλ“€ 수 있기 λ•Œλ¬Έμ—, μ΄λ ‡κ²Œ λ§Œλ“€μ–΄μ§„ λͺ¨λ“  λ¬Έμžμ—΄μ— 의미λ₯Ό 각각 λΆ€μ—¬ν•΄μ£ΌλŠ” 것이 κ°€λŠ₯ν•˜κΈ° λ•Œλ¬Έμ΄λ‹€.

    a = λ°°κ°€ κ³ νŒŒμš”
    b = ν‡΄κ·Όν•˜κ³  μ‹Άμ–΄μš”
    aa = μ„œλ²„μ—μ„œ 500이 λ–¨μ–΄μ Έμš”
    ...

    ν•„μžλŠ” μ΄λ ‡κ²Œ 단 5λΆ„ λ§Œμ— μ–Έμ–΄μ˜ 쑰건 3개λ₯Ό λͺ¨λ‘ μΆ©μ‘±μ‹œμΌœμ„œ ν—ˆμ ‘ν•œ μ–Έμ–΄λ₯Ό λ§Œλ“€μ–΄λ‚Ό 수 μžˆμ—ˆλ‹€. μ•žμœΌλ‘œμ˜ μ„€λͺ…μ—μ„œ 이 μ–Έμ–΄λŠ” β€œμ—λ°˜μ–΄β€λΌκ³  λΆ€λ₯΄λ„둝 ν•˜κ² λ‹€.

    기계야 λ‚΄ μ–Έμ–΄λ₯Ό μ΄ν•΄ν•΄μ€˜

    사싀 μ–΄λ–€ μ–Έμ–΄λ₯Ό λ§Œλ“œλŠ” κ·œμΉ™ μžμ²΄λŠ” λ‹¨μˆœν•˜κΈ° λ•Œλ¬Έμ— λˆ„κ΅¬λΌλ„ μ—λ°˜μ–΄μ²˜λŸΌ ν—ˆμ ‘ν•œ μ–Έμ–΄λ₯Ό λ§Œλ“€μ–΄λ‚Ό μˆ˜λŠ” μžˆλ‹€. 그런데 λ¬Έμ œλŠ” 이 μ–Έμ–΄λ₯Ό 기계가 이해할 수 μžˆλƒλŠ” 것이닀.

    κ²°κ΅­ μ–΄λ–€ 기계가 μ–Έμ–΄λ₯Ό 이해할 수 μžˆλ‹€λŠ” 것은 이 μ–Έμ–΄λ₯Ό κ΅¬μ„±ν•˜λŠ” λ¬Έμžμ—΄μ— νŠΉμ •ν•œ νŒ¨ν„΄μ΄ μžˆμ–΄μ•Ό ν•œλ‹€λŠ” μ˜λ―Έμ΄λ‹€. 즉, μ–Έμ–΄λ₯Ό κ΅¬μ„±ν•˜λŠ” λ¬Έμžμ—΄μ˜ νŒ¨ν„΄μ„ μˆ˜ν•™μ μœΌλ‘œ ν‘œν˜„ν•  수만 μžˆλ‹€λ©΄ 이 μ–Έμ–΄λŠ” 기계가 이해할 수 μžˆλŠ” 언어라고 이야기할 수 μžˆλŠ” 것이닀.

    λ¬Όλ‘  같은 언어라고 해도 μš°λ¦¬κ°€ 일상 μ†μ—μ„œ μ‚¬μš©ν•˜λŠ” ν•œκ΅­μ–΄, μ˜μ–΄μ™€ 같은 μžμ—°μ–΄λŠ” λ¬Έλ§₯이 ꡉμž₯히 자유둭고 μ‹œλŒ€μ˜ 흐름에 따라 λ¬Έλ²•μ΄λ‚˜ μ˜λ―Έκ°€ λ³€κ²½λ˜λŠ” 일도 있기 λ•Œλ¬Έμ— μ ˆλŒ€μ μΈ νŒ¨ν„΄μ΄λΌλŠ” 것이 μ‘΄μž¬ν•  수 μ—†λ‹€. ν•˜μ§€λ§Œ ν•„μžκ°€ 방금 λ§Œλ“  μ—λ°˜μ–΄μ²˜λŸΌ λ¬Έμžμ—΄λ“€μ„ κ΅¬μ„±ν•˜λŠ” κ·œμΉ™μ΄ λͺ…ν™•ν•˜λ‹€λ©΄ 이것은 기계가 이해할 수 μžˆλŠ” μ–Έμ–΄κ°€ λœλ‹€.

    ν•„μžκ°€ λ§Œλ“  μ—λ°˜μ–΄λŠ” a와 b둜 이루어진 3자리 μ΄ν•˜μ˜ λ¬Έμžμ—΄μ΄λΌλŠ” λͺ…ν™•ν•œ κ·œμΉ™μ΄ μ‘΄μž¬ν•˜κΈ° λ•Œλ¬Έμ— μ΄λ ‡κ²Œ μˆ˜μ‹μœΌλ‘œ ν‘œν˜„ν•˜λŠ” 것이 κ°€λŠ₯ν•˜λ‹€.

    L=(a+b+Ο΅)(a+b+Ο΅)(a+b+Ο΅)={Ο΅,a,b,aa,ab,ba,bb,ba,bb,aaa,aab,...bbb}\begin{aligned} L = (a+b+\epsilon)(a+b+\epsilon)(a+b+\epsilon) \\ = \{ \epsilon, a, b, aa, ab, ba, bb, ba, bb, aaa, aab, ... bbb \} \end{aligned}

    μ—λ°˜μ–΄λŠ” β€œa, b둜 λ§Œλ“€ 수 μžˆλŠ” 3자리 μ΄ν•˜μ˜ λ¬Έμžμ—΄β€μ˜ μ§‘ν•©μœΌλ‘œ κ΅¬μ„±λ˜μ–΄ μžˆλŠ” 언어이기 λ•Œλ¬Έμ— 빈 λ¬Έμžμ—΄ λ˜ν•œ 이 κ·œμΉ™μ— ν¬ν•¨λœλ‹€. κ·Έλž˜μ„œ μˆ˜μ‹μ—μ„œλ„ 빈 λ¬Έμžμ—΄μ„ λœ»ν•˜λŠ” Ο΅\epsilon(μ•±μ‹€λ‘ )을 각 μžλ¦¬λ§ˆλ‹€ λ”ν•΄μ£ΌλŠ” λ°©μ‹μœΌλ‘œ ν‘œν˜„ν•΄μ•Όν•˜λ©°, μœ„ 식이 ν‘œν˜„ν•˜λŠ” λ¬Έμžμ—΄μ˜ μ§‘ν•©μœΌλ‘œ κ΅¬μ„±λœ μ–Έμ–΄, μ—λ°˜μ–΄λ„ 빈 λ¬Έμžμ—΄μΈ Ο΅\epsilon을 ν¬ν•¨ν•˜κ³  μžˆλ‹€.

    그리고 이 μˆ˜μ‹μ„ 기계가 μ•Œμ•„λ“€μ„ 수 있게 νŠΉμ •ν•œ μ–Έμ–΄λ‘œ λ°”κΏ”μ€€ 것이 λ°”λ‘œβ€¦

    ^[ab]{0,3}$

    μš°λ¦¬κ°€ 일반적으둜 μ•Œκ³  μžˆλŠ” μ •κ·œ ν‘œν˜„μ‹μΈ 것이닀.

    즉, 기계가 μ–Έμ–΄λ₯Ό μΈμ§€ν•˜κΈ° μœ„ν•œ 첫 번째 λ°œκ±ΈμŒμ€ μ–Έμ–΄λ₯Ό κ΅¬μ„±ν•˜λŠ” λ¬Έμžμ—΄μ΄ μƒμ„±λ˜λŠ” β€œκ·œμΉ™β€μ„ ν‘œν˜„ν•  수 μžˆλŠ” 방법을 λ§Œλ“œλŠ” 것이고, 이게 λ°”λ‘œ μ •κ·œ ν‘œν˜„μ‹μ˜ 기원이닀. μœ„ν‚€ν”Όλ””μ•„μ˜ μ •κ·œ ν‘œν˜„μ‹ ν•­λͺ©μ„ 보면 이 λ§₯락이 μ •κ·œ ν‘œν˜„μ‹μ˜ μ •μ˜μ— κ·ΈλŒ€λ‘œ λ…Ήμ•„μžˆλŠ” 것을 λ³Ό 수 μžˆλ‹€.

    μ •κ·œ ν‘œν˜„μ‹(正規葨現式, μ˜μ–΄: regular expression, κ°„λ‹¨νžˆ regexp[1] λ˜λŠ” regex, rational expression)[2][3] λ˜λŠ” μ •κ·œμ‹(正規式)은 νŠΉμ •ν•œ κ·œμΉ™μ„ κ°€μ§„ λ¬Έμžμ—΄μ˜ 집합을 ν‘œν˜„ν•˜λŠ” 데 μ‚¬μš©ν•˜λŠ” ν˜•μ‹ 언어이닀.

    λ¬Όλ‘  ν•„μžκ°€ 이 ν¬μŠ€νŒ…μ—μ„œ μ„€λͺ…ν•˜κ³  μžˆλŠ” μ–Έμ–΄μ˜ μ •μ˜λŠ” ꡉμž₯히 λ‹¨νŽΈμ μΈ λ‚΄μš©μ„ μ΄μ•ΌκΈ°ν•˜κ³  μžˆλŠ” κ²ƒμ΄λ―€λ‘œ, 이 뢀뢄에 λŒ€ν•΄ 더 관심이 μžˆμœΌμ‹  뢄듀은 β€œν˜•μ‹ 언어”, β€œμ΄˜μŠ€ν‚€ μœ„κ³„β€ λ“±μ˜ ν‚€μ›Œλ“œλ‘œ ꡬ글링을 ν•œλ²ˆ ν•΄λ³΄λŠ” 것을 κΆŒν•œλ‹€.

    μ •κ·œ ν‘œν˜„μ‹μ΄ κ΅¬λ™λ˜λŠ” ν™˜κ²½, μœ ν•œ μ˜€ν† λ§ˆνƒ€

    μš°λ¦¬λŠ” 이제 μ •κ·œ ν‘œν˜„μ‹μ΄λΌλŠ” 것이 λ‹¨μˆœνžˆ λ¬Έμžμ—΄μ˜ νŒ¨ν„΄μ„ ν‘œν˜„ν•˜κΈ° μœ„ν•œ μ–Έμ–΄κ°€ μ•„λ‹ˆλΌ, μ–Έμ–΄λ₯Ό κΈ°κ³„μ—κ²Œ μΈμ§€μ‹œν‚€κΈ° μœ„ν•œ λ…Έλ ₯의 κ³Όμ • 끝에 νƒœμ–΄λ‚œ κΈ°μˆ μ΄λΌλŠ” 것을 μ•Œκ²Œ λ˜μ—ˆλ‹€. 그런데 ν•„μžκ°€ μ•„κΉŒλΆ€ν„° β€œκΈ°κ³„β€λΌλŠ” 말을 계속 ν•˜κ³  μžˆλŠ”λ°, 이 κΈ°κ³„λŠ” λ„λŒ€μ²΄ 무엇을 λ§ν•˜λŠ” κ²ƒμΌκΉŒ?

    참고둜 μ •κ·œ ν‘œν˜„μ‹μ΄λΌλŠ” κ°œλ…μ΄ νƒœμ–΄λ‚œ λ…„λ„λŠ” 1951년이닀. λ¬Όλ‘  이 λ‹Ήμ‹œμ—λ„ μ»΄ν“¨ν„°λΌλŠ” 것이 μžˆκΈ°λŠ” ν–ˆμ§€λ§Œ μ»΄ν“¨ν„°μ˜ λ©”λͺ¨λ¦¬λ‘œ μˆ˜μ€μ„ μ“°λ„€ μžκΈ°μ½”μ–΄λ₯Ό μ“°λ„€ μ–΄μ©Œλ„€ν•˜λ˜ μ§ˆν’λ…Έλ„μ˜ μ‹œκΈ°μ˜€κΈ° λ•Œλ¬Έμ—, ν˜„μž¬ μš°λ¦¬κ°€ 일반적인 ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•  λ•Œμ²˜λŸΌ λ©”λͺ¨λ¦¬μ˜ ν•œκ³„μ„±μ— λŒ€ν•œ 큰 걱정없이 μ½”λ”©ν•˜λ˜ μ‹œλŒ€λŠ” μ•„λ‹ˆμ˜€λ‹€.

    κ·Έλž˜μ„œ 이 μ‹œκΈ°μ— 기계λ₯Ό λŒ€μƒμœΌλ‘œ ν•˜λŠ” μ—°κ΅¬λŠ” μš°λ¦¬κ°€ μƒκ°ν•˜λŠ” 컴퓨터가 μ•„λ‹ˆλΌ κ·Έλƒ₯ 계산 λŠ₯λ ₯이 μžˆλŠ” 기계λ₯Ό λ¨Έλ¦Ώ μ†μœΌλ‘œ μƒμƒν•΄μ„œ μ§„ν–‰ν•˜λŠ” κ²½μš°κ°€ λ§Žμ•˜λ‹€. (본격 μƒμƒμ½”λ”©μ˜ 원쑰…)

    magnatic drum 본격 1952년 발 최신형 컴퓨터의 메모리인 자기 드럼의 위용

    κ·Έ μ€‘μ—μ„œλ„ μ •κ·œ ν‘œν˜„μ‹μ€ μœ ν•œ μ˜€ν† λ§ˆνƒ€λΌλŠ” 좔상 기계가 μ•Œμ•„λ“€μ„ 수 μžˆλŠ” μ–Έμ–΄λ₯Ό ν‘œν˜„ν•˜λŠ” μ—°κ΅¬μ—μ„œ νŒŒμƒλœ 이둠이닀.

    μ˜€ν† λ§ˆνƒ€λŠ” μžλ™(Auto) 기계(Mata)λΌλŠ” 의미인데, 이건 말 κ·ΈλŒ€λ‘œ μžλ™ν™”λœ 좔상적인 기계이기 λ•Œλ¬Έμ— λ°˜λ“œμ‹œ μ»΄ν“¨ν„°μ²˜λŸΌ 물리적인 μž₯μΉ˜κ°€ ν•„μš”ν•œ 것은 μ•„λ‹ˆλ‹€. κ·Έλƒ₯ μ΄λ‘ μ΄λ‚˜ μ„€κ³„λ‘œλ§Œ μ‘΄μž¬ν•  μˆ˜λ„ μžˆλ‹€λŠ” 것이닀.

    μ΄λ ‡κ²Œ μ˜€ν† λ§ˆνƒ€λ₯Ό μ—°κ΅¬ν•˜λŠ” 학문은 근본적으둜 μ–΄λ–€ 기계가 ν•  수 μžˆλŠ” 것은 무엇이고 ν•  수 μ—†λŠ” 것은 무엇인지에 λŒ€ν•œ 해닡을 μ°ΎλŠ” 학문이기 λ•Œλ¬Έμ—, ν˜„μž¬ μš°λ¦¬κ°€ κ³΅λΆ€ν•˜λŠ” 컴퓨터 κ³Όν•™μ˜ λͺ¨νƒœκ°€ λ˜λŠ” 학문이라고도 λ³Ό 수 μžˆλ‹€.

    κ·Έ μ€‘μ—μ„œλ„ μœ ν•œ μ˜€ν† λ§ˆνƒ€λŠ” κ°„λ‹¨ν•˜κ²Œ μ–˜κΈ°ν•΄μ„œ μœ ν•œ 개의 μƒνƒœ 쀑 ν•œ λ²ˆμ— ν•˜λ‚˜μ˜ μƒνƒœλ§Œμ„ κ°€μ§ˆ 수 μžˆλŠ” 기계이닀. μœ ν•œ μ˜€ν† λ§ˆνƒ€λ₯Ό 섀계할 λ•ŒλŠ” λ‹€μ΄μ–΄κ·Έλž¨μ„ μ‚¬μš©ν•˜μ—¬ μ˜€ν† λ§ˆνƒ€μ˜ μƒνƒœκ°€ λ³€κ²½λ˜λŠ” 과정을 그림으둜 λ‚˜νƒ€λ‚΄κ²Œ λ˜λŠ”λ°,λŒ€μΆ© 이런 λŠλ‚Œμ΄λ‹€.



    μœ„ μƒνƒœ μ „μ΄λ„λŠ” μœ ν•œ μ˜€ν† λ§ˆνƒ€μ˜ μƒνƒœκ°€ μ–΄λ–»κ²Œ λ³€κ²½λ˜λŠ” μ§€λ₯Ό ν‘œν˜„ν•œ 것인데, 이 κΈ°κ³„λŠ” μΈν’‹μœΌλ‘œ μ–΄λ–€ λ¬Έμžμ—΄μ„ λ°›μ•„μ„œ 이 λ¬Έμžμ—΄μ΄ a라면 μƒνƒœ1둜 λ³€κ²½λ˜λ©°, κ·Έ 이후에 μ˜€λŠ” λ¬Έμžμ—΄μ΄ b라면 μƒνƒœ2둜 λ³€κ²½λ˜λŠ” κ°„λ‹¨ν•œ 기계이닀. 그리고 μƒνƒœ2λŠ” 이 기계가 λ³€κ²½ν•  수 μžˆλŠ” μ΅œμ’… μƒνƒœμ΄κΈ° λ•Œλ¬Έμ— κ²Ήλ™κ·ΈλΌλ―Έλ‘œ ν‘œν˜„ν•΄μ£Όμ—ˆλ‹€.

    κ²°κ΅­ 이 기계가 μΈν’‹μœΌλ‘œ μ–΄λ–€ λ¬Έμžμ—΄μ„ 받은 후에 μƒνƒœκ°€ λκΉŒμ§€ λ‚˜μ•„κ°”λ‹€λ©΄ ab, aab, aaa...b λ“±μ˜ λ¬Έμžμ—΄μ΄λΌλŠ” 것이 보μž₯λ˜λŠ” 것이닀. 그리고 이 κΈ°κ³„λŠ” a+bμ΄λΌλŠ” μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œλ„ ν‘œν˜„ν•  수 μžˆλ‹€. 즉, ν•„μžκ°€ κ·Έλ¦° 기계와 a+bλΌλŠ” μ •κ·œ ν‘œν˜„μ‹μ€ κ°œλ…μ μœΌλ‘œ 같은 것이며, 이 μ •κ·œ ν‘œν˜„μ‹μ€ μœ„μ˜ 기계λ₯Ό ν‘œν˜„ν–ˆλ‹€κ³  봐도 λ¬΄λ°©ν•˜λ‹€. (μœ ν•œ μ˜€ν† λ§ˆνƒ€μ™€ μ •κ·œ ν‘œν˜„μ€ λ™μΉ˜κ΄€κ³„λΌκ³ λ„ ν‘œν˜„ν•œλ‹€)

    μ΄λ ‡κ²Œ μ–΄λ–€ μƒνƒœμ—μ„œ λ‹€λ₯Έ μƒνƒœλ‘œ 변경될 수 μžˆλŠ” 길이 ν•˜λ‚˜ 밖에 μ—†λŠ” κΈ°κ³„λŠ” μœ„μ˜ μƒνƒœ 전이도 그림만 봐도 이 기계가 μ–΄λ–»κ²Œ μž‘λ™ν•  μ§€ λ‹¨λ²ˆμ— μ•Œ 수 μžˆλ‹€. κ·Έ μ΄μœ λŠ” μ–΄λ–€ μƒνƒœμ—μ„œ λ‹€μŒ μƒνƒœλ‘œ λ‚˜μ•„κ°ˆ μˆ˜μžˆλŠ” 길이 단 ν•˜λ‚˜λ§Œ μ‘΄μž¬ν•˜κΈ° λ•Œλ¬ΈμΈλ°, 이런 μœ ν•œ μ˜€ν† λ§ˆνƒ€λŠ” μƒνƒœκ°€ λ³€κ²½λ˜λŠ” 길이 이미 λ‹€ κ²°μ •λ˜μ–΄μžˆλ‹€κ³  ν•΄μ„œ 결정적 μœ ν•œ μ˜€ν† λ§ˆνƒ€(Deterministic Finite Automaton, DFA)라고 λΆˆλ¦°λ‹€.

    DFAλŠ” 이처럼 ꡬ쑰가 κ°„κ²°ν•˜κ³  κΈ°κ³„μ˜ μƒνƒœλ₯Ό λͺ¨λ‘ 예츑 κ°€λŠ₯ν•˜κΈ° λ•Œλ¬Έμ— ν”„λ‘œκ·Έλž¨μœΌλ‘œ μž‘μ„±ν•˜κΈ°λ„ νŽΈν•˜κ³  νš¨μœ¨λ„ 잘 λ‚˜μ˜€μ§€λ§Œ ν•œ κ°€μ§€ 단점이 μ‘΄μž¬ν•œλ‹€.

    difficult 제한적인 상태 변경만 가능한 DFA로는 언어의 구조를 표현하기가 너무 빡세다...

    이게 μ™œ μ–΄λ €μš΄ 걸까? λ¬Όλ‘  방금 ν•„μžκ°€ μ˜ˆμ‹œλ‘œ λ“€μ—ˆλ˜ a+bλΌλŠ” κ°„λ‹¨ν•œ μ •κ·œ ν‘œν˜„μ‹μ΄λΌλ©΄ μƒνƒœ 전이도도 DFA둜 κ°„λ‹¨ν•˜κ²Œ κ·Έλ €λ‚Ό 수 μžˆμ§€λ§Œ λ§Œμ•½ ORλ₯Ό μ˜λ―Έν•˜λŠ” (a|b)b같은 μ •κ·œ ν‘œν˜„μ‹μ„ DFA둜 ν‘œν˜„ν•˜λ €κ³  ν•˜λ©΄ 생각보닀 λΉ‘μ„Έλ‹€. DFAλŠ” μ–΄λ–€ 인풋을 λ°›μ•˜μ„ λ•Œ 변경될 수 μžˆλŠ” μƒνƒœκ°€ 무쑰건 ν•œ 개 뿐이어야 ν•˜κΈ° λ•Œλ¬Έμ΄λ‹€. 이건 마치 ifλ¬Έ 없이 쑰건을 μ²˜λ¦¬ν•΄μ•Ό ν•˜λŠ” μƒν™©μ΄λž„κΉŒ.

    이런 이유둜 μ–Έμ–΄λ₯Ό μΈμ‹ν•˜λŠ” 기계λ₯Ό ν‘œν˜„ν•  λ•ŒλŠ” 변경될 수 μžˆλŠ” μƒνƒœκ°€ λ°˜λ“œμ‹œ ν•œ 개만 μ‘΄μž¬ν•˜λŠ” DFAκ°€ μ•„λ‹Œ μ—¬λŸ¬ κ°œλ„ μ‘΄μž¬ν•  수 μžˆλŠ” 기계λ₯Ό ν‘œν˜„ν•˜κ²Œ λ˜λŠ”λ°, 이런 κΈ°κ³„λŠ” μ–΄λ–€ 인풋이 λ“€μ–΄μ˜€λƒμ— λ”°λΌμ„œ 변경될 μƒνƒœκ°€ λ³€κ²½λ˜κΈ° λ•Œλ¬Έμ— μƒνƒœ μ „μ΄λ„λ§Œ λ΄μ„œλŠ” 이 기계가 μ–΄λ–»κ²Œ μž‘λ™ν• μ§€ μ˜ˆμΈ‘ν•˜λŠ” 것이 λΆˆκ°€λŠ₯ν•˜λ‹€.

    nfa

    그리고 이런 κΈ°κ³„λŠ” μ–΄λ–€ μƒνƒœμ—μ„œ λ‹€μŒ μƒνƒœλ‘œ λ‚˜μ•„κ°€λŠ” 길이 미리 κ²°μ •λ˜μ–΄μžˆλŠ” 것이 μ•„λ‹ˆλΌ 인풋에 따라 길이 λ³€κ²½λ˜κΈ° λ•Œλ¬Έμ— 비결정적 μœ ν•œ μ˜€ν† λ§ˆνƒ€(Nondeterministic Finite Automata, NFA)라고 ν•œλ‹€.

    μœ„ κΈ°κ³„λŠ” 빈 λ¬Έμžμ—΄μ„ μ˜λ―Έν•˜λŠ” Ο΅\epsilon을 λ°›μ•„λ“€μ΄λŠ” κ²ƒμœΌλ‘œ μ‹œμž‘ν•˜μ—¬, κ·Έ λ‹€μŒ λ¬Έμžμ—΄μ΄ a라면 μƒνƒœ2둜, b라면 μƒνƒœ3으둜 λ³€κ²½λ˜λŠ” ꡬ쑰λ₯Ό κ°€μ§€κ³  μžˆλ‹€. 즉, μ–΄λ–€ μƒνƒœμ—μ„œ λ‹€λ₯Έ μƒνƒœλ‘œ 변경될 수 μžˆλŠ” κ°œμˆ˜κ°€ 2개 이상인 것이닀. 즉, 이 κΈ°κ³„λŠ” 좔상 μ „μ΄λ„λ§Œ λ΄μ„œλŠ” νŠΉμ • μƒνƒœμ˜ λ‹€μŒ μƒνƒœκ°€ 무엇이 될지 μ•Œ μˆ˜κ°€ μ—†κΈ° λ•Œλ¬Έμ— β€œλΉ„κ²°μ •β€μ  μœ ν•œ μ˜€ν† λ§ˆνƒ€λΌκ³  λΆˆλ¦¬λŠ” 것이닀.

    이게 λ°”λ‘œ μ •κ·œ ν‘œν˜„μ‹μ΄ κ΅¬λ™λ˜λŠ” 기계인 μœ ν•œ μ˜€ν† λ§ˆνƒ€μ˜ λŒ€λž΅μ μΈ κ°œλ…μ΄λ©°, μ •κ·œ ν‘œν˜„μ‹μ€ λ°”λ‘œ 이런 κ°œλ…μ˜ 좔상 κΈ°κ³„μ—κ²Œ μ–Έμ–΄λ₯Ό μΈμ§€μ‹œν‚€λŠ” 것을 λͺ©ν‘œλ‘œ λ§Œλ“€μ–΄μ‘Œλ‹€. μ—¬κΈ°μ„œ λΆ„λͺ…νžˆ 짚고 λ„˜μ–΄κ°€μ•Ό ν•  점은 이 μœ ν•œ μ˜€ν† λ§ˆνƒ€λΌλŠ” κΈ°κ³„λŠ” β€œκΈ°μ–΅ν•  수 μžˆλŠ” μƒνƒœκ°€ 단 ν•˜λ‚˜ 밖에 μ—†λ‹€λŠ” 것”이닀.

    λ°”λ‘œ 이 μ œμ•½ 쑰건으둜 μΈν•΄μ„œ μ •κ·œ ν‘œν˜„μ‹μ΄λΌλŠ” μ–Έμ–΄μ˜ ν•œκ³„κ°€ λ°œμƒν•˜κ²Œ λœλ‹€.

    μ •κ·œ ν‘œν˜„μ‹μ˜ ν•œκ³„

    이처럼 μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ ν‘œν˜„ν•  수 μžˆλŠ” μ–Έμ–΄, 즉 μœ ν•œ μ˜€ν† λ§ˆνƒ€κ°€ 이해할 수 μžˆλŠ” μ–Έμ–΄λ₯Ό μ •κ·œ μ–Έμ–΄(Regular Language)라고 λΆ€λ₯Έλ‹€.

    μ•žμ„œ μ•Œμ•„λ³΄μ•˜λ“―μ΄ μ• μ΄ˆμ— μ •κ·œ ν‘œν˜„μ‹μ€ μˆ˜ν•™μ μœΌλ‘œ ν‘œν˜„ν•  수 μžˆλŠ” κ·œμΉ™μ΄ μ‘΄μž¬ν•˜λŠ” μ–Έμ–΄λ₯Ό ν‘œν˜„ν•˜λŠ” μš©λ„μΈλ°λ‹€κ°€ ν•œ λ²ˆμ— ν•œ κ°€μ§€ μƒνƒœλ§Œ κ°€μ§ˆ 수 μžˆλŠ” μœ ν•œ μ˜€ν† λ§ˆνƒ€μ—μ„œ κ΅¬λ™λ˜λŠ” 것을 μ „μ œλ‘œ ν•˜κΈ° λ•Œλ¬Έμ— λͺ¨λ“  μ–Έμ–΄λ₯Ό λ‹€ ν‘œν˜„ν•  수 μžˆλŠ” 것이 μ•„λ‹ˆλ‹€.

    μ‰½κ²Œ μƒκ°ν•΄μ„œ μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ λ¬Έλ§₯이 ꡉμž₯히 자유둜운 ν•œκ΅­μ–΄λ‚˜ μ˜μ–΄κ°™μ€ μ–Έμ–΄λŠ” μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ ν‘œν˜„ν•  수 μ—†λŠ” 것을 생각해보면 λœλ‹€. (μ• μ΄ˆμ— μžμ—°μ–΄λ₯Ό μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ ν‘œν˜„ν•  수 μžˆμ—ˆμœΌλ©΄ λ¨Έμ‹ λŸ¬λ‹μ„ 쓰지도 μ•ŠλŠ”λ‹€)

    즉, μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ ν‘œν˜„ν•  수 μžˆλŠ” μ–Έμ–΄μ—λŠ” λΆ„λͺ…ν•œ ν•œκ³„κ°€ μžˆλ‹€λŠ” 것이며, μ΄λ ‡κ²Œ μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ ν‘œν˜„ν•  수 μžˆλŠ” μ–Έμ–΄λ₯Ό μ •κ·œ 언어라고 λΆ€λ₯΄λŠ” 것이닀.

    언어들의 위계를 표현한 촘스키 위계에서도 정규(Regular) 언어는 가장 아래 쪽을 차지한다.

    사싀 μš°λ¦¬κ°€ 일반적인 λΉ„μ¦ˆλ‹ˆμŠ€ λ ˆλ²¨μ—μ„œ λ‹€λ£¨λŠ” λ¬Έμžμ—΄λ“€ 쀑에도 μ •κ·œ μ–Έμ–΄κ°€ μ•„λ‹Œ 것듀이 κ½€λ‚˜ μ‘΄μž¬ν•˜λŠ”λ°, κ·Έ 쀑 λŒ€ν‘œμ μΈ 것이 λ°”λ‘œ HTML 같은 언어이닀. 즉, μ–΄λ–€ λ¬Έμžμ—΄μ΄ μ œλŒ€λ‘œ 된 HTML인지 μ•„λ‹Œμ§€λ₯Ό μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ μ•Œμ•„λ‚΄λŠ” 것은 λΆˆκ°€λŠ₯ν•˜λ‹€λŠ” 것이닀.

    question 어라? 저는 분명 정규 표현식으로 HTML을 매칭해본 적이 있는데요?

    λ¬Όλ‘  ν•„μžλ„ μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ HTML을 λ§€μΉ­ν•΄λ³Έ κ²½ν—˜μ€ μžˆλ‹€. ν•˜μ§€λ§Œ μ•„λ§ˆ μš°λ¦¬κ°€ λ‹Ήμ‹œ HTML을 λ§€μΉ­ν•  λ•Œμ˜ κ·œμΉ™μ€ 전체 HTML이 μœ νš¨ν•œμ§€ μ•„λ‹Œμ§€κ°€ μ•„λ‹ˆλΌ ”<div> νƒœκ·Έκ°€ μ—΄λ Έλ‹€κ°€ λ‹«ν˜”μ–΄?”와 같은 HTML의 일뢀뢄을 κ²€μ¦ν•˜λŠ” μž‘μ€ κ·œμΉ™μ΄μ—ˆμ„ 것이닀.

    κ·Έλ ‡λ‹€λ©΄ μ™œ ν•„μžλŠ” μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ HTML의 μœ νš¨μ„±μ„ 검증할 수 μ—†λ‹€κ³  ν•œ κ²ƒμΌκΉŒ? κ·Έ 닡은 μ •κ·œ ν‘œν˜„μ‹μ΄ 사싀은 μƒνƒœλ₯Ό ν•˜λ‚˜λ§Œ κΈ°μ–΅ν•  수 μžˆλŠ” μœ ν•œ μ˜€ν† λ§ˆνƒ€λ₯Ό ν‘œν˜„ν•˜κ³  μžˆλ‹€λŠ” 것을 μƒκ°ν•˜λ©° HTML의 μƒκΉ€μƒˆλ₯Ό 보면 μ‰½κ²Œ μ•Œ μˆ˜κ°€ μžˆλ‹€.

    μ •κ·œ ν‘œν˜„μ‹μ΄ HTML을 μ΄ν•΄ν•˜μ§€ λͺ» ν•˜λŠ” 이유

    ν•„μžλ„ μ•Œκ³  μ—¬λŸ¬λΆ„λ„ μ•Œκ³  λͺ¨λ‘κ°€ μ•Œλ‹€μ‹œν”Ό HTML은 μ–΄λ–€ νƒœκ·Έκ°€ μ—΄κ³  λ‹«νžˆλ©° κ·Έ λ‚΄λΆ€μ—λŠ” λ¬΄ν•œνžˆ νƒœκ·Έκ°€ 쀑첩될 수 μžˆλŠ” ꡬ쑰λ₯Ό κ°€μ§€κ³  μžˆλ‹€.

    <main>
      <section>
        <h1>
          ...
        </h1>
      </section>
    </main>

    κ·Έλ ‡λ‹€λ©΄ λ§Œμ•½ μ–΄λ–€ 기계가 이런 HTML λ¬Έμžμ—΄μ„ μΈν’‹μœΌλ‘œ λ°›μ•˜μ„ λ•Œ, 이 HTML이 μœ νš¨ν•˜λ‹€λŠ” 것을 검증해내렀면 μ–΄λ–»κ²Œ ν•΄μ•Όν• κΉŒ?

    μ˜¬λ°”λ₯Έ HTML이라고 λΆ€λ₯Ό 수 μžˆλŠ” λ¬Έμžμ—΄μ€ λ°˜λ“œμ‹œ μ—¬λŠ” νƒœκ·Έμ™€ λ‹«λŠ” νƒœκ·Έκ°€ ν•¨κ»˜ μ‘΄μž¬ν•΄μ•Όν•œλ‹€. 즉, νƒœκ·Έκ°€ ν•œλ²ˆ μ—΄λ ΈμœΌλ©΄ 무쑰건 λ‹«ν˜€μ•Ό ν•œλ‹€λŠ” 것이닀. κ²°κ΅­ μ˜¬λ°”λ₯Έ HTML을 νŒλ³„ν•˜λŠ” κΈ°κ³„λŠ” 문자λ₯Ό ν•˜λ‚˜μ”© μ½μœΌλ©΄μ„œ 그와 λ™μ‹œμ— νƒœκ·Έμ˜ μ—΄κ³  λ‹«μŒμ„ μ•Œ 수 μžˆμ–΄μ•Ό ν•œλ‹€λŠ” 것이고, λŒ€μΆ© 이런 λŠλ‚ŒμœΌλ‘œ μž‘λ™ν•  것이닀.


    1. <main> λ¬Έμžμ—΄μ„ λ§Œλ‚¬λ‹€. 이후 <main> νƒœκ·Έκ°€ μ—΄λ Έλ‹€λŠ” μƒνƒœλ₯Ό μ €μž₯ν•œλ‹€.
    2. <section> λ¬Έμžμ—΄μ„ λ§Œλ‚¬λ‹€. 이후 <section> νƒœκ·Έκ°€ μ—΄λ Έλ‹€λŠ” μƒνƒœλ₯Ό μ €μž₯ν•œλ‹€.
    3. β€¦λ°˜λ³΅
    4. </main> λ¬Έμžμ—΄μ„ λ§Œλ‚¬λ‹€. λ§Œμ•½ <main> νƒœκ·Έκ°€ μ—΄λ¦° μƒνƒœκ°€ μ €μž₯λ˜μ–΄μžˆλ‹€λ©΄ μ˜¬λ°”λ₯΄κ²Œ λ‹«ν˜”λ‹€κ³  νŒλ‹¨ν•œλ‹€.
    5. </section> λ¬Έμžμ—΄μ„ λ§Œλ‚¬λ‹€. λ§Œμ•½ <section> νƒœκ·Έκ°€ μ—΄λ¦° μƒνƒœκ°€ μ €μž₯λ˜μ–΄μžˆλ‹€λ©΄ μ˜¬λ°”λ₯΄κ²Œ λ‹«ν˜”λ‹€κ³  νŒλ‹¨ν•œλ‹€.
    6. λ¬Έμžμ—΄μ˜ λκΉŒμ§€ νƒμƒ‰ν–ˆμ„ λ•Œ μ—΄λ¦° μƒνƒœλ‘œ λλ‚œ νƒœκ·Έκ°€ μ—†λ‹€λ©΄ 이 HTML은 μ˜¬λ°”λ₯Έ HTML이닀.

    μ—¬λŸ¬λΆ„μ΄ λ§Œμ•½ 이런 기계λ₯Ό λ§Œλ“ λ‹€κ³  μƒκ°ν•΄λ³΄μž. 이 κΈ°κ³„λŠ” λͺ‡ 개의 μƒνƒœλ₯Ό μ €μž₯ν•  수 μžˆλ„λ‘ μ„€κ³„λ˜μ–΄μ•Όν• κΉŒ?

    .
    .
    .

    닡은 λ¬΄ν•œλŒ€μ΄λ‹€

    ν˜Ήμ—¬λ‚˜ 잘 이해가 κ°€μ§€ μ•ŠλŠ”λ‹€λ©΄, μ—¬λŸ¬λΆ„μ΄ 직접 HTML νŒŒμ„œλ₯Ό λ§Œλ“ λ‹€κ³  μƒμƒν•΄λ³΄μž. μ•žμ„œ λ§ν–ˆλ“―μ΄ 이 νŒŒμ„œλŠ” νƒœκ·Έκ°€ 열리고 λ‹«ν˜”λ‹€λŠ” 사싀을 검증해야 ν•˜κΈ° λ•Œλ¬Έμ—, λ¬Έμžμ—΄μ„ 순차적으둜 νƒμƒ‰ν•˜λ©΄μ„œ μ–΄λ–€ νƒœκ·Έκ°€ μ—΄λ¦° 것을 μ˜λ―Έν•˜λŠ” λ¬Έμžμ—΄μ„ λ§Œλ‚¬λ‹€λ©΄ 이 μƒνƒœλ₯Ό μ–΄λ”˜κ°€μ— μ €μž₯해놓아야 ν•œλ‹€.

    μ΄λ•Œ μ–΄λ–€ λ°©μ‹μœΌλ‘œ μƒνƒœλ₯Ό κ΄€λ¦¬ν•˜λŠ”μ§€λŠ” μ‚¬λžŒλ§ˆλ‹€ μ‘°κΈˆμ”© λ‹€λ₯Ό 수 μžˆμ§€λ§Œ μ΄λ ‡κ²Œ 쌍으둜 μ—΄λ Έλ‹€ λ‹«νžˆλŠ” κ΄„ν˜Έλ₯Ό 검증할 λ•Œμ˜ 정석은 μŠ€νƒ(Stack)을 μ‚¬μš©ν•˜λŠ” 방법이닀.

    이렇게 여는 태그를 만났을 때 스택에 Push하고
    닫는 태그를 만났을 때 Pop하는 동작만 사용해도 허접한 HTML 파서는 구현 가능하다


    νƒœκ·Έκ°€ 아무리 μ€‘μ²©λ˜μ–΄λ„ λ°˜λ“œμ‹œ μ•ˆ μͺ½μ— μžˆλŠ” νƒœκ·Έκ°€ λ¨Όμ € λ‹«νž 수 밖에 μ—†λŠ” HTML ꡬ쑰λ₯Ό κ²€μ¦ν•˜κΈ°μ—λŠ” λ§ˆμ§€λ§‰μ— λ“€μ–΄μ˜¨ 녀석이 λ°˜λ“œμ‹œ λ¨Όμ € λ‚˜κ°€μ•Ό ν•˜λŠ” μŠ€νƒμ΄ μ•„μ£Ό 찰떑ꢁ합이기 λ•Œλ¬Έμ΄λ‹€.

    ν•˜μ§€λ§Œ μ—¬κΈ°μ„œ λ¬Έμ œλŠ” λ°”λ‘œ μŠ€νƒμ˜ 크기이닀. 이 μŠ€νƒμ˜ 크기λ₯Ό μ–Όλ§ˆλ‚˜ 크게 μž‘μ•„μ•Ό μ–΄λ–€ λ¬Έμžμ—΄μ΄λ“  μ†Œν™”ν•  수 μžˆλŠ” HTML νŒŒμ„œλ₯Ό λ§Œλ“€ 수 μžˆμ„κΉŒ?

    λ‹Ήμ—°νžˆ 크면 클수둝 μ’‹λ‹€. μŠ€νƒμ˜ 크기가 크면 클 수둝 더 κΉŠμ€ 깊이의 트리둜 이루어진 HTML도 νŒŒμ‹±ν•  수 있기 λ•Œλ¬Έμ΄λ‹€. ν•˜μ§€λ§Œ κ²°κ΅­ 이 μŠ€νƒμ˜ 크기λ₯Ό μ΄ˆκ³Όν•˜λŠ” 트리λ₯Ό κ°€μ§„ HTML이 νŒŒμ„œμ— λ“€μ–΄μ˜€λ©΄ ν”„λ‘œκ·Έλž¨μ€ ν„°μ§ˆ 수 밖에 μ—†λ‹€. 즉, μ–΄λ–€ λ¬Έμžμ—΄μ΄λ“  μ†Œν™”ν•  수 μžˆλŠ” HTML νŒŒμ„œλ₯Ό λ§Œλ“œλ €λ©΄ μŠ€νƒμ˜ 크기λ₯Ό λ¬΄ν•œν•˜κ²Œ μž‘μ•„μ•Όν•œλ‹€.

    μ •κ·œ ν‘œν˜„μ‹μ€ κ²°κ΅­ μœ ν•œ μ˜€ν† λ§ˆνƒ€μ΄λ‹€

    이처럼 μ–΄λ– ν•œ 기계가 HTML이 μ˜¬λ°”λ₯Έμ§€ μ•„λ‹Œμ§€λ₯Ό κ²€μ¦ν•˜κΈ° μœ„ν•΄μ„œλŠ” λ¬΄ν•œ 개의 μƒνƒœκ°€ ν•„μš”ν•˜λ‹€. ν•˜μ§€λ§Œ μ •κ·œ ν‘œν˜„μ‹μ€ 단 ν•œ 개의 μƒνƒœλ§Œμ„ κ°€μ§€λŠ” μœ ν•œ μ˜€ν† λ§ˆνƒ€λ₯Ό ν‘œν˜„ν•œ 것이기 λ•Œλ¬Έμ— λ‹Ήμ—°νžˆ λ¬΄ν•œ 개의 μƒνƒœλ₯Ό κ°€μ Έμ•Ό νŒŒμ‹±ν•  수 μžˆλŠ” HTML을 μ ˆλŒ€ 인지할 μˆ˜κ°€ μ—†λŠ” 것이닀.

    κ²°κ΅­ 핡심은 μ •κ·œ ν‘œν˜„μ‹μ΄ μƒνƒœλ₯Ό ν•˜λ‚˜ 밖에 κ°€μ§ˆ 수 μ—†λŠ” μœ ν•œ μ˜€ν† λ§ˆνƒ€λ₯Ό ν‘œν˜„ν•˜κ³  μžˆλ‹€λŠ” 것이며, μƒνƒœλ₯Ό ν•˜λ‚˜ 밖에 κ°€μ§ˆ 수 μ—†λŠ” κΈ°κ³„λ‘œλŠ” μ ˆλŒ€ ν•΄κ²°ν•  수 μ—†λŠ” λ¬Έμ œκ°€ μ‘΄μž¬ν•œλ‹€λŠ” 것이닀.

    κ·ΈλŸ¬λ‹ˆ μ–΄λ–€ λ¬Έμžμ—΄μ„ 보면 λ°”λ‘œ μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ ν•΄κ²°ν•˜λ €κ³  λ€λΉ„κΈ°λ³΄λ‹€λŠ” λ‚΄κ°€ 이 λ¬Έμžμ—΄μ„ νŒŒμ‹±ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ λ§Œλ“ λ‹€κ³  μƒκ°ν•΄λ³΄μ•˜μ„λ•Œ β€œλͺ‡ 개의 μƒνƒœβ€κ°€ ν•„μš”ν•œ μ§€λ₯Ό λ¨Όμ € κ³ λ―Όν•΄λ³΄λŠ” μ—°μŠ΅μ΄ ν•„μš”ν•˜λ‹€. λ§Œμ•½ 두 개 μ΄μƒμ˜ μƒνƒœκ°€ ν•„μš”ν•˜λ‹€λ©΄ 일단 μ •κ·œ ν‘œν˜„μ‹λ§ŒμœΌλ‘œ ν•΄κ²°ν•˜κΈ°λŠ” 쉽지 μ•Šμ€ 문제라고 νŒλ‹¨ν•  수 μžˆλŠ” 것이닀.

    λ¬Όλ‘  이런 상상 μ•Œκ³ λ¦¬μ¦˜μ€ μ΅μˆ™ν•œ μ‚¬λžŒκ³Ό μ΅μˆ™ν•˜μ§€ μ•Šμ€ μ‚¬λžŒμ˜ 문제 ν’€μ΄μ˜ 차이가 μ‘΄μž¬ν•˜κΈ° λ•Œλ¬Έμ— ν•˜λ‚˜μ˜ μƒνƒœλ§ŒμœΌλ‘œ ν•΄κ²°ν•  수 μžˆλŠ” 문제λ₯Ό μ—¬λŸ¬ 개의 μƒνƒœκ°€ ν•„μš”ν•˜λ‹€κ³  생각할 μˆ˜λ„ μžˆμ§€λ§Œ, κ·Έλž˜λ„ μ•Œκ³ λ¦¬μ¦˜μ€ 재λŠ₯의 μ˜μ—­μ΄ μ•„λ‹ˆλΌ μ—°μŠ΅μ˜ μ˜μ—­μ΄λ―€λ‘œ 1λ…„, 2λ…„ κΎΈμ€€νžˆ ν•˜λ‹€λ³΄λ©΄ μ‘°κΈˆμ”© 감을 μž‘λŠ” μ‹œκ°„μ΄ μ§§μ•„μ§ˆ 것이닀.

    마치며

    사싀 μ •κ·œ ν‘œν˜„μ‹μ˜ ν•œκ³„λŠ” κ·Έλƒ₯ β€œκ΄„ν˜Έμ˜ κΉŠμ΄μ— μ œν•œμ΄ μ—†λŠ” λ¬Έμžμ—΄μ€ 인지할 수 μ—†λ‹€β€μ²˜λŸΌ κ°„λ‹¨ν•œ λ§λ‘œλ„ μ„€λͺ…ν•  수 μžˆλŠ” 뢀뢄이닀.

    ν•˜μ§€λ§Œ κ·Έλƒ₯ μ΄λ ‡κ²Œ μ„€λͺ…ν•˜κ³  μ™Έμš°λŠ” 것 λ³΄λ‹€λŠ” μ •κ·œ ν‘œν˜„μ‹μ΄ μ–΄λ–€ 문제λ₯Ό ν•΄κ²°ν•˜κΈ° μœ„ν•΄ νƒ„μƒν•œ 도ꡬ인지, μ–΄λ–€ 컨셉을 κ°€μ§€κ³  μžˆλŠ”μ§€λ₯Ό ν•¨κ»˜ μ΄μ•ΌκΈ°ν•˜λ©΄ 쑰금 더 μ΄ν•΄ν•˜κΈ°κ°€ μ‰¬μšΈ 것이라고 μƒκ°ν–ˆλ‹€.

    μ •κ·œ ν‘œν˜„μ‹μ— 이런 ν•œκ³„κ°€ μ‘΄μž¬ν•œλ‹€λŠ” 사싀을 λͺ¨λ₯Έλ‹€λ©΄ ”<ul> νƒœκ·Έ μ•ˆμ— <li> νƒœκ·Έκ°€ μ‘΄μž¬ν•˜λ‹ˆ?” 같은 μ œν•œμ μΈ 상황을 μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œ ν•΄κ²°ν–ˆλ˜ κ²½ν—˜μ„ λ°”νƒ•μœΌλ‘œ, 해결이 λΆˆκ°€λŠ₯ν•œ 문제λ₯Ό ν•΄κ²°ν•˜λ €κ³  λ„μ „ν•˜κ²Œ 될 μˆ˜λ„ μžˆλ‹€.

    λ¬Όλ‘  μ •κ·œ ν‘œν˜„μ‹μ΄ λ¬Έμžμ—΄μ„ λ‹€λ£° λ•Œ λ§Žμ€ νŽΈλ¦¬ν•¨μ„ μ£ΌλŠ” 것은 사싀이닀. ν•˜μ§€λ§Œ μ•žμ„œ 이야기 ν–ˆλ“― μ •κ·œ ν‘œν˜„μ‹μ˜ λ°±νŠΈλž˜ν‚Ή μ•Œκ³ λ¦¬μ¦˜μ€ μ˜ˆμƒν•˜μ§€ λͺ» ν–ˆλ˜ 퍼포먼슀 이슈λ₯Ό κ°€μ Έλ‹€ 쀄 μˆ˜λ„ 있고, μ •κ·œ ν‘œν˜„μ‹μœΌλ‘œλŠ” κ²°μ½” ν’€μ§€ λͺ»ν•˜λŠ” λ¬Έμ œλ„ μ‘΄μž¬ν•˜κΈ° λ•Œλ¬Έμ— 항상 μ •κ·œ ν‘œν˜„μ‹μ΄λΌλŠ” 도ꡬλ₯Ό μ‚¬μš©ν•œλ‹€κ³  μ„ νƒν•˜κΈ° μ „μ—λŠ” β€œμ΄κ²Œ 정말 효율적인 선택인지”에 λŒ€ν•œ 고민을 ν•΄λ³΄λŠ” μ—°μŠ΅μ΄ ν•„μš”ν•˜λ‹€.

    μ΄μƒμœΌλ‘œ HTML을 μ •κ·œ ν‘œν˜„μ‹λ§ŒμœΌλ‘œ νŒŒμ‹±ν•  수 μžˆμ„κΉŒ? ν¬μŠ€νŒ…μ„ λ§ˆμΉœλ‹€.

    Evan Moon

    🐒 거뢁이처럼 μ‚΄μž

    κ°œλ°œμ„ μž˜ν•˜κΈ° μœ„ν•΄μ„œκ°€ μ•„λ‹Œ κ°œλ°œμ„ 즐기기 μœ„ν•΄ λ…Έλ ₯ν•˜λŠ” κ°œλ°œμžμž…λ‹ˆλ‹€. μ‚¬μ†Œν•œ 생각 정리뢀터 νŠœν† λ¦¬μ–Ό, μ‚½μ§ˆκΈ° 정도λ₯Ό 주둜 끄적이고 μžˆμŠ΅λ‹ˆλ‹€.