[FrontPage] [TitleIndex] [WordIndex

October 12, 2004 Project class

Opening Remarks / Overview

  1. 5 minutes on XML from MattC
  2. Theoretically everyone's been working on FSM/regexp stuff
  3. Lynn hopes to add to the list of stuff people are looking at -- parsers -- play with one. See SICP(wizard book) ch 4, Lex/YACC, and the internet(s). Parsers are awesome.

Things people are working on

[NB: Lynn wants a paragraph every week updating her on what you're up to -- she doesn't need to see every line of code you ever write, but if you want her to run something send everything necessary for the running of the thing.]

Matt C's code:

;Example of how to use the FSM simulator
(define q0 (create-state '(('a q1))))
(define q1 (create-final-state '(('a q0) ('b q1))))

;Alias to the general function
(define create-final-state
  (lambda (links)
    (create-state-general links 'final)
;Alias to the general function
(define create-state
  (lambda (links)
    (create-state-general links 'not-final)
;General function to create states
(define create-state-general
  (lambda (links state)
    (lambda (expr)
          `(((null? ',expr) ',state))
          (map (lambda (pair)
               `((eq? ',expr ,(car pair)) ',(cadr pair))
          '((else #f))
;Function that tail-recurses through a given FSM
(define simulate-fsm-
  (lambda (initial parameters)
    (let ((result (if (pair? parameters)
                    ((eval initial) (car parameters))
                    ((eval initial) '())
      (cond ((eq? result #f) #f)
            ((null? parameters)
              (cond ((eq? 'final result) #t)
                    (else #f)
            (else (simulate-fsm result (cdr parameters)))

Katie's code mostly at NotesOctober12Proj/KatieCode; an example run is here:

;; this tests an fsm which accepts the regular expression (a* U b*)
(run-fsm (make-fsm (list 'q0 'q1 'q2) ; states
                   (list 'a 'b) ;alphabet
                   (delta-add 'q0 'a 'q1 
                              (delta-add 'q0 'b 'q2 
                                         (delta-add 'q1 'a 'q1 
                                                    (delta-add 'q2 'b 'q2 
                                                               (make-empty-delta))))) ;delta
                   (list 'q0) ; start-state
                   (list 'q0 'q1 'q2)) ; accept-states
         (list 'a 'a 'a)) ;; input string



5 min on XML

For Next Time

  1. Interpreters: See ProjectAssignment3

  2. If you can't tear yourself away from the other things you've been working on, then continue being productive in that fashion.

2013-07-17 10:43