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 ¶
- Constants
- func Apd(ope operator) operator
- func Cho(opes ...operator) operator
- func ChoCore(opes []operator) operator
- func Cls(chars string) operator
- func Dot() operator
- func EnableExpressionParsing(p *Parser, name string, bopinf BinOpeInfo) error
- func Exp(atom operator, binop operator, bopinf BinOpeInfo, action *Action) operator
- func Ign(ope operator) operator
- func Lit(lit string) operator
- func Npd(ope operator) operator
- func Oom(ope operator) operator
- func Opt(ope operator) operator
- func Ref(ident string, args []operator, pos int) operator
- func Seq(opes ...operator) operator
- func SeqCore(opes []operator) operator
- func Tok(ope operator) operator
- func Usr(fn func(s string, p int, v *Values, d Any) int) operator
- func Wsp(ope operator) operator
- func Zom(ope operator) operator
- type Action
- type Any
- type Ast
- type AstOptimizer
- type BinOpeInfo
- type Error
- type ErrorDetail
- type Parser
- type Rule
- type Token
- type Values
Examples ¶
Constants ¶
View Source
const ( WhitespceRuleName = "%whitespace" WordRuleName = "%word" OptExpressionRule = "%expr" OptBinaryOperator = "%binop" )
Variables ¶
This section is empty.
Functions ¶
func EnableExpressionParsing ¶
func EnableExpressionParsing(p *Parser, name string, bopinf BinOpeInfo) error
func Exp ¶
func Exp(atom operator, binop operator, bopinf BinOpeInfo, action *Action) operator
Types ¶
type Ast ¶
type AstOptimizer ¶
type AstOptimizer struct {
// contains filtered or unexported fields
}
func NewAstOptimizer ¶
func NewAstOptimizer(exceptions []string) *AstOptimizer
type BinOpeInfo ¶
type BinOpeInfo map[string]struct { // contains filtered or unexported fields }
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 NewParserWithUserRules ¶
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
Source Files
Directories
Click to show internal directories.
Click to hide internal directories.