Source

lisp-random / dfa.lisp

Robert Smith 0e5efd8 



Robert Smith 8aa7158 
Robert Smith 0e5efd8 












Robert Smith 8aa7158 




Robert Smith 0e5efd8 
Robert Smith 8aa7158 

Robert Smith 0e5efd8 
Robert Smith 8aa7158 
Robert Smith 0e5efd8 
Robert Smith 8aa7158 





Robert Smith 0e5efd8 
Robert Smith 8aa7158 






Robert Smith 0e5efd8 
Robert Smith 8aa7158 



Robert Smith 0e5efd8 
Robert Smith 8aa7158 


Robert Smith 0e5efd8 
Robert Smith 8aa7158 







;;;; dfa.lisp
;;;; Copyright (c) 2013 Robert Smith


;;;; Special edges and utilities

(defconstant nul (code-char 0)
  "No transition.")

(defconstant eps (code-char 1)
  "Epsilon transition.")

(defun nul? (char)
  (char= char nul))

(defun eps? (char)
  (char= char eps))

(defun array-from-list (list-rep)
  (let ((rows (length list-rep))
        (cols (length (first list-rep))))
    (make-array (list rows cols)
                :initial-contents list-rep)))

(defun explode (string)
  (coerce string 'list))

;;;; DFA Representation

(defstruct dfa
  state-count
  alphabet
  start-state
  accepting-states
  transition-table)

(defun dfa-of-transition-table (table accepting-states)
  (make-dfa
   :state-count (length (rest table))
   :alphabet (coerce (first table) 'vector)
   :start-state 0                       ; Do we want this as the DEFAULT?
   :accepting-states accepting-states
   :transition-table (array-from-list (rest table))))

(defun transition (dfa from-state edge)
  (let ((idx (position edge (dfa-alphabet dfa))))
    (and idx
         (aref (dfa-transition-table dfa) from-state idx))))

(defun accepting-state-p (dfa state)
  (and (find state (dfa-accepting-states dfa))
       t))

(defun match-string (dfa string)
  (labels ((step (state chars)
             (cond
               ((null state) nil)
               ((null chars) (accepting-state-p dfa state))
               (t (step (transition dfa state (car chars))
                        (cdr chars))))))
    (step (dfa-start-state dfa)
          (explode string))))
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.