Tekst źródłowy strony Przyrostowa sieć przejść

'''Przyrostowa sieć przejść''' ([[język angielski|ang.]] '''''Augmented Transition Network''''', '''ATN''') zwana czasem uogólnioną siecią przejść stanowi rozszerzenie [[Rekurencyjna sieć przejść|RTN]].

Sieci te używane są najczęściej w analizie języków naturalnych. Również w algorytmie [[Parser LL(*)|parsera LL(*)]]. Jest postaci grupy grafów, gdzie przechodzimy z jednego stanu sieci do następnego przez etykietowaną krawędź. Oprócz etykiet występujących w RTN, z których najważniejsze to PUSH i POP, krawędź ma przypisany warunek, który musi być spełniony, aby móc tą krawędzią przejść oraz akcje do wykonania. Sieć poza tym wyposażona jest w rejestry, gdzie trzymane są wartości, które potem mogą być poddawane badaniu przez procedury testujące oraz ustawiane przez akcje.

Dzięki temu może równoważna jest mocą [[Maszyna Turinga|maszynie Turinga]].

Jak podaje Bates<ref>(Bates, M. [1978] "The Theory and Practice of Augmented Transition Network Grammars", Lecture Notes in Computer Science, Vol. 63, Bole, L.(Ed.) "Natural Language Communication with Computers", Springer Verlag Berlin, Heidelberg, New York https://courses.cit.cornell.edu/ling7710/readings/bates.pdf)</ref> łuki mogą być typów:
:(CAT <category> <test> <action>*(TO <next state>))
:(WRD <word> <test> <action>*(TO <next state>))
:(MEM <list> <test> <action>*(TO <next state>))
:(PUSH <state> <test> <pre-action>*<action>*(TO <next state>))
:(VIR <constit-type> <test> <action>*(TO <next state>))
:(JUMP <next state> <test> <action>*
:(POP <form> <test>)

część typów jest znana z RTN:
:CAT – kategoria np. rzeczownik, przymiotnik
:WRD – symbol terminalny
:PUSH – zapamiętanie stanu przed przejściem do początku innego diagramu <state>
:POP – odtworzenie pozycji ze stosu
:JUMP – przejścia bez żadnego symbolu terminalnego

Dodatkowo:
:MEM – tak jak WRD z wyjątkiem tego, ze symbol musi należeć do listy <list>
:VIR sprawdza, czy jakaś akcja przy wcześniejszej krawędzi nie umieściła nic na globalnej liście HOLD, jeśli tak – element jest usuwany z listy i wykonywane jest przejście.

Akcje:
:(SETR <reg> <form>) powoduje że rejestr <reg> przyjmuje wartość wyliczoną z <form>
:(SETRQ <reg> <value>) bezpośrednio podstawia <value> to <reg>
:(ADDL <reg> <form>) zamiast zastąpić wartość w rejestrze, wyliczona wartość <form> dodawana jest do lewej strony listy
:(ADDR <reg> <form>) podobnie do ADDL tylko do prawej strony listy
:(SENDR <reg> <form>) wstępna akcja używana tylko dla krawędzi PUSH; ustawia rejestr <reg> na wartość <form> na niższym poziomie [[Rekurencja|rekurencji]]; efektem jest, że sieć niższego poziomu jest wołana niczym proceura z parametrem przesyłanym przeze SENDR
:(SENDRQ <reg> <value>) - tak się ma SENDR jak SETRQ do SETR
:(LIFTR <reg> <form>) różni się od SENDR w tym, że ustawia rejestr na wartość <form> poziomu powyżej bieżącego
:(HOLD <constit-type> <form>) wkłada wskazane <form> na listę HOLD jako element <constit-type>. Lista HOLD jest globalna, widzialna przez wszystkie poziomy, ta akcja działa razem z VIR
:(VERIFY <form>) drugi test dla <form>

gramatyka dla <math>a^nb^nc^n</math> :

  (defatn anbncn
        (abc (wrd a t (hold 'a 'a) (to abc/a)))
        (abc/a (wrd b t (to abc/b))
                (push abc t (to abc/ab)))
        (abc/ab (wrd c t (to abc/abc)))
        (abc/abc (pop t))
        (abc/b (vir a t (to abc/ba)))
        (abc/ba (wrd c t (to abc/abc))
                (wrd b t (to abc/b))))

Składnia opisu przypomina [[Lisp]] czy [[Clojure]].

== Przypisy ==
{{Przypisy}}

[[Kategoria:Teoria automatów]]