Parser równań (wyrażeń) z pierwszeństwem?

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

Inteligentny projekt parsera matematycznego?

-Adam

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,

1+11*5

aby zrobić to ręcznie, musiałbyś przeczytać 1, a następnie zobaczyć plus i rozpocząć zupełnie nową rekurencyjną "sesję" parsowania zaczynając od 11... i upewnić się, że przeanalizowałeś 11 * 5swój własny czynnik, uzyskując drzewo parsowania z 1 + (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ć 11jako 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 ¹ 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

Główna lekcja Emacsa jest taka, że ​​język rozszerzeń nie powinien być zwykłym „językiem rozszerzeń”. Powinien to być prawdziwy język programowania, przeznaczony do pisania i utrzymywania istotnych programów. Ponieważ ludzie będą chcieli to zrobić!

[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).

aexpr   =   expr `chainl1` toOp
expr    =   optChainl1 term addop (toScalar 0)
term    =   factor `chainl1` mulop
factor  =   sexpr  `chainr1` powop
sexpr   =   parens aexpr
        <|> scalar
        <|> ident

powop   =   sym "^" >>= return . (B Pow)
        <|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))

toOp    =   sym "->" >>= return . (B To)

mulop   =   sym "*" >>= return . (B Mul)
        <|> sym "/" >>= return . (B Div)
        <|> sym "%" >>= return . (B Mod)
        <|>             return . (B Mul)

addop   =   sym "+" >>= return . (B Add) 
        <|> sym "-" >>= return . (B Sub)

scalar = number >>= return . toScalar

ident  = literal >>= return . Lit

parens p = do
             lparen
             result <- p
             rparen
             return result

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ć:

1. Spójrz na: 1 + 2, nic nie rób.
2. Teraz spójrz na 1 + 2 * 3, nadal nic nie rób.
3. Teraz spójrz na 1 + 2 * 3 + 4, teraz wiesz, że 2 * 3 musi zostać oszacowane, ponieważ następny operator ma niższy priorytet.

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 = []

• Przeczytaj 1. N = [1], Ops = []
• Przeczytaj +. N = [1], Ops = [+]
• Przeczytaj 2. N = [1 2], Ops = [+]
• Przeczytaj *. N = [1 2], Ops = [+ *]
• Przeczytaj 3. N = [1 2 3], Ops = [+ *]
• Przeczytaj +. N = [1 2 3], Ops = [+ *]
  • Wystrzel 3, 2 i wykonaj 2 *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 = [].
  • Na koniec wepchnij [+] na stos operatora. N = [7], Ops = [+].
• Przeczytaj 4. N = [7 4]. Ops = [+].
• Skończyły Ci się dane wejściowe, więc chcesz teraz opróżnić stosy. Po którym otrzymasz wynik 11.

To nie jest takie trudne, prawda? I nie wywołuje żadnych gramatyk ani generatorów parserów.

http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Bardzo dobre wyjaśnienie różnych podejść:

• Rozpoznawanie zejścia rekurencyjnego
• Algorytm stacji manewrowej
• Klasyczne rozwiązanie
• Pierwszeństwo w wspinaczce

Napisany prostym językiem i pseudokodem.

Podoba mi się „wspinaczka na pierwszeństwo”.

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.

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 .

// operator table
var ops = {
   '+'  : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } },
   '-'  : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return l-r; } },
   '*'  : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } },
   '/'  : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } },
   '**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } }
};

// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };

// input for parsing
// var r = { string: '123.45+33*8', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
    var startOffset = r.offset;
    var value;
    var m;
    // floating point number
    // example of parsing ("lexing") without aid of regular expressions
    value = 0;
    while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    if(r.string.substr(r.offset, 1) == ".") {
        r.offset++;
        while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    }
    if(r.offset > startOffset) {  // did that work?
        // OK, so I'm lazy...
        return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
    } else if(r.string.substr(r.offset, 1) == "+") {  // unary plus
        r.offset++;
        return parseVal(r);
    } else if(r.string.substr(r.offset, 1) == "-") {  // unary minus
        r.offset++;
        return negate(parseVal(r));
    } else if(r.string.substr(r.offset, 1) == "(") {  // expression in parens
        r.offset++;   // eat "("
        value = parseExpr(r);
        if(r.string.substr(r.offset, 1) == ")") {
            r.offset++;
            return value;
        }
        r.error = "Parsing error: ')' expected";
        throw 'parseError';
    } else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) {  // variable/constant name        
        // sorry for the regular expression, but I'm too lazy to manually build a varname lexer
        var name = m[0];  // matched string
        r.offset += name.length;
        if(name in vars) return vars[name];  // I know that thing!
        r.error = "Semantic error: unknown variable '" + name + "'";
        throw 'unknownVar';        
    } else {
        if(r.string.length == r.offset) {
            r.error = 'Parsing error at end of string: value expected';
            throw 'valueMissing';
        } else  {
            r.error = "Parsing error: unrecognized value";
            throw 'valueNotParsed';
        }
    }
}

function negate (value) {
    return -value;
}

function parseOp(r) {
    if(r.string.substr(r.offset,2) == '**') {
        r.offset += 2;
        return ops['**'];
    }
    if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
        return ops[r.string.substr(r.offset++, 1)];
    return null;
}

function parseExpr(r) {
    var stack = [{precedence: 0, assoc: 'L'}];
    var op;
    var value = parseVal(r);  // first value on the left
    for(;;){
        op = parseOp(r) || {precedence: 0, assoc: 'L'}; 
        while(op.precedence < stack[stack.length-1].precedence ||
              (op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) {  
            // precedence op is too low, calculate with what we've got on the left, first
            var tos = stack.pop();
            if(!tos.exec) return value;  // end  reached
            // do the calculation ("reduce"), producing a new value
            value = tos.exec(tos.value, value);
        }
        // store on stack and continue parsing ("shift")
        stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
        value = parseVal(r);  // value on the right
    }
}

function parse (string) {   // wrapper
    var r = {string: string, offset: 0};
    try {
        var value = parseExpr(r);
        if(r.offset < r.string.length){
          r.error = 'Syntax error: junk found at offset ' + r.offset;
            throw 'trailingJunk';
        }
        return value;
    } catch(e) {
        alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset));
        return;
    }    
}

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:

<Exp> ::= <Exp> + <Term> |
          <Exp> - <Term> |
          <Term>

<Term> ::= <Term> * <Factor> |
           <Term> / <Factor> |
           <Factor>

<Factor> ::= x | y | ... |
             ( <Exp> ) |
             - <Factor> |
             <Number>

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:

<Exp>  :: <Leaf> | <Exp> <Op> <Leaf>

<Op>   :: + | - | * | /

<Leaf> :: <Number> | (<Exp>)

(lub coś w tym rodzaju), nie wiedząc o tym!

Czy myślałeś o użyciu Boost Spirit ? Pozwala na pisanie gramatyki podobnej do EBNF w C ++ w następujący sposób:

group       = '(' >> expression >> ')';
factor      = integer | group;
term        = factor >> *(('*' >> factor) | ('/' >> factor));
expression  = term >> *(('+' >> term) | ('-' >> term));

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.

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.

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.

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ć :-)

Znalazłem to na liście PIC o algorytmie manewrowania :

Harold pisze:

Pamiętam, że dawno temu czytałem o algorytmie, który konwertował wyrażenia algebraiczne na RPN w celu łatwej oceny. Każda wartość wrostka, operator lub nawias był reprezentowany przez wagon na torze. Jeden typ samochodu odjechał na inny tor, a drugi jechał prosto. Nie pamiętam szczegółów (oczywiście!), Ale zawsze myślałem, że kodowanie będzie interesujące. To jest z powrotem, kiedy pisałem kod asemblera 6800 (nie 68000).

Jest to „algorytm stacji manewrowej”, z którego korzysta większość parserów maszyn. Zobacz artykuł o parsowaniu w Wikipedii. Prostym sposobem zakodowania algorytmu stacji manewrowej jest użycie dwóch stosów. Jeden to stos typu „push”, a drugi to stos „redukcja” lub „wynik”. Przykład:

pstack = () // pusty rstack = () input: 1 + 2 * 3 precedence = 10 // najniższa redukcja = 0 // nie zmniejszaj

start: token '1': isnumber, put in pstack (push) token '+': isoperator set precedence = 2 if precedence <previous_operator_precedence then zredukuj () // patrz poniżej wstaw '+' w pstack (push) token '2' : isnumber, put in pstack (push) token '*': isoperator, set precedence = 1, put in pstack (push) // sprawdź pierwszeństwo jako // nad tokenem '3': isnumber, put in pstack (push) end of wejście, trzeba zredukować (cel jest pusty pstack) zredukować () // gotowe

aby zredukować, zdejmij elementy ze stosu wypychania i umieść je w stosie wynikowym, zawsze zamień 2 górne elementy na stosie p, jeśli mają one postać „operator” „liczba”:

pstack: '1' '+' '2' ' ' '3' rstack: () ... pstack: () rstack: '3' '2' ' ' '1' '+'

gdyby wyrażenie brzmiało:

1 * 2 + 3

wtedy wyzwalaczem redukującym byłby odczyt tokena „+”, który ma niższy warunek wstępny niż „*” już wciśnięty, więc zrobiłby to:

pstack: '1' ' ' '2' rstack: () ... pstack: () rstack: '1' '2' ' '

a następnie wcisnął „+”, a następnie „3” i ostatecznie zmniejszył:

pstack: '+' '3' rstack: '1' '2' ' ' ... pstack: () rstack: '1' '2' ' ' '3' '+'

Tak więc skrócona wersja to: wypychaj liczby, podczas wypychania operatorów sprawdzaj pierwszeństwo poprzedniego operatora. Jeśli był wyższy niż operator, który ma być teraz popchnięty, najpierw zmniejsz, a następnie popchnij aktualnego operatora. Aby obsłużyć pareny, po prostu zachowaj pierwszeństwo operatora „poprzedni” i umieść znak na stosie p, który mówi algorytmowi redukującemu, aby przestał redukować podczas rozwiązywania problemu wewnętrznego pary pozawetowej. Paren zamykający wyzwala redukcję, podobnie jak koniec wprowadzania, a także usuwa znacznik otwartego paren ze stosu i przywraca pierwszeństwo „poprzedniej operacji”, dzięki czemu analizowanie może być kontynuowane po zamknięciu paren, w którym zostało przerwane. Można to zrobić z rekurencją lub bez (wskazówka: użyj stosu do przechowywania poprzedniego pierwszeństwa, gdy napotkasz '(' ...). Uogólniona wersja tego polega na wykorzystaniu generatora parsera zaimplementowanego algorytmu stacji manewrowej, np. za pomocą yacc lub bison lub taccle (tcl analog yacc).

Piotr

-Adam

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:

#include <stdio.h>
int main(int argc, char *argv[]){
  printf("((((");
  for(int i=1;i!=argc;i++){
    if(argv[i] && !argv[i][1]){
      switch(argv[i]){
      case '^': printf(")^("); continue;
      case '*': printf("))*(("); continue;
      case '/': printf("))/(("); continue;
      case '+': printf(")))+((("); continue;
      case '-': printf(")))-((("); continue;
      }
    }
    printf("%s", argv[i]);
  }
  printf("))))\n");
  return 0;
}

Wywołaj to jako:

$ cc -o parenthesise parenthesise.c
$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))

Co jest niesamowite w swojej prostocie i bardzo zrozumiałe.

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.

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

Zaimplementowałem rekurencyjny parser zejścia w Javie w projekcie MathEclipse Parser . Może być również używany jako moduł Google Web Toolkit

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.

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ń.

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(dawniej operatorPrecedence) 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.

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.

#lang racket
;cool the algorithm fits in 100 lines!
(define MIN-PREC -10000)
;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp)
;for example "not a*-7+5 < b*b or c >= 4"
;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))"
;is represented as '((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 <)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4)) 
;higher numbers are higher precedence
;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c))

