Opracowałem parser równań przy użyciu prostego algorytmu stosu, który obsługuje operatory binarne (+, -, |, &, *, / itp.), Operatory jednoargumentowe (!) I nawiasy.
Jednak użycie tej metody pozostawia wszystko, co ma ten sam priorytet - jest oceniany od lewej do prawej, niezależnie od operatora, chociaż pierwszeństwo można wymusić za pomocą nawiasów.
Zatem w tej chwili „1 + 11 * 5” zwraca 60, a nie 56, jak można by się spodziewać.
Chociaż jest to odpowiednie dla bieżącego projektu, chcę mieć procedurę ogólnego przeznaczenia, której mogę używać w późniejszych projektach.
Zredagowano dla przejrzystości:
Jaki jest dobry algorytm do analizowania równań z priorytetem?
Interesuje mnie coś prostego do wdrożenia i rozumiem, że umiem sam kodować, aby uniknąć problemów z licencjonowaniem dostępnego kodu.
Gramatyka:
Nie rozumiem pytania gramatycznego - napisałem to odręcznie. To na tyle proste, że nie widzę potrzeby YACC ani Bison. Wystarczy obliczyć ciągi za pomocą równań, takich jak „2 + 3 * (42/13)”.
Język:
Robię to w C, ale interesuje mnie algorytm, a nie rozwiązanie specyficzne dla języka. C jest na tyle niski, że w razie potrzeby łatwo będzie go przekonwertować na inny język.
Przykład kodu
Opublikowałem kod testowy dla prostego parsera wyrażeń , o którym mówiłem powyżej. Wymagania projektu uległy zmianie, więc nigdy nie musiałem optymalizować kodu pod kątem wydajności lub przestrzeni, ponieważ nie został on uwzględniony w projekcie. Jest w oryginalnej, pełnej treści i powinien być łatwo zrozumiały. Jeśli zrobię z nim coś więcej w zakresie pierwszeństwa operatorów, prawdopodobnie wybiorę hackowanie makra, ponieważ pasuje do reszty programu w prostocie. Jeśli jednak kiedykolwiek użyję tego w prawdziwym projekcie, wybiorę bardziej kompaktowy / szybki parser.
Powiązane pytanie
-Adam
Odpowiedzi:
Trudna droga
Chcesz rekurencyjnego parsera zstępującego .
Aby uzyskać pierwszeństwo, musisz myśleć rekurencyjnie, na przykład używając przykładowego ciągu,
aby zrobić to ręcznie, musiałbyś przeczytać
1
, a następnie zobaczyć plus i rozpocząć zupełnie nową rekurencyjną "sesję" parsowania zaczynając od11
... i upewnić się, że przeanalizowałeś11 * 5
swój własny czynnik, uzyskując drzewo parsowania z1 + (11 * 5)
.To wszystko wydaje się tak bolesne, że nawet próba wyjaśnienia, szczególnie z dodatkową bezsilnością C. Widzisz, po przeanalizowaniu 11, gdyby * było faktycznie + zamiast tego, musiałbyś porzucić próbę stworzenia terminu i zamiast tego przeanalizować
11
jako czynnik. Moja głowa już eksploduje. Jest to możliwe dzięki rekurencyjnej przyzwoitej strategii, ale jest lepszy sposób ...Prosty (właściwy) sposób
Jeśli używasz narzędzia GPL, takiego jak Bison, prawdopodobnie nie musisz się martwić problemami licencyjnymi, ponieważ kod C wygenerowany przez bison nie jest objęty GPL (IANAL, ale jestem prawie pewien, że narzędzia GPL nie wymuszają GPL wygenerowany kod / pliki binarne; na przykład Apple kompiluje kod, na przykład Aperture z GCC i sprzedaje go bez konieczności GPL wspomnianego kodu).
Pobierz Bison (lub coś równoważnego, ANTLR itp.).
Zwykle istnieje przykładowy kod, na którym można po prostu uruchomić bison i uzyskać żądany kod C, który demonstruje ten czterofunkcyjny kalkulator:
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
Spójrz na wygenerowany kod i przekonaj się, że nie jest to takie proste, jak się wydaje. Ponadto korzyści wynikające z używania narzędzia takiego jak Bison to: 1) nauczysz się czegoś (zwłaszcza jeśli czytasz książkę o smokach i uczysz się o gramatyce), 2) unikasz próby odkrycia koła przez NIH . Dzięki prawdziwemu narzędziu do generowania parserów masz nadzieję na późniejsze skalowanie, pokazując innym osobom, które znasz, że parsery są domeną narzędzi parsujących.
Aktualizacja:
Ludzie tutaj udzielili wielu rozsądnych rad. Moim jedynym ostrzeżeniem przed pomijaniem narzędzi parsujących lub po prostu korzystaniem z algorytmu Shunting Yard lub ręcznie obracanego rekurencyjnego, przyzwoitego parsera jest to, że małe języki zabawkowe 1 mogą kiedyś przekształcić się w duże, rzeczywiste języki z funkcjami (sin, cos, log) i zmiennymi, warunkami i pętle.
Flex / Bison może być przesadą dla małego, prostego tłumacza, ale jednorazowy parser + ewaluator może powodować problemy, gdy trzeba wprowadzić zmiany lub dodać funkcje. Twoja sytuacja będzie się różnić i będziesz musiał kierować się własnym osądem; po prostu nie karz innych ludzi za swoje grzechy [2] i buduj mniej niż odpowiednie narzędzie.
Moje ulubione narzędzie do parsowania
Najlepszym narzędziem na świecie do tego zadania jest biblioteka Parsec (dla rekurencyjnych porządnych parserów), która jest dostarczana z językiem programowania Haskell. Wygląda bardzo podobnie do BNF lub jakiegoś wyspecjalizowanego narzędzia lub języka specyficznego dla domeny do analizowania (przykładowy kod [3]), ale w rzeczywistości jest to zwykła biblioteka w Haskell, co oznacza, że kompiluje się w tym samym kroku co reszta Twojego kodu Haskell i możesz napisać dowolny kod Haskell i wywołać go w swoim parserze, a także możesz mieszać i dopasowywać inne biblioteki w tym samym kodzie . (Nawiasem mówiąc, osadzenie takiego języka parsującego w języku innym niż Haskell skutkuje mnóstwem syntaktycznego cruft. Zrobiłem to w C # i działa całkiem dobrze, ale nie jest tak ładne i zwięzłe.)
Uwagi:
1 Richard Stallman mówi, w Dlaczego nie powinieneś używać Tcl
[2] Tak, jestem na zawsze przerażony używaniem tego „języka”.
Należy również pamiętać, że kiedy złożyłam tego wpisu, podgląd było poprawne, ale tak to mniej niż odpowiednie parser zjadł moją bliską znacznik zakotwiczenia w akapicie pierwszym , udowadniając, że parser nie są czymś, co należy lekceważyć, ponieważ jeśli używasz regexes i jednorazowe hacki ty prawdopodobnie dostanie coś subtelnego i małego nie tak .
[3] Fragment parsera Haskella używającego Parseka: czterofunkcyjny kalkulator rozszerzony o wykładniki, nawiasy, białe znaki do mnożenia i stałe (jak pi i e).
źródło
Algorytm manewrowy stoczni jest odpowiednim narzędziem do tego. Wikipedia jest naprawdę zagmatwana, ale zasadniczo algorytm działa w ten sposób:
Powiedzmy, że chcesz ocenić 1 + 2 * 3 + 4. Intuicyjnie „wiesz”, że musisz najpierw wykonać 2 * 3, ale jak uzyskać ten wynik? Kluczem jest uświadomienie sobie, że kiedy skanujesz ciąg od lewej do prawej, oszacujesz operator, gdy operator następujący po nim ma niższy (lub równy) priorytet. W kontekście przykładu, oto co chcesz zrobić:
Jak to realizujesz?
Chcesz mieć dwa stosy, jeden dla liczb, a drugi dla operatorów. Cały czas wciskasz liczby na stos. Porównujesz każdy nowy operator z tym na szczycie stosu, jeśli ten na szczycie stosu ma wyższy priorytet, zdejmujesz go ze stosu operatorów, zdejmujesz operandy ze stosu liczb, stosujesz operator i odkładasz wynik na stos liczb. Teraz powtórz porównanie z operatorem wierzchołka stosu.
Wracając do przykładu, działa to tak:
N = [] Ops = []
*
. N = [1 2], Ops = [+ *]*
3, a następnie wypchnij wynik na numer N. N = [1 6], Ops = [+]+
jest lewostronny, więc chcesz zdjąć 1, 6 również i wykonać +. N = [7], Ops = [].To nie jest takie trudne, prawda? I nie wywołuje żadnych gramatyk ani generatorów parserów.
źródło
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Bardzo dobre wyjaśnienie różnych podejść:
Napisany prostym językiem i pseudokodem.
Podoba mi się „wspinaczka na pierwszeństwo”.
źródło
Jest ładny artykuł tutaj o łączenie prosty rekurencyjny-zejście z parsera operatora pierwszeństwa parsowania. Jeśli ostatnio pisałeś parsery, przeczytanie powinno być bardzo interesujące i pouczające.
źródło
Dawno temu stworzyłem własny algorytm parsowania, którego nie mogłem znaleźć w żadnej książce o parsowaniu (jak Dragon Book). Patrząc na wskaźniki do algorytmu manewrowania, widzę podobieństwo.
Około 2 lata temu napisałem o tym post, wraz z kodem źródłowym Perla, na http://www.perlmonks.org/?node_id=554516 . Łatwo jest przenieść na inne języki: pierwsza implementacja, którą zrobiłem, była w asemblerze Z80.
Jest to idealne rozwiązanie do bezpośrednich obliczeń na liczbach, ale możesz go użyć do utworzenia drzewa parsowania, jeśli musisz.
Aktualizacja Ponieważ więcej osób może czytać (lub uruchamiać) JavaScript, po reorganizacji kodu ponownie zaimplementowałem mój parser w Javascript. Cały parser zajmuje około 5k kodu JavaScript (około 100 wierszy dla parsera, 15 wierszy dla funkcji opakowującej), w tym raportowania błędów i komentarzy.
Demo na żywo można znaleźć pod adresem http://users.telenet.be/bartl/expressionParser/expressionParser.html .
źródło
Byłoby pomocne, gdybyś mógł opisać gramatykę, której obecnie używasz do analizowania. Wygląda na to, że problem może tam leżeć!
Edytować:
Fakt, że nie rozumiesz pytania gramatycznego i że „napisałeś to ręcznie” bardzo prawdopodobnie wyjaśnia, dlaczego masz problemy z wyrażeniami w postaci „1 + 11 * 5” (tj. Z pierwszeństwem operatorów) . Na przykład wyszukanie w Google hasła „gramatyka dla wyrażeń arytmetycznych” powinno przynieść dobre wskazówki. Taka gramatyka nie musi być skomplikowana:
załatwi sprawę na przykład i może być trywialnie rozszerzony, aby zająć się bardziej skomplikowanymi wyrażeniami (w tym na przykład funkcjami lub potęgami ...).
Proponuję spojrzeć na tym wątku, na przykład.
Prawie wszystkie wprowadzenia do gramatyki / analizy składniowej traktują wyrażenia arytmetyczne jako przykład.
Zwróć uwagę, że użycie gramatyki wcale nie oznacza użycia określonego narzędzia ( a la Yacc, Bison, ...). Rzeczywiście, z całą pewnością używasz już następującej gramatyki:
(lub coś w tym rodzaju), nie wiedząc o tym!
źródło
Czy myślałeś o użyciu Boost Spirit ? Pozwala na pisanie gramatyki podobnej do EBNF w C ++ w następujący sposób:
źródło
Kiedy zadajesz swoje pytanie, rekurencja w ogóle nie jest potrzebna. Odpowiedź brzmi: trzy rzeczy: notacja Postfix plus algorytm Shunting Yard plus ocena wyrażenia Postfix:
1). Notacja postfiksowa = wymyślona, aby wyeliminować potrzebę jawnej specyfikacji pierwszeństwa. Przeczytaj więcej w sieci, ale oto sedno tego: wyrażenie wrostkowe (1 + 2) * 3, chociaż łatwe do odczytania i przetwarzania przez ludzi, niezbyt wydajne w obliczeniach za pośrednictwem komputera. Co jest? Prosta reguła, która mówi „przepisz wyrażenie, zapisując je w pamięci podręcznej w pierwszeństwie, a następnie zawsze przetwarzaj je od lewej do prawej”. Zatem wrostek (1 + 2) * 3 staje się postfiksem 12 + 3 *. POST, ponieważ operator jest umieszczany zawsze ZA operandami.
2). Obliczanie wyrażenia postfiksowego. Łatwo. Odczytaj liczby z ciągu postfiksowego. Wepchnij je na stos, aż zobaczysz operatora. Sprawdź typ operatora - jednoargumentowy? dwójkowy? trzeciorzędowy? Zdejmij tyle operandów ze stosu, ile potrzeba, aby ocenić ten operator. Oceniać. Wepchnij wynik z powrotem na stos! Jesteś prawie gotowy. Rób to tak długo, aż stos będzie zawierał tylko jeden wpis = wartość, której szukasz.
Zróbmy (1 + 2) * 3, co w postfiksie to „12 + 3 *”. Przeczytaj pierwszą liczbę = 1. Umieść ją na stosie. Czytaj dalej. Liczba = 2. Umieść ją na stosie. Czytaj dalej. Operator. Który? +. Jaki rodzaj? Binarny = potrzebuje dwóch operandów. Pop stos dwukrotnie = argright to 2, a argleft to 1. 1 + 2 to 3. Odepchnij 3 z powrotem na stos. Czytaj dalej z ciągu postfix. To liczba. 3. Wciśnij. Czytaj dalej. Operator. Który? *. Jaki rodzaj? Binarny = potrzebuje dwóch liczb -> dwukrotnie wyskakuj stos. Najpierw wejdź w argright, drugi raz w argleft. Oceń operację - 3 razy 3 to 9.Wepchnij 9 na stos. Przeczytaj następny postfix char. To jest zerowe. Koniec wprowadzania. Pop stack onec = to twoja odpowiedź.
3). Shunting Yard służy do przekształcenia ludzkiego (łatwo) czytelnego wyrażenia wrostek w wyrażenie postfiksowe (również ludzkie łatwe do odczytania po pewnym czasie). Łatwe do ręcznego kodowania. Zobacz komentarze powyżej i netto.
źródło
Czy jest jakiś język, którego chcesz używać? ANTLR pozwoli ci to zrobić z perspektywy Java. Adrian Kuhn ma świetny opis, jak napisać wykonywalną gramatykę w Rubim; w rzeczywistości jego przykład jest prawie dokładnie twoim przykładem wyrażenia arytmetycznego.
źródło
Zależy to od tego, jak „ogólne” ma być.
Jeśli chcesz, aby był naprawdę bardzo ogólny, na przykład mógł analizować funkcje matematyczne, a także sin (4 + 5) * cos (7 ^ 3), prawdopodobnie będziesz potrzebować drzewa parsowania.
W którym nie sądzę, aby wklejać tutaj pełną implementację. Proponuję zapoznać się z jedną z niesławnych „ Książek o smokach ”.
Ale jeśli chcesz tylko obsługi pierwszeństwa , możesz to zrobić, najpierw konwertując wyrażenie do postaci postfiksowej, w której algorytm, który możesz kopiować i wklejać, powinien być dostępny w google lub myślę, że możesz go samodzielnie zakodować za pomocą pliku binarnego drzewo.
Kiedy masz go w postaci postfixa, od tego momentu jest to bułka z masłem, ponieważ już wiesz, jak pomaga stos.
źródło
Sugerowałbym oszukiwanie i skorzystanie z Algorytmu na placu manewrowym . Jest to łatwy sposób na napisanie prostego parsera typu kalkulatora i bierze pod uwagę pierwszeństwo.
Jeśli chcesz poprawnie tokenizować rzeczy i mieć zaangażowane zmienne itp., Napiszę rekurencyjny parser zejścia, zgodnie z sugestiami innych tutaj, jednak jeśli potrzebujesz po prostu parsera w stylu kalkulatora, ten algorytm powinien wystarczyć :-)
źródło
Znalazłem to na liście PIC o algorytmie manewrowania :
-Adam
źródło
Innym zasobem do analizowania pierwszeństwa jest wpis parsera pierwszeństwa operatora w Wikipedii. Obejmuje algorytm stacji manewrowej Dijkstry i alternatywny algorytm drzewa, ale przede wszystkim obejmuje naprawdę prosty algorytm zastępowania makr, który można w trywialny sposób zaimplementować przed dowolnym ignorującym parser o pierwszeństwie:
Wywołaj to jako:
Co jest niesamowite w swojej prostocie i bardzo zrozumiałe.
źródło
Opublikowałem źródło ultra kompaktowego (1 klasa, <10 KiB) Java Math EvaluatorNa mojej stronie internetowej . Jest to rekurencyjny parser zejścia typu, który spowodował eksplozję czaszki dla plakatu zaakceptowanej odpowiedzi.
Obsługuje pełne pierwszeństwo, nawiasy, nazwane zmienne i funkcje jednoargumentowe.
źródło
Wydałem parser wyrażeń oparty na algorytmie Dijkstra's Shunting Yard , na warunkach licencji Apache 2.0 :
http://projects.congrace.de/exp4j/index.html
źródło
Zaimplementowałem rekurencyjny parser zejścia w Javie w projekcie MathEclipse Parser . Może być również używany jako moduł Google Web Toolkit
źródło
Obecnie pracuję nad serią artykułów budujących parser wyrażeń regularnych jako narzędzie do nauki wzorców projektowych i czytelnego programowania. Możesz rzucić okiem na readablecode . W artykule przedstawiono klarowne zastosowanie algorytmu na rozrządach.
źródło
Napisałem parser wyrażeń w języku F # i opisałem go tutaj na blogu . Używa algorytmu stacji manewrowej, ale zamiast konwersji z wrostka na RPN, dodałem drugi stos, aby zebrać wyniki obliczeń. Prawidłowo obsługuje pierwszeństwo operatorów, ale nie obsługuje operatorów jednoargumentowych. Napisałem to, żeby nauczyć się F #, ale nie żeby nauczyć się analizowania wyrażeń.
źródło
Rozwiązanie w języku Python wykorzystujące pyparsing można znaleźć tutaj . Przetwarzanie notacji wrostkowej z różnymi operatorami z pierwszeństwem jest dość powszechne, dlatego parsowanie obejmuje również
infixNotation
(dawniejoperatorPrecedence
) konstruktor wyrażeń. Dzięki niemu możesz łatwo definiować wyrażenia boolowskie, na przykład za pomocą „AND”, „OR”, „NOT”. Lub możesz rozszerzyć swoją czterofunkcyjną arytmetykę, aby używać innych operatorów, takich jak! dla silni lub „%” dla modułu lub dodaj operatory P i C, aby obliczyć permutacje i kombinacje. Mógłbyś napisać parser infiksowy dla notacji macierzowej, który obejmuje obsługę operatorów „-1” lub „T” (dla inwersji i transpozycji). Przykład operatoraPrecedence 4-funkcyjnego parsera (z wrzuconym '!' Dla zabawy) jest tutaj.źródło
Wiem, że to późna odpowiedź, ale właśnie napisałem mały parser, który pozwala wszystkim operatorom (prefiksowi, postfiksowi i infix-left, infix-right i nonassociative) mieć arbitralny priorytet.
Mam zamiar rozszerzyć to na język z dowolną obsługą DSL, ale chciałem tylko zauważyć, że nie potrzeba niestandardowych parserów do pierwszeństwa operatorów, można użyć uogólnionego parsera, który w ogóle nie potrzebuje tabel, i po prostu wyszukuje pierwszeństwo każdego operatora, tak jak się pojawia. Ludzie wspominali o niestandardowych parserach Pratta lub parserach manewrowych, które mogą akceptować nielegalne dane wejściowe - ten nie musi być dostosowywany i (chyba że jest błąd) nie zaakceptuje złych danych wejściowych. W pewnym sensie nie jest to kompletne, zostało napisane, aby przetestować algorytm, a jego dane wejściowe mają postać, która będzie wymagała pewnego wstępnego przetworzenia, ale są komentarze, które to wyjaśniają.
Zwróć uwagę, że brakuje niektórych typowych operatorów, na przykład rodzaju operatora używanego do indeksowania tj. Tabela [indeks] lub wywoływanie funkcji (parametr-wyrażenie, ...) Zamierzam je dodać, ale myślę o obu jako o przyrostkach operatory, w których to, co znajduje się między separatorami „[” i „]” lub „(” i „)”, jest analizowane z inną instancją parsera wyrażeń. Przepraszam, że to pominęliśmy, ale część dotycząca postfiksa jest już dostępna - dodanie reszty prawdopodobnie prawie podwoi rozmiar kodu.
Ponieważ parser to tylko 100 linii kodu rakiety, może powinienem go po prostu wkleić tutaj, mam nadzieję, że to nie jest dłuższe niż pozwala na to stackoverflow.
Kilka szczegółów na temat arbitralnych decyzji:
Jeśli operator przyrostka o niskim priorytecie konkuruje o te same bloki wrostkowe, co operator prefiksu o niskim priorytecie, wygrywa operator prefiksu. Nie pojawia się to w większości języków, ponieważ większość z nich nie ma operatorów przyrostków o niskim priorytecie. - na przykład: ((data a) (left 1 +) (pre 2 not) (data b) (post 3!) (left 1 +) (data c)) to a + not b! + c gdzie not to a operator prefiksu i! jest operatorem postfiksowym i oba mają niższy priorytet niż +, więc chcą grupować w niekompatybilne sposoby albo jako (a + nie b!) + c, albo jako a + (nie b! + c) w tych przypadkach operator prefiksu zawsze wygrywa, więc po drugie sposób analizowania
Niezespolone operatory wrostkowe są naprawdę dostępne, więc nie musisz udawać, że operatory zwracające różne typy, niż mają razem sens, ale bez różnych typów wyrażeń dla każdego jest to kludge. W związku z tym w tym algorytmie operatory nieasocjacyjne odmawiają kojarzenia nie tylko ze sobą, ale z dowolnym operatorem o tym samym pierwszeństwie. To częsty przypadek, ponieważ <<= ==> = etc nie są ze sobą powiązane w większości języków.
Pytanie, w jaki sposób różne rodzaje operatorów (lewy, przedrostek itp.) Łamią powiązania na podstawie pierwszeństwa, nie powinno się pojawiać, ponieważ tak naprawdę nie ma sensu nadawać operatorom różnych typów tego samego pierwszeństwa. Ten algorytm robi coś w takich przypadkach, ale nawet nie kłopoczę się, aby dowiedzieć się, co dokładnie, ponieważ taka gramatyka jest po pierwsze złym pomysłem.
źródło
Oto proste rozwiązanie rekurencyjne, napisane w Javie. Zauważ, że nie obsługuje liczb ujemnych, ale możesz to dodać, jeśli chcesz:
}
źródło
Algorytm można łatwo zakodować w C jako rekurencyjny parser zstępujący.
przydatne mogą być następne biblioteki: yupana - operacje ściśle arytmetyczne; tinyexpr - operacje arytmetyczne + funkcje matematyczne w C + jedna zapewniana przez użytkownika; mpc - kombinatory parsera
Wyjaśnienie
Uchwyćmy sekwencję symboli, które reprezentują wyrażenie algebraiczne. Pierwsza to liczba, czyli cyfra dziesiętna powtórzona raz lub więcej razy. Taką notację będziemy nazywać regułą produkcji.
Operator dodawania i jego operandy to kolejna reguła. To jeden
number
lub dowolny symbol reprezentującysum "*" sum
sekwencję.Spróbuj zamienić
number
nasum "+" sum
to,number "+" number
które z kolei mogłoby zostać rozszerzone na to,[0..9]+ "+" [0..9]+
które ostatecznie można by zredukować, do1+8
którego jest poprawne wyrażenie dodawania.Inne podstawienia również dadzą prawidłowe wyrażenie:
sum "+" sum
->number "+" sum
->number "+" sum "+" sum
->number "+" sum "+" number
->number "+" number "+" number
->12+3+5
Kawałek po kawałku moglibyśmy przypominać zestaw reguł produkcji zwanych gramatyką, które wyrażają wszystkie możliwe wyrażenia algebraiczne.
Aby kontrolować pierwszeństwo operatora, zmień pozycję jego reguły produkcyjnej względem innych. Spójrz na gramatykę powyżej i zauważ, że reguła tworzenia
*
jest umieszczona poniżej,+
to wymusiproduct
ocenę wcześniejsum
. Wdrożenie po prostu łączy rozpoznawanie wzorców z oceną, a zatem ściśle odzwierciedla zasady produkcji.Tutaj
term
najpierw oceniamy i zwracamy go, jeśli nie ma*
po nim znaku, to jest pozostawione w naszej regule produkcji w przeciwnym razie - oceniamy symbole po i zwracamyterm.value * product.value
to jest właściwy wybór w naszej regule produkcyjnej, tj.term "*" product
źródło