y

package module
v0.0.1 Latest Latest
Warning

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

Go to latest
Published: Dec 19, 2020 License: BSD-3-Clause Imports: 15 Imported by: 0

README

github.com/cznic/y has moved to modernc.org/y (vcs).

Please update your import paths to modernc.org/y.

This repo is now archived.

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].

Example
p, err := ProcessSource(
	token.NewFileSet(),
	"example.y",
	[]byte(`
// ----------------------------------------------------------------- yacc code
//

%token NUM

%left '+'
%left '*'

%%

E: E '*' E
|  E '+' E
|  NUM

// ---------------------------------------------------------------------------

`),
	&Options{
		Closures: true,
		Report:   os.Stdout,
		Resolved: true,
		XErrorsSrc: []byte(`
// ------------------------------------------------------------ error examples
//

'+' |
'-' "unary operator not supported"

NUM '+' |
NUM '*' "missing operand"

NUM '/' |
NUM '-' "binary operator not supported"

NUM error "expected operator"

error "expected number"

// ---------------------------------------------------------------------------

`),
	})
if err != nil {
	panic(err)
}
fmt.Printf("XErrors\n")
for i, v := range p.XErrors {
	fmt.Printf("%d: %v lookahead %q, msg %q\n", i, v.Stack, v.Lookahead, v.Msg)
}
Output:

state 0 //

    0 $accept: . E
    1 E: . E '*' E  // assoc %left, prec 2
    2 E: . E '+' E  // assoc %left, prec 1
    3 E: . NUM

    NUM  shift, and goto state 2

    E  goto state 1

state 1 // NUM [$end]

    0 $accept: E .  [$end]
    1 E: E . '*' E  // assoc %left, prec 2
    2 E: E . '+' E  // assoc %left, prec 1

    $end  accept
    '*'   shift, and goto state 3
    '+'   shift, and goto state 4

state 2 // NUM

    3 E: NUM .  [$end, '*', '+']

    $end  reduce using rule 3 (E)
    '*'   reduce using rule 3 (E)
    '+'   reduce using rule 3 (E)

state 3 // NUM '*'

    1 E: . E '*' E  // assoc %left, prec 2
    1 E: E '*' . E  // assoc %left, prec 2
    2 E: . E '+' E  // assoc %left, prec 1
    3 E: . NUM

    NUM  shift, and goto state 2

    E  goto state 6

state 4 // NUM '+'

    1 E: . E '*' E  // assoc %left, prec 2
    2 E: . E '+' E  // assoc %left, prec 1
    2 E: E '+' . E  // assoc %left, prec 1
    3 E: . NUM

    NUM  shift, and goto state 2

    E  goto state 5

state 5 // NUM '+' NUM [$end]

    1 E: E . '*' E  // assoc %left, prec 2
    2 E: E . '+' E  // assoc %left, prec 1
    2 E: E '+' E .  [$end, '+']  // assoc %left, prec 1

    $end  reduce using rule 2 (E)
    '*'   shift, and goto state 3
    '+'   reduce using rule 2 (E)

    Conflict between rule 2 and token '*' resolved as shift ('+' < '*').
    Conflict between rule 2 and token '+' resolved as reduce (%left '+').

state 6 // NUM '*' NUM [$end]

    1 E: E . '*' E  // assoc %left, prec 2
    1 E: E '*' E .  [$end, '*', '+']  // assoc %left, prec 2
    2 E: E . '+' E  // assoc %left, prec 1

    $end  reduce using rule 1 (E)
    '*'   reduce using rule 1 (E)
    '+'   reduce using rule 1 (E)

    Conflict between rule 1 and token '*' resolved as reduce (%left '*').
    Conflict between rule 1 and token '+' resolved as reduce ('+' < '*').

XErrors
0: [0] lookahead "'+'", msg "unary operator not supported"
1: [0] lookahead "'-'", msg "unary operator not supported"
2: [0 1 4] lookahead "$end", msg "missing operand"
3: [0 1 3] lookahead "$end", msg "missing operand"
4: [0 2] lookahead "'/'", msg "binary operator not supported"
5: [0 2] lookahead "'-'", msg "binary operator not supported"
6: [0 2] lookahead "<nil>", msg "expected operator"
7: [0] lookahead "<nil>", msg "expected number"
Example (SkeletonXErrors)
p, err := ProcessSource(
	token.NewFileSet(),
	"example.y",
	[]byte(`
%token NUMBER

%left                '+' '-'
%left                '*' '/'
%precedence        UNARY

%%

Expression:
        Term
|   Term '+' Term
|   Term '-' Term

Term:
        Factor
|   Factor '*' Factor        
|   Factor '/' Factor

Factor:
        NUMBER
|   '+' NUMBER %prec UNARY
|   '-' NUMBER %prec UNARY

`),
	&Options{})
if err != nil {
	panic(err)
}

p.SkeletonXErrors(os.Stdout)
Output:

/*
	Reject empty input
*/
0
"invalid empty input"

1 // NUMBER
15 // NUMBER '-' NUMBER
16 // NUMBER '+' NUMBER
error "expected $end"

0
error "expected Expression or one of ['+', '-', NUMBER]"

9 // NUMBER '*'
10 // NUMBER '/'
error "expected Factor or one of ['+', '-', NUMBER]"

5 // '+'
6 // '-'
error "expected NUMBER"

13 // NUMBER '+'
14 // NUMBER '-'
error "expected Term or one of ['+', '-', NUMBER]"

3 // NUMBER
4 // NUMBER
7 // '-' NUMBER
8 // '+' NUMBER
error "expected one of [$end, '*', '+', '-', '/']"

2 // NUMBER
11 // NUMBER '/' NUMBER
12 // NUMBER '*' NUMBER
error "expected one of [$end, '+', '-']"

Index

Examples

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

func YMax

func YMax(a, b int) int

Max returns the larger of a and b.

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].

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL