Analyseur d'équation (expression) avec précédence ?

Question

J'ai développé un analyseur d'équation utilisant un algorithme de pile simple qui gère les opérateurs binaires (+, -, |, &, *, /, etc), les opérateurs unaires ( !) et les parenthèses.

En utilisant cette méthode, cependant, tout a la même préséance - tout est évalué de gauche à droite, quel que soit l'opérateur, bien que la préséance puisse être imposée en utilisant des parenthèses.

Donc, actuellement, "1+11*5" renvoie 60, et non 56 comme on pourrait s'y attendre.

Bien que cela convienne au projet actuel, je souhaite disposer d'une routine d'usage général que je pourrai utiliser pour des projets ultérieurs.

Modifié pour plus de clarté :

Quel est un bon algorithme pour analyser les équations avec la préséance ?

Je suis intéressé par quelque chose de simple à mettre en œuvre et à comprendre que je peux coder moi-même pour éviter les problèmes de licence avec le code disponible.

La grammaire :

Je ne comprends pas la question de la grammaire - j'ai écrit ceci à la main. C'est suffisamment simple pour que je ne voie pas l'utilité de YACC ou de Bison. J'ai simplement besoin de calculer des chaînes de caractères avec des équations telles que "2+3 * (42/13)".

Langue :

Je fais cela en C, mais je suis intéressé par un algorithme, pas par une solution spécifique au langage. Le C est suffisamment bas niveau pour qu'il soit facile de le convertir dans un autre langage si le besoin s'en fait sentir.

Exemple de code

J'ai posté le code de test pour l'analyseur d'expression simple dont je parlais plus haut. Les exigences du projet ont changé et je n'ai donc jamais eu besoin d'optimiser le code pour les performances ou l'espace, car cela n'était pas intégré au projet. C'est dans la forme verbeuse originale, et devrait être facilement compréhensible. Si je fais quoi que ce soit d'autre avec lui en termes de précédence des opérateurs, je choisirai probablement le macro hack parce qu'il correspond au reste du programme en termes de simplicité. Si je l'utilise un jour dans un vrai projet, j'opterai pour un analyseur plus compact et plus rapide.

Question connexe

Conception intelligente d'un analyseur mathématique ?

-Adam

Answer 1

Le site algorithme de la gare de triage est l'outil idéal pour cela. Wikipedia est très confus à ce sujet, mais en gros, l'algorithme fonctionne comme suit :

Disons que vous voulez évaluer 1 + 2 * 3 + 4. Intuitivement, vous "savez" que vous devez d'abord faire le 2 * 3, mais comment obtenir ce résultat ? La clé est de réaliser que, lorsque vous parcourez la chaîne de caractères de gauche à droite, vous évaluez un opérateur lorsque l'opérateur que vous avez choisi est le même. suit il a une précédence inférieure (ou égale). Dans le contexte de l'exemple, voici ce que vous voulez faire :

1. Regarde : 1 + 2, ne faites rien.
2. Maintenant, regardez 1 + 2 * 3, ça ne fait toujours rien.
3. Regardez maintenant 1 + 2 * 3 + 4, vous savez maintenant que 2 * 3 doit être évalué parce que l'opérateur suivant a une priorité inférieure.

Comment le mettre en œuvre ?

Vous voulez avoir deux piles, une pour les nombres, et une autre pour les opérateurs. Vous poussez les nombres sur la pile en permanence. Vous comparez chaque nouvel opérateur avec celui qui se trouve en haut de la pile, si celui qui se trouve en haut de la pile est plus prioritaire, vous le sortez de la pile des opérateurs, vous sortez les opérandes de la pile des nombres, vous appliquez l'opérateur et vous poussez le résultat sur la pile des nombres. Maintenant, vous répétez la comparaison avec l'opérateur du haut de la pile.

Pour en revenir à l'exemple, cela fonctionne comme suit :

N = [ ] Ops = [ ]

