muesli/parser.go

package muesli

import (
	_ "bufio"
	_ "bytes"
	_ "errors"
	"fmt"
	_ "io"
	_ "os"
	_ "reflect"
	_ "runtime"
	_ "strings"
	_ "unicode"
	// "gitlab.com/beoran/woe/graphviz"
	// _ "gitlab.com/beoran/woe/monolog"
)

/* Grammar:
Desrired syntax (verified LL(1) on smlweb.cpsc.ucalgary.ca)

PROGRAM -> STATEMENTS.
CLOSED -> BLOCK | LIST | PARENTHESIS .
STATEMENTS -> STATEMENT STATEMENTS | .
STATEMENT -> CLOSED | EXPRESSION eos | eos .
COMMAND -> word PARAMETERS.
PARAMETERS -> PARAMETER PARAMETERS | .
PARAMETER -> WORDVALUE | GETTER | SETTER | CLOSED .
EXPRESSION -> COMMAND | GETTER | SETTER | VALUE.
PARENTHESIS -> closeparen EXPRESSION openparen .
BLOCK -> openblock STATEMENTS closeblock .
LIST -> openlist PARAMETERS closelist .
VALUE -> string | int | float | symbol | type .
WORDVALUE -> word | VALUE.
SETTER -> set TARGET . 
TARGET -> word PARAMETER | GETTER PARAMETER .
GETTER -> get ORIGIN .
ORIGIN -> word | SETTER | GETTER .


Or with simple operators variant.

PROGRAM -> STATEMENTS.
CLOSED -> BLOCK | LIST | PARENTHESIS .
STATEMENTS -> STATEMENT STATEMENTS | .
STATEMENT -> CLOSED | EXPRESSION eos | eos .
COMMAND -> WORDVALUE DETAILS .
DETAILS -> OPERATION | PARAMETERS .
OPERATION -> operator COMMAND .
PARAMETERS -> PARAMETER PARAMETERS | .
PARAMETER -> WORDVALUE | GETTER | SETTER | CLOSED .
EXPRESSION -> COMMAND | GETTER | SETTER.
PARENTHESIS -> openparen EXPRESSION closeparen .
BLOCK -> openblock STATEMENTS closeblock .
LIST -> openlist PARAMETERS closelist .
VALUE -> string | int | float | symbol | type .
WORDVALUE -> word | VALUE.
SETTER -> set TARGET . 
TARGET -> word PARAMETER | GETTER PARAMETER .
GETTER -> get ORIGIN .
GETCALL -> comma COMMAND | .
ORIGIN -> word | SETTER | GETTER .

Note that the Muesli syntax description below is not strictly LL(1), 
notably the optional operator after a getter, but the recursive descent parser 
can parse it correctly.

PROGRAM -> STATEMENTS.
CLOSED -> BLOCK | LIST | PARENTHESIS .
STATEMENTS -> STATEMENT STATEMENTS | .
STATEMENT -> CLOSED | EXPRESSION eos | eos .
COMMAND -> WORDVALUE DETAILS .
DETAILS -> OPERATION | PARAMETERS .
OPT_OPER -> OPERATION | .
OPERATION -> operator COMMAND .
PARAMETERS -> PARAMETER PARAMETERS | .
PARAMETER -> WORDVALUE | GETTER | SETTER | CLOSED .
EXPRESSION -> COMMAND | GETTER | SETTER.
PARENTHESIS -> openparen EXPRESSION closeparen .
BLOCK -> openblock STATEMENTS closeblock .
LIST -> openlist PARAMETERS closelist .
VALUE -> string | int | float | symbol | type .
WORDVALUE -> word | VALUE.
SETTER -> set TARGET . 
TARGET -> word PARAMETER | GETTER PARAMETER .
GETTER -> get ORIGIN OPT_OPER .
GETCALL -> comma COMMAND | .
ORIGIN -> word | SETTER | GETTER .


 *
 * program -> statements
 * statements -> statement+
 * statement -> get / set / command
 *
*/

type Parser struct {
	Lexer   *Lexer
	current Token
	LoggerWrapper
    Errors []ParserError
}

// panic with this type on errors that would prevent the parser 
// from making progress.
type ParserError struct {
    *Parser
    *Token 
    Chain error
}

func (pe ParserError) Error() string {
	return fmt.Sprintf("%s %s", pe.Token.String(), pe.Chain.Error())
}

func (parser *Parser) SetLogger(logger Logger) {
	parser.LoggerWrapper = LoggerWrapper{logger}
}

