Hi all. Just a quick note. I can't think of a parsing strategy that couldn't be implemented as both a table driven machine and as a bit of generated code. I know of "recursive ascent" LR parsers as well as LALR machines generated in x86 machine code. Instead of using a pointer, it uses the machine program counter.
The choice of using table driven or generating code comes down to two key issues: size of generated parsers and how easy it is to understand the generated parser. Naturally, top-down strategies are easier to read when generated as source code. Ter PS ANTLR memoize is partial results; as far as I understand packrat parsing, that qualifies it. ANTLR starts at LL(1) and gradually scales up to k>1 them to arbitrary regular lookahead and then to syntactic predicates, which amount to PEG-based parsing. With memoization, it's linear. 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? > > I know Terrance Parr wrote in his "ANTLRWorks" draft paper: > >> ANTLR provides the power of a PEG with the semantic action flexibility and low >> overhead of a traditional LL-based parser. ANTLR not only supports manual >> backtracking via syntactic predicates, but supports an automatic backtracking >> option that tells ANTLR to backtrack at runtime if LL(*) static analysis >> fails. > > However, ANTLR generates code (aside from it not strictly being a Packrat > parser). > Perhaps there is no reason why it could not be made to generate a table and > support code. > > I am also aware of the paper by Roman R. Redziejowski titled > "Applying Classical Concepts to Parsing Expression Grammar", which seems to > attempt to define the FIRST and FOLLOW sets for PEGs. (Caveat, as I have not > read this paper yet.) > > So, are there any "table driven" PEG based parsers? > > 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.) > > Thanks for your time. > > _bernhard > > > > _______________________________________________ > PEG mailing list > PEG@lists.csail.mit.edu > https://lists.csail.mit.edu/mailman/listinfo/peg _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
