Jak Mogę włączyć operatory trójdzielne do algorytmu wspinaczki?
Zastosowałem się do wyjaśnienia podanego w sekcji "prefiks Climbing" na tej stronie, aby zaimplementować ewaluator arytmetyczny przy użyciu algorytmu prefiksu climbing z różnymi uniarnymi prefiksami i binarnymi operatorami infiksu. Chciałbym również włączyć operatorów trójkowych (mianowicie trójkowy operator warunkowy ?:).
Algorytm podany na stronie wykorzystuje następującą gramatykę:
E --> Exp(0)
Exp(p) --> P {B Exp(q)}
P --> U Exp(q) | "(" E ")" | v
B --> "+" | "-" | "*" |"/" | "^" | "||" | "&&" | "="
U --> "-"
Jak mogę włączyć operatory trójdzielne do tej gramatyki?
3 answers
Aby być konkretnym, użyję C/C++ / Java ?: jako przykład.
Wydaje się, że w tych językach operator ?: zezwala na dowolne poprawne wyrażenie pomiędzy ? a :, w tym wyrażenia utworzone za pomocą samego ?: oraz wyrażenia utworzone za pomocą operatorów, których pierwszeństwo jest mniejsze niż pierwszeństwo ?:, np. = i , (przykłady: a ? b = c : d, a ? b , c : d, a ? b ? c : d : e).
Sugeruje to, że należy traktować ? i : W dokładnie taki sam sposób jak ( i ) podczas gdy parsowanie wyrażeń. Po przetworzeniu ? expr :, jako całość jest operatorem binarnym. Tak więc, analizujesz ( expr ) i ? expr : w ten sam sposób, ale pierwszy jest wyrażeniem, podczas gdy drugi jest operatorem binarnym (z wyrażeniem w nim osadzonym).
Teraz, gdy ? expr : jest operatorem binarnym (a ?-expr-: b nie różni się od a * b pod względem "binarności"), powinieneś być w stanie go obsługiwać tak jak każdy inny operator binarny, który już obsługujesz.
Osobiście nie Postaraj się podzielić ?: na osobne operatory binarne. W końcu jest operatorem trójdzielnym i musi być połączony z 3 operandami i rozpatrywany jako całość podczas oceny wyrażenia. Jeśli stosujesz podejście opisane w artykule i tworzysz AST, to ?: ma lewy węzeł potomny, prawy węzeł potomny (jak każdy inny operator binarny) i dodatkowo środkowy węzeł potomny.
Pierwszeństwo ?-expr-: jako całość powinna być niska. W C / C++ (a w Javie?) nie jest jednak najniższy. To do ciebie należy decyzja, co chcesz, aby to było.
Do tej pory nie omówiliśmy asocjacji ?:. W C/C++ i Javie, ?-expr-: jest prawostronnie asocjacyjny, podobnie jak operator przypisania =. Ponownie, to do ciebie, aby to lewo-asocjacyjny Lub zachować go prawo-asocjacyjny.
I to:
E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"
Powinno być coś takiego:
E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^" | "?" E ":"
U --> "-"
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-09-21 03:12:48
Natknąłem się na to pytanie szukając informacji na temat przekształcania operatorów trójkowych w odwrotne notacje Polskie (RPN), więc chociaż nie mam solidnej implementacji do implementacji ?: operatora z pierwszeństwem wspinania się, myślę, że mogę być w stanie dać jakąś wskazówkę do przekształcenia ?: operatora do RPN za pomocą dwóch stosów ... co jest podobne do algorytmu manewrowego na podanej stronie internetowej.
[Edytuj] muszę zaznaczyć, że to, co tu robię, nie jest bardzo wydajny (obie gałęzie operatora trójdzielnego muszą być ocenione), ale aby zademonstrować jak łatwo jest Włączyć Nowy operator (?:) w istniejącym frameworku (kod transformacji RPN) (deklarując ? i : z dwoma najniższymi poziomami pierwszeństwa).
Chcę zacząć od kilku przykładów jak wyrażenia z ?: są przekształcane do RPN na podstawie mojego parsera...
Dodaję dwa operatory zamiast tylko jednego, ? i :, ale nie sądzę, aby robi dużą różnicę, ponieważ : i ? będą zawsze połączone razem (jest po prostu wygodniejsze, że RPN i oryginalne wyrażenie mają taką samą liczbę tokenów). W przykładach można zobaczyć, jak to działa.
Przykład 1: 1 + ((0+1) ? 2 : 3 + 8) + 4
RPN: 1 0 1 + 2 3 8 + : ? + 4 +
Teraz Oceń RPN.
1-wpychanie pierwszych elementów do stosu i natkniemy się na pierwszy binarny operator:
1 0 1 i operatorem +, dodajemy 2 górne elementy, zamieniając stos na 1 1
2 - następnie wciśnięcie trzech kolejnych elementów i natkniemy się na drugi operator binarny:
1 1 2 3 8 + ------> 1 1 2 11
3 - Teraz mamy : i ?. To faktycznie mówi nam, aby wybrać albo następczą gałąź (2nd najwyższy element na szczycie stosu, 2) lub alternatywna gałąź (najwyższy element na stosie, 11), oparta na predykacie (trzeci najwyższy element na stosie, 1). Ponieważ predykatem jest 1 (prawda), wybieramy 2 i odrzucamy 11. Parser wyskakuje z 3 elementów (predykat / konsekwencja / alternatywa) i odchyla wybrany (w tym przypadku następująca gałąź), więc stos staje się
1 2
4 - zużywają pozostałe elementy:
1 2 + ------> 3
3 4 + ------> 7
Przykład 2: 1 + ((0+0+0?0:0) ? 2 : (3 + 8)) + 4
RPN: 1 0 0 + 0 + 0 0 : ? 2 3 8 + : ? + 4 +
Ocena:
Początek:
1 0 0 + 0 + 0 0 : ? 2 3 8 + : ? + 4 +
Po dodaniu 0 do 0:
1 0 0 + 0 0 : ? 2 3 8 + : ? + 4 +
Po dodaniu 0 do 0:
1 0 0 0 : ? 2 3 8 + : ? + 4 +
Po pierwszym :? wybiera 0:
1 0 2 3 8 + : ? + 4 +
Po dodaniu 3 i 8:
1 0 2 11 : ? + 4 +
Po ?: wybiera 11:
1 11 + 4 +
Po dodaniu 1 i 11:
12 4 +
Wreszcie:
16
Może to sugerować, że możliwe jest przekształcenie wyrażenia z ?: w odwrotną notację polską. Jak mówi strona RPN i AST są równoważne w tym, że mogą być przekształcane w i od siebie, operator trójdzielny powinien być w podobny sposób zaimplementowany.
Jedną z rzeczy, które należy zrobić, wydaje się być" priorytet " (lub pierwszeństwo) operatora ?:. I rzeczywiście natknąłem się na to podczas próby transformacji RPN. Podałem znaki zapytania i dwukropki najniższy priorytet:
Jak widać z powyższego przykładu, gdy mamy zamiar wykonać ?:, gałąź pierwszeństwa i alternatywna gałąź i predykat powinny być już ocenione, dając w rezultacie pojedynczą liczbę. Jest to gwarantowane przez pierwszeństwo.
Poniżej znajduje się tabela priorytetów (pierwszeństwo).
! ~ > * / % > + - > & > ^ > | > && > || > ? > :
? i : mają najmniejszy priorytet, czyli w wyrażeniach takich jak 1?2+3:4+5, ? and : will never take operandów wokół nich.
? poprzedza :, Aby : pojawiło się przed ? w RPN. W moim rozumieniu jest to tylko wybór projektu, ponieważ : i ? nie muszą nawet dzielić się na dwa operatory w pierwszej kolejności.
Numer referencyjny: http://en.cppreference.com/w/cpp/language/operator_precedence
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-06-05 03:47:18
Zdefiniuj dwukropek, aby miał niższy priorytet niż znak zapytania. Innymi słowy, a ? b: c będzie parsowane jako (a ? B): c. pozwala to parserowi konstruować (if/then/empty-else) węzeł abstrakcyjnej składni, który następnie byłby obsługiwany przez ": operator" w celu dostarczenia żądanego komponentu else.
Relacje pierwszeństwa również zachowują zmienność operatora. Np. a ? b: c ? D: E parses as (a ? b): (c ? d): e, jak można się spodziewać.
Hope this pomaga.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-09-10 08:15:01