parser

README

Zed parser

This directory contains the Zed parser implemented in PEG.

There is a single PEG input file that works with both pigeon, which is Go based, and pegjs, which is JavaScript based. This allows us to embed a Zed compiler into either JavaScript or Go.

The single parser file is run through the C pre-processor allowing macro and ifdef logic to create the two variants of PEG.

Install

You need pegjs, pigeon, and goimports to build the parsers. To install them, run:

go get github.com/mna/pigeon golang.org/x/tools/cmd/goimports
npm install -g pegjs

Build

To build the parsers, just run make:

make

This will run the C pre-processor to make the two PEG files and run pigeon and pegjs to create the two parsers.

Testing

The zed dev compile command can be used for easily testing the output of the Zed parser.

Development

During development, the easiest way to run the parser is with this make command at the root of this repository:

make peg

This will ensure the PEG-generated JavaScript and Go parsers are up to date with parser.peg

To update the parser and launch the zc -repl, your can run make peg-run.

Documentation

Index

• func ImproveError(err error, src string, sis []SourceInfo) error
• func NewError(src string, sis []SourceInfo, offset int) error
• func OR(a, b interface{}) interface{}
• func Parse(filename string, b []byte, opts ...Option) (interface{}, error)
• func ParseFile(filename string, opts ...Option) (i interface{}, err error)
• func ParseReader(filename string, r io.Reader, opts ...Option) (interface{}, error)
• func ParseZed(filenames []string, src string) (interface{}, error)
• type Cloner
• type Error
  • func (e *Error) Error() string
  • func (e *Error) ParseErrorContext() string
• type Option
  • func AllowInvalidUTF8(b bool) Option
  • func Debug(b bool) Option
  • func Entrypoint(ruleName string) Option
  • func GlobalStore(key string, value interface{}) Option
  • func InitState(key string, value interface{}) Option
  • func MaxExpressions(maxExprCnt uint64) Option
  • func Memoize(b bool) Option
  • func Recover(b bool) Option
  • func Statistics(stats *Stats, choiceNoMatch string) Option
• type SourceInfo
  • func ConcatSource(filenames []string, src string) (string, []SourceInfo, error)
• type Stats

Functions

func ImproveError

func ImproveError(err error, src string, sis []SourceInfo) error

ImproveError tries to improve an error from Parse. err is the error. src is the source code for which Parse return err. If src came from ConcatSource, sis is the corresponding slice of SourceInfo; otherwise, sis is nil.

func NewError

func NewError(src string, sis []SourceInfo, offset int) error

NewError returns an Error. src is the source code containing the error. If src came from ConcatSource, sis is the corresponding slice of SourceInfo; otherwise, src is nil. offset is the offset of the error within src.

func OR

func OR(a, b interface{}) interface{}

func Parse

func Parse(filename string, b []byte, opts ...Option) (interface{}, error)

Parse parses the data from b using filename as information in the error messages.

func ParseFile

func ParseFile(filename string, opts ...Option) (i interface{}, err error)

ParseFile parses the file identified by filename.

func ParseReader

func ParseReader(filename string, r io.Reader, opts ...Option) (interface{}, error)

ParseReader parses the data from r using filename as information in the error messages.

func ParseZed

func ParseZed(filenames []string, src string) (interface{}, error)

ParseZed calls ConcatSource followed by Parse. If Parse fails, it calls ImproveError.

Types

type Cloner

type Cloner interface {
	Clone() interface{}
}

Cloner is implemented by any value that has a Clone method, which returns a copy of the value. This is mainly used for types which are not passed by value (e.g map, slice, chan) or structs that contain such types.

This is used in conjunction with the global state feature to create proper copies of the state to allow the parser to properly restore the state in the case of backtracking.

type Error

type Error struct {
	Offset int // offset into original source code

	LineNum int // zero-based; omitted from formatting if negative

	Column int // zero-based
	// contains filtered or unexported fields
}

Error is a parse error with nice formatting. It includes the source code line containing the error.

