peg

package module
v0.0.0-...-de25d67 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 4, 2021 License: MIT Imports: 5 Imported by: 13

README

go-peg

NOTE: This library is deprecated. Please use cpp-peglib instead.

Yet another PEG (Parsing Expression Grammars) parser generator for Go.

If you need a PEG grammar checker, you may want to check peglint.

If you need a C++ version, please see cpp-peglib.

Extended features
  • Token operator: < >
  • Automatic whitespace skipping: %whitespace
  • Expression parsing for binary operators (precedence climbing method)
  • Parameterized rule or Macro
  • Word expression: %word
  • AST generation
Usage
// Create a PEG parser
parser, _ := NewParser(`
    # Simple calculator
    EXPR         ←  ATOM (BINOP ATOM)*
    ATOM         ←  NUMBER / '(' EXPR ')'
    BINOP        ←  < [-+/*] >
    NUMBER       ←  < [0-9]+ >
    %whitespace  ←  [ \t]*
    ---
    # Expression parsing option
    %expr  = EXPR   # Rule to apply 'precedence climbing method' to
    %binop = L + -  # Precedence level 1
    %binop = L * /  # Precedence level 2
`)

// Setup semantic actions
g := parser.Grammar
g["EXPR"].Action = func(v *Values, d Any) (Any, error) {
    val := v.ToInt(0)
    if v.Len() > 1 {
        ope := v.ToStr(1)
        rhs := v.ToInt(2)
        switch ope {
        case "+": val += rhs
        case "-": val -= rhs
        case "*": val *= rhs
        case "/": val /= rhs
        }
    }
    return val, nil
}
g["BINOP"].Action = func(v *Values, d Any) (Any, error) {
    return v.Token(), nil
}
g["NUMBER"].Action = func(v *Values, d Any) (Any, error) {
    return strconv.Atoi(v.Token())
}

// Parse
input := " 1 + 2 * 3 * (4 - 5 + 6) / 7 - 8 "
val, _ := parser.ParseAndGetValue(input, nil)

fmt.Println(val) // Output: -3

Parameterized Rule or Macro

# Syntax
Start      ← _ Expr
Expr       ← Sum
Sum        ← List(Product, SumOpe)
Product    ← List(Value, ProOpe)
Value      ← Number / T('(') Expr T(')')

# Token
SumOpe     ← T('+' / '-')
ProOpe     ← T('*' / '/')
Number     ← T([0-9]+)
~_         ← [ \t\r\n]*

# Macro
List(I, D) ← I (D I)*
T(x)       ← < x > _

Word expression

parser, _ := NewParser(`
    ROOT         ←  'hello' 'world'
    %whitespace  ←  [ \t\r\n]*
    %word        ←  [a-z]+
`)

parser.Parse("hello world", nil) # OK
parser.Parse("helloworld", nil)  # NG

AST generation

// Create a PEG parser
parser, _ := NewParser(`
    EXPRESSION       <-  TERM (TERM_OPERATOR TERM)*
    TERM             <-  FACTOR (FACTOR_OPERATOR FACTOR)*
    FACTOR           <-  NUMBER / '(' EXPRESSION ')'
    TERM_OPERATOR    <-  < [-+] >
    FACTOR_OPERATOR  <-  < [/*] >
    NUMBER           <-  < [0-9]+ >
    %whitespace      <-  [ \t\r\n]*
`)

// Evaluator
var eval func(ast *Ast) int
eval = func(ast *Ast) int {
    if ast.Name == "NUMBER" {
        val, _ := strconv.Atoi(ast.Token)
        return val
    } else {
        nodes := ast.Nodes
        val := eval(nodes[0])
        for i := 1; i < len(nodes); i += 2 {
            num := eval(nodes[i+1])
            ope := nodes[i].Token[0]
            switch ope {
            case '+':
                val += num
                break
            case '-':
                val -= num
                break
            case '*':
                val *= num
                break
            case '/':
                val /= num
                break
            }
        }
        return val
    }
}

