Python Language Partie 2: Analyse d'entrées Tokenized avec Yacc


Exemple

Cette section explique comment est traitée la saisie de jetons de la partie 1 - elle est effectuée à l'aide de grammaires sans contexte (CFG). La grammaire doit être spécifiée et les jetons sont traités en fonction de la grammaire. Sous le capot, l'analyseur utilise un analyseur LALR.

# Yacc example

import ply.yacc as yacc

# Get the token map from the lexer. This is required.
from calclex import tokens

def p_expression_plus(p):
    'expression : expression PLUS term'
    p[0] = p[1] + p[3]

def p_expression_minus(p):
    'expression : expression MINUS term'
    p[0] = p[1] - p[3]

def p_expression_term(p):
    'expression : term'
    p[0] = p[1]

def p_term_times(p):
    'term : term TIMES factor'
    p[0] = p[1] * p[3]

def p_term_div(p):
    'term : term DIVIDE factor'
    p[0] = p[1] / p[3]

def p_term_factor(p):
    'term : factor'
    p[0] = p[1]

def p_factor_num(p):
    'factor : NUMBER'
    p[0] = p[1]

def p_factor_expr(p):
    'factor : LPAREN expression RPAREN'
    p[0] = p[2]

# Error rule for syntax errors
def p_error(p):
    print("Syntax error in input!")

# Build the parser
parser = yacc.yacc()

while True:
   try:
       s = raw_input('calc > ')
   except EOFError:
       break
   if not s: continue
   result = parser.parse(s)
   print(result)

Panne

  • Chaque règle de grammaire est définie par une fonction dans laquelle docstring à cette fonction contient la spécification de grammaire sans contexte appropriée. Les instructions qui constituent le corps de la fonction implémentent les actions sémantiques de la règle. Chaque fonction accepte un seul argument p qui est une séquence contenant les valeurs de chaque symbole de grammaire dans la règle correspondante. Les valeurs de p[i] sont mappées sur des symboles de grammaire, comme indiqué ici:

      def p_expression_plus(p):
          'expression : expression PLUS term'
          #   ^            ^        ^    ^
          #  p[0]         p[1]     p[2] p[3]
    
          p[0] = p[1] + p[3]
    
  • Pour les jetons, la "valeur" du p[i] est identique à l'attribut p.value attribué dans le module lexer. Donc, PLUS aura la valeur + .

  • Pour les non-terminaux, la valeur est déterminée par tout ce qui est placé dans p[0] . Si rien n'est placé, la valeur est Aucun. De plus, p[-1] n'est pas la même chose que p[3] , puisque p n'est pas une simple liste ( p[-1] peut spécifier des actions incorporées (non discuté ici)).

Notez que la fonction peut avoir n'importe quel nom, tant qu'elle est précédée de p_ .

  • La p_error(p) est définie pour intercepter les erreurs de syntaxe (comme yyerror dans yacc / bison).

  • Plusieurs règles de grammaire peuvent être combinées en une seule fonction, ce qui est une bonne idée si les productions ont une structure similaire.

      def p_binary_operators(p):
          '''expression : expression PLUS term
                        | expression MINUS term
             term       : term TIMES factor
                        | term DIVIDE factor'''
          if p[2] == '+':
              p[0] = p[1] + p[3]
          elif p[2] == '-':
              p[0] = p[1] - p[3]
          elif p[2] == '*':
              p[0] = p[1] * p[3]
          elif p[2] == '/':
              p[0] = p[1] / p[3] 
    
  • Les littéraux de caractères peuvent être utilisés à la place des jetons.

      def p_binary_operators(p):
          '''expression : expression '+' term
                        | expression '-' term
             term       : term '*' factor
                        | term '/' factor'''
          if p[2] == '+':
              p[0] = p[1] + p[3]
          elif p[2] == '-':
              p[0] = p[1] - p[3]
          elif p[2] == '*':
              p[0] = p[1] * p[3]
          elif p[2] == '/':
              p[0] = p[1] / p[3]
    

    Bien entendu, les littéraux doivent être spécifiés dans le module lexer.

  • Les productions vides ont la forme '''symbol : '''

  • Pour définir explicitement le symbole de début, utilisez start = 'foo' , où foo est un non-terminal.

  • La définition de la priorité et de l’associativité peut être effectuée à l’aide de la variable de priorité.

      precedence = (
          ('nonassoc', 'LESSTHAN', 'GREATERTHAN'),  # Nonassociative operators
          ('left', 'PLUS', 'MINUS'),
          ('left', 'TIMES', 'DIVIDE'),
          ('right', 'UMINUS'),            # Unary minus operator
      )
    

    Les jetons sont classés de la plus basse à la plus haute priorité. nonassoc signifie que ces jetons ne sont pas associés. Cela signifie que quelque chose comme a < b < c est illégal alors a < b est toujours légal.

  • parser.out est un fichier de débogage créé lorsque le programme yacc est exécuté pour la première fois. Chaque fois qu'un changement / une réduction de conflit se produit, l'analyseur se déplace toujours.