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 ¶
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.
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 ¶
ProcessAST processes yacc source code parsed in ast. It returns a *Parser or an error, if any.
func ProcessFile ¶
ProcessFile processes yacc source code in a named file. It returns a *Parser or an error, if any.
func ProcessSource ¶
ProcessSource processes yacc source code in src. It returns a *Parser or an error, if any.
func (*Parser) AcceptsEmptyInput ¶
AcceptsEmptyInput returns whether the token string [$end] is accepted by the grammar.
func (*Parser) Reductions ¶
Reductions returns a mapping rule# -> []state#. The slice is a sorted set of states in which the corresponding rule is reduced.
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].
type State ¶
type State struct {
// contains filtered or unexported fields
}
State represents one state of the parser.
func (*State) Reduce0 ¶
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 ¶
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 ¶
DerivesEmpty returns whether s derives ε.
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