tokenstream

README

tokenstream

This project generates a string of non-terminal symbols (tokens) that parses to a given non-terminal in a context-free grammar.

• Parser: (tokens, grammar) -> tree
• Unparser: (tree, grammar) -> tokens
• this project: (non-terminal, grammar) -> tokens

Parsers take a string of tokens (and a grammar) and output a syntax or parse tree. Unparsers do the reverse and take a tree (and a grammar) and output a string of tokens through a simple walk through the tree.

This project takes a non-terminal (and a grammar) and directly outputs a string of terminals, saving memory by not building the entire tree.

Documentation

Index

• type Grammar
  • func ParseCFG(grammar io.Reader) (Grammar, error)
  • func ParseCFGLines(grammar io.Reader) (Grammar, error)
• type ProductionRule
• type Symbol
• type TokenStream
  • func MakeTokenStream(g *Grammar, startSymbol string) TokenStream
  • func (t *TokenStream) Next() string
  • func (t *TokenStream) Produce(stopAfter uint) string

Types

type Grammar

type Grammar struct {
	// Productions is a map from a non-terminal (LHS) to its set of production rules (RHS)
	Productions map[string][]ProductionRule
}

Grammar represents a context-free grammar.

func ParseCFG

func ParseCFG(grammar io.Reader) (Grammar, error)

ParseCFG parses a CFG from a reader.

It expects rules in the form of rule = <lhs> "->" <rhs> * ("|" <rhs>) ";"

func ParseCFGLines

func ParseCFGLines(grammar io.Reader) (Grammar, error)

ParseCFGLines parses a CFG from a reader.

It expects one rule per line in the format rule = <lhs> "->" <rhs> * ("|" <rhs>) <newline>

type ProductionRule

type ProductionRule []Symbol

ProductionRule is the right-hand-side of a production

type Symbol

type Symbol struct {
	Terminal bool
	Value    string
}

Symbol represents a symbol in a Grammar, which can be either terminal or non-terminal

type TokenStream

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

TokenStream produces a string of tokens from a grammar

func MakeTokenStream

func MakeTokenStream(g *Grammar, startSymbol string) TokenStream

MakeTokenStream creates a TokenStream for a Grammar and start symbol.

func (*TokenStream) Next

func (t *TokenStream) Next() string

Next gets the next token

func (*TokenStream) Produce

func (t *TokenStream) Produce(stopAfter uint) string

Produce generates a string of tokens but stops after a length limit is reached. The length of the returned string may exceed stopAfter.