(struct prec-parse ([data-stack #:mutable #:auto]
                    [op-stack #:mutable #:auto])
  #:auto-value '())

(define (pop-data stacks)
  (let [(data (car (prec-parse-data-stack stacks)))]
    (set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))
    data))

(define (pop-op stacks)
  (let [(op (car (prec-parse-op-stack stacks)))]
    (set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))
    op))

(define (push-data! stacks data)
    (set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks))))

(define (push-op! stacks op)
    (set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks))))

(define (process-prec min-prec stacks)
  (let [(op-stack (prec-parse-op-stack stacks))]
    (cond ((not (null? op-stack))
           (let [(op (car op-stack))]
             (cond ((>= (cadr op) min-prec) 
                    (apply-op op stacks)
                    (set-prec-parse-op-stack! stacks (cdr op-stack))
                    (process-prec min-prec stacks))))))))

(define (process-nonassoc min-prec stacks)
  (let [(op-stack (prec-parse-op-stack stacks))]
    (cond ((not (null? op-stack))
           (let [(op (car op-stack))]
             (cond ((> (cadr op) min-prec) 
                    (apply-op op stacks)
                    (set-prec-parse-op-stack! stacks (cdr op-stack))
                    (process-nonassoc min-prec stacks))
                   ((= (cadr op) min-prec) (error "multiply applied non-associative operator"))
                   ))))))

(define (apply-op op stacks)
  (let [(op-type (car op))]
    (cond ((eq? op-type 'post)
           (push-data! stacks `(,op ,(pop-data stacks) )))
          (else ;assume infix
           (let [(tos (pop-data stacks))]
             (push-data! stacks `(,op ,(pop-data stacks) ,tos))))))) 

(define (finish input min-prec stacks)
  (process-prec min-prec stacks)
  input
  )

