Foro - Perl en Español

¡Excelente!

Aún no he leído mucho sobre Perl 6, pero voy a permitirme compartir otro ejemplo que había probado hace como un mes, y que me parece muy interesante.

Es bien sabido que el lenguaje formal { a^n b^n : n >=1 } = { ab, aabb, aaabbb, aaaabbbb, ... } es un lenguaje NO regular, o sea, que no existe una expresión regular que lo represente (esto se prueba utilizando un teorema llamado Lema de bombeo para lenguajes regulares). En términos de programación, esto equivale a que NO existe una expresión regular que coincida exclusivamente con las cadenas de este lenguaje (esto podría no ser cierto en el caso de Perl 5, pues la expresividad de las regexps de Perl 5 excede a la de las regexps concebidas como objeto matemático). Por ejemplo, la expresión regular

/a+b+/

ciertamente coincide con todas las cadenas de la forma a^n b^n pero además coincide con cadenas como "abbb" que no tienen la misma cantidad de letras "a" que de letras "b". Por eso en la teoría de lenguajes formales, existen las gramáticas formales, que extienden la potencia de las expresiones regulares. Una gramática G para el lenguaje anterior está dada por las reglas: S -> aSb | ab.

Perl 6 brinda soporte incluído en su núcleo para definir gramáticas

Y, como se puede ver en el siguiente ejemplo, la "traducción" a Perl 6 de la gramática anterior es casi inmediata:

explorer escribiste:Una expresión en Perl5 que es capaz de localizar esas cadenas:

¡Bien! Yo había intentado algo similar (también embebiendo código Perl dentro de la expresión regular). Por eso hice la aclaración:

pierrot escribiste:(esto podría no ser cierto en el caso de Perl 5, pues la expresividad de las regexps de Perl 5 excede a la de las regexps concebidas como objeto matemático).

Otra feature o característica de las regexps de Perl que no es precisamente regular, es el de las backreferences. Por ejemplo, el lenguaje { w w | w en { 0, 1 }* } es claramente NO regular, y sin embargo la regexp de Perl 5,

es capaz de "localizar" estas cadenas.

Sin embargo, en el caso de otros lenguajes no regulares que son igualmente simples, por ejemplo, {a^n b^m : n, m >= 1, m > n}, empiezan a notarse las limitaciones de las expresiones regulares. Si pensamos utilizar (??{...}) como en tu solución:


en este caso no sabemos exactamente cuántas letras 'b' van después de las 'a' (sabemos que son una cantidad mayor a la de las 'a', pero desconocemos el número exacto). Con una gramática sigue siendo natural:


La gramática formal para este lenguaje sería la dada por las reglas: S -> aSb | abB, B -> bB | b. Como sabemos que la regla de B genera cadenas de la forma b+, podemos (en Perl 6) escribir directamente S -> aSb | abb+ y ahorrarnos la definición de la regla para B. No he leído mucho sobre las gramáticas en Perl 6, pero son como unas gramáticas libres de contexto (o sea, solo una variable del lado izquierdo de las reglas) y del lado derecho se aceptan nombres de variables y ¡expresiones regulares en vez de terminales!

explorer escribiste:De momento, para Perl 5, la exp. reg. para el segundo lenguaje que has publicado, se puede resolver así (una posible forma):

Tienes razón; todavía se puede hacer medianamente simple. Escribí mi mensaje anterior justo antes de tomar un ómnibus y mientras subía se me ocurrió esta otra:

Es casi idéntica a la primera tuya añadiendo un b+ al final.

Cuando tenga tiempo, voy a pensar un lenguaje simple (así como éstos), para el que realmente sea muy complicado encontrar una expresión regular en Perl 5 y que en cambio, con gramáticas sea muy fácil generarlo (sin considerar ejemplos complejos, como por ejemplo, que sus cadenas sean texto HTML o un programa válido dada la especificación EBNF de un lenguaje de programación, en que resulta evidente que son necesarias gramáticas más que expresiones regulares).

Peteris Krumins, el autor de Perl One-Liners: 130 Programs That Get Things Done, en su blog tiene una entrada sobre expresiones regulares "recursivas", donde aporta otra expresión regular posible para {a^n b^n : n>=1}: