[plt-scheme] Natural Language parsing in CS1

Have you looked at the book David Evans (Virginia) has been writing?

http://www.cs.virginia.edu/~evans/ctbook/

Your goal sounds similar to part of his.


On 1-Jun-09, at 6:14 AM, Todd O'Bryan wrote:

> I'm starting to think about my courses for next year, and one thing
> that I really want to do with my intro classes is introduce topics
> that require the same kinds of thinking as programming, but feel
> different enough that students will see them as something different.
>
> For example, I think I'm going to do a short unit on finite state
> automata and regular expressions (and I'll use something like the
> macros Shriram presents in his "The Swine Before Perl" talk
> http://www.cs.brown.edu/~sk/Publications/Talks/SwineBeforePerl/ ).
>
> I also thought I could do a short unit on parsing, in order to
> introduce the idea of context-free grammars. What I'd like to do is
> create a teachpack that would take code like this:
>
> (define-grammar G
>  ((S -> NP VP)
>   (NP -> "Bob")
>   (VP -> "ate")))
>
> and then
>
> (parse G S "Bob ate")
>
> would produce a parse tree
>
> (S (NP ("Bob"))
>    (VP ("ate")))
>
> and ideally, I could write a function that would display this as text
> (this looks good in monospace):
>
>      S
> +----+----+
> NP        VP
> |         |
> "Bob"    "ate"
>
> and maybe even display the tree graphically.
>
> Eventually, I'd like to do some kind of features:
>
> (define-grammar G
>  ((S -> NP[number: X] VP[number: X])
>   (NP[number: sing] -> "he")
>   (NP[number: plur] -> "they")
>   (VP[number: sing] -> "sleeps")
>   (VP[number: plur] -> "sleep")))
>
> So that "He sleeps" and "They sleep" parse, but *"They sleeps" and
> *"He sleep" don't.
>
> So, the question...
>
> Where do I start? I can write a parser that produces a list of all
> possible parses given a grammar and a list of terminals, but I'm not
> sure how to approach this in Scheme. After the recent comment that OO
> doesn't scale down, I'm wondering if Grammar and Tree are worth my
> first attempt at classes in Scheme. I think I should probably use
> strings for the terminals, but should I use symbols for the symbols of
> the grammar or is there something built in that would handle
> attribute-value pairs nicely if I get that far?
>
> Any suggestions appreciated. I'll try to publish back what I come up
> with, along with whatever assignments I come up with.
>
> Thanks,
> Todd
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>