Stateful lexer - return to Root

[kellerza]

In my stateful lexer I can enter new groups with {, and exit them with }. Groups can be multiple levels deep.

The special character / allows you to exit all groups (Returns to root).

How would I solve this in particle?

Attempts so far was to introduce a PopToRoot action, but the lexer.stack is private.
Hopefully there is another approach?

type ActionPopToRoot struct{}

func (p ActionPopToRoot) applyAction(lexer *lexer.StatefulLexer, groups []string) error {
	if groups[0] == "" {
		return errors.New("did not consume any input")
	}
	lexer.stack = nil
	return nil
}

[alecthomas]

There is no such action currently. What's an example of an input you're parsing?

[kellerza]

It is router configuration:

/configure router { autonomous-system 65400 }
configure {
router "Base" {
bgp {
 # comment: Line one for connect retry timer
 # comment:   Line two indented
 connect-retry 37
}
}
}
     
/configure service vprn 1234 {
   sap 1/2/2 { }

In the example, the three }'s are optional

I realise that I'll never get a perfect AST, and will have to do some post-processing, since you can access containers/groups directly (see the bgp example above), but it would still be nice not to have root elements everywhere

[alecthomas]

You're missing GroupStart and GroupEnd from the simple lexer.

[alecthomas]

For a grammar like this I'd typically have something like the following tokens: Ident, Whitespace (elided), Number, String, Punctuation, Comment (elided). You can break tokens down into more specific types (GroupStart, etc.), but I typically just match the text directly in the parser.

[kellerza]

I got the stateless lexer to work, but once again considering stateful 😄

The / can be a navigation command of start of the path. or part of another command's argument

/configure service etc
delete /configure service etc

So either stateful or not matching on individual terms

[alecthomas]

You absolutely do not need the stateful lexer ;)

To deal with this, the wrapping lexer I described earlier would match any / immediately preceded by a \n, and insert the corret number of closing }

[alecthomas]

Ah I see. This doesn't look like a problem that should be solved by the stateful lexer, it looks like a parser issue. The stateful aspects of the lexer should only really be used if you have nested languages with the same token used to terminate and end a nesting, such that they can't be disambiguated any other way. The classic example of this is interpolation such as "a string ${func("nested string")}".

That said, I'm not sure how you'd express this in the parser. I think what you'll need to do is implement a lexer that wraps the existing one, and synthesises the missing closing }'s. For example if you have {{{/ it would replace the / with }}} leaving {{{}}}.

[kellerza]

I was under the impression that the stateful lexer was the only way to get an optional group closing bracket }, but as I'm working more with this, it seems like it might be possible with a simple lexer. Will try and give some feedback

[kellerza]

Currently, the stateful lexer works a charm, but cannot get the corresponding Simple lexer working... it does not like the groups/optional group ends

The current code, with both lexers:

package main

import (
	"os"

	"github.com/alecthomas/repr"

	"github.com/alecthomas/participle/v2"
	"github.com/alecthomas/participle/v2/lexer"
	"github.com/go-test/deep"
)

type Bool bool

func (b *Bool) Capture(v []string) error { *b = v[0] != ""; return nil }

type Term struct {
	Text    string  `parser:"( (@Char|@String)+"`
	Comment string  `parser:" | @Comment"`
	Eol     Bool    `parser:" | @EOL )"`
	Group   []*Term `parser:"('{' @@* '}'|'{' @@*)?"`
	Root    Bool    `parser:"@GotoRoot?"`
}

type Terms struct {
	Terms []*Term `parser:"@@*"`
}

var (
	lxr1 = lexer.MustSimple([]lexer.SimpleRule{
		{`EOL`, `[\n\r]+`},
		{`Whitespace`, `\s+`},
		{`GotoRoot`, `/`},
		{`Comment`, `#[^\n]+`},
		{`Char`, `[^\n# "}]+ ?`},
		{`String`, `"(?:[^"\\]|\\.)*" ?`},
	})

	lxr2 = lexer.MustStateful(lexer.Rules{
		"Root": {
			{`EOL`, `[\n\r]+`, nil},
			{`Whitespace`, `\s+`, nil},
			{`GotoRoot`, `/`, nil},
			{`GroupStart`, `{`, lexer.Push("Group")},
			{`Comment`, `#[^\n]+`, nil},
			{`Char`, `[^\n# "}]+ ?`, nil},
			{`String`, `"(?:[^"\\]|\\.)*" ?`, nil},
		},
		"Group": {
			{`GroupEnd`, `}`, lexer.Pop()},
			lexer.Include("Root"),
		},
	})

	parser1 = participle.MustBuild[Terms](participle.Lexer(lxr1),
		participle.Elide("Whitespace"))

	parser2 = participle.MustBuild[Terms](participle.Lexer(lxr2),
		participle.Elide("Whitespace"))
)

func main() {

	f, err := os.Open("example.txt")
	if err != nil {
		panic(err)
	}
	defer f.Close()

	// Parse with the stateful lexer
	ast2, err := parser2.Parse("", f)
	repr.Println(ast2)
	if err != nil {
		repr.Println("stateful fail", err)
	}

	// Repeat with the Simple Lexer
	f.Seek(0, 0)
	ast1, err := parser1.Parse("", f)
	repr.Println(ast1)
	if err != nil {
		repr.Println("Simple fail", err)
	}

	// Diff
	if diff := deep.Equal(ast1, ast2); diff != nil {
		repr.Println(diff)
	} else {
		repr.Println("The same!")
	}

}

[alecthomas]

This is not uncommon BTW, lexers for languages with semantic indentation do something similar, as do some lexers for languages that have optional statement ending ; tokens - a ; will be inserted at certain points.