trans

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Jun 5, 2023 License: MIT Imports: 10 Imported by: 3

Documentation

Overview

Package trans provides syntax-directed translations of parse trees for the ictiobus parser generator. It is involved in the final stage of input analysis. A complete SDTS's Evaluate() function is called with a parse.Tree as input to produce the final result of the analysis, the intermediate representation.

At this time, while there are function stubs and supposed availability of inherited attributes in an SDTS, only S-attributed attribute grammars are supported at this time. Attempting to use inherited attributes will result in untested and undefined behavior.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Validate added in v1.0.0 

func Validate(sdts SDTS, g grammar.CFG, attribute string, debug ValidationOptions, fakeValProducer ...map[string]func() string) (warns []string, err error)

Validate runs the SDTS on a fake parse tree derived from the grammar. The given attribute will be attempted to be evaluated on the root node.

It will use fake value producer, if provided, to generate lexemes for terminals in the tree; otherwise contrived values will be used.

Types

type AnnotatedTree added in v1.0.0 

type AnnotatedTree struct {
	// Terminal is whether this node is for a terminal symbol.
	Terminal bool

	// Symbol is the symbol at this node's head.
	Symbol string

	// Source is only available when Terminal is true.
	Source lex.Token

	// Children is all children of the parse tree.
	Children []*AnnotatedTree

	// Attributes is the data for attributes at the given position in the parse
	// tree.
	Attributes nodeAttrs
}

AnnotatedTree is a parse tree annotated with attributes at every node. These attributes are set by calling hook functions on other attributes, and doing so succesively is what eventually implements a complete syntax-directed translation.

Some attributes are built in; these begin with a $. This includes $id, which is the ID of a node and is defined on all nodes; $ft, which is the first token lexed for a node and is defined for all nodes except for terminal nodes produced by an epsilon production; $text, which is the lexed text and is defined only for terminal symbol nodes.

An AnnotatedTree can be created from a parse.Tree by calling Annotate.

func ATLeaf added in v1.0.0 

func ATLeaf(id uint64, term string, t ...lex.Token) *AnnotatedTree

ATLeaf is a convenience function for creating a new AnnotatedTree that represents a terminal symbol. The Source token is set to t if one is provided. Note that t's type being ...Token is simply to make it optional; only the first such provided t is examined. The given id must be unique for the entire tree.

func ATNode added in v1.0.0 

func ATNode(id uint64, nt string, children ...*AnnotatedTree) *AnnotatedTree

ATNode is a convenience function for creating a new AnnotatedTree that represents a non-terminal symbol with minimal properties. The given id must be unique for the entire tree.

func Annotate added in v0.8.0 

func Annotate(root parse.Tree) AnnotatedTree

Annotate adds attribute fields to the given parse tree to convert it to an AnnotatedTree. Returns an AnnotatedTree with only auto fields set ('$text' for terminals, '$id' for all nodes, and '$ft' for all nodes except epsilon terminal nodes, representing the first Token of the expression).

func (AnnotatedTree) AttributeValueOf added in v1.0.0 

func (apt AnnotatedTree) AttributeValueOf(ref AttrRef) (val interface{}, ok bool)

AttributeValueOf returns the value of the named attribute in the node referred to by ref. Additionally, a second 'ok' value is returned that specifies whether ref refers to an existing attribute in the node whose relation to apt matches that specified in ref; if the returned 'ok' value is false, val should be considered a nil value and unsafe to use.

func (AnnotatedTree) AttributesOf added in v1.0.0 

func (apt AnnotatedTree) AttributesOf(rel NodeRelation) (attributes nodeAttrs, ok bool)

AttributesOf gets the Attributes of the node referred to by the given AttrRelNode value. For valid relations (those for which apt has a match for among itself (for the head symbol) and children (for the produced symbols)), the Attributes of the specified node are returned, as well as a second 'ok' value which will be true. If rel specifies a node that doesn't exist relative to apt, then the second value will be false and the returned node attributes will be nil.

func (*AnnotatedTree) First added in v1.0.0 

