Defer lookahead to allow optional tail

[ryo33]

I want to make a LL(1) language, and I've written the following grammar:

Expr: A B C
    | '!' Expr [ '->' Expr ]
    ;

A: "a";
B: "b";
C: "c";

parol emits this exceeds the maximum lookahead of 1.

Yes, it's not LL(1) because we should look ahead for -> after the Expr, and the Expr can be the infinite size.
It's clear in an expanded grammar:

/* 0 */ Expr: A B C;
/* 1 */ Expr: '!' Expr ExprOpt /* Option */;
/* 2 */ ExprOpt /* Option<T>::Some */: '->' Expr;
/* 3 */ ExprOpt /* Option<T>::None */: ;
/* 4 */ A: "a";
/* 5 */ B: "b";
/* 6 */ C: "c";

But the production for ! abc -> abc is the following struct:

pub struct BangExprArrowExpr<'t> {
    pub bang: Token<'t>, /* ! */
    pub expr: Box<Expr<'t>>,
    pub expr_opt: Option<Box<ExprOpt<'t>>>,
}

and not something like this:

pub enum BangExprArrowExpr {
    SomeTail(BangExprArrowExprSomeTail),
    NoneTail(BangExprArrowExprNoneTail),
}

Given this, it seems to me that LL(1) parsing can actually be done if we defer the lookahead of -> because ! already tells us this is a BangExprArrowExpr.

[jsinger67]

Quick shot, but please try this grammar:

Expr: A B C
    | '!' Expr '->' Expr
    | '!' Expr
    ;

A: "a";
B: "b";
C: "c";

This should make parol able to left factor it into a LL(1) grammar.

[ryo33]

It does indeed seem to output another expanded grammar, but it also exceeds the maximum lookahead of 5.

/* 0 */ Expr: '!' Expr ExprSuffix;
/* 1 */ Expr: A B C;
/* 2 */ ExprSuffix: '->' Expr;
/* 3 */ ExprSuffix: ;
/* 4 */ A: "a";
/* 5 */ B: "b";
/* 6 */ C: "c";

[ryo33]

Here is the source code: https://github.com/ryo33/parol_sandbox/tree/tail-optional

[jsinger67]

Ok, I will try it 😉

[jsinger67]

The problem is the recursion in Expr.

You have to formulate your grammar like this:

%start Expr
%title "ParolSandbox grammar"
%comment "Empty grammar generated by `parol`"
%scanner String {
    %auto_ws_off
    %auto_newline_off
 }

%%

Expr
    : AbcExpr
    | BangExpr
    ;

AbcExpr:
    | A B C;

BangExpr
    : '!' AbcExpr '->' Expr 
    | '!' AbcExpr
    ;

A: "a";
B: "b";
C: "c";

[jsinger67]

BangExpr
    : '!' AbcExpr ['->' Expr] 
    ;

will work this way too.

[ryo33]

Expr: A B C
    | '!' Expr [ '->' Other ]
    ;

A: "a";
B: "b";
C: "c";
Other: "other";

Somehow I think this example would work, but at least it's not an LL(1) grammar. Still, LL(1) parsing seems feasible, but I don't understand how PDA actually works, so I don't know if it is feasible. In the meantime, I'd like to start by taking a peek at the source code.

[ryo33]

I finally figured it out.

! ! ! abc -> other -> other

we cannot determine where the -> belongs.

[jsinger67]

Yeah, you have basically a recursion at Expr that can infinitely add inner expressions.
You actually have to remove this recursion if your intended syntax allows this.