Asocjacja operatora - Operator associativity

Aby zapoznać się z matematyczną koncepcją asocjacji, zobacz Własność asocjacyjna .

W językach programowania , asocjatywność się z operatorem to właściwość, która określa, jak operatorzy tym samym priorytecie są grupowane w przypadku braku nawiasów . Jeśli operand jest poprzedzony i poprzedzony przez operatory (na przykład ^ 3 ^), a operatory te mają równy priorytet, to operand może być użyty jako dane wejściowe dla dwóch różnych operacji (tj. dwóch operacji wskazanych przez dwa operatory). Wybór, do których operacji zastosować operand, jest określony przez łączność operatorów. Operatory mogą być asocjacyjne (co oznacza, że ​​operacje mogą być grupowane dowolnie), lewostronnie zespolone (co oznacza, że ​​operacje są grupowane od lewej), prawostronnie zespolone (co oznacza, że ​​operacje są grupowane od prawej strony) lub niełączące (co oznacza, że ​​operacje nie mogą być połączone, często dlatego, że typ danych wyjściowych jest niezgodny z typami wejściowymi). Asocjatywność i pierwszeństwo operatora jest częścią definicji języka programowania; różne języki programowania mogą mieć różną asocjatywność i pierwszeństwo dla tego samego typu operatora.

Rozważ wyrażenie a ~ b ~ c. Jeśli operator ~opuścił łączność, to wyrażenie zostanie zinterpretowane jako (a ~ b) ~ c. Jeśli operator ma właściwą asocjatywność, wyrażenie zostanie zinterpretowane jako a ~ (b ~ c). Jeśli operator jest nieskojarzony, wyrażenie może być błędem składni lub może mieć specjalne znaczenie. Niektóre operatory matematyczne mają wrodzoną asocjatywność. Na przykład odejmowanie i dzielenie, używane w konwencjonalnej notacji matematycznej, są z natury lewostronne. W przeciwieństwie do tego, dodawanie i mnożenie są skojarzone zarówno w lewo, jak i w prawo. (np (a * b) * c = a * (b * c). ).

Wiele podręczników języków programowania zawiera tabelę pierwszeństwa i asocjacji operatorów; zobacz na przykład tabelę dla C i C++ .

Opisana tu koncepcja asocjatywności notacyjnej jest powiązana z asocjatywnością matematyczną, ale różni się od niej . Operacja, która jest matematycznie asocjacyjna, z definicji nie wymaga asocjatywności notacyjnej. (Na przykład dodawanie ma własność asocjacyjną, dlatego nie musi być ani lewostronnie, ani prawostronnie zespolone). Jednak operacja, która nie jest matematycznie zespolona, ​​musi być notacyjnie lewostronna, prawostronna lub niełączna. (Na przykład odejmowanie nie ma własności asocjacyjnej, dlatego musi mieć asocjatywność notacyjną).

Przykłady

Asocjatywność jest potrzebna tylko wtedy, gdy operatory w wyrażeniu mają ten sam priorytet. Zwykle +i -mają ten sam priorytet. Rozważ wyrażenie 7 - 4 + 2. Wynikiem może być albo (7 - 4) + 2 = 5lub 7 - (4 + 2) = 1. Pierwszy wynik odpowiada przypadkowi, kiedy +i -są lewostronnie skojarzone, drugi kiedy +i -są prawostronnie skojarzone.

Aby odzwierciedlić normalne użycie, operatory dodawania , odejmowania , mnożenia i dzielenia są zwykle lewostronnie zespolone, podczas gdy w przypadku operatora potęgowania (jeśli jest obecny) i operatorów strzałek w górę Knutha nie ma ogólnej zgodności. Wszystkie operatory przypisania są zazwyczaj prawe skojarzone. Aby zapobiec przypadkom, w których operandy byłyby skojarzone z dwoma operatorami lub w ogóle z żadnym operatorem, operatory o tym samym priorytecie muszą mieć tę samą łączność.

Szczegółowy przykład

