1

Тема: sed, perl та інша регекс-езотерика

Вирішив створити тему, в якій можна поділитися різними крутими штуками, зробленими на самих регексах (чи майже на самих). У першу чергу, програми, написані на sed, perl та інших подібних мовах. Хоча після успіху perl у 90-х практично в кожній сучасній мові з'явились інструменти для роботи з регулярними виразами — тому чітких обмежень нема, це може бути й php, Python, JS — за умови, що регулярні вирази є основним інструментом реалізації думки автора.

Наприклад, ось такий код:

#!/usr/bin/env sed -f
# Ханойська вежа
# Ввід: кількість дисків цифрами.
# Вивід: розв'язок задачі для заданої кількості дисків.
# Підтримуються числа в діапазоні від 1 до 999, 
# за умови достатньої кількості пам'яті та часу :)
s/[^0-9]//g
s/^/000/
s/.*\(.\)\(.\)\(.\)/\1C\2X\3I/
s/0[A-Z]//g
s/\(.\)\(.\)/\1987654321\2/g
s/\([0-9]\)[0-9]*\1//g
:roman
s/[0-9]\([A-Z]\)/\1\1/g
/[0-9]/broman
s/C/XXXXXXXXXX/g
s/X/IIIIIIIIII/g
s/./-/g
s/^..*$/A&B/
:loop
s/\([ABC]\)-\(--*\)\([ABC]\)/\1\2\1\3 \1-\3 \1\3\2\3/g
s/AB\|BA/C/g
s/AC\|CA/B/g
s/BC\|CB/A/g
/--/bloop
s/-/->/g

Або інша реалізація

#!/usr/bin/env sed -f
# Ханойська вежа (з використанням перекодування y/.../.../)
# Приймає числа 1...40
/^0$/bend
s/^/(A->B)/
# Конвертувати 10...40 в a...z,E,F,G,H :
/)1./y/0123456789/abcdefghij/
/)2./y/0123456789/klmnopqrst/
/)3./y/0123456789/uvwxyzEFGH/
s/).\(.\)$/)\1/
:loop
/1$/bend
h
y/AC/CA/
x
y/BC/CB/
G
s/)[^(]*(/ A->B /
y/123456789abcdefghijklmnopqrstuvwxyzEFGH/0123456789abcdefghijklmnopqrstuvwxyzEFG/
bloop
:end
s/[^-> ABC]//g

У другому варіанті вежі основним інструментом є не власне регекси, а простіший інструмент — перекодування. Завдяки цьому, програма працює трохи швидше, ніж попередня.
Обидва скрипти можуть приймати більші числа, ніж реально здатні обробити: оскільки увесь результат у процесі обробки тримається в оперативці, розв'язок задачі для 30 дисків вимагатиме декілька ГБ...

Подякували: ReAl1

2

Re: sed, perl та інша регекс-езотерика

Ну, вітаю! Вам вдалося із снайперської рушниці стріляючи гумовими кульками забити цвях на відстані 2 км.

Подякували: bvn1

3

Re: sed, perl та інша регекс-езотерика

При цьому, код займає не набагато більше, ніж якби я вибрав молоток. 20 рядків на sed проти 10 на паскалі — по моєму, доволі непогано.

4 Востаннє редагувалося P.Y. (21.11.2016 19:39:27)

Re: sed, perl та інша регекс-езотерика

Зі шматка коду на початку першого прикладу вирішив зробити конвертер в римські цифри, потім дописав функціонал для зворотнього перетворення.

#!/usr/bin/env sed -f
# Конвертер арабські цифри <=> римські цифри
# Підтримуються числа в діапазоні від 1 до 9999
/[0-9]/!btoarab
s/[^0-9]//g
s/^/000/
s/.*\(.\)\(.\)\(.\)\(.\)/\1M\2C\3X\4I/
s/0[A-Z]//g
s/\(.\)\(.\)/\1987654321\2/g
s/\([0-9]\)[0-9]*\1//g
:roman
s/[0-9]\([A-Z]\)/\1\1/g
/[0-9]/broman
s/CCCCC/D/
s/CCCC/CD/
s/DCD/CM/
s/XXXXX/L/
s/XXXX/XL/
s/LXL/XC/
s/IIIII/V/
s/IIII/IV/
s/VIV/IX/
b
:toarab
# конвертер з римських цифр в арабські
y/mdclxvi/MDCLXVI/
s/CM/DCD/g
s/XC/LXL/g
s/IX/VIV/g
s/\(M\)\([^MCD]\|$\)/\10C\2/g
s/\([CD]\)\([^CDXL]\|$\)/\10X\2/g
s/\([XL]\)\([^XLIV]\|$\)/\10I\2/g
:arab
s/0I/0/g
s/VIV\|IIIIIIIII/9/g
# (додаткові символи для вищих порядків не використовуються, 
# тому 4000...9000 записуються повтором знаку тисяч — 
# доводиться дублювати обидва формати)
s/IV/4/g
s/VIII\|IIIIIIII/8/g
s/VII\|IIIIIII/7/g
s/VI\|IIIIII/6/g
s/V\|IIIII/5/g
s/IIII/4/g
s/III/3/g
s/II/2/g
s/I/1/g
y/MDCLXVI/CLXVI?!/
/[VI]/barab

5 Востаннє редагувалося P.Y. (21.08.2021 18:19:42)

Re: sed, perl та інша регекс-езотерика

Перевірка подільності на 7 та 13:

mod7.sed
#!/usr/bin/env sed -f
# :mode=perl:
# Перевірка подільності на 7
# Записати число N в буфер:
h
# Конвертувати число у псевдоримське з цифрами IXCMYD (після мільйона циклічно повторюються):
s/[^0-9]//g
s/^/_/
:roman
y/IXCMYG/XCMYGI/
s/_/9876543210_/
:roman1
/\([0-9]\)_\1/broman2
s/\([0-9]*\)[0-9]\(_[0-9]\)/I\1\2/
/[0-9]_/broman1
:roman2
s/[0-9]*_[0-9]/_/
/[0-9]/broman
s/_//
:expand
# Для сотень, десятків, одиниць:
# x = x//100*2 + x%100:
s/C/II/g
# x = x//10*3 + x%10:
s/X/III/g
# Повторити це ж для тисяч, десятків тисяч, сотень тисяч (обмінявши IXC<=>MYG):
y/IXCMYG/MYGIXC/
/[XCYG]/bexpand
# Позбутися всіх MI, IM, семикратних повторів:
:reduce
s/IIIIIII//g
s/MI//g
y/MI/IM/
/M/breduce
/IIIIIII/breduce
# Якщо результат пустий, вивести N%7 == 0, інакше N%7 != 0:
G
s/[^0-9I]//g
s/$/ % 7 == 0/
/I/s/==/!=/
s/I//g
mod13.sed
#!/usr/bin/env sed -f
# :mode=perl:
# Перевірка подільності на 13
# Записати число N в буфер:
h
# Конвертувати число у псевдоримське з цифрами IXCMYD (після мільйона циклічно повторюються):
s/[^0-9]//g
s/^/_/
:roman
y/IXCMYG/XCMYGI/
s/_/9876543210_/
:roman1
/\([0-9]\)_\1/broman2
s/\([0-9]*\)[0-9]\(_[0-9]\)/I\1\2/
/[0-9]_/broman1
:roman2
s/[0-9]*_[0-9]/_/
/[0-9]/broman
s/_//
:expand
# Для сотень, десятків, одиниць:
# x = -x//100*4 + x%100:
s/C/MMMM/g
# x = -x//10*3 + x%10:
s/X/MMM/g
# Повторити це ж для тисяч, десятків тисяч, сотень тисяч (обмінявши IXC<=>MYG):
y/IXCMYG/MYGIXC/
/[XCYG]/bexpand
# Позбутися всіх MI, IM, 13-кратних повторів:
:reduce
s/IIIIIIIIIIIII//g
s/MI//g
y/MI/IM/
/M/breduce
/IIIIIIIIIIIII/breduce
# Якщо результат пустий, вивести N%13 == 0, інакше N%13 != 0:
G
s/[^0-9I]//g
s/$/ % 13 == 0/
/I/s/==/!=/
s/I//g

Властивості обох дільників дозволяють використати приблизно однакову послідовність дій для перевірки ділення на них, працюючи з діленим як з десятковим числом. Розмір вхідного числа обмежується лише довжиною рядка, потрібною для псевдоримського запису (коли кожна десяткова цифра записується відповідною їй кількістю літер).

6 Востаннє редагувалося P.Y. (27.08.2021 13:21:10)

Re: sed, perl та інша регекс-езотерика

Виявив, що sed обробляє всі шматки коду, задані різними способами (-f ФАЙЛ чи -e ІНСТРУКЦІЇ) як єдину програму зі спільними мітками. Цим можна скористатися, щоб передати програмі на sed додаткові опції (що може бути корисно, оскільки чогось назразок сішних argc, argv програма, написана на цій примітивній мові, безпосередньо не отримує, та й змінних у звичному сенсі в ній нема). Для роботи з мітками використовуються директиви
:МІТКА — задає мітку
bМІТКА — перехід на мітку (аналог goto); у варіанті без мітки, завершує обробку рядка; також може мати префікс умови перед собою, що дозволяє використовувати його для умовного переходу (потрібного, щоб організувати галуження, цикл з умовою виходу. Структурованих алгоритмічних конструкцій у цій мові нема).

Приклад програми (батник, що передає додаткові параметри sed-скрипту, підставляючи їх в імена міток):

babel2.bat
::xxxx ; /.*/!a\
@sed -f "%~f0" -e "b; :*format; bformat%1; :*format2; bformat2%1" & goto :eof
# :mode=perl:
# Перетворення з 10-кової в 60-кову систему
s/[^0-9.]//g
s/^/:_/
:scan
# n*=60:
s/C/ICCCC/g
y/r/C/
s/_/9876543210_/
:scan1
/\([0-9]\)_\1/bscan2
s/\([0-9]*\)[0-9]\(_[0-9]\)/r\1\2/
/[0-9]_/bscan1
:scan2
s/[0-9]*_[0-9]/_/
:60
s/^\([^:]\)/:\1/
s/:\(C*\)I/r:\1/g
/I/b60
s/rrrrrrrrrr/C/g
s/CCCCCC/I/g
/I/b60
/_[0-9]/bscan
s/_//
s/^:*//
# і так само з дробовою частиною (якщо є):
/\./!bendfrac
y/Cr/<l/
s/$/_:/

:fscan
# перетворити останню арабську цифру на серію вавилонських одиниць:
s/_/_0123456789/
:fscan1
/\([0-9]\)_\1/bfscan2
s/\([0-9]_\)[0-9]\([0-9]*\)/\1\2r/
/_[0-9]/bfscan1
:fscan2
s/[0-9]_[0-9]*/_/

# поділити на 10:
/:$/!s/$/:/
s/\(r*\):/:\1\1\1\1\1\1/g
y/C/r/
s/rrrrrrrrrr/C/g

/[0-9]_/bfscan
s/_://
s/:*$//
y/<l/Cr/
:endfrac
b*format

# перетворити вавилонські цифри в десяткові:
:format-d
s/Cr/C_r/g
s/C$/C_0/
s/C:/C_0:/g
s/C\./C_0./
s/[Cr]*/\00123456789/g
:10
s/[Cr][0-9]//g
/[Cr]/b10
s/\([0-9]\)[0-9]*/\1/g
s/_//g
s/::/:0:/g
s/::/:0:/g
s/\.:/.0:/
s/:\./:0./
b

# або у стиснуті вавилонські (що простіше):
:format
:format-b
s/rrr/m/g
s/rr/n/g
s/CC/E/g
b

# або в зображення:
:format-i
:format-img
:format-html
s/[Cr]*/[\0]/g
s/Cr/C][r/g
s/rrr/m/g
s/rr/n/g
b*format2
:format2-i
:format2-img
s/\[mmr]/[Seven]/g; s/\[mmn]/[Eight]/g; s/\[mmm]/[Nine]/g
s/\[mr]/[Four]/g;   s/\[mn]/[Five]/g;   s/\[mm]/[Six]/g
s/\[r]/[One]/g;     s/\[n]/[Two]/g;    s/\[m]/[Three]/g
s/\[CCCCC]/[Fifty]/g; s/\[CCCC]/[Forty]/g; s/\[CCC]/[Thirty]/g; s/\[CC]/[Twenty]/g; s/\[C]/[Ten]/g
s/:/  /g
s!\[\([a-z]*\)]![img]https://web.archive.org/web/19991116085124im_/http://it.stlawu.edu/~dmelvill/mesomath/pix/\1.gif[/img]!ig
b

# html (від зображення відрізняється продовженням):
:format2-html
s/\[r]/[12079]/g;   s/\[n]/[1222B]/g;   s/\[m]/[12408]/g 
s/\[mr]/[12409]/g;  s/\[mn]/[1240A]/g;  s/\[mm]/[1240B]/g 
s/\[mmr]/[1240C]/g; s/\[mmn]/[1240D]/g; s/\[mmm]/[1240E]/g
s/\[C]/[1230B]/g;    s/\[CC]/[1230B][1230B]/g; s/\[CCC]/[1230D]/g
s/\[CCCC]/[1240F]/g; s/\[CCCCC]/[12410]/g
s/\[/\&#x/g; s/]/;/g
b

Програма конвертує десяткові числа в різні формати 60-кової системи (з десятковим представлення розрядів, транслітеровану вавилонську, клинопис зображеннями чи html-кодами символів)

D:\> echo 9783961689|babel2
Cn:ECmr:EECmm:mmr:mmn:mmm

D:\> echo 9783961689|babel2 -d
12:34:56:7:8:9

D:\> echo 9783961689|babel2 -html
&#x1230B;&#x1222B;:&#x1230D;&#x12409;:&#x12410;&#x1240B;:&#x1240C;:&#x1240D;:&#x1240E;
echo 9783961689|babel2 -img

https://web.archive.org/web/19991116085124im_/http://it.stlawu.edu/~dmelvill/mesomath/pix/Ten.gifhttps://web.archive.org/web/19991116085124im_/http://it.stlawu.edu/~dmelvill/mesomath/pix/Two.gif  https://web.archive.org/web/19991116085124im_/http://it.stlawu.edu/~dmelvill/mesomath/pix/Thirty.gifhttps://web.archive.org/web/19991116085124im_/http://it.stlawu.edu/~dmelvill/mesomath/pix/Four.gif  https://web.archive.org/web/19991116085124im_/http://it.stlawu.edu/~dmelvill/mesomath/pix/Fifty.gifhttps://web.archive.org/web/19991116085124im_/http://it.stlawu.edu/~dmelvill/mesomath/pix/Six.gif  https://web.archive.org/web/19991116085124im_/http://it.stlawu.edu/~dmelvill/mesomath/pix/Seven.gif  https://web.archive.org/web/19991116085124im_/http://it.stlawu.edu/~dmelvill/mesomath/pix/Eight.gif  https://web.archive.org/web/19991116085124im_/http://it.stlawu.edu/~dmelvill/mesomath/pix/Nine.gif

Подякували: tchort1