En prolog una secuencia de caracteres como "ab+c" corresponde a una lista de números que representan la codificación en ASCII de las letras a, b, + y c. Por lo tanto "ab+c" y [97, 98, 43, 99] son lo mismo.

Una expresión regular r puede ser:

• Cualquier caracter que no sea alguno de los siguientes 3 caracteres: +, ( o ). Ejemplos: "a", "b", "1", "2".
• La concatenación de dos expresiones regulares. Ejemplos: "ab", "a1", "21c".
• La alternancia de dos expresiones regulares. Ejemplos: "a+b", "1+a", "abc+3".
• Una expresión regular entre paréntesis. Ejemplo: "(a+b)".

La concatenación tiene mayor precedencia que la alternancia y por lo tanto "abc+3" equivale a "(abc)+3".

El predicado match-regexp(S, RE) es verdadero cuando la secuencia de caracteres S calza con la expresión regular RE. Este predicado debe verificar las siguientes consultas:

?- match-regexp("a", "a"), not(match-regexp("ab")),
   match-regexp("ab", "ab"), not(match-regexp("ac", "ab")),
     not(match-regexp("cb", "ab")),
   match-regexp("a", "a+b"), match-regexp("b", "a+b"),
     not(match-regexp("c", "a+b")),
   match-regexp("a", "(a)"), match-regexp("ab", "a(b+c)"),
     match-regexp("ab", "(a+c)b"), match-regexp("ab","(a+c)(d+b)"),
     not(match-regexp("ab", "(b+c)(d+b)")), not(match-regexp("ab","(a+b)bc")),
   match-regexp("abc", "(a+b+c)(a+b+c)(a+b+c)"),
     not(match-regexp("abc", "(a+b+c)(a+b+c)(b+d)")).
   Yes
?- between(1,3,X), length(L, X),
     match-regexp(L, "a(b+c+bc+aaa)"), writef("%s",[L]).
   ab

   X = 2
   L = [97, 98] ;
   ac

   X = 2
   L = [97, 99] ;
   abc

   X = 3
   L = [97, 98, 99] ;

   No

Requerimientos

• Programe un predicado parse(RE, T) que determina si T es el árbol de sintaxis abstracta de RE. Por ejemplo:
  

  parse("a(bcd+e)",
        and(atom(97), or(and(and(atom(98), atom(99)), atom(100)), atom(101))) ).
  

  En donde 97, 98, 99, etc. es la codificación ascii de a, b, c, etc.
• Programe match-tree(S, T) que determina si la secuencia de caracteres S calza con la expresión regular representada por el árbol de sintaxis abstracta T.
• Programe match-regexp(S, RE) en términos de parse y match-tree.

Para aprobar el curso y obtener un 6.0 en esta tarea, su tarea debe verificar obligatoriamente la primera de las consultas que aparece más arriba. Los que verifiquen además la segunda consulta obtendrán nota 7.0.

Plazo de entrega