parser para fórmulas de lógica proposicional (o una somera introducción a pyparsing)

La semana pasada empecé a cursar, de oyente, dos materias en Exactas: Lógica y Computabilidad y Teoría de Lenguajes. En la primera, empezamos a estudiar algunos conceptos de cálculo proposicional. Al final de la clase, el profesor sugirió escribir un pequeño parser que reconozca fórmulas de lógica proposicional. Dado que venía con ganas de entender mejor pyparsing, me pareció que podía ser una buena forma de empezar.

Primero, la teoría. Dado el alfabeto $latex A$, $latex A^*$ es el conjunto de palabras que pueden formarse combinando sus elementos.
$latex A=\{ \to , \wedge , \vee , \neg , ( , ) , p , \prime \}$
Existe un tipo particular de palabras, a las que llamamos variables.
$latex Var=\{p , p\prime, p\prime\prime , \ldots \}$
Es un conjunto infinito y, dado que puede ser tedioso contar la cantidad de primas, las variables pueden ser referenciadas como $latex p_n$, donde n es la cantidad de primas. Así, parece razonable pensar que no todas las palabras son válidas a la hora de escribir una fórmula (que es como llamaremos a las palabras válidas).

Ejemplos de fórmulas:

  • $latex p_2$
  • $latex ( ( p_3 \wedge p_5 ) \to ( \neg p_2 \vee p_5 ) )$
  • $latex \neg \neg ( p\prime \vee p_{1232} )$

Ejemplos de no-fórmulas (palabras que no forman una fórmula):

  • $latex \neg\prime$
  • $latex ( p_2 )$
  • $latex p_3 \vee \wedge $

Si bien es más o menos intuitivo qué es una fórmula y qué no, es necesario definirlo en un sentido formal. Así $latex Form \subset A^* $ y es el conjunto de las palabras que cumplen:

  1. si $latex \alpha \in A^*$ y $latex \alpha \in Var$, entonces $latex \alpha \in Form$
  2. si $latex \alpha \in Form$, entonces $latex \neg \alpha \in Form$
  3. si $latex \alpha,\beta \in Form$, entonces $latex ( \alpha \circledast \beta)\in Form$. Donde $latex \circledast=\vee,\wedge,\to $

Nada más es una fórmula.

Ahora, a la práctica. Queremos escribir un parser que, dada una palabra, reconozca si es una fórmula. Y para esto vamos a jugar con el módulo pyparsing, para python.

Lo primero es definir el conjunto de variables.

>>> from pyparsing import Word
>>> variable=Word('Pp',"0123456789'")
>>> variable.parseString('p1')
(['p1'], {})
>>> variable.parseString("P'")
(["P'"], {})

Así, variable reconoce los posibles nombres de variables. Toda expresión que sea parseable por variable, es una formula. Para el punto ii. hay que definir una estructura recursiva. Utilizaremos el bang (!) para la negación.
from pyparsing import Forward
formula=Forward()
ii='!' + formula

Caso similar en el punto iii.. Para esto hay que definir los operadores, que son and (&), or (|) y then (<).

operador=Word('&|>',max=1)
iii='('+formula+operador+formula+')'

Por último, definimos una fórmula cómo una variable (i.) o una negación de una fórmula (ii.) o una operación entre fórmulas (iii.).

formula << ( variable | ii | iii )

Y esto es, básicamente, nuestro parser:

>>> formula.parseString("(p1 | p4)")
(['(', 'p1', '|', 'p4', ')'], {})

Lo dicho, con un poco más de contexto y en un único archivo, a continuación:

1 thought on “parser para fórmulas de lógica proposicional (o una somera introducción a pyparsing)”

  1. Una vez empecé a hacer un probador automático de teoremas de lógica de predicados de primer grado. No funcionó, pero la parte del parser usando PLY quedó perfecta: (buscando el link...) oh! ni siquiera está on line. Voy a postear esa parte en el blog, cuando lo tenga on line vuelvo por aca y dejo el link. Espero acordarme de hacerlo el fin de semana.

Comments are closed.