;; C311 Programming Languages
;; Dana Vrajitoru
;; Functions to parse strings based on some grammar.

; 1     ; E => T TT
; 2|3   ; TT => AO T TT | e
; 4     ; T => F FT
; 5|6   ; FT => MO F FT | e
; 7|8|9 ; F => ( E ) | id | number
; 10|11 ; AO => + | 
; 12|13 : MO => * | /

(defun verif-expr (L)
  (let ((stack '(E)) (input L) (err nil) (active nil) (current nil))
    (while (and input stack (not err))
      (setq active (pop stack)   ; Pop a symbol from the stack and set it
            current (car input)) ; as the active symbol
                                 ; and set the current terminal as
                                 ; the first element of input
      (cond
       ((equal active 'E) ; E has only one rule
	(push 'TT stack)
	(push 'T stack))
       ((equal active 'TT) ; need to check the input token
	(cond ((or (equal current "+")
		   (equal current "-")) ; apply 2
	       (push 'TT stack) 
	       (push 'T stack)
	       (push 'AO stack))
	      (t t))) ; otherwise just delete TT based on 3 which means
		      ; that we don't add anything else to the stack
       ((equal active 'AO)
	(if (or (equal current "+")  ; if we find a + or -
		(equal current "-")) ; we push it on the stack
	    (push current stack)
	  (setq err t)))                 ; Otherwise it's an error
    ;; For the student:
    ;; Add more conditions here for the symbols T, F, FT, and MO
       ((equal active 'id)   ; We'll treat 'id and 'number as non-terminals
	(if (symbolp current) ; An 'id is a symbol
	    (pop input)
	  (setq err t)))
    ;; For the student:
    ;; Add a condition here for 'number using numberp
       ((equal active current) ; If we find anything else in the
	(pop input))               ; stack it must be a terminal
			           ; and it must match the input symbol
       (t (setq err t))))
    (if (or err input) ; If we find an error explicitly or
		       ; if we didn't finish the input string
	(progn (princ "Error at the character:")
	       (print current)
	       nil)
      (princ "String is correct\n")
      t)))

(verif-expr '(2 "+" a "*" "(" 5 "-" b ")" ))

; LL(1) parser for the following grammar:
; S => F
; S => ( S + F )
; F => 1
(defun verif (L)
  (let ((stack '(S)) (input L) (err nil) (active nil) (current nil))
    (while (and input stack (not err))
      (print stack)
      (setq active (pop stack)   ; Pop a symbol from the stack and set it 
	    current (car input)) ; as the active symbol
				 ; and set the current terminal as
				 ; the first element of input
      (cond 
       ((equal active 'S)   ; The top symbol is S
	(cond 
	 ((equal current "(" ) ; If we find a "(" we replace S on the
				   ; stack with the right-hand side of
				   ; the second rule in reverse order.
	  (push ")" stack) ; The next ones add the right-hand-side 
	  (push 'F stack)  ; of the rule
	  (push "+" stack)
	  (push 'S stack)
	  (push "(" stack))
	 ((equal current 1) ; If we find 1 we apply the first rule
	  (push 'F stack))
	 (t (setq err t))))
       ((equal active 'F)     ; The top symbol is F
	(if (equal current 1)  ; If we find 1 we replace F with 1
	    (push 1 stack)         ; based on the 3rd rule
	  (setq err t)))           ; Otherwise we report an error
       ((equal active current) ; If we find anything else in the
	(pop input))               ; stack it must be a terminal
	                           ; and it must match the input symbol
       (t (setq err t))))
    (if (or err input) ; If we find an error explicitly or 
		       ; if we didn't finish the input string
	(progn (princ "Error at the character:")
	       (print current)
	       nil)
      (princ "String is correct\n")
      t)))

(verif '( "(" 1 "+" 1 ")" ))

(S)

("(" S "+" F ")")

(S "+" F ")")

(F "+" F ")")

(1 "+" F ")")

("+" F ")")

(F ")")

(1 ")")

(")")
String is correct
t

(verif '( 1 + 1 )) ; 1 + 1 is not correct; this should be '( "(" 1 + 1  ")" )

(S)

(F)

(1)
Error at the character:
+
nil