Happy User Guide

A common type of sequence is one with a separator: for instance function bodies in C consist of statements separated by semicolons. To parse this kind of sequence we use a production like this:

If the ; is to be a terminator rather than a separator (i.e. there should be one following each statement), we can remove the semicolon from the above rule and redefine stmt as

where stmt1 is the real definition of statements.

We might like to allow extra semicolons between statements, to be a bit more liberal in what we allow as legal syntax. We probably just want the parser to ignore these extra semicolons, and not generate a ``null statement'' value or something. The following rule parses a sequence of zero or more statements separated by semicolons, in which the statements may be empty:

Parsing sequences of one or more possibly null statements is left as an exercise for the reader…​

The precedence directives, %left, %right and %nonassoc, assign precedence levels to the tokens in the declaration. A rule in the grammar may also have a precedence: if the last terminal in the right hand side of the rule has a precedence, then this is the precedence of the whole rule.

The precedences are used to resolve ambiguities in the grammar. If there is a shift/reduce conflict, then the precedence of the rule and the lookahead token are examined in order to resolve the conflict:

The precedence of an individual rule can be overriden, using context precedence. This is useful when, for example, a particular token has a different precedence depending on the context. A common example is the minus sign: it has high precedence when used as prefix negation, but a lower precedence when used as binary subtraction.

We can implement this in Happy as follows:

We invent a new token NEG as a placeholder for the precedence of our prefix negation rule. The NEG token doesn’t need to appear in a %token directive. The prefix negation rule has a %prec NEG directive attached, which overrides the default precedence for the rule (which would normally be the precedence of '-') with the precedence of NEG.

Rules annotated with the %shift directive have the lowest possible precedence and are non-associative. A shift/reduce conflict that involves such a rule is resolved as a shift. One can think of %shift as %prec SHIFT such that SHIFT has lower precedence than any other token.

This is useful in conjunction with %expect 0 to explicitly point out all rules in the grammar that result in conflicts, and thereby resolve such conflicts.

It’s not very convenient to just call error when a parse error is detected: in a robust setting, you’d like the program to recover gracefully and report a useful error message to the user. Exceptions (of which errors are a special case) are normally implemented in Haskell by using an exception monad, something like:

This monad just uses a string as the error type. The functions thenE and returnE are the usual bind and return operations of the monad, failE raises an error, and catchE is a combinator for handling exceptions.

We can add this monad to the parser with the declaration

Now, without changing the grammar, we can change the definition of parseError and have something sensible happen for a parse error:

The parser now raises an exception in the monad instead of bombing out on a parse error.

We can also generate errors during parsing. There are times when it is more convenient to parse a more general language than that which is actually intended, and check it later. An example comes from Haskell, where the precedence values in infix declarations must be between 0 and 9:

The monadic action allows the check to be placed in the parser itself, where it belongs.

Happy allows the monad concept to be extended to the lexical analyser, too. This has several useful consequences:

A monadic lexer is requested by adding the following declaration to the grammar file:

where <lexer> is the name of the lexical analyser function, and <eof> is a token that is to be treated as the end of file.

When using a monadic lexer, the parser no longer reads a list of tokens. Instead, it calls the lexical analysis function for each new token to be read. This has the side effect of eliminating the intermediate list of tokens, which is a slight performance win.

The type of the main parser function is now just P a - the input is being handled completely within the monad.

The type of parseError becomes Token → P a; that is it takes Happy’s current lookahead token as input. This can be useful, because the error function probably wants to report the token at which the parse error occurred, and otherwise the lexer would have to store this token in the monad.

The lexical analysis function must have the following type:

where P is the monad type constructor declared with %monad, and a can be replaced by the parser return type if desired.

You can see from this type that the lexer takes a continuation as an argument. The lexer is to find the next token, and pass it to this continuation to carry on with the parse. Obviously, we need to keep track of the input in the monad somehow, so that the lexer can do something different each time it’s called!

Let’s take the exception monad above, and extend it to add the input string so that we can use it with a threaded lexer.

