On Aug 9, 2010, at 2:46 PM, Bernhard Damberger wrote: > I was wondering if there are any "table driven" PEG/packrat based parsers. > In looking at the url > > http://en.wikipedia.org/wiki/Comparison_of_parser_generators#Parsing_Expression_Grammars > I see that there are four implementation styles for a PEG parser: > Packrat, Recursive Descent, Parsing Machine and PEG parser interpreter. > As far as I know, all the Packrat and Recursive Descent varieties generate > code. If I am wrong please correct me. > Parsing Machine seems to generate a byte code for a PEG virtual machine. > http://www.inf.puc-rio.br/~roberto/docs/ry08-4.pdf. > The PEG parser interpreter seems to just interpret the PEG directly via a > set of recursive functions. > http://fdik.org/pyPEG/ > > Can one create a table driven PEG/packrat parser? What would such a program > look like? Does this question even make sense? > > One reason I am asking this question is that I was wondering how to use PEGs > in > a dynamic context. If you read in a grammar and generate a table, you now have > a data driven process which can be used at runtime. Is there someway to use > PEGs > in a dynamic context, w/o having to generate code? (The Lua PEG virtual > machine > and the pyPeg mentioned above seem to be two approaches to this problem.)
I am no parser guru, but I do not think it is possible to have a purely table-based PEG parser. As I understand it, table-based parsing works because each symbol restricts the possible parses, thus the number of possible states decreases as you read more input until it homes in on the right parse. The process depends on a restricted amount of look-ahead so that you can have a reasonable number of possible states. But PEG parsing relies on arbitrary look-ahead and recursion. A simple table cannot handle the combinatorial explosion. I suppose you could create a series of linked tables, each parsing a restricted domain of possible inputs, and have them call on other tables when their remit is exceeded. But that last step of calling out to other tables seems equivalent to calling a sub-function in a recursive-descent-ish way. (I have added my Dylan Peg-parser library to that Wikipedia page. It is an PEG parser interpreter, if I understand your explanation of the term, but I think it is a third approach from the Lua and Python parsers you mention. The Peg-parser library is more like a DSL that calls out to specific library functions that implement PEG behavior. It works in a dynamic context without a code generation step. <http://wiki.opendylan.org/wiki/view.dsp?title=PEG%20Parser%20Library>) _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