// Generate AST
parser.EnableAst()
input := " 1 + 2 * 3 * (4 - 5 + 6) / 7 - 8 "
ret, _ := parser.ParseAndGetValue(input, nil)
ast := ret.(*Ast)

// Optimize AST
opt := NewAstOptimizer(nil)
ast = opt.Optimize(ast, nil)

// Evaluate AST
val := eval(ast)

fmt.Println(val) // Output: -3

TODO

  • Better error handling
  • Memoization (Packrat parsing)

License

MIT license (© 2016 Yuji Hirose)

Documentation

Overview

Example
// Create a PEG parser
parser, _ := NewParser(`
        # Grammar for simple calculator...
        EXPRESSION       <-  _ TERM (TERM_OPERATOR TERM)*
        TERM             <-  FACTOR (FACTOR_OPERATOR FACTOR)*
        FACTOR           <-  NUMBER / '(' _ EXPRESSION ')' _
        TERM_OPERATOR    <-  < [-+] > _
        FACTOR_OPERATOR  <-  < [/*] > _
        NUMBER           <-  < [0-9]+ > _
		~_               <-  [ \t]*
    `)

// Setup actions
reduce := func(v *Values, d Any) (Any, error) {
	val := v.ToInt(0)
	for i := 1; i < len(v.Vs); i += 2 {
		num := v.ToInt(i + 1)
		switch v.ToStr(i) {
		case "+":
			val += num
		case "-":
			val -= num
		case "*":
			val *= num
		case "/":
			val /= num
		}
	}
	return val, nil
}

g := parser.Grammar
g["EXPRESSION"].Action = reduce
g["TERM"].Action = reduce
g["TERM_OPERATOR"].Action = func(v *Values, d Any) (Any, error) { return v.Token(), nil }
g["FACTOR_OPERATOR"].Action = func(v *Values, d Any) (Any, error) { return v.Token(), nil }
g["NUMBER"].Action = func(v *Values, d Any) (Any, error) { return strconv.Atoi(v.Token()) }

// Parse
input := " 1 + 2 * 3 * (4 - 5 + 6) / 7 - 8 "
val, _ := parser.ParseAndGetValue(input, nil)

fmt.Println(val)
Output:

-3
Example (Combinators)
// Grammar
var EXPRESSION, TERM, FACTOR, TERM_OPERATOR, FACTOR_OPERATOR, NUMBER Rule

EXPRESSION.Ope = Seq(&TERM, Zom(Seq(&TERM_OPERATOR, &TERM)))
TERM.Ope = Seq(&FACTOR, Zom(Seq(&FACTOR_OPERATOR, &FACTOR)))
FACTOR.Ope = Cho(&NUMBER, Seq(Lit("("), &EXPRESSION, Lit(")")))
TERM_OPERATOR.Ope = Seq(Tok(Cls("-+")))
FACTOR_OPERATOR.Ope = Seq(Tok(Cls("/*")))
NUMBER.Ope = Seq(Tok(Oom(Cls("0-9"))))

EXPRESSION.WhitespaceOpe = Zom(Cls(" \t"))

// Actions
reduce := func(v *Values, d Any) (Any, error) {
	ret := v.ToInt(0)
	for i := 1; i < len(v.Vs); i += 2 {
		ope := v.ToStr(i)
		n := v.ToInt(i + 1)
		switch ope {
		case "+":
			ret += n
		case "-":
			ret -= n
		case "*":
			ret *= n
		case "/":
			ret /= n
		}
	}
	return ret, nil
}

EXPRESSION.Action = reduce
TERM.Action = reduce
TERM_OPERATOR.Action = func(v *Values, d Any) (Any, error) { return v.Token(), nil }
FACTOR_OPERATOR.Action = func(v *Values, d Any) (Any, error) { return v.Token(), nil }
NUMBER.Action = func(v *Values, d Any) (Any, error) { return strconv.Atoi(v.Token()) }

// Parse
l, v, _ := EXPRESSION.Parse(" (1 + 2 * (3 + 4)) / 5 - 6 ", nil)

