Regex! - to była pierwsza rzecz którą pomyślałem widząc treść dzisiejszego zadania, jako że awk opiera się mocno na wyrażeniach regularnych założyłem że nadal będzie to dobre narzędzie, jednak nie obyło się bez kilku problemów związanych z niedociągnięciami starych narzędzi a także brakiem jednolitego standardu w zapisie wyrażeń regularnych.

Zadanie

Na wejściu otrzymujemy stringa, będącego kodem źródłowym do języka programowania elfów:

xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)+mul(32,64]then(mul(11,8)mul(8,5))

Język programwania wspiera jedynie funkcję mul(a,b), której wynikiem jest pomnożenie dwóch argumentów. Wynikiem programu jest suma wyników wszystkich wywołań mul.

Rozwiązanie

Uznałem że podzielę problem na dwie częsci:

  1. parsowanie kodu źródłowego
  2. egzekucja programu

1. Parsowanie kodu źródłowego

Z kodu źródłowego muszę wyciągnąć poszczególne operacje mul, najlepszym sposobem na to będzie użycie wyrażenia regularnego. W tym przypadku jest ono dosyć proste:

mul\([0-9]+,[0-9]+\)   # \d+ oznacza niepusty ciąg cyfr

Wyrażenie to wspiera tylko liczby dodatnie, ale z tego co widzę w inpucie są tylko takie.

grep

Plan jest taki żeby wypisać wywołania mul po jednym w każdej linijce. Narzędziem do tego stworzonym jest grep.

Ciekawostka: nazwa grep pochodzi od komendy g/re/p w edytorze ed, która oznacza Global Regular Expression and Print.

Domyślnie grep wypisuje całe linijki w których znajduje się nasz pattern, jednak my chcemy wypisać tylko fragmenty które nas interesują, od tego jest flaga: -o. Dodatkowo przyda się też flaga -E, która uaktywnia wyrażenia regularne w rozszerzonej formie, domyślnie wyrażenia regularne w grepie są bardzo ograniczone.

Uruchamiamy poniższą komendę i otrzymujemy czytelny output:

$ grep -oE "mul\([0-9]+,[0-9]+\)" input.txt
mul(2,4)
mul(5,5)
mul(11,8)
mul(8,5)

Egzekucję programu chciałbym wykonać w AWK, jednak powyższy format, nie do końca temu sprzyja, dużo lepiej byłoby otrzymać same argumenty:

2 4
5 5
11 8
8 5

Przydałoby się stworzyć capture grupy, z argumentów w nawiasach, jednak po dłuższym analizowaniu manpage grepa i poszukiwaniu informacji na ten temat na stackoverflow doszedłem do tego że grep nie wspira printowania tylko poszczególnych capture grup :(

W tym celu przekierujemy output poprzedniej komendy do programu sed (stream editor)

grep ... | sed -En 's/mul\(([0-9]+),([0-9]+)\)/\1 \2/p' > preprocessed

Na szybko tłumacząc:

  • -E - rozszerzone regexy
  • -n - nie wypisuj oryginalnych linijek tekstu
  • s/ - oznacza zaczęcie komendy substytucji
  • /mul.../ nasz pattern jest podobny jak poprzednio ale tym razem obejmujemy jeszcze nasze argumenty w nawiasy ([0-9]+), żeby móc użyć referencji do nich później
  • /\1 \2 - zasępujemy poprzedni pattern pierwszą i drgugą złapaną w nim grupą
  • /p - wypisujemy wynik

Po uruchomieniu tych komend otrzymujemy program w wygodniejszej formie.

2. Egzekucja programu

Po takim preprocessingu egzekucja programu jest dziecinnie prosta:

awk '{ res += $1 * $2 } END { print res }' preprocessed

Otrzymujemy poprawny wynik :)

Jednolinijkowiec

grep -oE "mul\([0-9]+,[0-9]+\)" input.txt | sed -En 's/mul\(([0-9]+),([0-9]+)\)/\1 \2/p' | awk '{res+=$1*$2}END{print res}'

Część 2

W tej części dochodzą dwie nowe komendy

  • do() uruchamia następujące po niej instrukcje mul
  • don't() wyłącza następujące po niej instrukcje mul mul patrzy tylko na ostatnią komendę do albo don't

Rozszerzenie parsera

Musimy rozszerzyć nasz parser o dodatkowe komendy, z tego co teraz widzę to że podzieliliśmy parsowanie na grep i sed, może być teraz całḱiem pomocne, grep zajmie się tylko wyciąganiem wywyołań funkcji, zaś sed będzie odpowiedzialny za parsowanie ich argumentów.

grep

grep -oE "[a-z\']+\([0-9\,]*)" input.txt > extracted

Nazwa funkcji może być dowolnym stringiem zawierającym małe litery i ewentualnie pojedyńczy cudzysłów, z kolei w nawiasach oczekujemy cyfr lub przecinków (w liczbie 0 lub więcej).

sed

Tym razem w sedzie będzie kilka komend, dlatego wsadzimy go do swojego własnego pliku:

#parse.sed
s/[a-z\']*mul\(([0-9]+),([0-9]+)\)/mul \1 \2/p
s/[a-z\']*do\(\)/do/p
s/[a-z\']*don't\(\)/dont/p

Musiałem dodać [a-z\'] gdyż zdarza się że grep znajdzie komendy typu: xmul albo 'mul, dodatkowo usunąłem ten wkurzający apostrof z don't

Konwertujemy kod za pomocą komendy

sed -Enf parse.sed extracted >

W wyniku otrzymujemy piękną listę komend:

mul 2 4
dont
mul 5 5
mul 11 8
do
mul 8 5

Czy nie przypomina to trochę assembly?

Rozszerzenie interpretera

Jako że wprowadziliśmy dwie nowe komendy musimy rozszerzyć nasz skrypt w awk na szczęście nie będzie to trudne zadanie:

prog.awk
$1 == "do"   { disabled = 0 }
$1 == "dont" { disabled = 1 }
$1 == "mul"  {
    if (disabled) next
    res += $2 * $3
}
END { print res }

Cały pipeline uruchamiamy w ten sposób:

grep -oE "[a-z\']+\([0-9\,]*)" input.txt | sed -Enf parse.sed | awk -f prog.awk

Podsumowanie

Zadnie pozwoliło mi odświeżyć regexa i seda, nieco frustrujące są ograniczenia grepa i różnice w silnikach regexa, np. u mnie sed nie wspiera regexów Perlowych (-P). W pewnym momencie myślałem czy nie użyć dużo nowszego narzędzia ripgrep, rozwiązuje ono braki grepa w możliwości substytucji złapanych grup, jednak uznałem że na razie jestem jeszcze w stanie zostać przy podstawowch, portable narzędziach.

Myślę że mój kod jest też przygotowany na ewentualne rozszerzenie w przyszłości, czuję że wrócimy jeszcze do tego zadania w późniejszych dniach gdyż w outpucie grepa widziałem sporo różnych, nie wspomnianych w dzisiejszym zadaniu komend:

who()
how()
select()
'where()
...