Unsure how to capture optional tokens after recursively capturing a list

[chazu]

Participle is a fantastic resource which I'm enjoying thoroughly. I'm sure that my issue is simply a lack of understanding parser internals on my part, but I'm stymied - hopefully someone can point me in the right direction. If so, I'll be quite grateful for the help.

I'm implementing a parser for Visual Format Language - grammar at the bottom of the linked page - and I've hit an issue where I'm unable to capture an optional grammar element which comes after one or more instances of another grammar element. A specific example:

|-50-[View]-50-|

In this example, the [View] is captured into a slice of View instances, however all subsequent characters (-50-|) should be captured into another struct. I have one such struct which captures the leading form of this construct, and another which captures the trailing form - between them is a list of views [View] for example. I believe what I'm seeing is that capturing views recursively with @@+ causes an unexpected token "|" error because of the greediness of the parser, however if that is the case I'm uncertain how to capture an optional element which comes after a list of one or more other elements.

Code is as follows, with the final test case being the one which fails.

package main

import (
	"fmt"

	"github.com/alecthomas/participle/v2"
	"github.com/alecthomas/participle/v2/lexer"
	"github.com/davecgh/go-spew/spew"
)

var (
	//Custom lexer
	l = lexer.MustSimple([]lexer.SimpleRule{
		{"Ident", "[a-zA-Z_][a-zA-Z0-9_]*"},
		{"Number", "[0-9]+"},
		{"Punctuation", `[][.,]`},
		{"Relation", "==|>=|<="},
		{"Space", " +"},
		{"At", "@"},
		{"OpenParen", "\\("},
		{"CloseParen", "\\)"},
		{"Colon", ":"},
		{"Pipe", "\\|"},
		{"Dash", "-"},
	})
)

type Program struct {
	Orientation                 *Orientation                 `@@?`
	LeadingSuperViewConnection  *LeadingSuperViewConnection  `@@?`
	Views                       []*View                      `@@+`
	TrailingSuperViewConnection *TrailingSuperViewConnection `@@?`
}

type View struct {
	Connection *Connection   `@@?`
	Name       string        `"[" @Ident`
	Predicate  PredicateList `(Space @@)? "]"`
}

type Relation struct {
	Eq  *bool `@"=="`
	Gte *bool `| @">="`
	Lte *bool `| @"<="`
}

type PredicateObject struct {
	Number   int    `@Number`
	ViewName string `| @Ident`
}

type Predicate struct {
	Relation *Relation        `@@?`
	Object   *PredicateObject `@@`
	Priority *Priority        `@@?`
}

type Priority struct {
	Value *int `At @Number`
}

type PredicateList struct {
	Predicates []*Predicate `OpenParen @@ ("," @@)* CloseParen`
	Predicate  *Predicate   `| @@`
}

type Orientation struct {
	Direction *string `(@"H"? @"V"?)! Colon`
}

type LeadingSuperViewConnection struct {
	SuperView  bool        `@Pipe`
	Connection *Connection `@@?`
}

type TrailingSuperViewConnection struct {
	Connection *Connection `@@?`
	SuperView  bool        `@Pipe`
}

type Connection struct {
	Predicates *PredicateList `Dash (@@ Dash)?`
}

func main() {

	p := participle.MustBuild[Program](
		participle.Lexer(l),
	)
	cases := []string{
		"[Test]",
		"[Test 40]",
		"[Test1][Test2]",
		"[Test1 >=40]",
		"[Test1 >=40@10]",
		"[Test1 >=40][Test2 >=Foo]",
		"[Test1 >=40][Test2 >=Foo@10]",
		"[Test1 (>=40,<=80)]",
		"[Test1 (>=40)]",
		"H:[TestView]",
		"V:[TestView]",
		"V:[TestView]-[TestTwo]",
		"V:[TestView]-50-[TestTwo]",
		"|[Test]|",
		"|[Test][TestTwo]|",
		"|[Test]-[TestTwo]|",
		"|[Test]-(50)-[TestTwo]|",
		"|-[Test]-|",
		"|-50-[Test]-|",
		"|-50-[Test]-50-|",
	}
	for _, c := range cases {
		fmt.Printf("%s...", c)
		res, err := p.ParseString("", c)
		if err != nil {
			panic(err)
		}
		fmt.Printf("OK\n")
		spew.Dump(res)
	}

}

[alecthomas]

I haven't looked in detail, but using participle.UseLookahead() fixes this. What's likely happening is that there is some ambiguity between the inner case and TrailingSuperViewConnection, so the inner case partially matches, but fails to match completely.

[chazu]

Alec,

Thanks so much for the prompt reply - this was indeed enough to fix my issue. Thanks also for your work to create and also support such a fantastic tool.

Sincerely,
chazu