func (parser *Parser) Errorf(message string, args ...interface{}) ParserError {
	err := fmt.Errorf(message, args...)
    pe := ParserError { Parser: parser, Token:&parser.current, Chain: err }
    parser.Errors = append(parser.Errors, pe)
    return pe
}

func (parser *Parser) Panicf(message string, args ...interface{})  {
    pe := parser.Errorf(message, args...)
    panic(pe)
}

func (parser *Parser) Advance() {
	token := parser.Lexer.Lex()
	parser.current = token
	parser.LogDebug("Next token: %s\n", token.String())
}

/* Skips tokens until a closer, namely ), }, ], EOX or EOF is found, 
 * to skip parse errors, and to be able to continue parsing despite errors. */
func (parser *Parser) SkipError() Token {
    parser.Advance()
    for {
        parser.Advance()
        if parser.NextIsErrorSkipped() {
            return parser.current
        }
        if parser.NextIs(TokenKindError, TokenKindNone) {
            parser.Panicf("Cannot recover from parse error. Parse ended.")
        }
    }
    return parser.current
}

/* Looks at the current token and advances the lexer if the token is of any of
the token kinds given in kinds. In this case it will return the accepted
token and advance the parser. Otherwise, it will call parser.Panicf with a
* "Syntax error unexpected <token>".*/
func (parser *Parser) Require(kinds ...TokenKind) Token {
	if parser.current.IsNone() {
		parser.Advance()
	}
	
	expected := ""
	sep := ""    
	for _, kind := range kinds {
		if kind == parser.current.TokenKind {
			accepted := parser.current
			parser.Advance()
            parser.LogDebug("Require: Accepted token: %s\n", accepted.String())
			return accepted
		}
		expected = fmt.Sprintf("%s%s%s", expected, sep, kind.String())
	}
	
	parser.Panicf("error: expected one of the following: %s", expected)
	return Token{}
}


func (parser *Parser) NewAstError(message string, args ...interface{}) *Ast {
	sv := StringValue(fmt.Sprintf(message+" at token "+parser.current.String(), args))
	pos := parser.current.Position
	tok := NewToken(TokenKindError, sv, pos)
	parser.Errorf(message, args...)
	return NewAst(AstKindError, nil, EmptyAstArray(), tok)
}

// Also  handles none or error vales of the token

func (parser *Parser) NewAst(kind AstKind, parent * Ast, children []*Ast, value Token) *Ast{
    if value.IsNone() {
        return NewAstNone()
    }
    if value.IsError() {
        return NewAst(AstKindError, parent, children, value)
    }
    return NewAst(kind, parent, children, value)
}

func (parser *Parser) ParseValue() *Ast {
    parser.LogDebug("ParseValue: %s\n", parser.current.String())

	value := parser.Require(TokenKindInteger, TokenKindString,
		TokenKindBoolean, TokenKindNil, TokenKindFloat, TokenKindSymbol)
	return parser.NewAst(AstKindValue, nil, EmptyAstArray(), value)
}

func AstKindForToken(token Token) AstKind {
	switch token.TokenKind {
		case TokenKindInteger, TokenKindString,	TokenKindBoolean, 
			 TokenKindNil, TokenKindFloat, TokenKindSymbol:
			 return AstKindValue
		case TokenKindWord:
			 return AstKindWord
        case TokenKindOperator:
			 return AstKindWord
		case TokenKindType:
			return AstKindType
		default:
			return AstKindError
	}
}

func (parser *Parser) ParseWordValue() *Ast {
    parser.LogDebug("ParseWordValue: %s\n", parser.current.String())

	value := parser.Require(TokenKindInteger, TokenKindString,
		TokenKindBoolean, TokenKindNil, TokenKindFloat, TokenKindSymbol,
		TokenKindType, TokenKindWord)
	
	astKind := AstKindForToken(value)
	
	return parser.NewAst(astKind, nil, EmptyAstArray(), value)
}

func (parser *Parser) ParseArgument() *Ast {
    parser.LogDebug("ParseArgument: %s\n", parser.current.String())

	switch {
			case parser.NextIsGet(): return parser.ParseGet()
			case parser.NextIsSet(): return parser.ParseSet()
			case parser.NextIsClosed(): return parser.ParseClosed()
			case parser.NextIsWordValue(): return parser.ParseWordValue()
			default: parser.Panicf("error: in argument: expected $, =, }, word or value")
			return nil
	}
}

