Bovine parser development
*************************

The bovine parser is the original Semantic parser, and is an implementation of an LL parser.  It is good for simple languages.  It has many conveniences making grammar writing easy.  The conveniences make it less powerful than a Bison-like LALR parser.  For more information, see the Wisent Parser Manual (wisent).

Bovine LL grammars are stored in files with a .by extension.  When compiled, the contents is converted into a file of the form NAME-by.el.  This, in turn is byte compiled. See Grammar Framework Manual (grammar-fw).

Copyright © 1999--2004, 2012--2013 Free Software Foundation, Inc.

     Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, with the Front-Cover texts being ``A GNU Manual,'' and with the Back-Cover Texts as in (a) below.  A copy of the license is included in the section entitled ``GNU Free Documentation License''.

     (a) The FSF's Back-Cover Text is: ``You have the freedom to copy and modify this GNU manual.''

Starting Rules
**************

In Bison, one and only one nonterminal is designated as the ``start'' symbol.  In Semantic, one or more nonterminals can be designated as the ``start'' symbol.  They are declared following the %start keyword separated by spaces.  See start Decl (grammar-fw).

If no %start keyword is used in a grammar, then the very first is used.  Internally the first start nonterminal is targeted by the reserved symbol bovine-toplevel, so it can be found by the parser harness.

To find locally defined variables, the local context handler needs to parse the body of functional code.  The scopestart declaration specifies the name of a nonterminal used as the goal to parse a local context, see scopestart Decl (grammar-fw).  Internally the scopestart nonterminal is targeted by the reserved symbol bovine-inner-scope, so it can be found by the parser harness.

Bovine Grammar Rules
********************

The rules are what allow the compiler to create tags from a language file.  Once the setup is done in the prologue, you can start writing rules.  See Grammar Rules (grammar-fw).

     RESULT : COMPONENTS1 OPTIONAL-SEMANTIC-ACTION1)
            | COMPONENTS2 OPTIONAL-SEMANTIC-ACTION2
            ;

RESULT is a nonterminal, that is a symbol synthesized in your grammar. COMPONENTS is a list of elements that are to be matched if RESULT is to be made.  OPTIONAL-SEMANTIC-ACTION is an optional sequence of simplified Emacs Lisp expressions for concocting the parse tree.

In bison, each time an element of COMPONENTS is found, it is shifted onto the parser stack.  (The stack of matched elements.) When all COMPONENTS' elements have been matched, it is reduced to RESULT.  See Algorithm (The GNU Bison Manual).

A particular RESULT written into your grammar becomes the parser's goal.  It is designated by a %start statement (see Starting Rules).  The value returned by the associated OPTIONAL-SEMANTIC-ACTION is the parser's result.  It should be a tree of Semantic tags, see Semantic Tags (semantic-appdev).

COMPONENTS is made up of symbols.  A symbol such as FOO means that a syntactic token of class FOO must be matched.

How Lexical Tokens Match
========================

A lexical rule must be used to define how to match a lexical token.

For instance:

     %keyword FOO "foo"

Means that FOO is a reserved language keyword, matched as such by looking up into a keyword table, see keyword Decl (grammar-fw).  This is because "foo" will be converted to FOO in the lexical analysis stage.  Thus the symbol FOO won't be available any other way.

If we specify our token in this way:

     %token <symbol> FOO "foo"

then FOO will match the string "foo" explicitly, but it won't do so at the lexical level, allowing use of the text "foo" in other forms of regular expressions.

In that case, FOO is a symbol-type token.  To match, a symbol must first be encountered, and then it must string-match "foo".

Caution:
     Be especially careful to remember that "foo", and more generally the %token's match-value string, is a regular expression!

Non symbol tokens are also allowed.  For example:

     %token <punctuation> PERIOD "[.]"

     filename : symbol PERIOD symbol
              ;

PERIOD is a punctuation-type token that will explicitly match one period when used in the above rule.

Please Note:
     symbol, punctuation, etc., are predefined lexical token types, based on the syntax class-character associations currently in effect.

Grammar-to-Lisp Details
=======================

For the bovinator, lexical token matching patterns are inlined. When the grammar-to-lisp converter encounters a lexical token declaration of the form:

     %token <TYPE> TOKEN-NAME MATCH-VALUE

It substitutes every occurrences of TOKEN-NAME in rules, by its expanded form:

     TYPE MATCH-VALUE

For example:

     %token <symbol> MOOSE "moose"

     find_a_moose: MOOSE
                 ;

Will generate this pseudo equivalent-rule:

     find_a_moose: symbol "moose"   ;; invalid syntax!
                 ;

