Jaki jest związek między językami programowania, wyrażeniami regularnymi i językami formalnymi

Rozejrzałem się w sieci, szukając odpowiedzi na to pytanie i wydaje się, że wszyscy domyślnie znają odpowiedź oprócz mnie. Przypuszczalnie dzieje się tak, ponieważ jedynymi osobami, które się opiekują, są osoby z wyższym wykształceniem na ten temat. Z drugiej strony zostałem wrzucony w głęboki koniec za zadanie do szkoły średniej.

Moje pytanie brzmi: jak dokładnie języki programowania są powiązane z językami formalnymi? Wszędzie, gdzie czytam, mówi się coś w rodzaju „języków formalnych używa się do definiowania gramatyki języków programowania”.

Teraz, z tego, co udało mi się zebrać, język formalny to szereg reguł produkcji, które mają zastosowanie do określonego zestawu symboli (alfabetu języka). Te reguły produkcji definiują zestaw przekształceń, takich jak:

b -> a

aaa->c

Można to zastosować tak, aby:

abab->aaaa aaaa-> ca

Na marginesie, jeśli zdefiniujemy, że alfabet naszego języka formalnego to {a, b, c}, to a i b nie są terminalami, a c jest terminalem, ponieważ nie można go przekształcić (proszę poprawić mnie, jeśli się mylę że).

Biorąc to wszystko pod uwagę, jak do licha dotyczy to języków programowania? Często stwierdza się również, że wyrażenie regularne jest używane do analizowania języka w jego formie tekstowej, aby zapewnić poprawną gramatykę. To ma sens. Następnie stwierdza się, że wyrażenia regularne są definiowane przez języki formalne. Regex zwraca true lub false (przynajmniej według mojego doświadczenia) w zależności od tego, czy automaty skończone reprezentujące wyrażenia regularne osiągną punkt docelowy. O ile widzę, nie ma to nic wspólnego z transformacjami *.

Do kompilacji samego programu przypuszczam, że język formalny byłby w stanie przekształcić kod w kod o niższym poziomie, ostatecznie osiągając asemblację dzięki złożonemu zestawowi reguł, które sprzęt mógłby wtedy zrozumieć.

Tak to wygląda z mojego zagubionego punktu widzenia. Prawdopodobnie wiele rzeczy jest zasadniczo nie tak z tym, co powiedziałem i dlatego proszę o pomoc.

* Chyba że uważasz coś (a|b)*b*c->trueza regułę produkcji, w którym to przypadku reguła wymaga automatów skończonych (np. Regex). To nie ma sensu, jak to właśnie powiedzieliśmy

Ktokolwiek powiedział ci, że do analizowania kodu używane są wyrażenia regularne, szerzył dezinformację. Klasycznie (nie wiem, w jakim stopniu jest to prawdą we współczesnych kompilatorach), parsowanie kodu - konwersja kodu z tekstu na drzewo składniowe - składa się z dwóch etapów:

1. Analiza leksykalna: Przetwarza surowy tekst na fragmenty, takie jak słowa kluczowe , stałe liczbowe , ciągi znaków , identyfikatory i tak dalej. Jest to klasycznie realizowane za pomocą pewnego rodzaju maszyny stanów skończonych, podobnej w duchu do deterministycznego automatu skończonego (DFA).

2. Analizator składni: uruchamiany po analizie leksykalnej i konwertuje surowy tekst na adnotowane drzewo składniowe. Gramatyka języków programowania jest (do pierwszego przybliżenia) bezkontekstowa (w rzeczywistości potrzebny jest nawet bardziej rygorystyczny podzbiór), a to pozwala niektórym wydajnym algorytmom na analizowanie zrewidowanego kodu w drzewie składni. Jest to podobne do problemu rozpoznawania, czy dany ciąg należy do jakiejś gramatyki bezkontekstowej, z tą różnicą, że chcemy również dowodu w postaci drzewa składniowego.

Gramatyki dla języków programowania są pisane jako gramatyki bezkontekstowe, a ta reprezentacja jest wykorzystywana przez generatory parserów do konstruowania dla nich szybkich parserów. Prosty przykład miałby jakieś nieterminalne OŚWIADCZENIE, a następnie reguły w formie OŚWIADCZENIE JEŚLI OŚWIADCZENIE, gdzie OŚWIADCZENIE JEŻELI → jeśli WARUNEK to BLOKUJ endif lub podobne (na przykład BLOK → OŚWIADCZENIE | BLOK; OŚWIADCZENIE). Zwykle gramatyki te są określone w formie Backus-Naur (BNF).$\to$$\to$$\to$

