;; ** PCS-2046 - Logica Computacional **
;; Prof. Ricardo Luis de Azevedo da Rocha
;;
;; ** Coop 7 **
;; Adriana Haseyama - NUSP 3455942
;; Kenzo Okamura - NUSP 2937134
;;
;; ** Primeiro Exercicio-Programa - EP 1 **
;; = Item 1 =
;; Construa uma funcao em Scheme que permita percorrer
;; um conjunto recursivamente (recebido em uma lista) e,
;; a cada recurso, retorne um dos elementos do conjunto.

(define recursiva
  (lambda (lista)
    (begin
      (when (> (length lista) 0)
	  (display (car lista))
	  (newline)
	  (recursiva (cdr lista))
;	  (car lista)
	  ))))

;; Teste:
;;(recursiva (list 1 2 3 4 5 10 9 8 7 6))

;; = Item 2 =
;; Construa uma funcao em Scheme que permita a geracao de cadeias
;; (incluindo formas sentenciais e sentencas) em ordem de tamanho. A
;; sua funcao deve receber as regras de uma gramatica de estrutura de
;; frase, recursiva, e deve solicitar um valor de tamanho para as
;; cadeias.
;; A partir destes dados a sua funcao devera gerar todas as cadeias
;; cujos tamanhos sejam menores ou iguais ao valor recebido.
;; (use a funcao do item anterior como apoio)

;; Gramatica G=(V, T, P, S)
;; V = Lista de simbolos nao terminais
;; T = Lista de simbolos terminais
;; P = Lista de pares indicando regra de producao
;; S = Variavel inicial

(define V
  (list "S" "B"))
(define T
  (list "a" "b"))
(define P
  (list
   (cons "S" "aS")
   (cons "S" "B")
   (cons "B" "bB")
   (cons "B" "")))

(require (lib "list.ss"))

(define gera-cadeias
  (lambda (V T P S tamanho)
    (let ((regras (ordena-regra-decrescente P))
	  (nova-cadeia "") (lista-saida '()))
      
      (let iterator ((i 0))
	(when (and
	       (< i (length regras))
	       (<= (tamanho-cadeia-terminais S V) tamanho))
	  (begin
	    (let* ((regra (list-ref regras i))
		   (esquerda-regra (car regra))
		   (direita-regra (cdr regra)))
	      
	      (begin
		(when (regexp-match esquerda-regra S)
		  
		  (begin
		    (set! nova-cadeia
		     (regexp-replace
		      esquerda-regra
		      S
		      direita-regra))
		    
		    ;(debug-transformacao
		    ; S
		    ; esquerda-regra
		    ; direita-regra
		    ; nova-cadeia)
		    
		    (if (contem-nao-terminais? nova-cadeia V)
			(set! lista-saida
			      (append lista-saida
				      (gera-cadeias
				       V T regras nova-cadeia tamanho)))
			(begin
			  ;(display
			  ; (string-append
			  ;  "*** FINAL: "
			  ;  nova-cadeia
			  ;  " ***"))
			  
			  (set! lista-saida
				(append lista-saida
					(list nova-cadeia)))
			  ;(display lista-saida)
			  ))
		    ))))
	    
	    (iterator (+ i 1))
	    
	    )))
      (sort lista-saida compara-tamanho-cadeia)
      )))

(define tamanho-cadeia-terminais
  (lambda (cadeia lista-nao-terminais)
    (let iterator ((i 0))
      (when (< i (length lista-nao-terminais))
	(set! cadeia
	      (regexp-replace*
	       (list-ref lista-nao-terminais i) cadeia ""))
	(iterator (+ i 1))))
    (string-length cadeia)))

(define compara-tamanho
  (lambda (arg1 arg2)
    (if (> (string-length (car arg1)) (string-length (car arg2)))
	#t
	#f)))

(define compara-tamanho-cadeia
  (lambda (arg1 arg2)
    (if (> (string-length arg1) (string-length arg2))
	#f
	(begin
	  (if (= (string-length arg1) (string-length arg2))
	      (begin
		(if (string>? arg1 arg2)
		    #f
		    #t))
	      #t)))))

(define ordena-regra-decrescente
  (lambda (lista)
    (sort lista compara-tamanho)))

(define contem-nao-terminais?
  (lambda (cadeia lista-nao-terminais)
    (let ((encontrado #f))
      (let iterator ((i 0))
	(when (< i (length lista-nao-terminais))
	  (when (not encontrado)
	    (if (regexp-match (list-ref lista-nao-terminais i) cadeia)
		(begin
		  (set! encontrado #t)
		  (set! iterator (length lista-nao-terminais)))
		(iterator (+ i 1)))))
	encontrado
	))))

(define debug-transformacao
  (lambda (antes esquerda direita depois)
    (display
     (string-append
      "[" antes " (" esquerda " -> " direita " == " depois ")]"))
    (newline)))


;; Item 3
;; Construa um sistema em Scheme que implemente o algoritmo de
;; reconhecimento de cadeias a partir de uma determinada gramatica.
;; O seu sistema devera utilizar a funcao desenvolvida no item anterior.

(define reconhece-cadeia
  (lambda (cadeia V T P S tamanho)
    (let ((encontrado #f)
	  (cadeias-validas (gera-cadeias V T P S tamanho)))
      (let iterator ((i 0))
	(when (< i (length cadeias-validas))
	  (when (string=? cadeia (list-ref cadeias-validas i))
	    (set! encontrado #t)
	    (set! i (length cadeias-validas)))
	    
	  (iterator (+ i 1))
	  encontrado)))))