Representacion gramaticas

Esta representación también es recursiva, pero es más poderosa que la representación inductiva ya que podemos manejar diferentes casos. Vamos a utilizar gramáticas regulares por la izquierda.

<lista> ::= <empty>
        ::= <int> <lista>

'()
'(1)
'(1 2 3)

<arbol> ::= <int>
        ::= <symbol> <arbol> <arbol>

4
'(k 3 (p 2 (f 1 2)))

<arbol-t> ::= <int>
          ::= <symbol><arbol-t> <arbol-t> <arbol-t>

7
'(k 1 2 3)
'(k (k 2 3 4) 4 (s (t 1 3 2) 2 3))

#lang eopl
#|
<arbol-t> ::= <int>
          ::= <symbol><arbol-t> <arbol-t> <arbol-t>

|#
(define arbol1 2)
(define arbol2 '(k 1 2 3))
(define arbol3 '(k (k 2 3 4) 4 (s (t 1 3 2) 2 3)))
(define ovejamala  '(2 (k 2 3 4) 4 (s (t 1 3 2) 2 3)))
;;in-A? arbol -> booleano
(define in-A?
  (lambda (arb)
    (cond
      [(number? arb)]
      [(and
        (symbol? (car arb))
        (in-A? (cadr arb))
        (in-A? (caddr arb))
        (in-A? (cadddr arb))
        )]
      [else #F])))