Infinite Hang when Parsing (Probably own fault)

[Cookie04DE]

I am trying to parse a custom file format. This is my code:

package main

import (
	"fmt"
	"log"

	"github.com/alecthomas/participle"
	"github.com/alecthomas/participle/lexer"
)

func main() {
	lex := lexer.Must(lexer.Regexp(`([\s\n\r\t]+)` +
		//Comments starting with `#` e.g. `#This is a comment`
		`|(#[a-zA-Z0-9_\+\.@\-\/!]*\n)` +
		//Unquoted string e.g. `1.0` or `readDir`
		`|(?P<String>[a-zA-Z0-9_\+\.@\/]+)` +
		//Arrow `->`, separates expressions
		`|(?P<Arrow>(\->))|` +
		//Open bracket `(`
		`(?P<OpenBracket>\()` +
		//Closed bracket `)`
		`|(?P<ClosedBracket>\))` +
		//Open curly bracket `{`
		`|(?P<OpenCurly>{)` +
		//Closed curly bracket `}`
		`|(?P<ClosedCurly>})` +
		//Comma `,`, separates expressions in curly braces and arguments in stages
		`|(?P<Comma>,)` +
		//Colon `:`, separates argument name and value
		`|(?P<Colon>:)` +
		//Quoted String e.g. `"this is a quoted string"` or `"this uses \"escape\" sequences"`
		`|(?P<QuotedString>"[a-zA-Z0-9_\+\.@\/ ]+")` + //Not sure how to do escape sequences
		`|(?P<Int>)`)) //Not sure what to put here
	parser := participle.MustBuild(&CookieBackup{}, participle.Lexer(lex))
	cb := &CookieBackup{}
	err := parser.ParseString(`#!/bin/CookieBackup
	version 1.0
	#Read the directory which we want to backup
	readDir(Path: "/media/toBackup/", SymLinks: KeepAndCopy) -> tar(Path: "Backup.tar") ->
	{
		writeToDir(Path: "/media/Backups/"),
		gz -> writeToDir(Path: "/media/Backups/compressed/")
	}
	`, cb)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("%#v", cb)
}

type CookieBackup struct {
	Version      string       `parser:"'version' @String"` //parses "version: version_here" to version_here
	Instructions []Expression `parser:"@@*"`               //parses "expression \n expression2" to []Expression{expression, expression2}
}

type Expression struct { //Can either be a single stage, multiple expressions separated by an arrow or multiple expressions surrounded with curly braces and separated by commas
	Instructions  *[]Expression `parser:"(OpenCurly(@@Comma)+ClosedCurly)"` //parses "{expression, expression2}" to []Expression{expression, expression2}
	Instructions2 *[]Expression `parser:"| ((@@Arrow)+@@)"`                 //parses "expression -> expression2" to []Expression{expression, expression2}
	Step          *Step         `parser:"| @@"`                             //parses "step" to Step{}
}

type Step struct {
	Name      string      `parser:"@String"`                                     //parses "name" to "name"
	Arguments *[]Argument `parser:"'| (OpenBracket(@@Comma)+@@ClosedBracket)?'"` //parses "(argument1, argument2)" to []Argument{argument1, argument2} (optional, including brackets)
}

type Argument struct {
	Name   string  `parser:"@String Colon"`               //parses "name:" to "name"
	String *string `parser:"@QuotedString"`               //parses "\"test\"" to "test" and "\"this is an \\"escaped\\"" test\"" to "this is an \"escaped\" test"
	Bool   *bool   `parser:"| @(\"true\" | \"false\")\""` //parses "true" to true and "false" to false
	Int    *int64  `parser:"| @Int"`                      //parses "104" to 104 and "56" to 56
	Enum   *string `parser:"| @String"`                   //parses "Enum" to "Enum"
}

This code hangs indefinitely (as far as I can tell) and consumes a lot of memory.
The code is also incomplete since I don't know how to parse Ints and QuotedStrings, perhaps that's the reason it hangs.
Could you help?

[alecthomas]

Unfortunately you have a classic case of left recursion.

The problem lies in Expression. When it is attempting to match readDir it tries:

1. Instructions which doesn't match
2. Then falls through to Instructions2 which has Expression as its first match, recursing back to 1

The solution is to refactor your grammar to remove this recursion. Something like the following:

type Expression struct { //Can either be a single stage, multiple expressions separated by an arrow or multiple expressions surrounded with curly braces and separated by commas
	Instructions  *[]Expression `parser:"(OpenCurly(@@Comma)+ClosedCurly)"` //parses "{expression, expression2}" to []Expression{expression, expression2}
	Step          *Step         `parser:"| @@"`                             //parses "step" to Step{}
  Next *Expression `parser:"(Arrow @@)?"
}

All the best.

PS. Your bool value won't parse correctly. See documentation for details.

[Cookie04DE]

Thanks for the reply. I updated my code with your suggestions but unfortunately it still hangs. This is it now:

package main

import (
	"fmt"
	"log"

	"github.com/alecthomas/participle"
	"github.com/alecthomas/participle/lexer"
)

func main() {
	lex := lexer.Must(lexer.Regexp(`([\s\n\r\t]+)` +
		//Comments starting with `#` e.g. `#This is a comment`
		`|(#[a-zA-Z0-9_\+\.@\-\/!]*\n)` +
		//Unquoted string e.g. `1.0` or `readDir`
		`|(?P<String>[a-zA-Z0-9_\+\.@\/]+)` +
		//Arrow `->`, separates expressions
		`|(?P<Arrow>(\->))|` +
		//Open bracket `(`
		`(?P<OpenBracket>\()` +
		//Closed bracket `)`
		`|(?P<ClosedBracket>\))` +
		//Open curly bracket `{`
		`|(?P<OpenCurly>{)` +
		//Closed curly bracket `}`
		`|(?P<ClosedCurly>})` +
		//Comma `,`, separates expressions in curly braces and arguments in stages
		`|(?P<Comma>,)` +
		//Colon `:`, separates argument name and value
		`|(?P<Colon>:)` +
		//Quoted String e.g. `"this is a quoted string"` or `"this uses \"escape\" sequences"`
		`|(?P<QuotedString>"[a-zA-Z0-9_\+\.@\/ ]+")` +
		//Not sure how to do escape sequences
		`|(?P<Int>)`)) //Not sure what to put here
	parser := participle.MustBuild(&CookieBackup{}, participle.Lexer(lex))
	cb := &CookieBackup{}
	err := parser.ParseString(`#!/bin/CookieBackup
	version 1.0
	#Read the directory which we want to backup
	readDir(Path: "/media/toBackup/", SymLinks: KeepAndCopy) -> tar(Path: "Backup.tar") ->
	{
		writeToDir(Path: "/media/Backups/"),
		gz -> writeToDir(Path: "/media/Backups/compressed/")
	}
	`, cb)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("%#v", cb)
}

type CookieBackup struct {
	Version      string       `parser:"'version' @String"` //parses "version: version_here" to version_here
	Instructions []Expression `parser:"@@*"`               //parses "expression \n expression2" to []Expression{expression, expression2}
}

type Expression struct { //Can either be a single stage, multiple expressions separated by an arrow or multiple expressions surrounded with curly braces and separated by commas
	Instructions *[]Expression `parser:"(OpenCurly(@@Comma)+ClosedCurly)"` //parses "{expression, expression2}" to []Expression{expression, expression2}
	Step         *Step         `parser:"| @@"`                             //parses "step" to Step{}
	Next         *Expression   `parser:"(Arrow @@)?"`
}

type Step struct {
	Name      string      `parser:"@String"`                                     //parses "name" to "name"
	Arguments *[]Argument `parser:"'| (OpenBracket(@@Comma)+@@ClosedBracket)?'"` //parses "(argument1, argument2)" to []Argument{argument1, argument2} (optional, including brackets)
}

type Boolean bool

func (b *Boolean) Capture(values []string) error {
	*b = values[0] == "true"
	return nil
}

type Argument struct {
	Name   string   `parser:"@String Colon"`             //parses "name:" to "name"
	String *string  `parser:"@QuotedString"`             //parses "\"test\"" to "test" and "\"this is an \\"escaped\\"" test\"" to "this is an \"escaped\" test"
	Bool   *Boolean `parser:"| @(\"true\" | \"false\")"` //parses "true" to true and "false" to false
	Int    *int64   `parser:"| @Int"`                    //parses "104" to 104 and "56" to 56
	Enum   *string  `parser:"| @String"`                 //parses "Enum" to "Enum"
}

[alecthomas]

It will likely be the same problem. Have you looked at the rest of your grammar?

I've just added a Trace() option to v2, but if you'd like to use it you'll need to migrate.

[Cookie04DE]

Yes I have. Interestingly it hangs even if I simplify things by commenting out everything in Expression except Step and Name in Step. That shouldn't be able to hang since each expression is just a step, and each step is just a Name, but it does...