• Lire 1. N = [1], Ops = [ ]
• Lire +. N = [1], Ops = [+]
• Lire 2. N = [1 2], Ops = [+]
• Lire * . N = [1 2], Ops = [+ *]
• Lire 3. N = [1 2 3], Ops = [+ *]
• Lire +. N = [1 2 3], Ops = [+ *]
  • Pop 3, 2 et exécutez 2 * 3, et pousser le résultat sur N. N = [1 6], Ops = [+]
  • + est associatif à gauche, donc vous voulez enlever 1, 6 aussi et exécuter le +. N = [7], Ops = [].
  • Enfin, poussez le [+] sur la pile des opérateurs. N = [7], Ops = [+].
• Lire 4. N = [7 4]. Ops = [+].
• Vous êtes à court d'entrées, donc vous voulez vider les piles maintenant. Sur quoi vous obtiendrez le résultat 11.

Voilà, ce n'est pas si difficile, n'est-ce pas ? Et il ne fait aucune invocation à des grammaires ou des générateurs d'analyseurs.

Answer 2

La manière forte

Vous voulez un analyseur syntaxique à descente récursive .

Pour obtenir la préséance, vous devez penser de manière récursive, par exemple, en utilisant votre exemple de chaîne,

1+11*5

pour le faire manuellement, vous devriez lire le document 1 puis voir le plus et commencer une nouvelle "session" d'analyse récursive commençant par 11 ... et assurez-vous d'analyser l'élément 11 * 5 dans son propre facteur, ce qui donne un arbre d'analyse syntaxique avec 1 + (11 * 5) .

Tout cela est si pénible à expliquer, surtout si l'on ajoute l'impuissance de C. Vous voyez, après avoir analysé le 11, si le * était en fait un + à la place, vous devriez abandonner la tentative de créer un terme et analyser à la place l'expression 11 comme un facteur. Ma tête est déjà en train d'exploser. C'est possible avec la stratégie récursive décente, mais il y a un meilleur moyen...

La méthode simple (et correcte)

Si vous utilisez un outil GPL comme Bison, vous n'avez probablement pas à vous soucier des problèmes de licence puisque le code C généré par Bison n'est pas couvert par la GPL (je ne suis pas sûr que les outils GPL n'imposent pas la GPL sur le code/binaire généré ; par exemple, Apple compile du code comme Aperture avec GCC et le vend sans avoir à le mettre sous licence).

Télécharger Bison (ou quelque chose d'équivalent, ANTLR, etc.).

Il existe généralement un exemple de code sur lequel vous pouvez simplement exécuter bison et obtenir le code C souhaité qui démontre cette calculatrice à quatre fonctions :

http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html

Regardez le code généré, et vous verrez que ce n'est pas aussi facile qu'il n'y paraît. De plus, les avantages de l'utilisation d'un outil comme Bison sont les suivants : 1) vous apprenez quelque chose (surtout si vous lisez le livre de Dragon et apprenez les grammaires), 2) vous évitez NIH en essayant de réinventer la roue. Avec un véritable outil de génération d'analyseur syntaxique, vous avez une chance de passer à l'échelle plus tard, en montrant aux autres personnes que vous connaissez que les analyseurs syntaxiques sont le domaine des outils d'analyse syntaxique.

---

Mise à jour :

Les personnes présentes ici ont donné de nombreux conseils judicieux. Ma seule mise en garde contre le fait de ne pas utiliser les outils d'analyse syntaxique, de se contenter de l'algorithme Shunting Yard ou d'un analyseur syntaxique récursif décent est que les petits langages jouets 1 pourraient un jour se transformer en de véritables grands langages avec des fonctions (sin, cos, log) et des variables, des conditions et des boucles for.

Flex/Bison peut très bien être surdimensionné pour un petit interprète simple, mais un analyseur syntaxique + évaluateur unique peut causer des problèmes à long terme lorsque des modifications doivent être apportées ou que des fonctionnalités doivent être ajoutées. Votre situation variera et vous devrez faire preuve de discernement. punir d'autres personnes pour vos péchés [2] et construire un outil moins qu'adéquat.

Mon outil préféré pour l'analyse syntaxique

Le meilleur outil au monde pour ce travail est le Parsec (pour les analyseurs décents récursifs) qui est fournie avec le langage de programmation Haskell. Elle ressemble beaucoup à BNF ou comme un outil spécialisé ou un langage spécifique à un domaine pour l'analyse syntaxique (exemple de code [3]), mais il s'agit en fait d'une bibliothèque ordinaire en Haskell, ce qui signifie qu'elle se compile au cours de la même étape de construction que le reste de votre code Haskell, que vous pouvez écrire du code Haskell arbitraire et l'appeler dans votre analyse syntaxique, et que vous pouvez mélanger d'autres bibliothèques. tous dans le même code . (Intégrer un tel langage d'analyse syntaxique dans un langage autre que Haskell donne lieu à de nombreuses lacunes syntaxiques, soit dit en passant. J'ai fait cela en C# et cela fonctionne assez bien mais ce n'est pas aussi joli et succinct).

Notes :

1 Richard Stallman dit, dans Pourquoi vous ne devriez pas utiliser Tcl

La principale leçon d'Emacs est que un langage d'extension ne doit pas être un simple "langage d'extension". Il devrait être un véritable langage de programmation, conçu pour écrire et maintenir programmes substantiels. Parce que les gens voudront le faire !

[2] Oui, je suis marqué à jamais par l'utilisation de ce "langage".

Notez également que lorsque j'ai soumis cette entrée, l'aperçu était correct, mais L'analyseur de SO, moins qu'adéquat, a mangé ma balise d'ancre fermée dans le premier paragraphe. ce qui prouve que les analyseurs syntaxiques ne sont pas à prendre à la légère car si vous utilisez des regex et des bidouillages ponctuels vous allez probablement vous tromper sur quelque chose de subtil et de petit .

[3] Extrait d'un analyseur Haskell utilisant Parsec : une calculatrice à quatre fonctions étendue avec des exposants, des parenthèses, des espaces pour la multiplication et des constantes (comme pi et 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

Answer 3

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

Très bonne explication des différentes approches :

• Reconnaissance par descente récursive
• L'algorithme de la gare de triage
• La solution classique
• Montée de la préséance

Écrit dans un langage simple et en pseudo-code.

J'aime bien celui de "l'escalade de la préséance".

Answer 4

Il y a un bon article ici sur la combinaison d'un simple analyseur par descente récursive avec un analyseur par précédence d'opérateur. Si vous avez récemment écrit des analyseurs syntaxiques, sa lecture devrait être très intéressante et instructive.

Answer 5

Il y a longtemps, j'ai créé mon propre algorithme d'analyse syntaxique, que je ne trouvais pas dans les livres sur l'analyse syntaxique (comme le Livre du Dragon). En regardant les pointeurs de l'algorithme de Shunting Yard, je vois la ressemblance.

Il y a environ deux ans, j'ai publié un article à ce sujet, avec le code source en Perl, sur le site http://www.perlmonks.org/?node_id=554516 . Il est facile à porter vers d'autres langages : la première implémentation que j'ai faite était en assembleur Z80.

Il est idéal pour le calcul direct avec des nombres, mais vous pouvez l'utiliser pour produire un arbre d'analyse si vous le souhaitez.

Mise à jour Parce que plus de gens peuvent lire (ou exécuter) Javascript, j'ai réimplémenté mon analyseur en Javascript, après que le code ait été réorganisé. L'analyseur complet fait moins de 5k de code Javascript (environ 100 lignes pour l'analyseur, 15 lignes pour une fonction wrapper), y compris les rapports d'erreurs et les commentaires.

Vous pouvez trouver une démo en direct à l'adresse suivante 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;
    }    
}