Thus, from the bovinator point of view, the COMPONENTS part of a rule is made up of symbols and strings.  A string in the mix means that the previous symbol must have the additional constraint of exactly matching it, as described in How Lexical Tokens Match.

Please Note:
     For the bovinator, this task was mixed into the language definition to simplify implementation, though Bison's technique is more efficient.

Order of components in rules
============================

If a rule has multiple components, order is important, for example

     headerfile : symbol PERIOD symbol
                | symbol
                ;

would match foo.h or the C++ header foo. The bovine parser will first attempt to match the long form, and then the short form.  If they were in reverse order, then the long form would never be tested.

Optional Lambda Expressions
***************************

The OLE (Optional Lambda Expression) is converted into a bovine lambda.  This lambda has special short-cuts to simplify reading the semantic action definition.  An OLE like this:

     ( $1 )

results in a lambda return which consists entirely of the string or object found by matching the first (zeroth) element of match. An OLE like this:

     ( ,(foo $1) )

executes foo on the first argument, and then splices its return into the return list whereas:

     ( (foo $1) )

executes foo, and that is placed in the return list.

Here are other things that can appear inline:

$1
     The first object matched.

,$1
     The first object spliced into the list (assuming it is a list from a non-terminal).

'$1
     The first object matched, placed in a list.  I.e., ( $1 ).

foo
     The symbol foo (exactly as displayed).

(foo)
     A function call to foo which is stuck into the return list.

,(foo)
     A function call to foo which is spliced into the return list.

'(foo)
     A function call to foo which is stuck into the return list in a list.

(EXPAND $1 NONTERMINAL DEPTH)
     A list starting with EXPAND performs a recursive parse on the token passed to it (represented by $1 above.)  The semantic list is a common token to expand, as there are often interesting things in the list.  The NONTERMINAL is a symbol in your table which the bovinator will start with when parsing. NONTERMINAL's definition is the same as any other nonterminal. DEPTH should be at least 1 when descending into a semantic list.

(EXPANDFULL $1 NONTERMINAL DEPTH)
     Is like EXPAND, except that the parser will iterate over NONTERMINAL until there are no more matches.  (The same way the parser iterates over the starting rule (see Starting Rules). This lets you have much simpler rules in this specific case, and also lets you have positional information in the returned tokens, and error skipping.

(ASSOC SYMBOL1 VALUE1 SYMBOL2 VALUE2 ...)
     This is used for creating an association list.  Each SYMBOL is included in the list if the associated VALUE is non-nil. While the items are all listed explicitly, the created structure is an association list of the form:

          ((SYMBOL1 . VALUE1) (SYMBOL2 . VALUE2) ...)

(TAG NAME CLASS [ATTRIBUTES])
     This creates one tag in the current buffer.

     name
          Is a string that represents the tag in the language.

     class
          Is the kind of tag being create, such as function, or variable, though any symbol will work.

     attributes
          Is an optional set of labeled values such as :constant-flag t :parent "parenttype".

(TAG-VARIABLE NAME TYPE DEFAULT-VALUE [ATTRIBUTES])
(TAG-FUNCTION NAME TYPE ARG-LIST [ATTRIBUTES])
(TAG-TYPE NAME TYPE MEMBERS PARENTS [ATTRIBUTES])
(TAG-INCLUDE NAME SYSTEM-FLAG [ATTRIBUTES])
(TAG-PACKAGE NAME DETAIL [ATTRIBUTES])
(TAG-CODE NAME DETAIL [ATTRIBUTES])
     Create a tag with NAME of respectively the class variable, function, type, include, package, and code. See Creating Tags (semantic-appdev) for the lisp functions these translate into.

If the symbol %quotemode backquote is specified, then use ,@ to splice a list in, and , to evaluate the expression. This lets you send $1 as a symbol into a list instead of having it expanded inline.

Examples
********

The rule:

     any-symbol: symbol
               ;

is equivalent to

     any-symbol: symbol
                 ( $1 )
               ;

which, if it matched the string "A", would return

     ( "A" )

If this rule were used like this:

     %token <punctuation> EQUAL "="
     ...
     assign: any-symbol EQUAL any-symbol
             ( $1 $3 )
           ;

it would match "A=B", and return

     ( ("A") ("B") )

The letters A and B come back in lists because any-symbol is a nonterminal, not an actual lexical element.

To get a better result with nonterminals, use , to splice lists in like this:

     %token <punctuation> EQUAL "="
     ...
     assign: any-symbol EQUAL any-symbol
             ( ,$1 ,$3 )
           ;

which would return

     ( "A" "B" )

GNU Free Documentation License
******************************

     [file doclicense.texi not included]