func (parser *Parser) ParseArguments(extra ... *Ast) *Ast {
    parser.LogDebug("ParseArguments: %s\n", parser.current.String())
    
    ast := NewAstWithToken(AstKindArguments,  parser.current)
    var children []*Ast
    for _, arg := range extra {
		children = append(children, arg)
	}
    
    for parser.NextIsArgument() {
		child := parser.ParseArgument()
		children = append(children, child)
	}
	ast.AppendChildren(children...)
	return ast
}

func (parser *Parser) ParseList() *Ast {
    parser.LogDebug("ParseList: %s\n", parser.current.String())

	op := parser.Require(TokenKindOpenList)
	if op.IsError() {
        return parser.NewAstError("Unexpected value.")
    }

	ast := NewAstWithToken(AstKindList, op)
	args := parser.ParseArguments()
	if AstIsError(args) {
		return args
	}
	if cp := parser.Require(TokenKindCloseList); cp.IsError() {
		return parser.NewAstError("expected closing brackets")
	}

	ast.AppendChild(args)
	return ast
}

func (parser *Parser) ParseParenthesis() *Ast {
    parser.LogDebug("ParseParenthesis: %s\n", parser.current.String())

	op := parser.Require(TokenKindOpenParen)
    if op.IsError() {
        return parser.NewAstError("Unexpected value.")
    }


	ast := NewAstWithToken(AstKindParenthesis, op)
	expr := parser.ParseExpression()
	if expr.IsNone() {
		return parser.NewAstError("expected expression")
	}
	if AstIsError(expr) {
		return expr
	}
	if cp := parser.Require(TokenKindCloseParen); cp.IsError() {
		return parser.NewAstError("expected closing parenthesis")
	}

	ast.AppendChild(expr)
	return ast
}

func (parser *Parser) ParseBlock() *Ast {
    parser.LogDebug("ParseBlock: %s\n", parser.current.String())

	op := parser.Require(TokenKindOpenBlock)
    if op.IsError() {
        return parser.NewAstError("Unexpected value.")
    }

	ast := NewAstWithToken(AstKindBlock, op)
	stats := parser.ParseStatements()
	if stats.IsNone() {
		return parser.NewAstError("expected expression")
	}
	if AstIsError(stats) {
		return stats
	}
	if cp := parser.Require(TokenKindCloseBlock); cp.IsError() {
		return parser.NewAstError("expected closing block")
	}

	ast.AppendChild(stats)
	return ast
}

/* Parses the target of a set expression */
func (parser *Parser) ParseTarget() *Ast {
    parser.LogDebug("ParseTarget: %s\n", parser.current.String())
    var target *Ast
    
    switch {
		case parser.NextIs(TokenKindWord, TokenKindType, TokenKindSymbol):
			// Direct target to a set
			token := parser.Require(TokenKindWord, TokenKindType, TokenKindSymbol)
			target = NewAstWithToken(AstKindTarget, token)
		case parser.NextIsGet(): 
			// Indirect target
			target = NewAstWithToken(AstKindTarget, parser.current)
			target.AppendChild(parser.ParseGet())
		case parser.NextIsClosed():
			// Indirect target
			target = NewAstWithToken(AstKindTarget, parser.current)
			target.AppendChild(parser.ParseClosed())
		default: 
			parser.Panicf("Malformed setter.")
			return nil
	} 	
	
	argument := parser.ParseArgument()
	if argument.IsNone() {
		return parser.NewAstError("Expected argument to set")
	}
	target.AppendChild(argument)

	return target
}

/* Parses the origin of a get expression */
func (parser *Parser) ParseOrigin() *Ast {
    parser.LogDebug("ParseOrigin: %s\n", parser.current.String())
    var target *Ast
    
    switch {
		case parser.NextIs(TokenKindWord, TokenKindType, TokenKindSymbol):
			// Direct target to a set
			token := parser.Require(TokenKindWord, TokenKindType, TokenKindSymbol)		
			target = NewAstWithToken(AstKindTarget, token)
		case parser.NextIsGet(): 
			// Indirect target
			target = NewAstWithToken(AstKindTarget, parser.current)
			target.AppendChild(parser.ParseGet())
		case parser.NextIsClosed():
			// Indirect target
			target = NewAstWithToken(AstKindTarget, parser.current)
			target.AppendChild(parser.ParseClosed())
		default: 
			parser.Panicf("Malformed getter")
			return nil
	} 	
	
	return target
}


func (parser *Parser) ParseSet() *Ast {
    parser.LogDebug("ParseSet: %s\n", parser.current.String())
    
	set := parser.Require(TokenKindSet)
	ast := NewAstWithToken(AstKindSet, set)
	target := parser.ParseTarget()
	ast.AppendChild(target)
    if parser.NextIs(TokenKindOperator)  {
        ast = parser.ParseOperator(ast)
    }
    
    return ast
}

func (parser *Parser) ParseGet() *Ast {
    parser.LogDebug("ParseGet: %s\n", parser.current.String())

	get := parser.Require(TokenKindGet)
	ast := NewAstWithToken(AstKindGet, get)
	target := parser.ParseOrigin()
	ast.AppendChild(target)
    if parser.NextIs(TokenKindOperator)  {
        ast = parser.ParseOperator(ast)
    }
    
	return ast
}

func (parser *Parser) ParseOperator(operand *Ast) *Ast {
    parser.LogDebug("ParseOperator: %s\n", parser.current.String())
    
    operator := parser.Require(TokenKindOperator)
    arguments := parser.ParseArguments(operand)
    command := NewAstWithToken(AstKindCommand, operator)
    command.AppendChild(arguments)
    return command
}

func (parser *Parser) ParseCommand() *Ast {
    parser.LogDebug("ParseCommand: %s\n", parser.current.String())

    wordvalue := parser.ParseWordValue()
    
    // operator command
    if parser.NextIs(TokenKindOperator) {
        return parser.ParseOperator(wordvalue)
    } 
    
    arguments := parser.ParseArguments()
	command := NewAstWithToken(AstKindCommand, wordvalue.Token())
	command.AppendChild(arguments)
	return command
}

func (parser *Parser) ParseClosed() *Ast {
    parser.LogDebug("ParseClosed: %s\n", parser.current.String())
    switch {
		case parser.NextIs(TokenKindOpenBlock): return parser.ParseBlock()
		case parser.NextIs(TokenKindOpenParen): return parser.ParseParenthesis()
		case parser.NextIs(TokenKindOpenList): return parser.ParseList()
		default:
			parser.Panicf("Syntax error in closed, expected {, (, [")
			return nil
	}
}


func (parser *Parser) ParseExpression() *Ast {
    parser.LogDebug("ParseExpression: %s\n", parser.current.String())
    
    switch {
		case parser.NextIsWord(): return parser.ParseCommand()
		case parser.NextIsSet(): return parser.ParseSet()
		case parser.NextIsGet(): return parser.ParseGet()
		case parser.NextIsValue(): return parser.ParseCommand()
		default: 
			parser.Panicf("Syntax error in expression, expected word, $, =, value")
			return nil
    }
}

func (parser *Parser) ParseExpressionStatement() *Ast {
    parser.LogDebug("ParseExpressionStatement: %s\n", parser.current.String())
	expr := parser.ParseExpression()
    if expr.IsNone() {
        return NewAstNone()
    }
    
    // Expression statements must end on EOX or EOF
    if eox := parser.Require(TokenKindEOX, TokenKindEOF); eox.IsError() {
		return parser.NewAstError("expected end of statement")
	}
    
	return expr
}


func (parser *Parser) ParseEmptyStatement() *Ast {
    parser.LogDebug("ParseEmptyStatement: %s\n", parser.current.String())
	if eox := parser.Require(TokenKindEOX, TokenKindEOF); eox.IsError() {
		return parser.NewAstError("expected end of statement")
	}
    return NewAstWithToken(AstKindStatement, parser.current)
}

func (parser Parser) NextIs(kinds ...TokenKind) bool {
    if (parser.current.TokenKind == TokenKindNone) {
		parser.Advance()
	}    
    for _, kind := range kinds {
        if kind == parser.current.TokenKind  {
            return true
        }
    }
    return false
} 

func (parser Parser) NextIsClosed() bool {
    return parser.NextIs(TokenKindOpenBlock, TokenKindOpenList, TokenKindOpenParen)
}

func (parser Parser) NextIsWord() bool {
    return parser.NextIs(TokenKindWord)
}

func (parser Parser) NextIsGet() bool {
    return parser.NextIs(TokenKindGet)
}

func (parser Parser) NextIsSet() bool {
    return parser.NextIs(TokenKindSet)
}

func (parser Parser) NextIsValue() bool {
    return parser.NextIs(TokenKindString, TokenKindType, 
    TokenKindInteger, TokenKindFloat, TokenKindBoolean, TokenKindNil,
    TokenKindSymbol)
}

func (parser Parser) NextIsOperator() bool {
    return parser.NextIs(TokenKindOperator)
}

