Parser being greedy

[lmrcarneiro]

Hey, Alec Thomas.
I'm trying to parse the input "aa" which should be valid accordding to the grammar, but the example program returns an error.
It seems like the parser is greedy and does not "give back", so the second expression of the Text property of the Example struct never consumes anything.

Grammar:

Example = *( ALPHA / DIGIT / "-" ) Let-dig
Let-dig = ALPHA / DIGIT

Code:

var iniLexer = lexer.MustSimple([]lexer.SimpleRule{
	{Name: `ALPHA`, Pattern: `[A-Za-z]`},
	{Name: `DIGIT`, Pattern: `[0-9]`},
	{Name: `Others`, Pattern: `-`},
})

//	Example = *( ALPHA / DIGIT / "-" ) Let-dig
//	Let-dig = ALPHA / DIGIT
type Example struct {
	Text string `@(ALPHA | DIGIT | "-")* @(ALPHA | DIGIT)`
}

func main() {
	parser := participle.MustBuild[Example](
		participle.Lexer(iniLexer))
	_, err := parser.ParseString("", "aa")
	if err != nil {
		panic(err)
	}
}

Error:
panic: 1:3: unexpected token "<EOF>" (expected (<alpha> | <digit>))

I have tried to created the "Let-dig" symbol as indicated by the grammar but as you can expect it had no effect.
I have also tried to rewrite this grammar somehow to eliminate the ambiguity but I couldn't come up with anything.
Is this my fault? Should I use some kind of regex expression to prevent the first expression from matching the last occurrence? I'm kind of lost here...
Cheers

[alecthomas]

Participle is greedy yes.

[lmrcarneiro]

Okay, thanks.
Fow now I just added an extra check that returns an error when converting to string after parsing.

Out of curiosity, recursion is not yet supported right?

[alecthomas]

Recursion into structs is supported, yes.

[lmrcarneiro]

Sorry, I meant indirect recursion to itself.
Maybe it's easier with an example.

I came up with a workaround inspired by finite state machines which can be seen here. This produces the following grammar:

C -> "-"+                  | (alpha | digit) A
A -> (alpha | digit)+ | "-" B
B ->  "-"+                 |  (alpha | digit) A

I cannot code it because the parser complains of left recursion or says "branch "-"* was accepted but did not progress the lexer at 1:1". Maybe you have a better solution for this.. :)

As a reference, here is my code:

//C -> "-"+                  | (alpha | digit) A
type C struct {
	S string `@"-"* | ( @(ALPHA|DIGIT)`
	A *A     `		    @@ 			 )`
}

//A -> (alpha | digit)+ | "-" B
type A struct {
	S string `@(ALPHA|DIGIT)* | ( @"-"`
	B []*B   `					  @@  )`
}

//B ->  "-"+                 |  (alpha | digit) A
type B struct {
	S string `@"-"* | ( @(ALPHA|DIGIT)`
	A []*A   `			@@			 )`
}

So that's what I was trying to ask, forgive me for not being clear enough.
Again, thanks a lot for your attention :)

[alecthomas]

Ah, no left recursion it's not supported. You will have to manually refactor your grammar.

[lmrcarneiro]

But that's the thing, isn't my new grammar right recursive and not left recursive?
Since all non terminal symbols are on the right and not on the left.

Anyways, thanks for all of your help!!