func (*Error) Error

func (e *Error) Error() string

func (*Error) ParseErrorContext

func (e *Error) ParseErrorContext() string

type Option

type Option func(*parser) Option

Option is a function that can set an option on the parser. It returns the previous setting as an Option.

func AllowInvalidUTF8

func AllowInvalidUTF8(b bool) Option

AllowInvalidUTF8 creates an Option to allow invalid UTF-8 bytes. Every invalid UTF-8 byte is treated as a utf8.RuneError (U+FFFD) by character class matchers and is matched by the any matcher. The returned matched value, c.text and c.offset are NOT affected.

The default is false.

func Debug

func Debug(b bool) Option

Debug creates an Option to set the debug flag to b. When set to true, debugging information is printed to stdout while parsing.

The default is false.

func Entrypoint

func Entrypoint(ruleName string) Option

Entrypoint creates an Option to set the rule name to use as entrypoint. The rule name must have been specified in the -alternate-entrypoints if generating the parser with the -optimize-grammar flag, otherwise it may have been optimized out. Passing an empty string sets the entrypoint to the first rule in the grammar.

The default is to start parsing at the first rule in the grammar.

func GlobalStore

func GlobalStore(key string, value interface{}) Option

GlobalStore creates an Option to set a key to a certain value in the globalStore.

func InitState

func InitState(key string, value interface{}) Option

InitState creates an Option to set a key to a certain value in the global "state" store.

func MaxExpressions

func MaxExpressions(maxExprCnt uint64) Option

MaxExpressions creates an Option to stop parsing after the provided number of expressions have been parsed, if the value is 0 then the parser will parse for as many steps as needed (possibly an infinite number).

The default for maxExprCnt is 0.

func Memoize

func Memoize(b bool) Option

Memoize creates an Option to set the memoize flag to b. When set to true, the parser will cache all results so each expression is evaluated only once. This guarantees linear parsing time even for pathological cases, at the expense of more memory and slower times for typical cases.

The default is false.

func Recover

func Recover(b bool) Option

Recover creates an Option to set the recover flag to b. When set to true, this causes the parser to recover from panics and convert it to an error. Setting it to false can be useful while debugging to access the full stack trace.

The default is true.

func Statistics

func Statistics(stats *Stats, choiceNoMatch string) Option

Statistics adds a user provided Stats struct to the parser to allow the user to process the results after the parsing has finished. Also the key for the "no match" counter is set.

Example usage:

input := "input"
stats := Stats{}
_, err := Parse("input-file", []byte(input), Statistics(&stats, "no match"))
if err != nil {
    log.Panicln(err)
}
b, err := json.MarshalIndent(stats.ChoiceAltCnt, "", "  ")
if err != nil {
    log.Panicln(err)
}
fmt.Println(string(b))

type SourceInfo

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

SourceInfo holds source file offsets.

func ConcatSource

func ConcatSource(filenames []string, src string) (string, []SourceInfo, error)

ConcatSource concatenates the source files in filenames followed by src, returning the result and a corresponding slice of SourceInfos.

type Stats

type Stats struct {
	// ExprCnt counts the number of expressions processed during parsing
	// This value is compared to the maximum number of expressions allowed
	// (set by the MaxExpressions option).
	ExprCnt uint64

	// ChoiceAltCnt is used to count for each ordered choice expression,
	// which alternative is used how may times.
	// These numbers allow to optimize the order of the ordered choice expression
	// to increase the performance of the parser
	//
	// The outer key of ChoiceAltCnt is composed of the name of the rule as well
	// as the line and the column of the ordered choice.
	// The inner key of ChoiceAltCnt is the number (one-based) of the matching alternative.
	// For each alternative the number of matches are counted. If an ordered choice does not
	// match, a special counter is incremented. The name of this counter is set with
	// the parser option Statistics.
	// For an alternative to be included in ChoiceAltCnt, it has to match at least once.
	ChoiceAltCnt map[string]map[string]int
}

Stats stores some statistics, gathered during parsing