August 21, 2024
P96 - Syntax checker (alternative solution with difference lists)
In a certain programming language (Ada) identifiers are defined by the syntax diagram (railroad chart) opposite. Transform the syntax diagram into a system of syntax diagrams which do not contain loops; i.e. which are purely recursive.
Using these modified diagrams, write a function (identifier str) that can check whether or not a given string s is a legal identifier.* (identifier str) returns t when str is a legal identifier.
lisp
;;; Grammar used:
;;;
;;; id --> letter, rest
;;;
;;; rest --> ""
;;; rest --> dash, char, rest
;;;
;;; dash --> ""
;;; dash --> "-"
;;;
;;; char --> letter
;;; char --> digit
;;;
;;; 'letter' and 'digit' nonterminals are implemented by
;;; Lisp predicates alpha-char-p and digit-char-p, respectively.
(defun identifier (str)
(id str ())
)
(defun id (str stack)
"True when STR has a prefix that is an identifier and the rest
of STR can be parsewd sucessfully with the predicates in STACK."
(check str (cons #'letra (cons #'resto stack)))
)
(defun check (str stack)
(if (null stack)
(string= str "")
(funcall (car stack) str (cdr stack))
)
)
(defun letra (str stack)
(and
(> (length str) 0)
(alpha-char-p (elt str 0))
(check (subseq str 1) stack)
)
)
(defun digito (str stack)
(and
(> (length str) 0)
(digit-char-p (elt str 0))
(check (subseq str 1) stack)
)
)
(defun resto (str stack)
(or
(check str stack)
(check str (cons #'traco (cons #'carac (cons #'resto stack))))
)
)
(defun traco (str stack)
(or
(check str stack)
(and
(> (length str) 0)
(string= (elt str 0) "-")
(check (subseq str 1) stack)
)
)
)
(defun carac (str stack)
(or
(letra str stack)
(digito str stack)
)
)
Be first to comment