[plt-scheme] Natural Language parsing in CS1

From: Prabhakar Ragde (plragde at uwaterloo.ca)
Date: Mon Jun 1 18:48:15 EDT 2009

Todd wrote:

> So I'd write the parser and such and let the kids just play with the grammars.

You're then going to have to implement a general CFG parser (with decent 
error messages for malformed input). You can parse the CFGs they write 
with parser-tools, but you can't expect them to write grammars that can 
be handled by parser-tools. So you need to implement an Earley parser, 
or a functional version of it (because you can't expect them to avoid 
left recursion, either). You also have to think about what happens if 
there are a huge number of parse trees generated for a highly ambiguous 

You might be better off doing something more traditionally considered 
declarative programming -- maybe working with Jay's Datalog package. --PR

Posted on the users mailing list.