func (apt *AnnotatedTree) First() lex.Token

Returns the first token of the expression represented by this node in the parse tree. All nodes have a first token accessible via the special predefined attribute '$ft'; this function serves as a shortcut to getting the value from the node attributes with casting and sanity checking handled.

Epsilons are special and return nil. Non-terminals which only have an epsilon children also return nil.

Call on pointer because it may update $first if not already set.

func (AnnotatedTree) ID added in v1.0.0 

func (apt AnnotatedTree) ID() aptNodeID

ID returns the ID of this node in the parse tree. All nodes have an ID accessible via the special predefined attribute '$id'; this function serves as a shortcut to getting the value from the node attributes with casting and sanity checking handled.

If for whatever reason the ID has not been set on this node, IDZero is returned.

func (AnnotatedTree) RelativeNode added in v1.0.0 

func (apt AnnotatedTree) RelativeNode(rel NodeRelation) (related *AnnotatedTree, ok bool)

RelativeNode returns the node pointed to by rel. Specifically, it returns the node that is related to apt in the way specified by rel, which can be at most one node as per the definition of rel's type.

RelHead will cause apt itself to be returned; all others select a child node.

A second 'ok' value is returned. This value is true if rel is a relation that exists in apt. If rel specifies a node that does not exist, the ok value will be false and the returned related node should not be used.

func (AnnotatedTree) Rule added in v1.0.0 

func (apt AnnotatedTree) Rule() (head string, prod []string)

Rule returns the head and production of the grammar rule associated with the creation of this node in the parse tree. If apt is for a terminal, prod will be empty.

func (AnnotatedTree) String added in v1.0.0 

func (apt AnnotatedTree) String() string

String returns a string representation of the APT.

func (AnnotatedTree) SymbolOf added in v1.0.0 

func (apt AnnotatedTree) SymbolOf(rel NodeRelation) (symbol string, ok bool)

SymbolOf returns the symbol of the node referred to by rel. Additionally, a second 'ok' value is returned that specifies whether a node matches rel. Iff the second value is false, the first value should not be relied on.

type AttrRef 

type AttrRef struct {
	Rel  NodeRelation
	Name string
}

AttrRef contains no uncomparable attributes and can be assigned/copied directly.

func (AttrRef) ResolveSymbol added in v0.8.0 

func (ar AttrRef) ResolveSymbol(g grammar.CFG, head string, prod grammar.Production) (string, error)

ResolveSymbol finds the name of the symbol being referred to in a grammar production rule. Head is the head symbol of the rule, prod is the production of that rule.

If the AttrRef does not refer to any symbol in the rule, a blank string and a non-nil error is returned.

func (AttrRef) String 

func (ar AttrRef) String() string

String returns the string representation of an AttrRef.

type Event added in v1.0.0 

type Event struct {

	// Type gives the type of the event that has occurred.
	Type EventType

	// ParseTree is a pointer to the original parse tree passed to the
	// translation scheme for execution.
	ParseTree *parse.Tree

	// Tree is a pointer to the root node of the full annotated parse tree that
	// the translation scheme is being executed on.
	Tree *AnnotatedTree

	// Hook contains information on the hook that was called. It will only
	// contain valid values when Type is EventHookCall.
	Hook *struct {
		// Name is the name of the hook that was called.
		Name string

		// Args contains the arguments that were passed to the hook when calling
		// it, in the order they were given.
		Args []struct {
			// Ref is a reference to the attribute whose value was used as the
			// argument value, relative to Node of the Hook.
			Ref AttrRef

			// Value is the value of the argument.
			Value interface{}
		}

		// Node is a pointer to the node of the tree that the hook was executed
		// on.
		Node *AnnotatedTree

		// Target is a reference to the attribute that the result of the hook
		// was assigned to. It is relative to Node.
		Target AttrRef

		// Result contains the return values of the called hook.
		Result struct {

			// Value is the main value returned by the hook. By convention, this
			// is only valid if Error is nil, but it is up to the hook
			// implementation to determine that.
			Value interface{}

			// Error is the error value returned by the hook.
			Error error
		}
	}
}

Event holds information on a notable event that occurs as part of execution of a translation scheme. It is the main argument for calls to a listener given with RegisterListener.

type EventType added in v1.0.0 

type EventType int

EventType is a type of notable event that occurs as part of execution of a translation scheme. It is used as the Type of an Event to indicate which of its arguments are valid. 

const (
	// EventAnnotation events are emitted immediately after the tree from the
	// parsing phase has been successfully annotated with built-in properties.
	// This will be before any event hook is called on the annotated tree.
	EventAnnotation EventType = iota

	// EventHookCall events are emitted after a hook completes execution either
	// successfully or with an error. It is emitted even if the hook returned an
	// error, however it is *not* emitted if a hook panics.
	EventHookCall
)

type Hook added in v0.8.0 

type Hook func(info SetterInfo, args []interface{}) (interface{}, error)

Hook takes arguments from other attributes in an annotated parse tree and returns a value to set another attribute to. It can return an error if it encounters any issues.

type HookMap added in v0.8.0 

type HookMap map[string]Hook

HookMap is a mapping of hook names to hook functions. This is used for defining implementation functions for hooks named in a FISHI specification.

type NodeRelation 

type NodeRelation struct {
	// Type is the type of the relation.
	Type NodeRelationType

	// Index specifies which of the nodes of the given type that the relation
	// points to. If it is RelHead, this will be 0.
	Index int
}

NodeRelation is a relation to a symbol in a node of an annotated parse tree. It is either the head symbol of the node itself, or one of the symbols in the production.

func NRHead added in v1.0.0 

func NRHead() NodeRelation

NRHead is a convenience function for creating a NodeRelation whose type is RelHead and whose index is 0.

func NRNonTerminal added in v1.0.0 

func NRNonTerminal(n int) NodeRelation

NRNonTerminal is a convenience function for creating a NodeRelation whose type is RelNonTerminal and whose index is the one provided.

func NRSymbol added in v1.0.0 

func NRSymbol(n int) NodeRelation

NRSymbol is a convenience function for creating a NodeRelation whose type is RelSymbol and whose index is the one provided.

func NRTerminal added in v1.0.0 

func NRTerminal(n int) NodeRelation

NRTerminal is a convenience function for creating a NodeRelation whose type is RelTerminal and whose index is the one provided.

func (NodeRelation) String 

func (nr NodeRelation) String() string

String returns the string representation of a NodeRelation.

func (NodeRelation) ValidFor 

func (nr NodeRelation) ValidFor(head string, prod []string) bool

ValidFor returns whether the given node relation refers to a valid and existing node when applied to a node in parse tree that is the result of parsing production head -> production.

type NodeRelationType 

type NodeRelationType int

NodeRelationType is the type of a NodeRelation. 

const (
	RelHead NodeRelationType = iota
	RelTerminal
	RelNonTerminal
	RelSymbol
)

func (NodeRelationType) GoString 

func (nrt NodeRelationType) GoString() string

GoString returns the go string representation of a NodeRelationType.

func (NodeRelationType) String 

func (nrt NodeRelationType) String() string

String returns the string representation of a NodeRelationType.

type SDTS added in v0.8.0 