Notice that this isn’t a real state monad - the input string just gets passed around, not returned. Our lexer will now look something like this:

the lexer grabs the continuation and the input string, finds the next token token, and passes it together with the remaining input string s' to the continuation.

We can now indicate lexical errors by ignoring the continuation and calling failP "error message" s within the lexer (don’t forget to pass the input string to make the types work out).

This may all seem a bit weird. Why, you ask, doesn’t the lexer just have type P Token? It was done this way for performance reasons - this formulation sometimes means that you can use a reader monad instead of a state monad for P, and the reader monad might be faster. It’s not at all clear that this reasoning still holds (or indeed ever held), and it’s entirely possible that the use of a continuation here is just a misfeature.

If you want a lexer of type P Token, then just define a wrapper to deal with the continuation:

Previous versions of Happy had a %newline directive that enabled simple line numbers to be counted by the parser and referenced in the actions. We warned you that this facility may go away and be replaced by something more general, well guess what? :-)

Line numbers can now be dealt with quite straightforwardly using a monadic parser/lexer combination. Ok, we have to extend the monad a bit more:

(the rest of the functions in the monad follow by just adding the extra line number argument in the same way as the input string). Again, the line number is just passed down, not returned: this is OK because of the continuation-based lexer that can change the line number and pass the new one to the continuation.

The lexer can now update the line number as follows:

It’s as simple as that. Take a look at Happy's own parser if you have the sources lying around, it uses a monad just like the one above.

Reporting the line number of a parse error is achieved by changing parseError to look something like this:

We can also get hold of the line number during parsing, to put it in the parsed data structure for future reference. A good way to do this is to have a production in the grammar that returns the current line number:

The semantic value of lineno is the line number of the last token read - this will always be the token directly following the lineno symbol in the grammar, since Happy always keeps one lookahead token in reserve.

The types of various functions related to the parser are dependent on what combination of %monad and %lexer directives are present in the grammar. For reference, we list those types here. In the following types, t is the return type of the parser. A type containing a type variable indicates that the specified function must be polymorphic.

where the type constructor T is whatever you want (usually T a = String → a). I’m not sure if this is useful, or even if it works properly. *

+

The process of generating a GLR parser is broadly the same as for standard Happy. You write a grammar specification, run Happy on this to generate some Haskell code, then compile and link this into your program.

An alternative to using Happy directly is to use the BNF Converter tool by Markus Forsberg, Peter Gammie, Michael Pellauer and Aarne Ranta. This tool creates an abstract syntax, grammar, pretty-printer and other useful items from a single grammar formalism, thus it saves a lot of work and improves maintainability. The current output of BNFC can be used with GLR mode now with just a few small changes, but from January 2005 we expect to have a fully-compatible version of BNFC.

Most of the features of Happy still work, but note the important points below.

The driver file exports a function doParse :: → GLRResult. If you are using several parsers, use qualified naming to distinguish them. UserDefTok is a synonym for the type declared with the %tokentype directive.

The input to doParse is a list of list of token values. The outer level represents the sequence of input symbols, and the inner list represents ambiguity in the tokenisation of each input symbol. For example, the word "run" can be at least a noun or a verb, hence the inner list will contain at least two values. If your tokens are not ambiguous, you will need to convert each token to a singleton list before parsing.

The parse result is expressed with the following types. A successful parse yields a forest (explained below) and a single root node for the forest. A parse may fail for one of two reasons: running out of input or a (global) parse error. A global parse error means that it was not possible to continue parsing any of the live alternatives; this is different from a local error, which simply means that the current alternative dies and we try some other alternative. In both error cases, the forest at failure point is returned, since it may contain useful information. Unconsumed tokens are returned when there is a global parse error.

Conceptually, the parse forest is a directed, acyclic and-or graph. It is represented by a mapping of ForestIds to lists of possible analyses. The FiniteMap type is used to provide efficient and convenient access. The ForestId type identifies nodes in the graph, named by the range of input they span and the category of analysis they license. GSymbol is generated automatically as a union of the names of grammar rules (prefixed by G_ to avoid name clashes) and of tokens and an EOF symbol. Tokens are wrapped in the constructor HappyTok :: UserDefTok → GSymbol.