fmt.Println(l)
fmt.Println(v)
Output:

27
-3
Example (ExpressionParsing)
// Create a PEG parser
parser, _ := NewParser(`
        # Grammar for simple calculator...
        EXPRESSION   <-  ATOM (BINOP ATOM)*
        ATOM         <-  NUMBER / '(' EXPRESSION ')'
        BINOP        <-  < [-+/*] >
        NUMBER       <-  < [0-9]+ >
		%whitespace  <-  [ \t]*
		---
        # Expression parsing
		%expr  = EXPRESSION
		%binop = L + -  # level 1
		%binop = L * /  # level 2
    `)

// Setup actions
g := parser.Grammar
g["EXPRESSION"].Action = func(v *Values, d Any) (Any, error) {
	val := v.ToInt(0)
	if v.Len() > 1 {
		rhs := v.ToInt(2)
		ope := v.ToStr(1)
		switch ope {
		case "+":
			val += rhs
		case "-":
			val -= rhs
		case "*":
			val *= rhs
		case "/":
			val /= rhs
		}
	}
	return val, nil
}
g["BINOP"].Action = func(v *Values, d Any) (Any, error) {
	return v.Token(), nil
}
g["NUMBER"].Action = func(v *Values, d Any) (Any, error) {
	return strconv.Atoi(v.Token())
}

// Parse
input := " 1 + 2 * 3 * (4 - 5 + 6) / 7 - 8 "
val, _ := parser.ParseAndGetValue(input, nil)

fmt.Println(val)
Output:

-3
Example (Whitespace)
// Create a PEG parser
parser, _ := NewParser(`
        # Grammar for simple calculator...
        EXPRESSION       <-  TERM (TERM_OPERATOR TERM)*
        TERM             <-  FACTOR (FACTOR_OPERATOR FACTOR)*
        FACTOR           <-  NUMBER / '(' EXPRESSION ')'
        TERM_OPERATOR    <-  < [-+] >
        FACTOR_OPERATOR  <-  < [/*] >
        NUMBER           <-  < [0-9]+ >
		%whitespace      <-  [ \t]*
    `)

// Setup actions
reduce := func(v *Values, d Any) (Any, error) {
	val := v.ToInt(0)
	for i := 1; i < len(v.Vs); i += 2 {
		num := v.ToInt(i + 1)
		switch v.ToStr(i) {
		case "+":
			val += num
		case "-":
			val -= num
		case "*":
			val *= num
		case "/":
			val /= num
		}
	}
	return val, nil
}

g := parser.Grammar
g["EXPRESSION"].Action = reduce
g["TERM"].Action = reduce
g["TERM_OPERATOR"].Action = func(v *Values, d Any) (Any, error) { return v.Token(), nil }
g["FACTOR_OPERATOR"].Action = func(v *Values, d Any) (Any, error) { return v.Token(), nil }
g["NUMBER"].Action = func(v *Values, d Any) (Any, error) { return strconv.Atoi(v.Token()) }

// Parse
input := " 1 + 2 * 3 * (4 - 5 + 6) / 7 - 8 "
val, _ := parser.ParseAndGetValue(input, nil)

fmt.Println(val)
Output:

-3

Index

Examples

Constants

View Source
const (
	WhitespceRuleName = "%whitespace"
	WordRuleName      = "%word"
	OptExpressionRule = "%expr"
	OptBinaryOperator = "%binop"
)

Variables

This section is empty.

Functions

func Apd

func Apd(ope operator) operator

func Cho

func Cho(opes ...operator) operator

func ChoCore

func ChoCore(opes []operator) operator

func Cls

func Cls(chars string) operator

func Dot

func Dot() operator

func EnableExpressionParsing

func EnableExpressionParsing(p *Parser, name string, bopinf BinOpeInfo) error

func Exp

func Exp(atom operator, binop operator, bopinf BinOpeInfo, action *Action) operator

func Ign

func Ign(ope operator) operator

func Lit

func Lit(lit string) operator

func Npd

