Opération de l'analyseur syntaxique générée par la commande yacc

Editer en ligne

La commande yacc convertit le fichier de grammaire en programme en langage C.

Ce programme, lorsqu'il est compilé et exécuté, analyse l'entrée en fonction de la spécification grammaticale fournie.

L'analyseur est une machine à états finis avec une pile. L'analyseur syntaxique peut lire et mémoriser le jeton d'anticipation. L'état en cours est toujours l'état en haut de la pile. Les états de la machine à états finis sont représentés par de petits entiers. Au départ, la machine est à l'état 0, la pile ne contient que 0 et aucun jeton d'anticipation n'a été lu.

La machine peut effectuer l'une des actions suivantes:
Opération Descriptif
shift Etat L'analyseur syntaxique insère l'état en cours dans la pile, fait de l'état Etat l'état en cours et efface le jeton d'anticipation.
réduire Règle Lorsque l'analyseur trouve une chaîne définie par Règle (un numéro de règle) dans le flux d'entrée, il remplace cette chaîne par Règle dans le flux de sortie.
accepter L'analyseur syntaxique examine toutes les entrées, les met en correspondance avec la spécification grammaticale et reconnaît l'entrée comme satisfaisant à la structure de niveau le plus élevé (définie par le symbole de début). Cette action apparaît uniquement lorsque le jeton de recherche anticipée est le marqueur de fin et indique que l'analyseur syntaxique a effectué son travail avec succès.
Erreur L'analyseur syntaxique ne peut pas continuer à traiter le flux d'entrée et le faire correspondre avec les règles définies dans la spécification grammaticale. Les jetons d'entrée examinés par l'analyseur syntaxique, ainsi que le jeton d'entrée anticipée, ne peuvent pas être suivis de quoi que ce soit qui donnerait lieu à une entrée valide. L'analyseur syntaxique signale une erreur et tente de récupérer la situation et de reprendre l'analyse syntaxique.

L'analyseur syntaxique effectue les actions suivantes au cours d'une étape de processus:

  1. En fonction de son état actuel, l'analyseur syntaxique décide s'il a besoin d'un jeton d'anticipation pour déterminer l'action à effectuer. Si l'analyseur syntaxique a besoin d'un jeton d'anticipation et n'en a pas, il appelle la sous-routine yylex pour obtenir le jeton suivant.
  2. A l'aide de l'état en cours et du jeton de recherche anticipée, si nécessaire, l'analyseur syntaxique décide de son action suivante et l'exécute. Par conséquent, les états peuvent être insérés dans la pile ou en sortir, et le jeton d'anticipation peut être traité ou laissé seul.

Action Maj

L'action shift est l'action la plus courante que l'analyseur effectue. Chaque fois que l'analyseur syntaxique effectue un décalage, un jeton d'anticipation existe toujours. Par exemple, prenez en compte la règle de spécification de grammaire suivante:
IF shift 34
Si l'analyseur syntaxique est à l'état qui contient cette règle et que le jeton d'anticipation estIF, l'analyseur syntaxique:
  1. Envoie l'état en cours vers le bas sur la pile.
  2. Rend l'état34l'état courant (le place en haut de la pile).
  3. Efface le jeton d'anticipation.

Action Réduire

L'action reduce permet d'éviter que la pile ne soit trop volumineuse. L'analyseur syntaxique utilise des actions de réduction après la mise en correspondance du côté droit d'une règle avec le flux d'entrée. L'analyseur syntaxique est alors prêt à remplacer les caractères du flux d'entrée par le côté gauche de la règle. L'analyseur peut être amené à utiliser le jeton de recherche anticipée pour déterminer si le modèle est une correspondance complète.

Les actions de réduction sont associées à des règles grammaticales individuelles. Etant donné que les règles grammaticales comportent également des nombres entiers de petite taille, il est facile de confondre les significations des nombres dans les deux actions, shift et reduce. Par exemple, l'action suivante fait référence à la règle de grammaire18:
. reduce 18
L'action suivante fait référence à l'état34:
IF shift 34
Par exemple, pour réduire la règle suivante, l'analyseur syntaxique affiche les trois premiers états de la pile:
A  :  x y z ;

Le nombre d'états est égal au nombre de symboles à droite de la règle. Ces états sont ceux mis sur la pile lors de la reconnaissancex,yetz. Après l'apparition de ces états, un état est découvert, c'est-à-dire l'état dans lequel l'analyseur syntaxique se trouvait avant de commencer à traiter la règle, c'est-à-dire l'état qui devait reconnaître la règleApour satisfaire à sa règle. A l'aide de cet état non couvert et du symbole sur le côté gauche de la règle, l'analyseur syntaxique effectue une action appelée goto, qui est similaire à un décalage deA. Un nouvel état est obtenu, inséré dans la pile et l'analyse se poursuit.

L'action goto est différente d'une période de travail ordinaire d'un jeton. Le jeton d'anticipation est effacé par une période de travail mais n'est pas affecté par une action goto . Lorsque les trois états sont détectés, l'état non couvert contient une entrée telle que la suivante:
A  goto 20

Cette entrée provoque l'état20à pousser sur la pile et à devenir l'état courant.

L'action de réduction est également importante dans le traitement des actions et des valeurs fournies par l'utilisateur. Lorsqu'une règle est réduite, l'analyseur syntaxique exécute le code que vous avez inclus dans la règle avant d'ajuster la pile. Une autre pile s'exécutant en parallèle avec la pile contenant les états contient les valeurs renvoyées par l'analyseur lexical et les actions. Lorsqu'une période de travail est effectuée, la variable externe yylval est copiée sur la pile contenant les valeurs. Après l'exécution du code que vous fournissez, l'analyseur syntaxique effectue la réduction. Lorsque l'analyseur effectue l'action goto , il copie la variable externe yylval dans la pile de valeurs. Les mots clés yacc qui commencent par$faire référence à la pile de valeurs.