y

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Oct 16, 2017 License: Apache-2.0, BSD-3-Clause Imports: 15 Imported by: 0

Documentation

Overview

Package y converts .y (yacc[2]) source files to data suitable for a parser generator.

Changelog

2015-02-23: Added methods Parser.{AcceptsEmptyInput,SkeletonXErrors}.

2015-01-16: Added Parser.Reductions and State.Reduce0 methods.

2014-12-18: Support %precedence for better bison compatibility[5].

Index

Constants

View Source 
const (
	AssocNotSpecified = iota
	AssocLeft         // %left
	AssocRight        // %right
	AssocNone         // %nonassoc
	AssocPrecedence   // %precedence
)

Values of {AssocDef,Rule,Sym}.Associativity

Variables

This section is empty.

Functions

This section is empty.

Types

type Action 

type Action struct {
	Sym *Symbol
	// contains filtered or unexported fields
}

Action describes one cell of the parser table, ie. the action to be taken when the lookahead is Sym.

func (Action) Kind 

func (a Action) Kind() (typ, arg int)

Kind returns typ: 'a' for accept, 's' for shift, 'r' for reduce and 'g' for goto. 

For 'a' arg is not used.
For 's' arg is the state number to shift to.
For 'r' arg is the rule number to reduce.
For 'g' arg is the state number to goto.

type AssocDef 

type AssocDef struct {
	Associativity int       // One of the nonzero Assoc* constant values.
	Syms          []*Symbol // Symbols present for this association definition in the order of appearance.
}

AssocDef describes one association definition of the .y source code. For example: 

%left '+', '-'
%left '*', '/'

The above will produce two items in Parser.AssocDefs with the particular values of the associativity and precendce recorded in the Associativity and Precedence fields of the respective Syms element.

type Options 

type Options struct {
	AllowConflicts  bool      // Do not report unresolved conflicts as errors.
	AllowTypeErrors bool      // Continue even if type checks fail.
	Closures        bool      // Report non kernel items.
	LA              bool      // Report all lookahead sets.
	Report          io.Writer // If non nil, write a grammar report to Report.
	Resolved        bool      // Explain how conflicts were resolved.
	Reducible       bool      // Check if all states are reducible. (Expensive)
	XErrorsName     string    // Name used to report errors in XErrorsSrc, defaults to <xerrors>.
	XErrorsSrc      []byte    // Used to produce errors by example[1].
	// contains filtered or unexported fields
}

Options amend the behavior of the various Process* functions.

Error Examples

Error examples implement the ideas in "Generating LR Syntax Error Messages from Examples"[1]. They extend the capability of a LALR parser to produce better error messages.

XErrorSrc is a sequence of Go tokens separated by white space using the same rules as valid Go source code except that semicolon injection is not used. Comments of both short and long form are equal to white space. An example consists of an optional state set prefix followed by zero or more token specifiers followed by an error message. A state set is zero or more integer literals. Token specifier is a valid Go identifier or a Go character literal. The error message is a Go string literal. The EBNF is 

ErrorExamples = { { INT_LIT } { IDENTIFIER | CHAR_LIT } STRING_LIT } .

The identifiers used in XErrorsSrc must be those defined as tokens in the yacc file. An implicit $end token is inserted at the end of the example input if no state set is given for that example. Examples with a state set are assumed to always specify the error-triggering lookahead token as the last example token, which is usually, but not necessarily the reserved error terminal symbol. If an example has a state set but no example tokens, a $end is used as an example. For example: 

/*
	Reject empty file
*/
/* $end inserted here*/ "invalid empty input"

PACKAGE /* $end inserted here */
"Unexpected EOF"

PACKAGE ';' /* $end inserted here even though parsing stops at ';' */
`Missing package name or newline after "package"`

vs 

/*
	Reject empty file
*/
0
/* $end inserted here */ "invalid empty input"

2
PACKAGE error /* no $end inserted here */
`Missing package name or newline after "package"`

Other examples 

PACKAGE IDENT ';'
IMPORT STRING_LIT ','
"multiple imports must be separated by semicolons"

// Make the semicolon injection error a bit more user friendly.
PACKAGE ';'
`Missing package name or newline after "package"`

// A calculator parser might have error examples like
NUMBER '+' "operand expected"
NUMBER '-' error "invalid operand for subtraction"

Use a specific bad token to provide a specific message: 

