bsr

Documentation

Overview

Package bsr implements a Binary Subtree Representation set as defined in

Scott et al
Derivation representation using binary subtree sets,
Science of Computer Programming 175 (2019)

Index

• type BSR
  • func (b BSR) Alternate() int
  • func (b BSR) GetAllNTChildren() [][]BSR
  • func (b BSR) GetNTChild(nt symbols.NT, i int) BSR
  • func (b BSR) GetNTChildI(i int) BSR
  • func (b BSR) GetNTChildren(nt symbols.NT, i int) []BSR
  • func (b BSR) GetNTChildrenI(i int) []BSR
  • func (b BSR) GetTChildI(i int) *token.Token
  • func (b BSR) LeftExtent() int
  • func (b BSR) Pivot() int
  • func (b BSR) RightExtent() int
  • func (b BSR) String() string
• type BSRs
  • func (bs BSRs) Len() int
  • func (bs BSRs) Less(i, j int) bool
  • func (bs BSRs) Swap(i, j int)
• type Set
  • func New(startSymbol symbols.NT, l *lexer.Lexer) *Set
  • func (s *Set) Add(l slot.Label, i, k, j int)
  • func (s *Set) AddEmpty(l slot.Label, i int)
  • func (s *Set) Contain(nt symbols.NT, left, right int) bool
  • func (s *Set) Dump()
  • func (s *Set) GetAll() (bsrs []BSR)
  • func (s *Set) GetAllStrings(str symbols.Symbols, lext, rext int) (strs []*stringBSR)
  • func (s *Set) GetRightExtent() int
  • func (s *Set) GetRoot() BSR
  • func (s *Set) GetRoots() (roots []BSR)
  • func (s *Set) IsAmbiguous() bool
  • func (s *Set) ReportAmbiguous()
  • func (pf *Set) ToSPPF() *sppf.SymbolNode

Types

type BSR

type BSR struct {
	Label slot.Label
	// contains filtered or unexported fields
}

BSR is the binary subtree representation of a parsed nonterminal

func (BSR) Alternate

func (b BSR) Alternate() int

Alternate returns the index of the grammar rule alternate.

func (BSR) GetAllNTChildren

func (b BSR) GetAllNTChildren() [][]BSR

GetAllNTChildren returns all the NT Children of b. If an NT child of b has ambiguous parses then all parses of that child are returned.

func (BSR) GetNTChild

func (b BSR) GetNTChild(nt symbols.NT, i int) BSR

GetNTChild returns the BSR of occurrence i of nt in s. GetNTChild fails if s has ambiguous subtrees of occurrence i of nt.

func (BSR) GetNTChildI

func (b BSR) GetNTChildI(i int) BSR

GetNTChildI returns the BSR of NT symbol[i] in the BSR set. GetNTChildI fails if the BSR set has ambiguous subtrees of NT i.

func (BSR) GetNTChildren

func (b BSR) GetNTChildren(nt symbols.NT, i int) []BSR

GetNTChildren returns all the BSRs of occurrence i of nt in s

func (BSR) GetNTChildrenI

func (b BSR) GetNTChildrenI(i int) []BSR

GetNTChildrenI returns all the BSRs of NT symbol[i] in s

func (BSR) GetTChildI

func (b BSR) GetTChildI(i int) *token.Token

GetTChildI returns the terminal symbol at position i in b. GetTChildI panics if symbol i is not a valid terminal

func (BSR) LeftExtent

func (b BSR) LeftExtent() int

LeftExtent returns the left extent of the BSR in the stream of tokens

func (BSR) Pivot

func (b BSR) Pivot() int

Pivot returns the pivot of the BSR

func (BSR) RightExtent

func (b BSR) RightExtent() int

RightExtent returns the right extent of the BSR in the stream of tokens

func (BSR) String

func (b BSR) String() string

type BSRs

type BSRs []BSR

func (BSRs) Len

func (bs BSRs) Len() int

BSRs Sort interface

func (BSRs) Less

func (bs BSRs) Less(i, j int) bool

func (BSRs) Swap

func (bs BSRs) Swap(i, j int)

type Set

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

Set contains the set of Binary Subtree Representations (BSR).

func New

func New(startSymbol symbols.NT, l *lexer.Lexer) *Set

New returns a new initialised BSR Set

func (*Set) Add

func (s *Set) Add(l slot.Label, i, k, j int)

Add a bsr to the set. (i,j) is the extent. k is the pivot.

func (*Set) AddEmpty

func (s *Set) AddEmpty(l slot.Label, i int)

AddEmpty adds a grammar slot: X : ϵ•

func (*Set) Contain

func (s *Set) Contain(nt symbols.NT, left, right int) bool

Contain returns true iff the BSR Set contains the NT symbol with left and right extent.

func (*Set) Dump

func (s *Set) Dump()

Dump prints all the NT and string elements of the BSR set

func (*Set) GetAll

func (s *Set) GetAll() (bsrs []BSR)

GetAll returns all BSR grammar slot entries

func (*Set) GetAllStrings

func (s *Set) GetAllStrings(str symbols.Symbols, lext, rext int) (strs []*stringBSR)

GetAllStrings returns all string elements with symbols = str, left extent = lext and right extent = rext

func (*Set) GetRightExtent

func (s *Set) GetRightExtent() int

GetRightExtent returns the right extent of the BSR set

func (*Set) GetRoot

func (s *Set) GetRoot() BSR

GetRoot returns the root of the parse tree of an unambiguous parse. GetRoot fails if the parse was ambiguous. Use GetRoots() for ambiguous parses.

func (*Set) GetRoots

func (s *Set) GetRoots() (roots []BSR)

GetRoots returns all the roots of parse trees of the start symbol of the grammar.

func (*Set) IsAmbiguous

func (s *Set) IsAmbiguous() bool

IsAmbiguous returns true if the BSR set does not have exactly one root, or if any BSR in the set has an NT symbol, which does not have exactly one sub-tree.

func (*Set) ReportAmbiguous

func (s *Set) ReportAmbiguous()

ReportAmbiguous lists the ambiguous subtrees of the parse forest

func (*Set) ToSPPF

func (pf *Set) ToSPPF() *sppf.SymbolNode