The Branch type represents a match for some right-hand side of a production, containing semantic information (see below) and a list of sub-analyses. Each of these is a node in the graph. Note that tokens are represented as childless nodes that span one input position. Empty productions will appear as childless nodes that start and end at the same position.

Happy will generate two files, and these should be compiled as normal Haskell files. If speed is an issue, then you should use the -O flags etc with the driver code, and if feasible, with the parser tables too.

You can also use the --ghc flag to trigger certain GHC-specific optimizations. At present, this just causes use of unboxed types in the tables and in some key code. Using this flag causes relevant GHC option pragmas to be inserted into the generated code, so you shouldn’t have to use any strange flags (unless you want to…​).

Semantic information may be attached to productions in the conventional way, but when more than one analysis is possible, the use of the semantic information must change. Two schemes have been implemented, which we call tree decoding and label decoding. The former is for simple applications, where there is not much ambiguity and hence where the effective unpacking of the parse forest isn’t a factor. This mode is quite similar to the standard mode in Happy. The latter is for serious applications, where sharing is important and where processing of the forest (eg filtering) is needed. Here, the emphasis is about providing rich labels in nodes of the the parse forest, to support such processing.

The default mode is labelling. If you want the tree decode mode, use the --decode flag.

Tree decoding corresponds to unpacking the parse forest to individual trees and collecting the list of semantic results computed from each of these. It is a mode intended for simple applications, where there is limited ambiguity. You may access semantic results from components of a reduction using the dollar variables. As a working example, the following is taken from the expr-tree grammar in the examples. Note that the type signature is required, else the types in use can’t be determined by the parser generator.

This mode works by converting each of the semantic rules into functions (abstracted over the dollar variables mentioned), and labelling each Branch created from a reduction of that rule with the function value. This amounts to delaying the action of the rule, since we must wait until we know the results of all of the sub-analyses before computing any of the results. (Certain cases of packing can add new analyses at a later stage.)

At the end of parsing, the functions are applied across relevant sub-analyses via a recursive descent. The main interface to this is via the class and entry function below. Typically, decode should be called on the root of the forest, also supplying a function which maps node names to their list of analyses (typically a partial application of lookup in the forest value). The result is a list of semantic values. Note that the context of the call to decode should (eventually) supply a concrete type to allow selection of appropriate instance. Ie, you have to indicate in some way what type the semantic result should have. Decode_Result a is a synonym generated by Happy: for non-monadic semantics, it is equivalent to a; when monads are in use, it becomes the declared monad type. See the full expr-eval example for more information.

The GLR parser generator identifies the types involved in each semantic rule, hence the types of the functions, then creates a union containing distinct types. Values of this union are stored in the branches. (The union is actually a bit more complex: it must also distinguish patterns of dollar-variable usage, eg a function \x y → x + y ` could be applied to the first and second constituents, or to the first and third.) The parser generator also creates instances of the `TreeDecode class, which unpacks the semantic function and applies it across the decodings of the possible combinations of children. Effectively, it does a cartesian product operation across the lists of semantic results from each of the children. Eg [1,2] "+" [3,4] produces [4,5,5,6]. Information is extracted from token values using the patterns supplied by the user when declaring tokens and their Haskell representation, so the dollar-dollar convention works also.

The decoding process could be made more efficient by using memoisation techniques, but this hasn’t been implemented since we believe the other (label) decoding mode is more useful. (If someone sends in a patch, we may include it in a future release — but this might be tricky, eg require higher-order polymorphism? Plus, are there other ways of using this form of semantic function?)

The labelling mode aims to label branches in the forest with information that supports subsequent processing, for example the filtering and prioritisation of analyses prior to extraction of favoured solutions. As above, code fragments are given in braces and can contain dollar-variables. But these variables are expanded to node names in the graph, with the intention of easing navigation. The following grammar is from the expr-tree example.

Here, the semantic values provide more meaningful labels than the plain structural information. In particular, only the interesting parts of the branch are represented, and the programmer can clearly select or label the useful constituents if required. There is no need to remember that it is the first and third child in the branch which we need to extract, because the label only contains those values (the noise' has been dropped). Consider also the difference between concrete and abstract syntax. The labels are oriented towards abstract syntax. Tokens are handled slightly differently here: when they appear as children in a reduction, their informational content can be extracted directly, hence the `Const value above will be built with the Int value from the token, not some ForestId.

Note the useful technique of making the label types polymorphic in the position used for forest indices. This allows replacement at a later stage with more appropriate values, eg. inserting lists of actual subtrees from the final decoding.

Use of these labels is supported by a type class LabelDecode, which unpacks values of the automatically-generated union type GSem to the original type(s). The parser generator will create appropriate instances of this class, based on the type information in the grammar file. (Note that omitting type information leads to a default of ().) Observe that use of the labels is often like traversing an abstract syntax, and the structure of the abstract syntax type usually constrains the types of constituents; so once the overall type is fixed (eg. with a type cast or signature) then there are no problems with resolution of class instances.

Internally, the semantic values are packed in a union type as before, but there is no direct abstraction step. Instead, the ForestId values (from the dollar-variables) are bound when the corresponding branch is created from the list of constituent nodes. At this stage, token information is also extracted, using the patterns supplied by the user when declaring the tokens.

You can use the %monad directive in the tree-decode mode. Essentially, the decoding process now creates a list of monadic values, using the monad type declared in the directive. The default handling of the semantic functions is to apply the relevant return function to the value being returned. You can over-ride this using the {% …​ } convention. The declared (>>=) function is used to assemble the computations.

Note that no attempt is made to share the results of monadic computations from sub-trees. (You could possibly do this by supplying a memoising lookup function for the decoding process.) Hence, the usual behaviour is that decoding produces whole monadic computations, each part of which is computed afresh (in depth-first order) when the whole is computed. Hence you should take care to initialise any relevant state before computing the results from multiple solutions.

This facility is experimental, and we welcome comments or observations on the approach taken! An example is provided (examples/glr/expr-monad). It is the standard example of arithmetic expressions, except that the IO monad is used, and a user exception is thrown when the second argument to addition is an odd number. Running this example will show a zero (from the exception handler) instead of the expected number amongst the results from the other parses.

The directory examples/glr contains several examples from the small to the large. Please consult these or use them as a base for your experiments.

If you run the examples with GHC, each run will produce a file out.daVinci. This is a graph in the format expected by the daVinci graph visualization tool. (See http://www.informatik.uni-bremen.de/~davinci/ for more information. Educational use licenses are currently available without charge.)

We highly recommend looking at graphs of parse results - it really helps to understand the results. The graphs files are created with Sven Panne’s library for communicating with daVinci, supplemented with some extensions due to Callaghan. Copies of this code are included in the examples directory, for convenience. If you are trying to view large and complex graphs, contact Paul Callaghan (there are tools and techniques to make the graphs more manageable).

GLR parsing (and related techniques) aren’t just for badly written grammars or for things like natural language (NL) where ambiguity is inescapable. There are applications where ambiguity can represent possible alternatives in pattern-matching tasks, and the flexibility of these parsing techniques and the resulting graphs support deep analyses. Below, we briefly discuss some examples, a mixture from our recent work and from the literature.

The original implementation was developed by Ben Medlock, as his undergraduate final year project, using ideas from Peter Ljungloef’s Licentiate thesis (see http://www.cs.chalmers.se/~peb/parsing, and we recommend the thesis for its clear analysis of parsing algorithms). Ljungloef’s version produces lists of parse trees, but Medlock adapted this to produce an explicit graph containing parse structure information. He also incorporated the code into Happy.

After Medlock’s graduation, Callaghan extended the code to incorporate semantic information, and made several improvements to the original code, such as improved local packing and support for hidden left recursion. The performance of the code was significantly improved, after changes of representation (eg to a chart-style data structure) and technique. Medlock’s code was also used in several student projects, including analysis of gene sequences (Fischer) and analysis of rhythmic patterns in poetry (Henderson).

The current code implements the standard GLR algorithm extended to handle hidden left recursion. Such recursion, as in the grammar below from Rekers [1992], causes the standard algorithm to loop because the empty reduction A → ` is always possible and the LR parser will not change state. Alternatively, there is a problem because an unknown (at the start of parsing) number of `A items are required, to match the number of i tokens in the input.

The solution to this is not surprising. Problematic recursions are detected as zero-span reductions in a state which has a goto table entry looping to itself. A special symbol is pushed to the stack on the first such reduction, and such reductions are done at most once for any token alternative for any input position. When popping from the stack, if the last token being popped is such a special symbol, then two stack tails are returned: one corresponding to a conventional pop (which removes the symbol) and the other to a duplication of the special symbol (the stack is not changed, but a copy of the symbol is returned). This allows sufficient copies of the empty symbol to appear on some stack, hence allowing the parse to complete.

The forest is held in a chart-style data structure, and this supports local ambiguity packing (chart parsing is discussed in Ljungloef’s thesis, among other places). A limited amount of packing of live stacks is also done, to avoid some repetition of work.

[Rekers 1992] Parser Generation for Interactive Environments, PhD thesis, University of Amsterdam, 1992.

You might have noticed this GLR-related option. It is an experimental feature intended to restrict the amount of structure retained in the forest by discarding everything not required for the semantic results. It may or it may not work, and may be fixed in a future release.

The parser supports hidden left recursion, but makes no attempt to handle cyclic grammars that have rules which do not consume any input. If you have a grammar like this, for example with rules like S → S or S → A S | x; A → empty, the implementation will loop until you run out of stack - but if it will happen, it often happens quite quickly!

The code has been used and tested frequently over the past few years, including being used in several undergraduate projects. It should be fairly stable, but as usual, can’t be guaranteed bug-free. One day I will write it in Epigram!

If you have suggestions for improvements, or requests for features, please contact Paul Callaghan. There are some changes I am considering, and some views and/or encouragement from users will be much appreciated. Further information can be found on Callaghan’s GLR parser page.

Many thanks to the people who have used and tested this software in its various forms, including Julia Fischer, James Henderson, and Aarne Ranta.

The presence of one or more %attribute directives indicates that a grammar is an attribute grammar. Attributes are calculated properties that are associated with the non-terminals in a parse tree. Each %attribute directive generates a field in the attributes record with the given name and type.

The first %attribute directive in a grammar defines the default attribute. The default attribute is distinguished in two ways: 1) if no attribute specifier is given on an attribute reference, the default attribute is assumed (see Semantic Rules) and 2) the value for the default attribute of the starting non-terminal becomes the return value of the parse.

Optionally, one may specify a type declaration for the attribute record using the %attributetype declaration. This allows you to define the type given to the attribute record and, more importantly, allows you to introduce type variables that can be subsequently used in %attribute declarations. If the %attributetype directive is given without any %attribute declarations, then the %attributetype declaration has no effect.

For example, the following declarations:

would generate this attribute record declaration in the parser:

and value would be the default attribute.

In an ordinary Happy grammar, a production consists of a list of terminals and/or non-terminals followed by an uninterpreted code fragment enclosed in braces. With an attribute grammar, the format is very similar, but the braces enclose a set of semantic rules rather than uninterpreted Haskell code. Each semantic rule is either an attribute calculation or a conditional, and rules are separated by semicolons^[3].

Both attribute calculations and conditionals may contain attribute references and/or terminal references. Just like regular Happy grammars, the tokens $1 through $<n>, where n is the number of symbols in the production, refer to subtrees of the parse. If the referenced symbol is a terminal, then the value of the reference is just the value of the terminal, the same way as in a regular Happy grammar. If the referenced symbol is a non-terminal, then the reference may be followed by an attribute specifier, which is a dot followed by an attribute name. If the attribute specifier is omitted, then the default attribute is assumed (the default attribute is the first attribute appearing in an %attribute declaration). The special reference $$ references the attributes of the current node in the parse tree; it behaves exactly like the numbered references. Additionally, the reference $> always references the rightmost symbol in the production.

An attribute calculation rule is of the form:

A rule of this form defines the value of an attribute, possibly as a function of the attributes of $$ (inherited attributes), the attributes of non-terminals in the production (synthesized attributes), or the values of terminals in the production. The value for an attribute can only be defined once for a particular production.

The following rule calculates the default attribute of the current production in terms of the first and second items of the production (a synthesized attribute):

This rule calculates the length attribute of a non-terminal in terms of the length of the current non-terminal (an inherited attribute):

Conditional rules allow the rejection of strings due to context-sensitive properties. All conditional rules have the form:

For non-monadic parsers, all conditional expressions must be of the same (monomorphic) type. At the end of the parse, the conditionals will be reduced using seq, which gives the grammar an opportunity to call error with an informative message. For monadic parsers, all conditional statements must have type Monad m ⇒ m () where m is the monad in which the parser operates. All conditionals will be sequenced at the end of the parse, which allows the conditionals to call fail with an informative message.

The following conditional rule will cause the (non-monadic) parser to fail if the inherited length attribute is not 0.

This conditional is the monadic equivalent:

(mandatory) The %tokentype directive gives the type of the tokens passed from the lexical analyser to the parser (in order that Happy can supply types for functions and data in the generated parser).

(mandatory) The %token directive is used to tell Happy about all the terminal symbols used in the grammar. Each terminal has a name, by which it is referred to in the grammar itself, and a Haskell representation enclosed in braces. Each of the patterns must be of the same type, given by the %tokentype directive.

The name of each terminal follows the lexical rules for Happy identifiers given above. There are no lexical differences between terminals and non-terminals in the grammar, so it is recommended that you stick to a convention; for example using upper case letters for terminals and lower case for non-terminals, or vice-versa.

Happy will give you a warning if you try to use the same identifier both as a non-terminal and a terminal, or introduce an identifier which is declared as neither.

To save writing lots of projection functions that map tokens to their components, you can include $$ in your Haskell pattern. For example:

This makes the semantic value of INT refer to the first argument of TokenInt rather than the whole token, eliminating the need for any projection function.

(optional) The %name directive is followed by a valid Haskell identifier, and gives the name of the top-level parsing function in the generated parser. This is the only function that needs to be exported from a parser module.

If the %name directive is omitted, it defaults to happyParse.

The %name directive takes an optional second parameter which specifies the top-level non-terminal which is to be parsed. If this parameter is omitted, it defaults to the first non-terminal defined in the grammar.

Multiple %name directives may be given, specifying multiple parser entry points for this grammar (see Generating Multiple Parsers From a Single Grammar). When multiple %name directives are given, they must all specify explicit non-terminals.

The %partial directive can be used instead of %name. It indicates that the generated parser should be able to parse an initial portion of the input. In contrast, a parser specified with %name will only parse the entire input.

A parser specified with %partial will stop parsing and return a result as soon as there exists a complete parse, and no more of the input can be parsed. It does this by accepting the parse if it is followed by the error token, rather than insisting that the parse is followed by the end of the token stream (or the eof token in the case of a %lexer parser).

(optional) The %monad directive takes three arguments: the type constructor of the monad, the then (or bind) operation, and the return (or unit) operation. The type constructor can be any type with kind \* → *.

Monad declarations are described in more detail in Monadic Parsers.

(optional) The %lexer directive takes two arguments: <lexer> is the name of the lexical analyser function, and <eof> is a token that is to be treated as the end of file.

Lexer declarations are described in more detail in Threaded Lexers.

These declarations are used to specify the precedences and associativity of tokens. The precedence assigned by a %left, %right or %nonassoc declaration is defined to be higher than the precedence assigned by all declarations earlier in the file, and lower than the precedence assigned by all declarations later in the file.

The associativity of a token relative to tokens in the same %left, %right, or %nonassoc declaration is to the left, to the right, or non-associative respectively.

Precedence declarations are described in more detail in Using Precedences.

(optional) More often than not the grammar you write will have conflicts. These conflicts generate warnings. But when you have checked the warnings and made sure that Happy handles them correctly these warnings are just annoying. The %expect directive gives a way of avoiding them. Declaring %expectn is a way of telling Happy “There are exactly n shift/reduce conflicts and zero reduce/reduce conflicts in this grammar. I promise I have checked them and they are resolved correctly”. When processing the grammar, Happy will check the actual number of conflicts against the %expect declaration if any, and if there is a discrepancy then an error will be reported.

Happy’s %expect directive works exactly like that of yacc.

Specifies the function to be called in the event of a parse error. The type of <identifier> varies depending on the presence of %lexer (see Summary) and %errorhandlertype (see the following).

(optional) The expected type of the user-supplied error handling can be applied with additional information. By default, no information is added, for compatibility with previous versions. However, if explist is provided with this directive, then the first application will be of type [String], providing a description of possible tokens that would not have failed the parser in place of the token that has caused the error.

(optional) This directive allows you to declare the type of the attributes record when defining an attribute grammar. If this declaration is not given, Happy will choose a default. This declaration may only appear once in a grammar.

Attribute grammars are explained in Attribute Grammars.

The presence of one or more of these directives declares that the grammar is an attribute grammar. The first attribute listed becomes the default attribute. Each %attribute directive generates a field in the attributes record with the given label and type. If there is an %attributetype declaration in the grammar which introduces type variables, then the type of an attribute may mention any such type variables.

Attribute grammars are explained in Attribute Grammars.

Starting from version 1.17.1, Happy supports parameterized productions which provide a convenient notation for capturing recurring patterns in context free grammars. This gives the benefits of something similar to parsing combinators in the context of Happy grammars.

This functionality is best illustrated with an example:

The first production, opt, is used for optional components of a grammar. It is just like p? in regular expressions or EBNF. The second production, rev_list1, is for parsing a list of 1 or more occurrences of p. Parameterized productions are just like ordinary productions, except that they have parameter in parenthesis after the production name. Multiple parameters should be separated by commas:

To use a parameterized production, we have to pass values for the parameters, as if we are calling a function. The parameters can be either terminals, non-terminals, or other instantiations of parameterized productions. Here are some examples:

The first production uses rev_list to define a production that behaves like p+, returning a list of elements in the same order as they occurred in the input. The second one, list is like p*.

Parameterized productions are implemented as a preprocessing pass in Happy: each instantiation of a production turns into a separate non-terminal, but are careful to avoid generating the same rule multiple times, as this would lead to an ambiguous grammar. Consider, for example, the following parameterized rule:

The rules that would be generated for sep1(EXPR,SEP)

Note that this is just a normal grammar, with slightly strange names for the non-terminals.

A drawback of the current implementation is that it does not support type signatures for the parameterized productions, that depend on the types of the parameters. We plan to implement that in the future---the current workaround is to omit the type signatures for such rules.

There are three basic ways to build a shift-reduce parser. Full LR(1) (the `L' is the direction in which the input is scanned, the `R' is the way in which the parse is built, and the `1' is the number of tokens of lookahead) generates a parser with many states, and is therefore large and slow. SLR(1) (simple LR(1)) is a cut-down version of LR(1) which generates parsers with roughly one-tenth as many states, but lacks the power to parse many grammars (it finds conflicts in grammars which have none under LR(1)).

LALR(1) (look-ahead LR(1)), the method used by Happy and yacc, is a tradeoff between the two. An LALR(1) parser has the same number of states as an SLR(1) parser, but it uses a more complex method to calculate the lookahead tokens that are valid at each point, and resolves many of the conflicts that SLR(1) finds. However, there may still be conflicts in an LALR(1) parser that wouldn’t be there with full LR(1).