// Coders frequently make this mistake.
FOO BAR BAZ "baz cannot follow bar, only qux or frob can"

Use the reserved error token to be less specific: 

// Catch any invalid token sequences after foo bar.
FOO BAR error "bar must be followed by qux or frob"

Terminate the token sequence to detect premature end of file: 

PACKAGE "missing package name"

Similar to lex[3], examples sharing the same "action" can be joined by the | operator: 

CONST  |
FUNC   |
IMPORT |
TYPE   |
VAR "package clause must be first"

It's an error if the example token sequence is accepted by the parser, ie. if it does not produce an error.

Note: In the case of example with a state set, the example tokens, except for the last one, serve only documentation purposes. Only the combination of a state and a particular lookahead is actually considered by the parser.

Examples without a state set are processed differently and all the example tokens matter. An attempt is made to find the applicable state set automatically, but this computation is not yet completely functional and possibly only a subset of the real error states are produced.

type Parser 

type Parser struct {
	AssocDefs      []*AssocDef           // %left, %right, %nonassoc definitions in the order of appearance in the source code.
	ConflictsRR    int                   // Number of reduce/reduce conflicts.
	ConflictsSR    int                   // Number of shift/reduce conflicts.
	Definitions    []*yparser.Definition // All definitions.
	ErrorVerbose   bool                  // %error-verbose is present.
	LiteralStrings map[string]*Symbol    // See Symbol.LiteralString field.
	Prologue       string                // Collected prologue between the %{ and %} marks.
	Rules          []*Rule               // Rules indexed by rule number.
	Start          string                // Name of the start production.
	States         []*State              // Parser states indexed by state number.
	Syms           map[string]*Symbol    // Symbols indexed by name, eg. "IDENT", "Expression" or "';'".
	Table          [][]Action            // Indexed by state number.
	Tail           string                // Everyting after the second %%, if present.
	Union          *ast.StructType       // %union as Go AST.
	UnionSrc       string                // %union as Go source form.
	XErrors        []XError              // Errors by example[1] descriptions.
	// contains filtered or unexported fields
}

Parser describes the resulting parser. The intended client is a parser generator (like eg. [0]) producing the final Go source code.

func ProcessAST 

func ProcessAST(fset *token.FileSet, ast *yparser.Specification, opts *Options) (*Parser, error)

ProcessAST processes yacc source code parsed in ast. It returns a *Parser or an error, if any.

func ProcessFile 

func ProcessFile(fset *token.FileSet, fname string, opts *Options) (*Parser, error)

ProcessFile processes yacc source code in a named file. It returns a *Parser or an error, if any.

func ProcessSource 

func ProcessSource(fset *token.FileSet, fname string, src []byte, opts *Options) (*Parser, error)

ProcessSource processes yacc source code in src. It returns a *Parser or an error, if any.

func (*Parser) AcceptsEmptyInput 

func (p *Parser) AcceptsEmptyInput() bool

AcceptsEmptyInput returns whether the token string [$end] is accepted by the grammar.

func (*Parser) Reductions 

func (p *Parser) Reductions() map[int][]int

Reductions returns a mapping rule# -> []state#. The slice is a sorted set of states in which the corresponding rule is reduced.

func (*Parser) SkeletonXErrors 

func (p *Parser) SkeletonXErrors(w io.Writer) error

SkeletonXErrors writes an automatically generated errors by example file to w.

type Rule 

type Rule struct {
	Action          *yparser.Action // The semantic action associated with the rule, if any. If present then also the last element of Body.
	Associativity   int             // One of the assoc* constants.
	Body            []interface{}   // Rule components - int, string or *yparser.Action
	Components      []string        // Textual forms of the rule components, for example []string{"IDENT", "';'"}
	ExplicitPrecSym *Symbol         // Symbol used in the optional %prec sym clause, if present.
	MaxParentDlr    int             // See the Rule type docs for details.
	Name            *yparser.Token  // The rule name token, if any (otherwise the rule starts with "|").
	Parent          *Rule           // Non nil if a synthetic rule.
	PrecSym         *Symbol         // Effective %prec symbol used, if any.
	Precedence      int             // -1 if no precedence assigned.
	RuleNum         int             // Zero based rule number. Rule #0 is synthetic.
	Sym             *Symbol         // LHS of the rule.
	Token           *yparser.Token  // yparser.IDENT or "|"
	// contains filtered or unexported fields
}

Rule describes a single yacc rule, for example (in source form) 

Start:
	Prologue Body Epilogue
	{
		$$ = &ast{$1, $2, $3}
	}

Inner rule actions

A rule can prescribe semantic actions not only at the end. For example 

Foo:
	Bar
	{
		initBar($1)
	}
	Qux
	{
		handleQux($3)
	}

Such constructs are rewritten as 

$@1:
	{
		initBar($1)
	}

Foo:
	Bar $@1 Qux
	{
		handleQux($3)
	}

The $@1 and similar is a synthetic rule and such have non nil Parent. MaxParentDlr is used to check that the semantic action does not access parent values not yet shifted to the parse stack as well as to compute the position of the $n thing on the parse stack. See also [4].

func (*Rule) Actions 

func (r *Rule) Actions() string

Actions returns the textual representation of r.Actions combined.

type State 

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

State represents one state of the parser.

func (*State) Reduce0 

func (s *State) Reduce0(r *Rule) []*Symbol

Reduce0 returns an example of a string required to reduce rule r in state s starting at state 0. If states s does not reduce rule r the string is empty.

Note: Invalid grammars and grammars with conflicts may have not all states reachable and/or not all productions reducible.

func (*State) Syms0 

func (s *State) Syms0() ([]*Symbol, *Symbol)

Syms0 returns an example of a string and a lookahead, if any, required to get to state s starting at state 0. If s is shifted into the lookahead is nil.

Note: Invalid grammars and grammars with conflicts may have not all states reachable.

To construct an example of a string for which the parser enters state s: 

syms, la := s.Syms0()
if la != nil {
	syms = append(syms, la)
}

type Symbol 

type Symbol struct {
	Associativity    int       // One of the assoc* constants.
	ExplicitValue    int       // Explicit numeric value of the symbol or -1 if none.
	IsLeftRecursive  bool      // S: S ... ;
	IsRightRecursive bool      // S: ... S ;
	IsTerminal       bool      // Whether this is a terminal symbol.
	LiteralString    string    // See the "LiteralString field" part of the Symbol godocs.
	Name             string    // Textual value of the symbol, for example "IDENT" or "';'".
	Pos              token.Pos // Position where the symbol was firstly introduced.
	Precedence       int       // -1 of no precedence assigned.
	Rules            []*Rule   // Productions associated with this symbol.
	Type             string    // For example "int", "float64" or "foo", but possibly also "".
	Value            int       // Assigned numeric value of the symbol.
	// contains filtered or unexported fields
}

Symbol represents a terminal or non terminal symbol. A special end symbol has Name "$end" and represents the EOF token.

LiteralString field

Some parser generators accept an optional literal string token associated with a token definition. From [6]: 

You can associate a literal string token with a token type name by
writing the literal string at the end of a %token declaration which
declares the name. For example:

	%token arrow "=>"

For example, a grammar for the C language might specify these names
with equivalent literal string tokens:

	%token  <operator>  OR      "||"
	%token  <operator>  LE 134  "<="
	%left  OR  "<="

Once you equate the literal string and the token name, you can use them
interchangeably in further declarations or the grammar rules. The yylex
function can use the token name or the literal string to obtain the
token type code number (see Calling Convention). Syntax error messages
passed to yyerror from the parser will reference the literal string
instead of the token name.

The LiteralString captures the value of other definitions as well, namely also for %type definitions. 

%type CommaOpt "optional comma"

%%

CommaOpt:
	/* empty */
|	','

func (*Symbol) DerivesEmpty 

func (s *Symbol) DerivesEmpty() bool

DerivesEmpty returns whether s derives ε.

func (*Symbol) IsEmpty 

func (s *Symbol) IsEmpty() bool

IsEmpty reports whether s derives only ε.

func (*Symbol) MinString 

func (s *Symbol) MinString() (r []*Symbol)

MinString returns an example of a string of symbols which can be reduced to s. If s is a terminal symbol the result is s. If the only way to express some non terminal s includes s itself then nil is returned (and the grammar is invalid).

func (*Symbol) String 

func (s *Symbol) String() string

String implements fmt.Stringer.

type XError 

type XError struct {
	Stack     []int   // Parser states stack, potentially partial, of the error event. TOS is Stack[len(Stack)-1].
	Lookahead *Symbol // Error lookahead symbol. Nil if LA is the reserved error symbol.
	Msg       string  // Textual representation of the error condition.
}

XError describes the parser state for an error by example. See [1].

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.