Receta Python 3 No. 2-19: Escribir un Parser Recursivo

1. Problema

Parsear un texto conforme a unas reglas gramaticales.

2. Solución

Las reglas de la gramática para parsear el texto se especifican en BNF o EBNF.

Para el caso de expresiones aritméticas se puede tener una gramática como esta:

Figura 1. Gramática parser.

3. Código Python 3

Para este ejemplo se usa la versión original del parser creado por Beazly y Jones (2013):

Archivo Python parser.py  [enlace alternativo]:

La clase ExpressionEvaluator (líneas 32-103) se encarga de crear el parser. Se apoya en el método generate_tokens() (líneas 24-29), el cual particiona o genera los tokens de la expresión dada. La invocación de este método se realiza por medio del método parse() (líneas 41-46).

Continuando, otros métodos sobresalientes son:

• expr() (líneas 67-78): aplica la regla de expresiones de la aritmética; en este caso la suma y la resta.
• term() (líneas 80-91): se encarga de reconocer los términos de la expresión.
• factor() (líneas 93-103): reconoce las expresiones como números (literales) o expresiones encerradas entre paréntesis.

Prueba de ejecución:

2
5
14
37
('+', 2, 3)
('+', 2, ('*', 3, 4))
('+', 2, ('*', ('+', 3, 4), 5))
('+', ('+', 2, 3), 4)

4. Literatura & Enlaces

Beazly D, Jones B. K. (2013). Python Cookbook, Third Edition. United States: O'Reilly Media.

O