func (parser Parser) NextIsWordValue() bool {
    return parser.NextIs(TokenKindWord, TokenKindString, TokenKindType, 
    TokenKindInteger, TokenKindFloat, TokenKindBoolean, TokenKindNil,
    TokenKindSymbol)
}

func (parser Parser) NextIsArgument() bool {
    return parser.NextIs(TokenKindOpenBlock, TokenKindOpenList, TokenKindOpenParen, 
    TokenKindSet, TokenKindGet, TokenKindWord, TokenKindString, TokenKindType,
    TokenKindInteger, TokenKindFloat, TokenKindBoolean, TokenKindNil,
    TokenKindSymbol)
}

func (parser Parser) NextIsErrorSkipped() bool {
    return parser.NextIs(TokenKindCloseBlock, TokenKindCloseList, TokenKindCloseParen, 
    TokenKindEOX, TokenKindEOF)
}

func (parser Parser) NextIsEOX() bool {
    return parser.NextIs(TokenKindEOX)
}

func (parser Parser) NextIsEOF() bool {
    return parser.NextIs(TokenKindEOF)
}

func (parser Parser) NextIsExpression() bool {
    return parser.NextIs(TokenKindWord,
                    TokenKindGet,
                    TokenKindSet,
                    TokenKindString, 
                    TokenKindType, 
                    TokenKindInteger, 
                    TokenKindFloat, 
                    TokenKindBoolean, TokenKindNil,
                    TokenKindSymbol)
}

func (parser Parser) NextIsStatement() bool {
	return parser.NextIsExpression() || parser.NextIsClosed() || parser.NextIsEOX()
}


func (parser *Parser) ParseStatement() *Ast {
    parser.LogDebug("ParseStatement: %s\n", parser.current.String())
    switch  {
        case parser.NextIsClosed(): return parser.ParseClosed()
        case parser.NextIsExpression(): return parser.ParseExpressionStatement()
        case parser.NextIsEOX(): return parser.ParseEmptyStatement()
        default:
        parser.Panicf("Expected closed, expression, or EOX in statement")
        return parser.NewAstError("Expected closed, expression, or EOX in statement")
    }
}

func (parser *Parser) ParseStatements() *Ast {
    parser.LogDebug("ParseStatements: %s\n", parser.current.String())
    
    ast := NewAstWithToken(AstKindStatements,  parser.current)
    var children []*Ast
    for parser.NextIsStatement() {
		child := parser.ParseStatement()
		children = append(children, child)
	}
	ast.AppendChildren(children...)
	return ast
    
    
}

func (parser *Parser) ParseProgram() *Ast {
    parser.LogDebug("ParseProgram: %s\n", parser.current.String())

	stats := parser.ParseStatements()	
	eof := parser.Require(TokenKindEOF)
	aeof := NewAstWithToken(AstKindEnd, eof)
    if eof.IsNone() {
        aeof = parser.NewAstError("Expected EOF, have: %s", parser.current.String())
    }
    children := []*Ast{stats, aeof}
	return NewAst(AstKindProgram, nil, children, NoToken())
}

func (parser *Parser) Parse() (ast *Ast) {
	defer func() {
		if err := recover() ; err != nil {
			if perr, ok := err.(ParserError) ; ok{ 
				ast = parser.NewAstError("Parse error, recovered: %s\n", perr)
			} else {
				panic(err)
			}
		}
	} ()
	parser.Advance()
	ast = parser.ParseProgram()
	return ast
}

func NewParser(lexer *Lexer) *Parser {
	parser := &Parser{Lexer: lexer, current: NoToken(), LoggerWrapper: LoggerWrapper{nil}}
	return parser
}

func NewParserFromString(input string) *Parser {
	lexer := NewLexerFromString(input)
	return NewParser(lexer)
}

func NewParserFromFilename(filename string) (*Parser, error) {
	lexer, err := NewLexerFromFilename(filename)
	if err != nil {
		return nil, err
	}
	return NewParser(lexer), nil
}

func (parser * Parser) NewKeyword(name string, tk TokenKind, val Value) *Keyword {
	return parser.Lexer.NewKeyword(name, tk, val)
}

func (parser * Parser) AddKeyword(kw * Keyword) *Keyword {
	return parser.Lexer.AddKeyword(kw)
}

func (parser * Parser) AddKeywords(keywords []*Keyword) {
	for _, kw := range keywords {
		parser.AddKeyword(kw)
	}	
}

func (parser * Parser) AddDefaultKeywords() {
	parser.AddKeywords(DefaultKeywords)
}