Implicite priorité

Question

Je suis en train de lire un livre — "Flex et Bison" pour comprendre comment parser générateurs de travail et il est par exemple:

calclist: /* nothing */
        | calclist exp EOL { printf("= %d\n", $1); }
        ;

exp: factor
   | exp ADD factor { $$ = $1 + $3; } 
   | exp SUB factor { $$ = $1 - $3; }
   ;

factor: term
      | factor MUL term { $$ = $1 * $3; } 
      | factor DIV term { $$ = $1 / $3; }
      ;

term: NUMBER
    | ABS term { $$ = $2 >= 0? $2 : - $2; }
    ;

et dans le livre dit que la grammaire ci-dessus a priorité implicite en utilisant séparé non-terminal en question des symboles.Mais comment ça fonctionne?Considérons l'exemple suivant: 1 + 3 * 2 (les espacements juste sauts), nous lisons le premier gage 1 il sera poussé à pile NUMBER ou comme term ou comme factor pour combien de temps il sera "bouillonnement" par le biais de la grammaire?À partir de laquelle règle de grammaire prochain jeton sera vérifiée?Pourquoi avec cette grammaire de multiplication ont une priorité plus élevée que l'addition?

Answer 1

La raison de ce qui est "implicite" priorité (non explicite) est, en effet, tout comme le texte dit, en raison de la factorisée de grammaire (séparée nonterminals).

Travailler à travers votre exemple de 1 + 3 * 2, s'imaginer que l'ordinateur qui effectue l'analyse, à la suite de chaque instruction "à la lettre", comme elle l'avait fait.Afin de trouver un "exp" (l'expression de), vous devez d'abord trouver un facteur.(Vos autres options sont à commencer par trouver un "exp" mais qu'a trouver un "facteur".) Donc vous devez trouver un facteur de ...mais pour ce faire vous devez trouver un "terme", car un facteur est soit un terme, ou un facteur qui elle-même commence avec un terme.Alors maintenant, vous devez trouver un terme, qui est soit une NUMBER ou le mot-clé ABS.De sorte que vous pouvez "accepter" (en termes de grammaire) le 1, qui en fait est un NUMBER, et vous avez réussi à la première partie de l'analyse -- trouver un terme.(Vous maintenant supprimer le 1 le jeton de flux, vous laissant avec + comme le prochain jeton.)

Maintenant que vous avez un mandat, vous avez également un facteur (par définition), mais afin de "compléter l'action de ayant un facteur", comme c'était le cas, vous devez essayer pour le plus de match:un facteur suivie par MUL ou DIV, suivi par quelque chose.Votre prochain jeton est +:ce n'est pas une MUL et ce n'est pas une DIV.Ainsi, vous êtes contraint d'arrêter l'analyse du facteur et de renvoyer la totalité de l'analyser à la chaîne de mesure que votre facteur: 1 est un facteur, et le prochain jeton est toujours +.

Maintenant que vous avez un facteur, vous avez une exp (par définition), mais afin de "compléter l'action d'avoir une exp", vous êtes de nouveau obligé de l'essayer pour la plus de correspondance:une exp suivie par ADD ou SUB, suivi par quelque chose.Le prochain jeton est toujours + qui est en fait un complément ...si vous devez procéder à l' exp ADD factor { $$ = $1 + $3 }; la règle.

À ce stade, vous (en tant qu'analyseur) pousser la chose la mesure sur une pile et d'apprendre à travailler de nouveau à la recherche pour le non-terminal en question, dans ce cas, un autre "facteur".Si vous commencez maintenant à la règle pour un facteur.Vous devez chercher un "terme", et si vous en trouvez un, essayez de faire la version longue de la règle qui inclut une MUL ou DIV.Lorsque vous travaillez dans cette partie, vous verrez que la * jeton est en effet une MUL et vous aurez à prendre le long de la règle, de faire le "facteur" résultat, utilisez le factor MUL term { $$ = $1 * $3; } partie de la règle.Ceci permettra d'accepter, aka manger / l'utilisation, la 3 * 2 la séquence et le retour de la valeur 6 pour le "facteur" qui permet de compléter la règle que vous avez poussé sur votre analyser la pile.

De retour à votre poussée de l'état, vous effectuer l'analyse de "1 +" par l'ajout de 1 et de l'acceptation (manger) l'expression complète.Et bien sûr 1 + 6 est 7, de sorte que votre grammaire renvoie la valeur correcte.

Answer 2

L'ordre de préséance est le résultat de la opérandes de ADD et SUB étant les facteurs, et les seuls facteurs qui contiennent MUL et DIV opérateurs.AJOUTER n'est pas en concurrence avec MUL, parce que le MULTI est encapsulé dans un terme.

La réflexion sur ce qui, du point de vue de l'analyseur:le terme expression doit être réduite avant de l'analyseur estime que sa relation à l'AJOUT de l'opérateur, et que la réduction oblitère la MUL de l'opérateur.

Compte tenu de A + X * Y, le X * Y l'expression est réduite à term qui est une grammaire unique symbole qui n'exprime plus la * l'opérateur, et donc il n'y a rien pour l' + l'opérateur d'avoir une question de priorité à l'égard de;il est maintenant juste A + term.

Par ailleurs, la grammaire utilisations non conventionnelles inversée de la terminologie.

Ces termes:A + B + C

Ces sont des facteurs:A*B*C

Les termes sont ajoutés (les"conditions d'une série"), les facteurs sont multipliés ("facteurs d'un nombre entier ou polynomiale").

Est-ce vraiment à partir de ce manuel?Dans tous les cas, essayez de Compilateurs:Principes, Techniques et Outils par Aho, Sethi, Ullman.(1988 mais classique).