Dependent parsing combinators - Githubissues

ptal / oak

A typed parser generator embedded in Rust code for Parsing Expression Grammars

Apache License 2.0

142 stars 14 forks source link

Dependent parsing combinators #72

Open ptal opened 8 years ago

ptal commented 8 years ago

Dependent parsing allows semantic attribute to control the parsing. For example a new combinator #e expects a synthesized argument of type integer and repeat e exactly this number of times.

ptal commented 8 years ago

Here a non-exhaustive list of combinators that should be present for dependent-parsing:

Cardinality combinator: #e, expects integer as parameter. Use case: binary protocol, unknown field size.
Equality combinator: =e, expects parameter and the result of e to be of comparable type. Succeeds if they are equals. Use case: html/xml tags.
Constraint combinator: express constraint on the parsing such as bounds on integer ranges.

See papers:

Jim, Mandelbaum, and Walker, “Semantics and Algorithms for Data-Dependent Grammars.”
Atkey, “The Semantics of Parsing with Semantic Actions.”
Thielecke, “Functional Semantics of Parsing Actions, and Left Recursion Elimination as Continuation Passing.”
Jim and Mandelbaum, “A New Method for Dependent Parsing.”