Rozważmy wyrażenie 5^4^3^2, w którym ^przyjmuje się, że jest operatorem prawostronnie asocjacyjnym. Parser czytający tokeny od lewej do prawej zastosowałby regułę łączności do gałęzi, ze względu na prawoskojarzenie ^, w następujący sposób:

  1. Termin 5jest odczytany.
  2. Nieterminal ^jest czytany. Węzeł: „ 5^”.
  3. Termin 4jest odczytany. Węzeł: „ 5^4”.
  4. Nieterminal ^jest odczytywany, uruchamiając regułę właściwej asocjacji. Asocjatywność decyduje o węźle: " 5^(4^".
  5. Termin 3jest odczytany. Węzeł: „ 5^(4^3”.
  6. Nieterminal ^jest odczytywany, co powoduje ponowne zastosowanie zasady prawostronnej asocjacji. Węzeł „ 5^(4^(3^”.
  7. Termin 2jest odczytany. Węzeł „ 5^(4^(3^2”.
  8. Brak żetonów do przeczytania. Zastosuj asocjatywność, aby utworzyć drzewo analizy „ 5^(4^(3^2))”.

Można to następnie ocenić w pierwszej kolejności, zaczynając od najwyższego węzła (pierwszego ^):

  1. Oceniający schodzi po drzewie, od pierwszego, przez drugie, do trzeciego ^wyrażenia.
  2. Wynik otrzymuje postać: 3 2 = 9. Wynik zastępuje gałąź wyrażenia jako drugi argument drugiego ^.
  3. Ocena kontynuuje jeden poziom w górę drzewa analizy jako: 4 9 = 262144. Ponownie wynik zastępuje gałąź wyrażenia jako drugi argument pierwszego ^.
  4. Oceniający ponownie przechodzi w górę drzewa do wyrażenia głównego i oblicza jako: 5 262144 ≈ 6.2060699 × 10 183230 . Ostatnia pozostała gałąź załamuje się, a wynik staje się wynikiem ogólnym, kończąc w ten sposób ocenę ogólną.

Ewaluacja lewostronnie asocjacyjna dałaby drzewo parsowania ((5^4)^3)^2i zupełnie inne wyniki 625, 244140625 i ostatecznie ~5.9604645 × 10 16 .

Prawoskojarzenie operatorów przypisania

W wielu językach programowania nadrzędnych The operator przypisania określa się prawym asocjacyjne i przyporządkowanie określa się wyrażenie (która wyznaczona wartość), a nie tylko oświadczenie. Umożliwia to przypisanie łańcuchowe przy użyciu wartości jednego wyrażenia przypisania jako prawego operandu następnego wyrażenia przypisania.

W C , przypisanie a = bto wyrażenie, które ocenia się na tę samą wartość co ekspresji bprzekształcono w rodzaju a, przy czym efekt uboczny w przechowywaniu wartość R się bdo L wartości z a. Dlatego wyrażenie a = (b = c)można interpretować jako b = c; a = c;. Wyrażenie alternatywne (a = b) = cpowoduje błąd, ponieważ a = bnie jest wyrażeniem wartości L, tj. ma wartość R, ale nie ma wartości L, w której ma być przechowywana wartość R c. Prawoskojarzenie =operatora pozwala a = b = cna interpretację wyrażeń, takich jak a = (b = c).

W C++ przypisanie a = bjest wyrażeniem, którego wynikiem jest ta sama wartość co wyrażenie a, z efektem ubocznym przechowywania wartości R w wartości bL a. Dlatego wyrażenie a = (b = c)można nadal interpretować jako b = c; a = c;. A wyrażenie alternatywne (a = b) = cmożna interpretować jako a = b; a = c;zamiast zgłaszania błędu. Prawoskojarzenie =operatora pozwala a = b = cna interpretację wyrażeń, takich jak a = (b = c).

Operatory nieskojarzone

Operatory nieskojarzone to operatory, które nie mają zdefiniowanego zachowania, gdy są używane w sekwencji w wyrażeniu. W Prologu operator infiks :-jest nie-asocjatywnym ponieważ konstrukcje takie jak „ a :- b :- c” stanowią nie zawiera błędów.

Inną możliwością jest to, że sekwencje pewnych operatorów są interpretowane w inny sposób, którego nie można wyrazić jako asocjatywność. Ogólnie oznacza to, że syntaktycznie istnieje specjalna reguła dla sekwencji tych operacji, a semantycznie zachowanie jest inne. Dobrym przykładem jest Python , który ma kilka takich konstrukcji. Ponieważ przypisania są instrukcjami, a nie operacjami, operator przypisania nie ma wartości i nie jest asocjacyjny. Przypisanie łańcuchowe jest zamiast tego implementowane przez regułę gramatyczną dla sekwencji przypisań a = b = c, które są następnie przypisywane od lewej do prawej. Ponadto, kombinacje przyporządkowania i rozszerzonej zadania, jak a = b += cnie są legalne w Pythonie, choć są one legalne C. Innym przykładem są operatory porównania, takie jak >, ==i <=. Porównanie łańcuchowe, takie jak, a < b < cjest interpretowane jako (a < b) and (b < c), a nie jako równoważne z (a < b) < club a < (b < c).

Zobacz też

Uwagi

Bibliografia