# Proposal: Grammar Working Group **URL:** \ **Category:** compiler\ **Created:** [September 21, 2018, 2:34am UTC](https://internals.rust-lang.org/t/proposal-grammar-working-group/8442 "2018-09-21T02:34:55Z")\ **Posts on this page:** 1\ **Showing post:** 46
**Author:** ![eternaleye](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/eternaleye/32/3505_2.png) [@eternaleye](https://internals.rust-lang.org/u/eternaleye)\ **Post date:** [November 29, 2018, 10:37pm UTC](https://internals.rust-lang.org/t/proposal-grammar-working-group/8442/46 "2018-11-29T22:37:47Z")
First, regarding how GLL deals with left recursion - the answer is "quite nicely, thank you", but the actual mechanism ties back into the memoization. Essentially, _before_ attempting to match a rule, a _pre-memoziation_ is recorded for the rule. If the rule then attempts to invoke itself at the same position, the pre-memoization is promoted to a _full_ memoization of a _cyclic_ result, which then appears in the SPPF. The same technique can be seen (...modulo some excessively dense notation...) in Pierre Boullier's [paper](http://users.sussex.ac.uk/~johnca/iwpt2000/boullier-iwpt2000.ps.gz) (PS.GZ) that first introduced the Range Concatenation Grammars. [The paper @eddyb referred to](https://aclanthology.org/P01-1007.pdf) (PDF) is an instance of a general technique called "Guided Parsing", where one uses a simplified approximation of a grammar to guide parsing with the full grammar. Some background - I presume you're familiar with the most-discussed levels of the Chomsky hierarchy, namely the regular languages, the context-free languages, and the context-sensitive languages. In between context-free and context-sensitive, there are a number of _intermediate_ classes of grammars - some fascinating ones include the conjunctive grammars, the boolean grammars, linear context-free rewriting systems, positive range concatenation grammars, and "full" range concatenation grammars. To explain these, I'll first introduce an alternate _syntax_ for CFG, and then explain the rest in terms of that. In classic BNF, you have `rule := subrule other_subrule`. This can be seen as a form of logic program, but the arguments are _implicit_. These can be made _explicit_, resulting in `rule(segment1 segment2) := subrule(segment1), other_subrule(segment2)` - this takes a single argument (which is pattern-matched into two variables covering disjoint ranges), and delegates to subrules. Disjunctions are represented, as in BNF, by the existence of multiple rules with the same name. The syntactic restrictions necessary to permit _only_ CFGs are: 1. Rules take only a single argument 2. Every variable in the head of the rule must occur exactly once in the body of the rule The conjunctive grammars (usually defined as "CFG with conjunction") may be defined as the _relaxation_ of rule 2, to allow variables to be used multiple times. LCFRS may be defined as the relaxation of rule 1, to allow rules of higher arity, though that arity must be the same for all rules that share a name. Positive range concatenation grammars (PRCGs), then, apply _both_ of these relaxations, plus an additional extension: the ability to _concatenate_ variables _so long as_ the head pattern-matched them from adjacent segments of input. The addition of negation, then, affords one the "full" range concatenation grammars. An alternate name for LCFRS, used mostly when they are expressed in this syntax (which is, in fact, RCG syntax) is "Simple RCG" or "SRCG". In addition, a _k_-RCG is an RCG whose predicates have at most arity _k_. One can then define the other grammars as various trivial cases of RCG: - CFG is 1-SPRCG - conjunctive grammars are 1-PRCG - boolean grammars are 1-RCG - LCFRS are SPRCG - etc. (As an interesting aside, CFG can be characterized as "regular languages plus least fixpoints" in a [formal sense](https://www.cs.ru.nl/bachelors-theses/2018/Bart_Gruppen ___4465784___ From_mu-regular_expressions_to_CFGs_and_back.pdf) (PDF)) This use of a common syntax makes the _primary_ contribution of the paper much more tractable - a sound and complete _algorithm_ for generating a 1-PRCG approximation (which accepts a superset of the original language) from an arbitrary PRCG. From there, a 1-SPRCG approximation is relatively trivial (dropping all but one side of each conjunction), and existing techniques can even take you all the way down to the regular languages. [Another paper](https://hal.inria.fr/docs/00/07/30/67/PDF/RR-3611.pdf) (PDF) points out that the 1-PRCGs have worst-case performance `O(|G|n^3)`, the same as the CFGs, affording a nice increase in power without a loss of performance. [Work elsewhere by Alexander Okhotin](https://www.sciencedirect.com/science/article/abs/pii/S157401371300018X) has shown that this result extends to the boolean grammars, which as noted above are equivalent to the 1-RCGs. In addition, (P)RCG is a nice formalism in its own right - it characterizes the PTIME-recognizable languages. EDIT: Did up a table of the relationships of the grammar formalisms: | | Degree | Positive | Simple | | --- | --- | --- | --- | | CFG | 1 | ✅ | ✅ | | Conjunctive | 1 | ✅ | ❌ | | ??? | 1 | ❌ | ✅ | | Boolean | 1 | ❌ | ❌ | | LCFRS | k | ✅ | ✅ | | PRCG | k | ✅ | ❌ | | ??? | k | ❌ | ✅ | | RCG | k | ❌ | ❌ | If you want more info on the topic, I highly recommend Laura Kallmeyer's "Parsing Beyond Context-Free Grammars", ISBN 978-3-642-14845-3, DOI 10.1007/978-3-642-14846-0 Last-minute stinger: A 2-RCG for Rust raw strings: ```rust RawBytes('b' remainder) := RawString(remainder) RawString('r' lhs '"' body '"' rhs) := Hashes(lhs, rhs), !ContainsDelimiter('"' rhs, body) Hashes('#' a, '#' b) := Hashes(a, b) Hashes("", "") := true ContainsDelimiter(needle, prefix middle suffix) := Hashes(needle, middle) ``` This can be transformed into a PRCG, though that is left as an exercise for the reader 😛 --- _[View the full topic](https://internals.rust-lang.org/t/proposal-grammar-working-group/8442)._