October 12, 2004 Project class
Contents
Opening Remarks / Overview
- 5 minutes on XML from MattC
- Theoretically everyone's been working on FSM/regexp stuff
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.]
- Lex/YACC in low-level C (vs something more abstracted like Python -- tradeoff between ease of coding vs level of control?)
- FSA simulators
- Mel -- uses nodes as a thing you would pass an input to, and would give you the next node
- MattC -- uses nodes as procedures
- JonT -- generalization to the max
- Katie -- uses a transition table with scheme-symbols rather than individual nodes
It would be cool to put up code snippets here and continue discussion, since it's a hard thing to talk about in abstract and in class.
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) (eval (append- '(cond) `(((null? ',expr) ',state)) (map (lambda (pair) `((eq? ',expr ,(car pair)) ',(cadr pair)) ) links) '((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
Output:
q0 q1 q1 q1 #t >
5 min on XML
- XML is strict, easily parsable
- Direct relationship with the grammars stuff we were talking about in class
- Separates data from presentation -- makes data processing really easily
- A simplification(?) of SGML
- Two ways to look at a document:
- DOM model (document-object model) of processing
- Gives you a lovely object hierarchy, easy to translate between text files and objects
- "Here's the tree: Now we manipulate it"
- Tradeoff: a bit behemothy
- SAX model
- a bit more complicated
- well-suited for streams
- event-driven: "If I see this tag, what should I do?"
- DOM model (document-object model) of processing
For Next Time
Interpreters: See ProjectAssignment3
- If you can't tear yourself away from the other things you've been working on, then continue being productive in that fashion.