Python Language
Python Lex-Yacc

Introduction

Remarques

Premiers pas avec PLY

Pour installer PLY sur votre machine pour python2 / 3, procédez comme suit:

1. Téléchargez le code source à partir d' ici .
2. Décompressez le fichier zip téléchargé
3. Naviguez dans le dossier ply-3.10 décompressé
4. Exécutez la commande suivante dans votre terminal: python setup.py install

Si vous avez terminé tout ce qui précède, vous devriez maintenant pouvoir utiliser le module PLY. Vous pouvez le tester en ouvrant un interpréteur python et en tapant import ply.lex .

Remarque: N'utilisez pas pip pour installer PLY, il installera une distribution défectueuse sur votre machine.

Le "Bonjour, Monde!" de PLY - Une calculatrice simple

Démontrons la puissance de PLY avec un exemple simple: ce programme prendra une expression arithmétique comme entrée de chaîne et tentera de la résoudre.

Ouvrez votre éditeur préféré et copiez le code suivant:

from ply import lex
import ply.yacc as yacc

tokens = (
    'PLUS',
    'MINUS',
    'TIMES',
    'DIV',
    'LPAREN',
    'RPAREN',
    'NUMBER',
)

t_ignore = ' \t'

t_PLUS    = r'\+'
t_MINUS   = r'-'
t_TIMES   = r'\*'
t_DIV     = r'/'
t_LPAREN  = r'\('
t_RPAREN  = r'\)'

def t_NUMBER( t ) :
    r'[0-9]+'
    t.value = int( t.value )
    return t

def t_newline( t ):
  r'\n+'
  t.lexer.lineno += len( t.value )

def t_error( t ):
  print("Invalid Token:",t.value[0])
  t.lexer.skip( 1 )

lexer = lex.lex()

precedence = (
    ( 'left', 'PLUS', 'MINUS' ),
    ( 'left', 'TIMES', 'DIV' ),
    ( 'nonassoc', 'UMINUS' )
)

def p_add( p ) :
    'expr : expr PLUS expr'
    p[0] = p[1] + p[3]

def p_sub( p ) :
    'expr : expr MINUS expr'
    p[0] = p[1] - p[3]

def p_expr2uminus( p ) :
    'expr : MINUS expr %prec UMINUS'
    p[0] = - p[2]

def p_mult_div( p ) :
    '''expr : expr TIMES expr
            | expr DIV expr'''

    if p[2] == '*' :
        p[0] = p[1] * p[3]
    else :
        if p[3] == 0 :
            print("Can't divide by 0")
            raise ZeroDivisionError('integer division by 0')
        p[0] = p[1] / p[3]

def p_expr2NUM( p ) :
    'expr : NUMBER'
    p[0] = p[1]

def p_parens( p ) :
    'expr : LPAREN expr RPAREN'
    p[0] = p[2]

def p_error( p ):
    print("Syntax error in input!")

parser = yacc.yacc()

res = parser.parse("-4*-(3-5)") # the input
print(res)

Enregistrez ce fichier sous le nom calc.py et exécutez-le.

Sortie:

-8

Quelle est la bonne réponse pour -4 * - (3 - 5) .

Partie 1: Tokenizing Input avec Lex

Il y a deux étapes que le code de l' exemple 1 effectués: l' un a été l'entrée de jetons, ce qui signifie qu'il a cherché symboles qui constituent l'expression arithmétique, et la seconde étape est l' analyse, qui consiste à analyser les jetons extraits et évaluer le résultat.

Cette section fournit un exemple simple de tokenize de saisie utilisateur, puis la décompose ligne par ligne.

    import ply.lex as lex

    # List of token names. This is always required
    tokens = [
       'NUMBER',
       'PLUS',
       'MINUS',
       'TIMES',
       'DIVIDE',
       'LPAREN',
       'RPAREN',
    ]

    # Regular expression rules for simple tokens
    t_PLUS    = r'\+'
    t_MINUS   = r'-'
    t_TIMES   = r'\*'
    t_DIVIDE  = r'/'
    t_LPAREN  = r'\('
    t_RPAREN  = r'\)'

    # A regular expression rule with some action code
    def t_NUMBER(t):
        r'\d+'
        t.value = int(t.value)    
        return t

    # Define a rule so we can track line numbers
    def t_newline(t):
        r'\n+'
        t.lexer.lineno += len(t.value)

    # A string containing ignored characters (spaces and tabs)
    t_ignore  = ' \t'

    # Error handling rule
    def t_error(t):
        print("Illegal character '%s'" % t.value[0])
        t.lexer.skip(1)

    # Build the lexer
    lexer = lex.lex()

    # Give the lexer some input
    lexer.input(data)

    # Tokenize
    while True:
        tok = lexer.token()
        if not tok: 
            break      # No more input
        print(tok)

Enregistrez ce fichier sous le nom calclex.py . Nous l'utiliserons lors de la construction de notre analyseur Yacc.

Panne

1. Importer le module en utilisant import ply.lex

2. Tous les lexers doivent fournir une liste appelée tokens qui définit tous les noms de jetons possibles pouvant être produits par le lexer. Cette liste est toujours requise.

    tokens = [
       'NUMBER',
       'PLUS',
       'MINUS',
       'TIMES',
       'DIVIDE',
       'LPAREN',
       'RPAREN',
    ]
   

tokens peuvent aussi être un tuple de chaînes (plutôt qu'une chaîne), où chaque chaîne indique un jeton comme auparavant.

3. La règle de regex pour chaque chaîne peut être définie comme une chaîne ou une fonction. Dans les deux cas, le nom de la variable doit être préfixé par t_ pour indiquer qu'il s'agit d'une règle pour les jetons correspondants.

   • Pour les jetons simples, l'expression régulière peut être spécifiée sous la forme de chaînes: t_PLUS = r'\+'

   • Si une action doit être exécutée, une règle de jeton peut être spécifiée en tant que fonction.

        def t_NUMBER(t):
            r'\d+'
            t.value = int(t.value)
            return t
     

     Notez que la règle est spécifiée comme une chaîne de caractères dans la fonction. La fonction accepte un argument qui est une instance de LexToken , effectue une action puis renvoie l'argument.

     Si vous souhaitez utiliser une chaîne externe comme règle d'expression régulière pour la fonction au lieu de spécifier une chaîne de document, prenez l'exemple suivant:

        @TOKEN(identifier)         # identifier is a string holding the regex
        def t_ID(t):
            ...      # actions
     

   • Une instance d'objet LexToken (appelons cet objet t ) a les attributs suivants:

     1. t.type qui est le type de jeton (sous forme de chaîne) (par exemple: 'NUMBER' , 'PLUS' , etc.). Par défaut, t.type est défini sur le nom suivant le préfixe t_ .
     2. t.value qui est le lexème (le texte réel correspondant)
     3. t.lineno qui est le numéro de ligne actuel (ce n'est pas automatiquement mis à jour, car le lexer ne sait rien des numéros de ligne). Mettez à jour lineno en utilisant une fonction appelée t_newline .

       def t_newline(t):
           r'\n+'
           t.lexer.lineno += len(t.value)
     

     4. t.lexpos qui est la position du jeton par rapport au début du texte saisi.

   • Si rien n'est renvoyé par une fonction de règle d'expression régulière, le jeton est ignoré. Si vous souhaitez ignorer un jeton, vous pouvez également ajouter le préfixe t_ignore_ à une variable de règle d'expression régulière au lieu de définir une fonction pour la même règle.

        def t_COMMENT(t):
            r'\#.*'
            pass
            # No return value. Token discarded
     

     ...Est le même que:

        t_ignore_COMMENT = r'\#.*'
     

     ^{Ceci est bien sûr invalide si vous effectuez une action lorsque vous voyez un commentaire. Dans ce cas, utilisez une fonction pour définir la règle regex.}

     Si vous n'avez pas défini de jeton pour certains caractères mais que vous souhaitez toujours l'ignorer, utilisez t_ignore = "<characters to ignore>" (ces préfixes sont nécessaires):

        t_ignore_COMMENT = r'\#.*'
        t_ignore  = ' \t'    # ignores spaces and tabs
     

   • Lors de la création de l'expression rationnelle principale, lex ajoutera les expressions régulières spécifiées dans le fichier comme suit:

     1. Les jetons définis par les fonctions sont ajoutés dans le même ordre qu'ils apparaissent dans le fichier.
     2. Les jetons définis par des chaînes sont ajoutés par ordre décroissant de la longueur de chaîne de la chaîne définissant l'expression régulière pour ce jeton.

     Si vous faites correspondre == et = dans le même fichier, profitez de ces règles.

   • Les littéraux sont des jetons renvoyés tels quels. t.type et t.value seront tous deux définis sur le caractère lui-même. Définir une liste de littéraux en tant que tels:

     literals = [ '+', '-', '*', '/' ]
     

     ou,

     literals = "+-*/"
     

     Il est possible d'écrire des fonctions de jeton qui effectuent des actions supplémentaires lorsque les littéraux sont mis en correspondance. Cependant, vous devrez définir le type de jeton de manière appropriée. Par exemple:

     literals = [ '{', '}' ]
     
     def t_lbrace(t):
         r'\{'
         t.type = '{'  # Set token type to the expected literal (ABSOLUTE MUST if this is a literal)
         return t
     

   • Gérer les erreurs avec la fonction t_error.

     # Error handling rule
     def t_error(t):
         print("Illegal character '%s'" % t.value[0])
         t.lexer.skip(1) # skip the illegal token (don't process it)
     

     En général, t.lexer.skip(n) ignore n caractères dans la chaîne d'entrée.

4. Préparations finales:

   Construisez le lexer en utilisant lexer = lex.lex() .

   Vous pouvez également tout mettre dans une classe et appeler une instance use de la classe pour définir le lexer. Par exemple:

    import ply.lex as lex  
    class MyLexer(object):            
          ...     # everything relating to token rules and error handling comes here as usual 
   
          # Build the lexer
          def build(self, **kwargs):
              self.lexer = lex.lex(module=self, **kwargs)
   
          def test(self, data):
              self.lexer.input(data)
              for token in self.lexer.token():
                  print(token)
   
          # Build the lexer and try it out
   
    m = MyLexer()
    m.build()           # Build the lexer
    m.test("3 + 4")     #
   

   Fournit une entrée à l'aide de lexer.input(data) où data est une chaîne

   Pour obtenir les jetons, utilisez lexer.token() qui renvoie les jetons correspondants. Vous pouvez itérer sur lexer en boucle comme dans:

   for i in lexer: 
       print(i)
   

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

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.