Compiling a grammar

After providing a context-free grammar in a suitable format, it must be translated into a set of tables (an automaton) that will be used to derive the parser. Like Bison, Wisent translates grammars that must be LALR(1).

A grammar is LALR(1) if it is possible to tell how to parse any portion of an input string with just a single token of look-ahead: the look-ahead token. See (bison)Language and Grammar, in the Bison manual for more information.

Grammar translation (compilation) is achieved by the function:

Function: wisent-compile-grammar grammar &optional start-list

Compile grammar and return an LALR(1) automaton.

Optional argument start-list is a list of start symbols (nonterminals). If nil the first nonterminal defined in the grammar is the default start symbol. If start-list contains only one element, it defines the start symbol. If start-list contains more than one element, all are defined as potential start symbols, unless wisent-single-start-flag is non-nil. In that case the first element of start-list defines the start symbol and others are ignored.

The LALR(1) automaton is a vector of the form:

[actions gotos starts functions]

actions

A state/token matrix telling the parser what to do at every state based on the current look-ahead token. That is shift, reduce, accept or error. See also Wisent Parsing.

gotos

A state/nonterminal matrix telling the parser the next state to go to after reducing with each rule.

starts

An alist which maps the allowed start symbols (nonterminals) to lexical tokens that will be first shifted into the parser stack.

functions

An obarray of semantic action symbols. A semantic action is actually an Emacs Lisp function (lambda expression).