func Npd(ope operator) operator

func Oom

func Oom(ope operator) operator

func Opt

func Opt(ope operator) operator

func Ref

func Ref(ident string, args []operator, pos int) operator

func Seq

func Seq(opes ...operator) operator

func SeqCore

func SeqCore(opes []operator) operator

func Tok

func Tok(ope operator) operator

func Usr

func Usr(fn func(s string, p int, v *Values, d Any) int) operator

func Wsp

func Wsp(ope operator) operator

func Zom

func Zom(ope operator) operator

Types

type Action

type Action func(v *Values, d Any) (Any, error)

Action

type Any

type Any interface {
}

Any

type Ast

type Ast struct {
	//Path  string
	Ln     int
	Col    int
	S      string
	Name   string
	Token  string
	Nodes  []*Ast
	Parent *Ast
	Data   interface{}
}

func (*Ast) String

func (ast *Ast) String() string

type AstOptimizer

type AstOptimizer struct {
	// contains filtered or unexported fields
}

func NewAstOptimizer

func NewAstOptimizer(exceptions []string) *AstOptimizer

func (*AstOptimizer) Optimize

func (o *AstOptimizer) Optimize(org *Ast, par *Ast) *Ast

type BinOpeInfo

type BinOpeInfo map[string]struct {
	// contains filtered or unexported fields
}

type Error

type Error struct {
	Details []ErrorDetail
}

Error

func (*Error) Error

func (e *Error) Error() string

type ErrorDetail

type ErrorDetail struct {
	Ln  int
	Col int
	Msg string
}

Error detail

func (ErrorDetail) String

func (d ErrorDetail) String() string

type Parser

type Parser struct {
	Grammar map[string]*Rule

	TracerEnter func(name string, s string, v *Values, d Any, p int)
	TracerLeave func(name string, s string, v *Values, d Any, p int, l int)
	// contains filtered or unexported fields
}

Parser

func NewParser

func NewParser(s string) (p *Parser, err error)

func NewParserWithUserRules

func NewParserWithUserRules(s string, rules map[string]operator) (p *Parser, err error)

func (*Parser) EnableAst

func (p *Parser) EnableAst() (err error)

func (*Parser) Parse

func (p *Parser) Parse(s string, d Any) (err error)

func (*Parser) ParseAndGetAst

func (p *Parser) ParseAndGetAst(s string, d Any) (*Ast, error)

func (*Parser) ParseAndGetValue

func (p *Parser) ParseAndGetValue(s string, d Any) (val Any, err error)

type Rule

type Rule struct {
	Name          string
	SS            string
	Pos           int
	Ope           operator
	Action        Action
	Enter         func(d Any)
	Leave         func(d Any)
	Message       func() (message string)
	Ignore        bool
	WhitespaceOpe operator
	WordOpe       operator

	Parameters []string

	TracerEnter func(name string, s string, v *Values, d Any, p int)
	TracerLeave func(name string, s string, v *Values, d Any, p int, l int)
	// contains filtered or unexported fields
}

Rule

func (*Rule) Label

func (o *Rule) Label() string

func (*Rule) Parse

func (r *Rule) Parse(s string, d Any) (l int, val Any, err error)

type Token

type Token struct {
	Pos int
	S   string
}

Token

type Values

type Values struct {
	SS     string
	Vs     []Any
	Pos    int
	S      string
	Choice int
	Ts     []Token
}

Semantic values

func (*Values) Len

func (v *Values) Len() int

func (*Values) ToBool

func (v *Values) ToBool(i int) bool

func (*Values) ToFloat32

func (v *Values) ToFloat32(i int) float32

func (*Values) ToFloat64

func (v *Values) ToFloat64(i int) float64

func (*Values) ToInt

func (v *Values) ToInt(i int) int

func (*Values) ToOpe

func (v *Values) ToOpe(i int) operator

func (*Values) ToStr

func (v *Values) ToStr(i int) string

func (*Values) Token

func (v *Values) Token() string

Directories

Path Synopsis
cmd

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL