Write a Blog >>
PEPM 2017
Mon 16 - Tue 17 January 2017
co-located with POPL 2017
Mon 16 Jan 2017 11:30 - 12:00 at Salle 109, Barre 44-54 - Programming languages Chair(s): Andrew Farmer

Tabular top-down parsing and its lazy variant, Packrat, are linear-time execution models for the TDPL family of recursive descent parsers with limited backtracking. Exponential work due to backtracking is avoided by tabulating the result of each (nonterminal, offset)-pair at the expense of always using space proportional to the product of the input length and grammar size. Current methods for limiting the space usage relies either on manual annotations or on static analyses which are sensitive to the syntactic structure of the grammar.

We present progressive tabular parsing (PTP), a new execution model which progressively computes parse tables for longer prefixes of the input and simultaneously generates a leftmost expansion of the parts of the parse tree that can be resolved. Table columns can be discarded on-the-fly as the expansion progresses through the input string, providing best-case constant and worst-case linear memory use. Furthermore, semantic actions are scheduled before the parser has seen the end of the input. The scheduling is conservative in the sense that no action has to be ``undone'' in the case of backtracking.

The time complexity is O(dmn) where m is the size of the parser specification, n is the size of the input string, and d is either a configured constant or the maximum parser stack depth.

For common data exchange formats such as JSON, we demonstrate practically constant space usage.

Mon 16 Jan

Displayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

10:30 - 12:00
Programming languagesPEPM 2017 at Salle 109, Barre 44-54
Chair(s): Andrew Farmer Facebook
10:30
30m
Talk
Lightweight Soundness for Towers of Language Extensions
PEPM 2017
Alejandro Serrano Utrecht University, Jurriaan Hage Utrecht University
11:00
30m
Talk
Detecting code clones with gaps by function applications
PEPM 2017
Tsubasa Matsushita Shibaura Institute of Technology, Isao Sasano Shibaura Institute of Technology
11:30
30m
Talk
PEG Parsing in Less Space Using Progressive Tabling and Dynamic AnalysisBest Paper
PEPM 2017
Fritz Henglein DIKU, Denmark, Ulrik Terp Rasmussen DIKU, University of Copenhagen