type SDTS interface {
	// Evaluate takes a parse tree and executes the semantic actions defined as
	// SDDBindings for a node for each node in the tree and on completion,
	// returns the requested attributes values from the root node. Execution
	// order is automatically determined by taking the dependency graph of the
	// SDTS; cycles are not supported. Do note that this does not require the
	// SDTS to be S-attributed or L-attributed, only that it not have cycles in
	// its value dependency graph.
	//
	// Warn errors are provided in the slice of error and can be populated
	// regardless of whether the final (actual) error is non-nil.
	Evaluate(tree parse.Tree, attributes ...string) (vals []interface{}, warns []error, err error)

	// SetHooks sets the hook table for mapping SDTS hook names as used in a
	// call to BindSynthesizedAttribute or BindInheritedAttribute to their
	// actual implementations.
	//
	// Because the map from strings to function pointers, this hook map must be
	// set at least once before the SDTS is used. It is recommended to set it
	// every time the SDTS is loaded as soon as it is loaded.
	//
	// Calling it multiple times will add to the existing hook table, not
	// replace it entirely. If there are any duplicate hook names, the last one
	// set will be the one that is used.
	SetHooks(hooks HookMap)

	// BindI creates a new SDTS binding for setting the value of an inherited
	// attribute with name attrName. The production that the inherited attribute
	// is set on is specified with forProd, which must have its Type set to
	// something other than RelHead (inherited attributes can be set only on
	// production symbols).
	//
	// Inherited properties on SDTSs are not supported or tested at this time.
	// This function should only be called for experimental purposes.
	//
	// The binding applies only on nodes in the parse tree created by parsing
	// the grammar rule productions with head symbol head and production symbols
	// prod.
	//
	// The AttributeSetter bound to hook is called when the inherited value
	// attrName is to be set, in order to calculate the new value. Attribute
	// values to pass in as arguments are specified by passing references to the
	// node and attribute name whose value to retrieve in the withArgs slice.
	// Explicitlygiving the referenced attributes in this fashion makes it easy
	// to determine the dependency graph for later execution.
	BindI(head string, prod []string, attrName string, hook string, withArgs []AttrRef, forProd NodeRelation) error

	// Bind creates a new SDTS binding for setting the value of a synthesized
	// attribute with name attrName. The attribute is set on the symbol at the
	// head of the rule that the binding is being created for.
	//
	// The binding will be applied to nodes in the parse tree created by parsing
	// the grammar rule productions with head symbol head and production symbols
	// prod.
	//
	// The Hook implementation bound to hook is called when the synthesized
	// value attrName is to be set, in order to calculate the new value.
	// Attribute values to pass in as arguments are specified by passing
	// references to the node and attribute name whose value to retrieve in the
	// withArgs slice. Explicitly giving the referenced attributes in this
	// fashion makes it easy to determine the dependency graph for later
	// execution.
	Bind(head string, prod []string, attrName string, hook string, withArgs []AttrRef) error

	// String returns a string representation of the SDTS.
	String() string

	// RegisterListener registers a callback to be executed whenever an event
	// occurs in the translation scheme. This includes annotation of the parse
	// tree and execution of a hook function and may in the future be extended
	// to include other events. This can be useful for debugging.
	RegisterListener(func(e Event))
}

SDTS is a series of syntax-directed translations bound to syntactic rules of a grammar. It is used for evaluation of a parse tree into an intermediate representation, or for direct execution.

This is a representation of the additions to a grammar which would make it an attribute gramamr.

func NewSDTS 

func NewSDTS() SDTS

NewSDTS creates a new, empty Syntax-Directed Translation Scheme.

type SetterInfo 

type SetterInfo struct {
	// The name of the grammar symbol of the particular node that the attribute
	// is being set on.
	GrammarSymbol string

	// The first token of the grammar symbol that the attribute is being set on.
	FirstToken lex.Token

	// The name of the attribute being set.
	Name string

	// Whether the attribute is a synthetic attribute.
	Synthetic bool
}

SetterInfo is struct passed to all bound hooks in a translation scheme to provide information on what is being set. It includes the grammar symbol of the node it is being set for, the first token of that symbol as it was originally lexed, the name of the attribute that the return value of the hook will be assigned to, and whether the attribute is synthetic.

type ValidationOptions 

type ValidationOptions struct {
	// ParseTrees is whether to include parse trees in error output.
	ParseTrees bool

	// FullDepGraphs is whether to include full dependency graphs in error
	// output.
	FullDepGraphs bool

	// ShowAllErrors is whether to show all validation errors in error output.
	// If false, only the first error (after any skipped) will be shown.
	ShowAllErrors bool

	// SkipErrors is the number of initial errors to skip in error output, if
	// any.
	SkipErrors int
}

ValidationOptions is a struct passed to SDTS.Validate that selects the items to be included in the text of returned errors when problems are encountered.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.