(define (post input min-prec stacks)
  (if (null? input) (finish input min-prec stacks)
      (let* [(cur (car input))
             (input-type (car cur))]
        (cond ((eq? input-type 'post)
               (cond ((< (cadr cur) min-prec)
                      (finish input min-prec stacks))
                     (else 
                      (process-prec (cadr cur)stacks)
                      (push-data! stacks (cons cur (list (pop-data stacks))))
                      (post (cdr input) min-prec stacks))))
              (else (let [(handle-infix (lambda (proc-fn inc)
                                          (cond ((< (cadr cur) min-prec)
                                                 (finish input min-prec stacks))
                                                (else 
                                                 (proc-fn (+ inc (cadr cur)) stacks)
                                                 (push-op! stacks cur)
                                                 (start (cdr input) min-prec stacks)))))]
                      (cond ((eq? input-type 'left) (handle-infix process-prec 0))
                            ((eq? input-type 'right) (handle-infix process-prec 1))
                            ((eq? input-type 'nonassoc) (handle-infix process-nonassoc 0))
                            (else error "post op, infix op or end of expression expected here"))))))))

;alters the stacks and returns the input
(define (start input min-prec stacks)
  (if (null? input) (error "expression expected")
      (let* [(cur (car input))
             (input-type (car cur))]
        (set! input (cdr input))
        ;pre could clearly work with new stacks, but could it reuse the current one?
        (cond ((eq? input-type 'pre)
               (let [(new-stack (prec-parse))]
                 (set! input (start input (cadr cur) new-stack))
                 (push-data! stacks 
                             (cons cur (list (pop-data new-stack))))
                 ;we might want to assert here that the cdr of the new stack is null
                 (post input min-prec stacks)))
              ((eq? input-type 'data)
               (push-data! stacks cur)
               (post input min-prec stacks))
              ((eq? input-type 'grouped)
               (let [(new-stack (prec-parse))]
                 (start (cdr cur) MIN-PREC new-stack)
                 (push-data! stacks (pop-data new-stack)))
               ;we might want to assert here that the cdr of the new stack is null
               (post input min-prec stacks))
              (else (error "bad input"))))))

(define (op-parse input)
  (let [(stacks (prec-parse))]
    (start input MIN-PREC stacks)
    (pop-data stacks)))

(define (main)
  (op-parse (read)))

(main)

Oto proste rozwiązanie rekurencyjne, napisane w Javie. Zauważ, że nie obsługuje liczb ujemnych, ale możesz to dodać, jeśli chcesz:

public class ExpressionParser {

public double eval(String exp){
    int bracketCounter = 0;
    int operatorIndex = -1;

    for(int i=0; i<exp.length(); i++){
        char c = exp.charAt(i);
        if(c == '(') bracketCounter++;
        else if(c == ')') bracketCounter--;
        else if((c == '+' || c == '-') && bracketCounter == 0){
            operatorIndex = i;
            break;
        }
        else if((c == '*' || c == '/') && bracketCounter == 0 && operatorIndex < 0){
            operatorIndex = i;
        }
    }
    if(operatorIndex < 0){
        exp = exp.trim();
        if(exp.charAt(0) == '(' && exp.charAt(exp.length()-1) == ')')
            return eval(exp.substring(1, exp.length()-1));
        else
            return Double.parseDouble(exp);
    }
    else{
        switch(exp.charAt(operatorIndex)){
            case '+':
                return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));
            case '-':
                return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));
            case '*':
                return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));
            case '/':
                return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));
        }
    }
    return 0;
}

}

Algorytm można łatwo zakodować w C jako rekurencyjny parser zstępujący.

#include <stdio.h>
#include <ctype.h>

/*
 *  expression -> sum
 *  sum -> product | product "+" sum
 *  product -> term | term "*" product
 *  term -> number | expression
 *  number -> [0..9]+
 */

typedef struct {
    int value;
    const char* context;
} expression_t;

expression_t expression(int value, const char* context) {
    return (expression_t) { value, context };
}

/* begin: parsers */

expression_t eval_expression(const char* symbols);

expression_t eval_number(const char* symbols) {
    // number -> [0..9]+
    double number = 0;        
    while (isdigit(*symbols)) {
        number = 10 * number + (*symbols - '0');
        symbols++;
    }
    return expression(number, symbols);
}

expression_t eval_term(const char* symbols) {
    // term -> number | expression
    expression_t number = eval_number(symbols);
    return number.context != symbols ? number : eval_expression(symbols);
}

expression_t eval_product(const char* symbols) {
    // product -> term | term "*" product
    expression_t term = eval_term(symbols);
    if (*term.context != '*')
        return term;

    expression_t product = eval_product(term.context + 1);
    return expression(term.value * product.value, product.context);
}

expression_t eval_sum(const char* symbols) {
    // sum -> product | product "+" sum
    expression_t product = eval_product(symbols);
    if (*product.context != '+')
        return product;

    expression_t sum = eval_sum(product.context + 1);
    return expression(product.value + sum.value, sum.context);
}

expression_t eval_expression(const char* symbols) {
    // expression -> sum
    return eval_sum(symbols);
}

/* end: parsers */

int main() {
    const char* expression = "1+11*5";
    printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value);

    return 0;
}

_{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.}

number -> [0..9]+

Operator dodawania i jego operandy to kolejna reguła. To jeden numberlub dowolny symbol reprezentujący sum "*" sumsekwencję.

sum -> number | sum "+" sum

Spróbuj zamienić numberna sum "+" sumto, number "+" numberktóre z kolei mogłoby zostać rozszerzone na to, [0..9]+ "+" [0..9]+które ostatecznie można by zredukować, do 1+8któ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.

expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+                                                                    

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 wymusi productocenę wcześniej sum. Wdrożenie po prostu łączy rozpoznawanie wzorców z oceną, a zatem ściśle odzwierciedla zasady produkcji.

expression_t eval_product(const char* symbols) {
    // product -> term | term "*" product
    expression_t term = eval_term(symbols);
    if (*term.context != '*')
        return term;

    expression_t product = eval_product(term.context + 1);
    return expression(term.value * product.value, product.context);
}

Tutaj termnajpierw 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 zwracamy term.value * product.value _{to jest właściwy wybór w naszej regule produkcyjnej, tj.term "*" product}