Rzeczywiste specyfikacje języków programowania nie są pozbawione kontekstu. Na przykład zmienna nie może się pojawić, jeśli nie została zadeklarowana w wielu językach, a języki o ścisłym typowaniu mogą nie pozwolić na przypisanie liczby całkowitej do zmiennej łańcuchowej. Zadaniem parsera jest jedynie konwersja surowego kodu do postaci, która jest łatwiejsza do przetworzenia.

Powinienem wspomnieć, że istnieją inne podejścia, takie jak parsowanie rekurencyjne, które nie generuje drzewa parsowania, ale przetwarza kod podczas parsowania. Chociaż generowanie drzewa nie przeszkadza, pod wszystkimi innymi względami działa na tym samym poziomie, jak opisano powyżej.

To ciężkie rzeczy do zadania w szkole średniej.

Odpowiedź Yuvala Filmusa jest naprawdę dobra, więc jest to raczej odpowiedź uzupełniająca, aby wyjaśnić niektóre z jego uwag.

Język formalny jest konstrukcją matematyczną. Ich użycie w językach programowania jest tylko jednym z wielu możliwych zastosowań; w rzeczywistości językoznawca Noam Chomsky wniósł znaczący wkład we wczesną teorię języków formalnych. Wynalazł hierarchię Chomsky'ego, który klasyfikuje języki formalne na zwykłe, bezkontekstowe itp. Języki formalne są również stosowane w językoznawstwie do opisywania składni języków naturalnych, takich jak angielski. Pomyśl o tym jak o liczbach rzeczywistych: możemy użyć liczb rzeczywistych do opisania zarówno konkretnych rzeczy, jak odległość od Los Angeles do Nowego Jorku, jak i rzeczy abstrakcyjnych, takich jak stosunek obwodu koła do jego średnicy. Mimo że obie te rzeczy istnieją niezależnie od liczb rzeczywistych, liczby rzeczywiste są pomocnym systemem do ich opisu. Języki formalne są pomocnym systemem do opisu języka angielskiego i języka Python, ponieważ oba mają podobny format strukturalny.

$a + b + c = d$$a + b = d - c$$a$$b$$c$ na przykład kwoty w dolarach, a wtedy równanie ma znaczenie.

Klasycznie język programowania będzie miał dwie gramatyki: gramatykę leksykalną i gramatykę składniową. Gramatyka leksykalna dotyczy znaków, takich jak litery, średniki, nawiasy klamrowe i nawiasy. Zwykle jest to gramatyka regularna, więc można ją wyrazić za pomocą wyrażeń regularnych lub DFA lub NFA. (W formalnej teorii języka istnieją dowody na to, że te trzy są równoważne pod względem mocy - co oznacza, że ​​akceptują ten sam zestaw języków). Faza leksykalna kompilatora lub tłumacza jest rodzajem mini tłumacza dla gramatyki języka regularnego. Odczytuje zasady gramatyki i postępując zgodnie z tymi zasadami, grupuje pojedyncze postacie w tokeny. Na przykład, jeżeli język ma ifkomunikatu, który wygląda mniej więcej tak jak C, The lexer może guzek znaki ii fna pojedynczy znakIF, następnie poszukaj nawiasu otwierającego i wyślij token OPEN_PAREN, a następnie obsłuż wszystko, co znajduje się między nawiasami, a następnie znajdź nawias zamykający i wyślij a CLOSE_PAREN. Kiedy leksyker wykonuje tokeny, przekazuje je parserowi, który określa, czy tokeny faktycznie tworzą prawidłowe instrukcje języka programowania. Więc jeśli piszesz ip a == bw Pythonie, leksykon stara się odgadnąć, jakiego rodzaju ipjest token (prawdopodobnie byłby brany za identyfikator przez większość leksyków) i przekazuje go do parsera, który narzeka, ponieważ nie możesz mieć identyfikator w tej pozycji.

$a \rightarrow b$

Spójrzmy na reguły gramatyczne dla ifwypowiedzi Pythona . To jest zasada:

if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

