[rust-dev] LL(1) problems

Felix S. Klock II pnkfelix at mozilla.com
Thu Apr 25 09:23:47 PDT 2013

On 25/04/2013 18:12, Graydon Hoare wrote:
> I've been relatively insistent on LL(1) since it is a nice 
> intersection-of-inputs, practically guaranteed to parse under any 
> framework we retarget it to.
I'm a fan of this choice too, if only because the simplest efficient 
parser-generators and/or parser-composition methodologies I know of take 
an LL(1) grammar as input.

However, Paul's earlier plea on this thread ("Please don't do this 
[grammar factoring] to the official parser!") raised the following 
question in my mind:

Are we allowing for the possibility of choosing the semi-middle ground 
of: "There *exists* an LL(1) grammar for Rust that is derivable from the 
non-LL(1)-but-official grammar for Rust." ?  Or do we want to go all the 
way to ensuring that our own grammar that we e.g. use for defining the 
syntactic classes of the macro system etc is strictly LL(1) (or perhaps 
LL(k) for some small but known fixed k)?

(I'd have to go review my compiler text books at home to review how much 
this would actually buy us.)

If we've already discussed the latter, mea culpa.  :)


On 25/04/2013 18:12, Graydon Hoare wrote:
> On 13-04-25 08:37 AM, John Clements wrote:
>> FWIW, I'm (mildly) concerned too.  In particular, I'm disappointed to 
>> discover that in its present form (and using my present caveman-like 
>> invocation style), ANTLR parses source files so slowly that it's 
>> impossible to use directly as a validation tool; I would very much 
>> like to directly validate the grammar used for documentation purposes 
>> against the existing sources.  I haven't yet asked for help from the 
>> ANTLR folks, because I don't yet feel like I've finished due 
>> diligence on RTFMing ANTLR, which I would prefer to do before dumping 
>> the problem in their lap.
> I'm sorry for the confusion; I don't think patrick's work here 
> represents a divergence from yours so much as a continuation of it, in 
> a direction that answers a question I've asked repeatedly while you 
> were working on your grammar: "can we actually find an LL(1) 
> factoring?". Also "can any other non-antlr tools consume this grammar?"
> Since you chose antlr4 rather than antlr3, the LL(1) question in 
> particular was obscured under the "antlr4 will parse anything!" sales 
> pitch[1]. Which is fine as far as getting the grammar roughed out and 
> running -- I'm not criticizing that decision, it was yours to make, as 
> was the choice of antlr in the first place. But it _did_ dodge a 
> question I've been quite persistent about asking; one which I wanted 
> to have an answer for before considering the grammar "done".
> Longer term, I would like whatever grammar we wind up denoting as 
> canonical / documented / spec'ed to be as (re)target-able as possible. 
> I've been relatively insistent on LL(1) since it is a nice 
> intersection-of-inputs, practically guaranteed to parse under any 
> framework we retarget it to. IOW I do _not_ want to force anyone 
> working with rust grammars in the future to use antlr (3, 4, or 
> anything else). That's too tool-specific[2]. A grammar that is 
> trivally translatable between antlr4, antlr3, yapp2, llgen, llnextgen, 
> coco, javacc, parsec, spirit, "some rust parser-generator", and so 
> forth is my "eventual" goal here.
> -Graydon
> [1]: "We parse any grammar" is unfortunately common in 
> parser-generator sales pitches these days, with a profusion GLR and 
> LL(*) things. As a downstream consumer of parser-generator technology, 
> let me point out that while I appreciate broad guarantees by 
> tool-makers, I very much _dislike_ a tool that offers broad guarantees 
> at the expense of being able to make promises about efficiency, 
> grammar class and algorithmic complexity. IOW I actually prefer tools 
> that can tell me what I need to leave out (or change) in my grammar in 
> order to arrive at an efficient parser in a given complexity class. 
> "Don't worry about it" is the wrong answer here. I want to worry about 
> it.
> [2]: we also seem to be most-invested in python for in-tree 
> "maintainer-mode" tools associated with rust development; it seems 
> like a lot to ask to install a JDK in order to verify the grammar. If 
> the grammar-check _can_ be done in a python module, I'm happy to shift 
> over to using it. Unless antlr-ness is an important part of the 
> grammar in some way I'm not perceiving; do you have a strong 
> preference for keeping the java + antlr dependency?
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev

irc: pnkfelix on irc.mozilla.org
email: {fklock, pnkfelix}@mozilla.org

More information about the Rust-dev mailing list