1 \input texinfo @c -*-texinfo-*-
3 @setfilename ../../info/bovine
4 @set TITLE Bovine parser development
5 @set AUTHOR Eric M. Ludlam, David Ponce, and Richard Y. Kim
6 @settitle @value{TITLE}
7 @documentencoding UTF-8
10 @c *************************************************************************
12 @c *************************************************************************
14 @c Merge all indexes into a single index for now.
15 @c We can always separate them later into two or more as needed.
22 @c @footnotestyle separate
28 Copyright @copyright{} 1999--2004, 2012--2013 Free Software Foundation, Inc.
31 Permission is granted to copy, distribute and/or modify this document
32 under the terms of the GNU Free Documentation License, Version 1.3 or
33 any later version published by the Free Software Foundation; with no
34 Invariant Sections, with the Front-Cover texts being ``A GNU Manual,''
35 and with the Back-Cover Texts as in (a) below. A copy of the license
36 is included in the section entitled ``GNU Free Documentation License''.
38 (a) The FSF's Back-Cover Text is: ``You have the freedom to copy and
39 modify this GNU manual.''
43 @dircategory Emacs misc features
45 * Bovine: (bovine). Semantic bovine parser development.
52 @c @setchapternewpage odd
53 @c @setchapternewpage off
58 @author by @value{AUTHOR}
60 @vskip 0pt plus 1 fill
69 @c *************************************************************************
71 @c *************************************************************************
77 The @dfn{bovine} parser is the original @semantic{} parser, and is an
78 implementation of an @acronym{LL} parser. It is good for simple
79 languages. It has many conveniences making grammar writing easy. The
80 conveniences make it less powerful than a Bison-like @acronym{LALR}
81 parser. For more information, @inforef{Top, The Wisent Parser Manual,
84 Bovine @acronym{LL} grammars are stored in files with a @file{.by}
85 extension. When compiled, the contents is converted into a file of
86 the form @file{NAME-by.el}. This, in turn is byte compiled.
87 @inforef{top, Grammar Framework Manual, grammar-fw}.
94 * Starting Rules:: The starting rules for the grammar.
95 * Bovine Grammar Rules:: Rules used to parse a language.
96 * Optional Lambda Expression:: Actions to take when a rule is matched.
97 * Bovine Examples:: Simple Samples.
98 * GNU Free Documentation License:: The license for this documentation.
103 @chapter Starting Rules
105 In Bison, one and only one nonterminal is designated as the ``start''
106 symbol. In @semantic{}, one or more nonterminals can be designated as
107 the ``start'' symbol. They are declared following the @code{%start}
108 keyword separated by spaces. @inforef{start Decl, ,grammar-fw}.
110 If no @code{%start} keyword is used in a grammar, then the very first
111 is used. Internally the first start nonterminal is targeted by the
112 reserved symbol @code{bovine-toplevel}, so it can be found by the
115 To find locally defined variables, the local context handler needs to
116 parse the body of functional code. The @code{scopestart} declaration
117 specifies the name of a nonterminal used as the goal to parse a local
118 context, @inforef{scopestart Decl, ,grammar-fw}. Internally the
119 scopestart nonterminal is targeted by the reserved symbol
120 @code{bovine-inner-scope}, so it can be found by the parser harness.
122 @node Bovine Grammar Rules
123 @chapter Bovine Grammar Rules
125 The rules are what allow the compiler to create tags from a language
126 file. Once the setup is done in the prologue, you can start writing
127 rules. @inforef{Grammar Rules, ,grammar-fw}.
130 @var{result} : @var{components1} @var{optional-semantic-action1})
131 | @var{components2} @var{optional-semantic-action2}
135 @var{result} is a nonterminal, that is a symbol synthesized in your grammar.
136 @var{components} is a list of elements that are to be matched if @var{result}
137 is to be made. @var{optional-semantic-action} is an optional sequence
138 of simplified Emacs Lisp expressions for concocting the parse tree.
140 In bison, each time an element of @var{components} is found, it is
141 @dfn{shifted} onto the parser stack. (The stack of matched elements.)
142 When all @var{components}' elements have been matched, it is
143 @dfn{reduced} to @var{result}. @xref{Algorithm,,, bison, The GNU Bison Manual}.
145 A particular @var{result} written into your grammar becomes
146 the parser's goal. It is designated by a @code{%start} statement
147 (@pxref{Starting Rules}). The value returned by the associated
148 @var{optional-semantic-action} is the parser's result. It should be
149 a tree of @semantic{} @dfn{tags}, @inforef{Semantic Tags, ,
152 @var{components} is made up of symbols. A symbol such as @code{FOO}
153 means that a syntactic token of class @code{FOO} must be matched.
156 * How Lexical Tokens Match::
157 * Grammar-to-Lisp Details::
158 * Order of components in rules::
161 @node How Lexical Tokens Match
162 @section How Lexical Tokens Match
164 A lexical rule must be used to define how to match a lexical token.
172 Means that @code{FOO} is a reserved language keyword, matched as such
173 by looking up into a keyword table, @inforef{keyword Decl,
174 ,grammar-fw}. This is because @code{"foo"} will be converted to
175 @code{FOO} in the lexical analysis stage. Thus the symbol @code{FOO}
176 won't be available any other way.
178 If we specify our token in this way:
181 %token <symbol> FOO "foo"
184 then @code{FOO} will match the string @code{"foo"} explicitly, but it
185 won't do so at the lexical level, allowing use of the text
186 @code{"foo"} in other forms of regular expressions.
188 In that case, @code{FOO} is a @code{symbol}-type token. To match, a
189 @code{symbol} must first be encountered, and then it must
190 @code{string-match "foo"}.
194 Be especially careful to remember that @code{"foo"}, and more
195 generally the %token's match-value string, is a regular expression!
198 Non symbol tokens are also allowed. For example:
201 %token <punctuation> PERIOD "[.]"
203 filename : symbol PERIOD symbol
207 @code{PERIOD} is a @code{punctuation}-type token that will explicitly
208 match one period when used in the above rule.
212 @code{symbol}, @code{punctuation}, etc., are predefined lexical token
213 types, based on the @dfn{syntax class}-character associations
217 @node Grammar-to-Lisp Details
218 @section Grammar-to-Lisp Details
220 For the bovinator, lexical token matching patterns are @emph{inlined}.
221 When the grammar-to-lisp converter encounters a lexical token
222 declaration of the form:
225 %token <@var{type}> @var{token-name} @var{match-value}
228 It substitutes every occurrences of @var{token-name} in rules, by its
232 @var{type} @var{match-value}
238 %token <symbol> MOOSE "moose"
244 Will generate this pseudo equivalent-rule:
247 find_a_moose: symbol "moose" ;; invalid syntax!
251 Thus, from the bovinator point of view, the @var{components} part of a
252 rule is made up of symbols and strings. A string in the mix means
253 that the previous symbol must have the additional constraint of
254 exactly matching it, as described in @ref{How Lexical Tokens Match}.
258 For the bovinator, this task was mixed into the language definition to
259 simplify implementation, though Bison's technique is more efficient.
262 @node Order of components in rules
263 @section Order of components in rules
265 If a rule has multiple components, order is important, for example
268 headerfile : symbol PERIOD symbol
273 would match @samp{foo.h} or the @acronym{C++} header @samp{foo}.
274 The bovine parser will first attempt to match the long form, and then
275 the short form. If they were in reverse order, then the long form
276 would never be tested.
278 @c @xref{Default syntactic tokens}.
280 @node Optional Lambda Expression
281 @chapter Optional Lambda Expressions
283 The @acronym{OLE} (@dfn{Optional Lambda Expression}) is converted into
284 a bovine lambda. This lambda has special short-cuts to simplify
285 reading the semantic action definition. An @acronym{OLE} like this:
291 results in a lambda return which consists entirely of the string
292 or object found by matching the first (zeroth) element of match.
293 An @acronym{OLE} like this:
299 executes @code{foo} on the first argument, and then splices its return
300 into the return list whereas:
306 executes @code{foo}, and that is placed in the return list.
308 Here are other things that can appear inline:
312 The first object matched.
315 The first object spliced into the list (assuming it is a list from a
319 The first object matched, placed in a list. I.e., @code{( $1 )}.
322 The symbol @code{foo} (exactly as displayed).
325 A function call to foo which is stuck into the return list.
328 A function call to foo which is spliced into the return list.
331 A function call to foo which is stuck into the return list in a list.
333 @item (EXPAND @var{$1} @var{nonterminal} @var{depth})
334 A list starting with @code{EXPAND} performs a recursive parse on the
335 token passed to it (represented by @samp{$1} above.) The
336 @dfn{semantic list} is a common token to expand, as there are often
337 interesting things in the list. The @var{nonterminal} is a symbol in
338 your table which the bovinator will start with when parsing.
339 @var{nonterminal}'s definition is the same as any other nonterminal.
340 @var{depth} should be at least @samp{1} when descending into a
343 @item (EXPANDFULL @var{$1} @var{nonterminal} @var{depth})
344 Is like @code{EXPAND}, except that the parser will iterate over
345 @var{nonterminal} until there are no more matches. (The same way the
346 parser iterates over the starting rule (@pxref{Starting Rules}). This
347 lets you have much simpler rules in this specific case, and also lets
348 you have positional information in the returned tokens, and error
351 @item (ASSOC @var{symbol1} @var{value1} @var{symbol2} @var{value2} @dots{})
352 This is used for creating an association list. Each @var{symbol} is
353 included in the list if the associated @var{value} is non-@code{nil}.
354 While the items are all listed explicitly, the created structure is an
355 association list of the form:
358 ((@var{symbol1} . @var{value1}) (@var{symbol2} . @var{value2}) @dots{})
361 @item (TAG @var{name} @var{class} [@var{attributes}])
362 This creates one tag in the current buffer.
366 Is a string that represents the tag in the language.
369 Is the kind of tag being create, such as @code{function}, or
370 @code{variable}, though any symbol will work.
373 Is an optional set of labeled values such as @code{:constant-flag t :parent
377 @item (TAG-VARIABLE @var{name} @var{type} @var{default-value} [@var{attributes}])
378 @itemx (TAG-FUNCTION @var{name} @var{type} @var{arg-list} [@var{attributes}])
379 @itemx (TAG-TYPE @var{name} @var{type} @var{members} @var{parents} [@var{attributes}])
380 @itemx (TAG-INCLUDE @var{name} @var{system-flag} [@var{attributes}])
381 @itemx (TAG-PACKAGE @var{name} @var{detail} [@var{attributes}])
382 @itemx (TAG-CODE @var{name} @var{detail} [@var{attributes}])
383 Create a tag with @var{name} of respectively the class
384 @code{variable}, @code{function}, @code{type}, @code{include},
385 @code{package}, and @code{code}.
386 See @inforef{Creating Tags, , semantic-appdev} for the lisp
387 functions these translate into.
390 If the symbol @code{%quotemode backquote} is specified, then use
391 @code{,@@} to splice a list in, and @code{,} to evaluate the expression.
392 This lets you send @code{$1} as a symbol into a list instead of having
395 @node Bovine Examples
413 which, if it matched the string @samp{"A"}, would return
419 If this rule were used like this:
422 %token <punctuation> EQUAL "="
424 assign: any-symbol EQUAL any-symbol
429 it would match @samp{"A=B"}, and return
435 The letters @samp{A} and @samp{B} come back in lists because
436 @samp{any-symbol} is a nonterminal, not an actual lexical element.
438 To get a better result with nonterminals, use @asis{,} to splice lists
442 %token <punctuation> EQUAL "="
444 assign: any-symbol EQUAL any-symbol
455 @node GNU Free Documentation License
456 @appendix GNU Free Documentation License
458 @include doclicense.texi
460 @c There is nothing to index at the moment.
474 @c Following comments are for the benefit of ispell.
476 @c LocalWords: bovinator inlined