Ta reguła mówi nam, jak parser się zorientuje, czy ciąg tokenów wysłanych z leksera jest if-statement. Każde słowo w pojedynczym cudzysłowie musi pojawić się, podobnie jak to, w kodzie źródłowym, aby parser wyszukał zwykłe słowo if. Analizator składni spróbuje następnie dopasować niektóre tokeny do reguły dla test:

test: or_test ['if' or_test 'else' test] | lambdef

testjest zdefiniowany w kategoriach innych zasad gramatyki. Zwróć uwagę, jak testobejmuje się także w swojej definicji; to się nazywa definicja rekurencyjna. Jest to ogromna moc języków bezkontekstowych, których nie mają zwykłe języki, i pozwala na zdefiniowanie zagnieżdżonych pętli dla składni języka programowania.

Jeśli parserowi uda się dopasować niektóre tokeny test, spróbuje dopasować dwukropek. Jeśli to się powiedzie, spróbuje dopasować więcej tokenów, używając reguły dla suite. Sekcja ('elif' test ':' suite)*oznacza, że ​​możemy mieć dowolną liczbę powtórzeń dosłownego tekstu elif, po czym następuje dopasowanie test, następnie dwukropek, a po nim coś, co pasuje suite. Możemy również mieć zero powtórzeń; gwiazdka na końcu oznacza „zero lub tyle, ile chcemy”.

Na samym końcu jest ['else' ':' suite]. Ta część jest zamknięta w nawiasy kwadratowe; oznacza to, że możemy mieć zero lub jeden, ale nie więcej. Aby to dopasować, analizator składni musi dopasować dosłowny tekst else, dwukropek, a następnie a suite. Oto zasada dla suite:

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

Zasadniczo jest to blok w językach podobnych do C. Ponieważ Python używa nowej linii i wcięcia oznaczać rzeczy, wyjścia Lexer NEWLINE, INDENToraz DEDENTtokeny powiedzieć parser gdzie nowa linia uruchomiona, gdzie kod zaczął być wcięty, i gdzie został zwrócony do poziomu zewnętrznej wcięcia.

Jeśli którakolwiek z tych prób dopasowania zakończy się niepowodzeniem, analizator składni sygnalizuje błąd i zatrzymuje się. Jeśli parsowanie całego programu powiedzie się, analizator zwykle zbuduje drzewo parsowania, tak jak Yuval ujął w swojej odpowiedzi, i ewentualnie tablicę symboli i inne struktury danych przechowujące informacje semantyczne. Jeśli język zostanie wpisany statycznie, kompilator przejdzie przez drzewo analizy i wyszuka błędy typu. Przechodzi także drzewo analizujące, aby wygenerować kod niskiego poziomu (język asemblera, kod bajtowy Java, .Net Intermediate Language lub coś podobnego), co faktycznie działa.

Jako ćwiczenie polecam gramatykę znanego języka programowania (znowu Python , Java , a tutaj C # , JavaScript , C ) i spróbuję ręcznie przeanalizować coś prostego, na przykład może x = a + b;lub if (True): print("Yay!"). Jeśli szukasz czegoś prostszego, jest też ładna gramatyka dla JSON , która w zasadzie obejmuje tylko składnię literałów obiektowych w Javascript (jak {'a': 1, 'b': 2}). Powodzenia, to jest szalone rzeczy, ale okazuje się być naprawdę interesujące, gdy nie jesteś w jakimś szalonym terminie.

W skrócie

Języki programowania składają się ze składni, która reprezentuje program jako ciągi znaków, oraz semantyki, która jest zamierzonym znaczeniem programu.

Języki formalne są składnią bez znaczenia. Ma to na celu zbadanie struktury zestawów ciągów zdefiniowanych formalnie, zwykle bez przypisywania znaczenia tym ciągom.

Wyrażenia regularne i inne formalizmy (takie jak gramatyka bezkontekstowa) są używane do definiowania języków formalnych, używanych jako składniowy składnik programowania i języków naturalnych, tj. Do reprezentowania zdań w uporządkowany sposób. Inne mechanizmy są używane do powiązania tej struktury z semantyką języków programowania.

Wiele jest tutaj znacznie uproszczonych, szczególnie w odniesieniu do języka naturalnego.

Z wieloma szczegółami

Aby odpowiedzieć na twoje pytanie, powinniśmy zacząć od początku. Język w zwykłym znaczeniu to nieformalnie sposób przekazywania informacji lub pomysłów. W języku zwykle rozróżnia się składnię i semantykę. Semantyka jest tym, o czym chcesz rozmawiać / pisać. informacje, które chcesz przekazać. Składnia to sposób, w jaki ją przekazujesz, tj. Konwencjonalna reprezentacja, którą można wymieniać między ludźmi, a teraz także między ludźmi i urządzeniami lub między urządzeniami (komputerami).

Zazwyczaj używasz tego słowa, dogaby przekazać ideę psa. Słowo dogskłada się z trzech liter lub innego równoważnego dźwięku i ma być reprezentacją jakiegoś zwierzęcia. Kluczową ideą jest to, że komunikacja odbywa się poprzez przedstawienie tego, co ma zostać przekazane. Struktury reprezentacji są zwykle nazywane składnią, a reprezentowana jest semantyką. Dotyczy to mniej więcej języka naturalnego, a także języków programowania.

Słowa to byty syntaktyczne, które reprezentują mniej więcej podstawowe pojęcia semantyczne. Ale te podstawowe pojęcia należy łączyć na różne sposoby, aby nadać bardziej złożone znaczenie. Piszemy, the dogaby przekazać, że mamy na myśli konkretnego psa, i the dog bites the catprzekazać bardziej złożony pomysł. Ale sposób, w jaki słowa są zorganizowane, musi zostać ustalony przez reguły, abyśmy mogli stwierdzić, który z psów i kot rzeczywiście gryzie drugie.

Mamy więc takie zasady, sentence -> subject verb complementktóre powinny pasować do zdań i powiedzieć nam, w jaki sposób wyrażane są pomysły związane z każdą częścią. Reguły te są regułami składniowymi, ponieważ mówią nam, w jaki sposób ma być zorganizowana reprezentacja naszej wiadomości. Sama subjectmoże być zdefiniowana przez regułę subject -> article nouni tak dalej.

$2x+1=23$$x$$1$$23$

equation -> expression "=" expression  
expression -> expression "+" expression 
expression -> number

Struktura języków programowania jest taka sama. Języki programowania są semantycznie wyspecjalizowane w wyrażaniu obliczeń, które należy wykonać, a nie w wyrażaniu problemów do rozwiązania, dowodu twierdzeń lub przyjaznych relacji między zwierzętami. Ale to główna różnica.

Reprezentacje stosowane w składni to zwykle ciągi znaków lub dźwięków w językach mówionych. Semantyka zwykle należy do dziedziny abstrakcyjnej lub ewentualnie do rzeczywistości, ale wciąż jest abstrakcyjna w naszych procesach myślowych lub do dziedziny behawioralnej urządzeń. Komunikacja wymaga zakodowania informacji / idei w składni, która jest przesyłana i dekodowana przez odbiornik. Wynik jest następnie interpretowany w jakikolwiek sposób przez odbiorcę.

Widzimy więc głównie składnię i jej strukturę. Powyższy przykład jest tylko jednym z najczęstszych sposobów definiowania łańcuchów składniowych i ich organizacji strukturalnej. Są inni. Dla danego języka niektórym ciągom można przypisać strukturę, o których mówi się, że należą do języka, podczas gdy inne nie.

To samo dotyczy słów. Niektóre sekwencje liter (lub dźwięków) są prawidłowymi słowami, a inne nie.

Języki formalne to tylko składnia bez semantyki. Określają za pomocą zestawu reguł, jakie sekwencje można konstruować, używając podstawowych elementów alfabetu. Zasady mogą być bardzo zmienne, czasem złożone. Ale języki formalne są używane do wielu celów matematycznych poza komunikacją językową, zarówno naturalną, jak i do programowania. Zestaw reguł definiujących ciągi w języku nazywa się gramatyką. Ale istnieje wiele innych sposobów definiowania języków.

W praktyce język składa się z dwóch poziomów. Poziom leksykalny definiuje słowa zbudowane z alfabetu znaków. Poziom składniowy definiuje zdania lub programy zbudowane z alfabetu słów (a ściślej z rodzin słów, aby pozostały alfabetem skończonym). Jest to z konieczności nieco uproszczone.

Struktura słów jest dość prosta w większości języków (programistycznych lub naturalnych), dlatego zwykle definiuje się je za pomocą tego, co zwykle uważa się za najprostszy rodzaj języka formalnego: zwykłe języki. Można je zdefiniować za pomocą wyrażeń regularnych (regexp) i dość łatwo można je zidentyfikować za pomocą zaprogramowanych urządzeń zwanych automatami skończonymi. W przypadku języków programowania przykładami słowa są identyfikator, liczba całkowita, ciąg, liczba rzeczywista, słowo zastrzeżone, takie jak if lub repeat, symbol interpunkcyjny lub otwarty nawias. Przykładami rodzin słów są identyfikator, ciąg, liczba całkowita.

Poziom składniowy jest zwykle definiowany przez nieco bardziej złożony typ języka formalnego: języki bezkontekstowe, używając słów jako alfabetu. Reguły, które widzieliśmy powyżej, to bezkontekstowe reguły dla języka naturalnego. W przypadku języków programowania reguły mogą być:

statement -> assignment
statement -> loop
loop ->  "while" expression "do" statement
assignment -> "identifier" "=" expression
expression -> "identifier"
expression -> "integer"
expression -> expression "operator" expression

Dzięki takim regułom możesz pisać:

while aaa /= bbb do aaa = aaa + bbb / 6 który jest stwierdzeniem.

Sposób, w jaki został wytworzony, może być reprezentowany przez strukturę drzewa zwaną drzewem parsowania lub drzewem składni (tutaj niepełne):

                          statement
                              |
            _______________  loop _______________
           /      /                 \            \
      "while" expression           "do"       statement
       __________|_________                       |
      /          |         \                  assignment
 expression "operator" expression          _______|_______
     |           |          |             /       |       \
"identifier"   "/="   "identifier" "identifier"  "="   expression
     |                      |            |                 |
    aaa                    bbb          aaa             ... ...

Nazwy pojawiające się po lewej stronie reguły są nazywane nieterminalami, podczas gdy słowa te nazywane są także terminali, ponieważ znajdują się w alfabecie dla języka (powyżej poziomu leksykalnego). Nieterminalne reprezentują różne struktury składniowe, których można użyć do skomponowania programu.

Takie reguły nazywane są bezkontekstowe, ponieważ terminale nieterminalne można dowolnie zastąpić dowolnymi odpowiadającymi im regułami, niezależnie od kontekstu, w którym się pojawiają. Zestaw reguł definiujących język nazywa się gramatyką bezkontekstową.

W rzeczywistości istnieją ograniczenia dotyczące tego, kiedy identyfikatory muszą być najpierw zadeklarowane, lub gdy wyrażenie musi spełniać ograniczenia typu. Ale takie ograniczenie można uznać za semantyczne, a nie składniowe. W rzeczywistości niektórzy specjaliści umieszczają je w tak zwanej semantyce statycznej .

Przy danym zdaniu, dowolnym programie znaczenie tego zdania wyodrębnia się, analizując strukturę podaną przez drzewo analizy dla tego zdania. Dlatego bardzo ważne jest opracowanie algorytmów, zwanych parserami, które mogą odzyskać strukturę drzewa odpowiadającą programowi, jeśli zostanie mu dany program.

Parser poprzedza analizator leksykalny, który rozpoznaje słowa i określa rodzinę, do której należą. Następnie sekwencja słów lub elementów leksykalnych jest przekazywana do analizatora składni, który pobiera strukturę drzewa. Na podstawie tej struktury kompilator może następnie określić, w jaki sposób wygenerować kod, który jest jego semantyczną częścią przetwarzania programu po stronie kompilatora.

Analizator składni kompilatora może faktycznie zbudować strukturę danych odpowiadającą parsowaniu i przekazać go do późniejszych etapów procesu kompilacji, ale nie musi tego robić. Uruchomienie algorytmu analizującego sprowadza się do opracowania strategii obliczeniowej do eksploracji drzewa składni, które jest niejawne w tekście programu. To drzewo składni / parsowania może, ale nie musi być wyjaśnione w tym procesie, w zależności od strategii kompilacji (liczba etapów). Konieczne jest jednak to, że ostatecznie istnieje co najmniej jedno oddolne badanie drzewa parsowania, bez względu na to, czy zostało to wyjaśnione, czy pozostawione jako ukryte w strukturze obliczeniowej.

Powodem tego jest intuicyjnie to, że standardowym formalnym sposobem definiowania semantyki związanej ze strukturą drzewa składniowego jest tak zwany homomorfizm. Nie bój się wielkiego słowa. Chodzi o to, aby wziąć pod uwagę znaczenie całości zbudowane na podstawie znaczenia części, na podstawie operatora, który je łączy

Na przykład zdanie the dog bites the catmożna analizować za pomocą reguły sentence -> subject verb complement. Znając rozumieniu 3 poddrzew subject, verbi complement, zasadę, że komponuje im mówi, że przedmiotem robi akcję, a kot jest tym, który zostaje ugryziony.

To jest tylko intuicyjne wyjaśnienie, ale można je sformalizować. Semantyka jest konstruowana w górę od składników. Ale to kryje wiele komplikacji.

Wewnętrzne działanie kompilatora można rozłożyć na kilka etapów. Rzeczywisty kompilator może działać etapy, wykorzystując reprezentacje pośrednie. Może także łączyć niektóre etapy. Zależy to od zastosowanej technologii i złożoności kompilacji danego języka.

Istnieją znaczne różnice. Powiedziałbym, że najważniejsze jest to, że podczas analizowania prawdziwych języków programowania chodzi o obsługę błędów składniowych. W języku formalnym powiedziałbyś po prostu „no cóż, nie jest w tym języku”, ale kompilator, który mówi, że to nie jest bardzo przydatne - powinien powiedzieć ci, co jest nie tak, a jeśli był to mały błąd, najlepiej parsuj, aby mógł zgłoś więcej błędów. Wiele badań (i wysiłków wdrożeniowych) wymaga tego. Więc tak naprawdę nie przejmujesz się tak naprawdę wynikiem prawda / fałsz, po prostu chcesz przeanalizować strukturę danych wejściowych. Języki formalne są tam używane jako narzędzie i nakładają się na siebie, ale naprawdę rozwiązujesz inny problem.

Ponadto w większości języków wybrano niewymuszanie pewnych elementów gramatyki , na przykład w wspomnianym przykładzie „zmienna nie może się pojawić, jeśli nie została zadeklarowana”. Zwykle jest to rzecz, która zostałaby całkowicie zignorowana przez analizator składni, a następnie ujęta w osobnej analizie (analizie semantycznej), która analizuje tego rodzaju rzeczy i nie ma na nią wpływu takie względy, jak brak kontekstu. Ale nie zawsze - na przykład do parsowania C, często używany jest hak leksykalny , a C ++ jest znanym przykładem języka, którego nie można przeanalizować bez jednoczesnej poważnej analizy semantycznej (w rzeczywistości analizowanie C ++ jest nierozstrzygalne, ponieważ szablony są Turing zakończone ). W prostszych językach jest jednak podzielony, tak jest łatwiej.

Język formalny to zestaw słów - gdzie słowo jest ciągiem symboli z jakiegoś alfabetu.

Oznacza to, że twoje połączenie reguł produkcji i języka formalnego jest zbyt silne. Niepoprawne jest to, że językiem formalnym są reguły produkcji. Reguły produkcji określają raczej język formalny. Formalnym językiem są słowa, które mogą być tworzone przez regułę produkcji. (Wymaga to, że język formalny jest tego rodzaju, który można zdefiniować za pomocą reguł produkcji, np. Zwykłe języki można zdefiniować za pomocą gramatyki bezkontekstowej)

Tak więc język regularny odpowiadający wyrażeniu (a|b)*c*djest zdefiniowany przez reguły produkcji;

S->ACd
A->
A->aA
A->bA
C->
C->cC

Słowa generowane przez te reguły produkcji z początkowego symbolu S są dokładnie tymi łańcuchami, które akceptuje wyrażenie regularne.

Istnieje inna zależność między wyrażeniami regularnymi a językami programowania, która dotyczy semantyki. Podstawowe konstrukcje kontrolne języka imperatywnego to składanie sekwencyjne (do A, a następnie B), wybór (do A lub B) i powtarzanie (do A w kółko).

Te same trzy sposoby łączenia zachowań znajdują się w wyrażeniach regularnych. Wrzuć wywołania podprogramów i masz analogię do EBNF.

Istnieje więc wiele podobieństw między algebrą wyrażeń regularnych a algebrą poleceń. Zostało to szczegółowo zbadane przez Dijkstrę w „Unifikacji trzech obliczeń”. Jest to również podstawa CCS Milnera, która daje odpowiedź na pytanie: co jeśli dodamy paralelizm?