Commit | Line | Data |
---|---|---|
9e7abd17 EL |
1 | \input texinfo @c -*-texinfo-*- |
2 | @c %**start of header | |
bfe6ffb6 | 3 | @setfilename ../../info/wisent |
9e7abd17 EL |
4 | @set TITLE Wisent Parser Development |
5 | @set AUTHOR Eric M. Ludlam, David Ponce, and Richard Y. Kim | |
6 | @settitle @value{TITLE} | |
7 | ||
8 | @c ************************************************************************* | |
9 | @c @ Header | |
10 | @c ************************************************************************* | |
11 | ||
12 | @c Merge all indexes into a single index for now. | |
13 | @c We can always separate them later into two or more as needed. | |
14 | @syncodeindex vr cp | |
15 | @syncodeindex fn cp | |
16 | @syncodeindex ky cp | |
17 | @syncodeindex pg cp | |
18 | @syncodeindex tp cp | |
19 | ||
20 | @c @footnotestyle separate | |
21 | @c @paragraphindent 2 | |
22 | @c @@smallbook | |
23 | @c %**end of header | |
24 | ||
25 | @copying | |
bfe6ffb6 GM |
26 | Copyright @copyright{} 1988-1993, 1995, 1998-2004, 2007, 2012 |
27 | Free Software Foundation, Inc. | |
9e7abd17 | 28 | |
bfe6ffb6 GM |
29 | @c Since we are both GNU manuals, we do not need to ack each other here. |
30 | @ignore | |
9e7abd17 EL |
31 | Some texts are borrowed or adapted from the manual of Bison version |
32 | 1.35. The text in section entitled ``Understanding the automaton'' is | |
33 | adapted from the section ``Understanding Your Parser'' in the manual | |
34 | of Bison version 1.49. | |
bfe6ffb6 | 35 | @end ignore |
9e7abd17 EL |
36 | |
37 | @quotation | |
38 | Permission is granted to copy, distribute and/or modify this document | |
bfe6ffb6 GM |
39 | under the terms of the GNU Free Documentation License, Version 1.3 or |
40 | any later version published by the Free Software Foundation; with no | |
41 | Invariant Sections, with the Front-Cover texts being ``A GNU Manual,'' | |
42 | and with the Back-Cover Texts as in (a) below. A copy of the license | |
43 | is included in the section entitled ``GNU Free Documentation License''. | |
44 | ||
45 | (a) The FSF's Back-Cover Text is: ``You have the freedom to copy and | |
46 | modify this GNU manual. Buying copies from the FSF supports it in | |
47 | developing GNU and promoting software freedom.'' | |
9e7abd17 EL |
48 | @end quotation |
49 | @end copying | |
50 | ||
bfe6ffb6 | 51 | @dircategory Emacs misc features |
9e7abd17 | 52 | @direntry |
bfe6ffb6 | 53 | * Wisent: (wisent). Semantic Wisent parser development. |
9e7abd17 | 54 | @end direntry |
9e7abd17 EL |
55 | |
56 | @iftex | |
57 | @finalout | |
58 | @end iftex | |
59 | ||
60 | @c @setchapternewpage odd | |
61 | @c @setchapternewpage off | |
62 | ||
9e7abd17 EL |
63 | @titlepage |
64 | @sp 10 | |
65 | @title @value{TITLE} | |
66 | @author by @value{AUTHOR} | |
9e7abd17 EL |
67 | @page |
68 | @vskip 0pt plus 1 fill | |
69 | @insertcopying | |
70 | @end titlepage | |
71 | @page | |
72 | ||
bfe6ffb6 GM |
73 | @macro semantic{} |
74 | @i{Semantic} | |
75 | @end macro | |
9e7abd17 EL |
76 | |
77 | @c ************************************************************************* | |
78 | @c @ Document | |
79 | @c ************************************************************************* | |
80 | @contents | |
81 | ||
82 | @node top | |
83 | @top @value{TITLE} | |
84 | ||
85 | Wisent (the European Bison ;-) is an Emacs Lisp implementation of the | |
86 | GNU Compiler Compiler Bison. | |
87 | ||
88 | This manual describes how to use Wisent to develop grammars for | |
89 | programming languages, and how to use grammars to parse language | |
90 | source in Emacs buffers. | |
91 | ||
92 | It also describes how Wisent is used with the @semantic{} tool set | |
93 | described in the @ref{Top, Semantic Manual, Semantic Manual, semantic}. | |
94 | ||
bfe6ffb6 GM |
95 | @ifnottex |
96 | @insertcopying | |
97 | @end ifnottex | |
98 | ||
9e7abd17 | 99 | @menu |
bfe6ffb6 GM |
100 | * Wisent Overview:: |
101 | * Wisent Grammar:: | |
102 | * Wisent Parsing:: | |
103 | * Wisent Semantic:: | |
104 | * GNU Free Documentation License:: | |
105 | * Index:: | |
9e7abd17 EL |
106 | @end menu |
107 | ||
108 | @node Wisent Overview | |
109 | @chapter Wisent Overview | |
110 | ||
111 | @dfn{Wisent} (the European Bison) is an implementation in Emacs Lisp | |
112 | of the GNU Compiler Compiler Bison. Its code is a port of the C code | |
113 | of GNU Bison 1.28 & 1.31. | |
114 | ||
115 | For more details on the basic concepts for understanding Wisent, it is | |
116 | worthwhile to read the @ref{Top, Bison Manual, bison}. | |
117 | @ifhtml | |
118 | @uref{http://www.gnu.org/manual/bison/html_node/index.html}. | |
119 | @end ifhtml | |
120 | ||
121 | Wisent can generate compilers compatible with the @semantic{} tool set. | |
122 | See the @ref{Top, Semantic Manual, , semantic}. | |
123 | ||
124 | It benefits from these Bison features: | |
125 | ||
126 | @itemize @bullet | |
bfe6ffb6 | 127 | @item |
9e7abd17 EL |
128 | It uses a fast but not so space-efficient encoding for the parse |
129 | tables, described in Corbett's PhD thesis from Berkeley: | |
130 | @quotation | |
131 | @cite{Static Semantics in Compiler Error Recovery}@* | |
132 | June 1985, Report No. UCB/CSD 85/251. | |
133 | @end quotation | |
134 | ||
bfe6ffb6 | 135 | @item |
9e7abd17 EL |
136 | For generating the lookahead sets, Wisent uses the well-known |
137 | technique of F. DeRemer and A. Pennello they described in: | |
138 | @quotation | |
139 | @cite{Efficient Construction of LALR(1) Lookahead Sets}@* | |
140 | October 1982, ACM TOPLS Vol 4 No 4. | |
141 | @end quotation | |
142 | ||
bfe6ffb6 | 143 | @item |
9e7abd17 EL |
144 | Wisent resolves shift/reduce conflicts using operator precedence and |
145 | associativity. | |
146 | ||
bfe6ffb6 | 147 | @item |
9e7abd17 EL |
148 | Parser error recovery is accomplished using rules which match the |
149 | special token @code{error}. | |
150 | @end itemize | |
151 | ||
152 | Nevertheless there are some fundamental differences between Bison and | |
153 | Wisent. | |
154 | ||
155 | @itemize | |
156 | @item | |
157 | Wisent is intended to be used in Emacs. It reads and produces Emacs | |
158 | Lisp data structures. All the additional code used in grammars is | |
159 | Emacs Lisp code. | |
160 | ||
161 | @item | |
162 | Contrary to Bison, Wisent does not generate a parser which combines | |
163 | Emacs Lisp code and grammar constructs. They exist separately. | |
164 | Wisent reads the grammar from a Lisp data structure and then generates | |
165 | grammar constructs as tables. Afterward, the derived tables can be | |
166 | included and byte-compiled in separate Emacs Lisp files, and be used | |
167 | at a later time by the Wisent's parser engine. | |
168 | ||
169 | @item | |
170 | Wisent allows multiple start nonterminals and allows a call to the | |
171 | parsing function to be made for a particular start nonterminal. For | |
172 | example, this is particularly useful to parse a region of an Emacs | |
173 | buffer. @semantic{} heavily depends on the availability of this feature. | |
174 | @end itemize | |
175 | ||
176 | @node Wisent Grammar | |
177 | @chapter Wisent Grammar | |
178 | ||
179 | @cindex context-free grammar | |
180 | @cindex rule | |
181 | In order for Wisent to parse a language, it must be described by a | |
182 | @dfn{context-free grammar}. That is a grammar specified as rules that | |
183 | can be applied regardless of context. For more information, see | |
184 | @ref{Language and Grammar, , , bison}, in the Bison manual. | |
185 | ||
186 | @cindex terminal | |
187 | @cindex nonterminal | |
188 | The formal grammar is formulated using @dfn{terminal} and | |
189 | @dfn{nonterminal} items. Terminals can be Emacs Lisp symbols or | |
190 | characters, and nonterminals are symbols only. | |
191 | ||
192 | @cindex token | |
193 | Terminals (also known as @dfn{tokens}) represent the lexical | |
194 | elements of the language like numbers, strings, etc.. | |
195 | ||
196 | For example @samp{PLUS} can represent the operator @samp{+}. | |
197 | ||
198 | Nonterminal symbols are described by rules: | |
199 | ||
200 | @example | |
201 | @group | |
202 | RESULT @equiv{} COMPONENTS@dots{} | |
203 | @end group | |
204 | @end example | |
205 | ||
206 | @samp{RESULT} is a nonterminal that this rule describes and | |
207 | @samp{COMPONENTS} are various terminals and nonterminals that are put | |
208 | together by this rule. | |
209 | ||
210 | For example, this rule: | |
211 | ||
212 | @example | |
213 | @group | |
214 | exp @equiv{} exp PLUS exp | |
215 | @end group | |
216 | @end example | |
217 | ||
218 | Says that two groupings of type @samp{exp}, with a @samp{PLUS} token | |
219 | in between, can be combined into a larger grouping of type @samp{exp}. | |
bfe6ffb6 | 220 | |
9e7abd17 | 221 | @menu |
bfe6ffb6 GM |
222 | * Grammar format:: |
223 | * Example:: | |
224 | * Compiling a grammar:: | |
225 | * Conflicts:: | |
9e7abd17 EL |
226 | @end menu |
227 | ||
228 | @node Grammar format, Example, Wisent Grammar, Wisent Grammar | |
229 | @comment node-name, next, previous, up | |
230 | @section Grammar format | |
231 | ||
232 | @cindex grammar format | |
233 | To be acceptable by Wisent a context-free grammar must respect a | |
234 | particular format. That is, must be represented as an Emacs Lisp list | |
235 | of the form: | |
236 | ||
237 | @code{(@var{terminals} @var{assocs} . @var{non-terminals})} | |
238 | ||
239 | @table @var | |
240 | @item terminals | |
241 | Is the list of terminal symbols used in the grammar. | |
242 | ||
243 | @cindex associativity | |
244 | @item assocs | |
245 | Specify the associativity of @var{terminals}. It is @code{nil} when | |
246 | there is no associativity defined, or an alist of | |
247 | @w{@code{(@var{assoc-type} . @var{assoc-value})}} elements. | |
248 | ||
249 | @var{assoc-type} must be one of the @code{default-prec}, | |
250 | @code{nonassoc}, @code{left} or @code{right} symbols. When | |
251 | @var{assoc-type} is @code{default-prec}, @var{assoc-value} must be | |
252 | @code{nil} or @code{t} (the default). Otherwise it is a list of | |
253 | tokens which must have been previously declared in @var{terminals}. | |
254 | ||
255 | For details, see @ref{Contextual Precedence, , , bison}, in the | |
256 | Bison manual. | |
257 | ||
258 | @item non-terminals | |
259 | Is the list of nonterminal definitions. Each definition has the form: | |
260 | ||
261 | @code{(@var{nonterm} . @var{rules})} | |
262 | ||
263 | Where @var{nonterm} is the nonterminal symbol defined and | |
264 | @var{rules} the list of rules that describe this nonterminal. Each | |
265 | rule is a list: | |
266 | ||
267 | @code{(@var{components} [@var{precedence}] [@var{action}])} | |
268 | ||
269 | Where: | |
270 | ||
271 | @table @var | |
272 | @item components | |
273 | Is a list of various terminals and nonterminals that are put together | |
274 | by this rule. | |
275 | ||
276 | For example, | |
277 | ||
278 | @example | |
279 | @group | |
280 | (exp ((exp ?+ exp)) ;; exp: exp '+' exp | |
281 | ) ;; ; | |
282 | @end group | |
283 | @end example | |
284 | ||
285 | Says that two groupings of type @samp{exp}, with a @samp{+} token in | |
286 | between, can be combined into a larger grouping of type @samp{exp}. | |
287 | ||
288 | @cindex grammar coding conventions | |
289 | By convention, a nonterminal symbol should be in lower case, such as | |
290 | @samp{exp}, @samp{stmt} or @samp{declaration}. Terminal symbols | |
291 | should be upper case to distinguish them from nonterminals: for | |
292 | example, @samp{INTEGER}, @samp{IDENTIFIER}, @samp{IF} or | |
293 | @samp{RETURN}. A terminal symbol that represents a particular keyword | |
294 | in the language is conventionally the same as that keyword converted | |
295 | to upper case. The terminal symbol @code{error} is reserved for error | |
296 | recovery. | |
297 | ||
298 | @cindex middle-rule actions | |
299 | Scattered among the components can be @dfn{middle-rule} actions. | |
300 | Usually only @var{action} is provided (@pxref{action}). | |
301 | ||
302 | If @var{components} in a rule is @code{nil}, it means that the rule | |
303 | can match the empty string. For example, here is how to define a | |
304 | comma-separated sequence of zero or more @samp{exp} groupings: | |
305 | ||
306 | @example | |
307 | @group | |
308 | (expseq (nil) ;; expseq: ;; empty | |
309 | ((expseq1)) ;; | expseq1 | |
310 | ) ;; ; | |
311 | ||
312 | (expseq1 ((exp)) ;; expseq1: exp | |
313 | ((expseq1 ?, exp)) ;; | expseq1 ',' exp | |
314 | ) ;; ; | |
315 | @end group | |
316 | @end example | |
317 | ||
318 | @cindex precedence level | |
319 | @item precedence | |
320 | Assign the rule the precedence of the given terminal item, overriding | |
321 | the precedence that would be deduced for it, that is the one of the | |
322 | last terminal in it. Notice that only terminals declared in | |
323 | @var{assocs} have a precedence level. The altered rule precedence | |
324 | then affects how conflicts involving that rule are resolved. | |
325 | ||
326 | @var{precedence} is an optional vector of one terminal item. | |
327 | ||
328 | Here is how @var{precedence} solves the problem of unary minus. | |
329 | First, declare a precedence for a fictitious terminal symbol named | |
330 | @code{UMINUS}. There are no tokens of this type, but the symbol | |
331 | serves to stand for its precedence: | |
332 | ||
333 | @example | |
334 | @dots{} | |
335 | ((default-prec t) ;; This is the default | |
336 | (left '+' '-') | |
337 | (left '*') | |
338 | (left UMINUS)) | |
339 | @end example | |
340 | ||
341 | Now the precedence of @code{UMINUS} can be used in specific rules: | |
342 | ||
343 | @example | |
344 | @group | |
345 | (exp @dots{} ;; exp: @dots{} | |
346 | ((exp ?- exp)) ;; | exp '-' exp | |
347 | @dots{} ;; @dots{} | |
348 | ((?- exp) [UMINUS]) ;; | '-' exp %prec UMINUS | |
349 | @dots{} ;; @dots{} | |
350 | ) ;; ; | |
351 | @end group | |
352 | @end example | |
353 | ||
354 | If you forget to append @code{[UMINUS]} to the rule for unary minus, | |
355 | Wisent silently assumes that minus has its usual precedence. This | |
356 | kind of problem can be tricky to debug, since one typically discovers | |
357 | the mistake only by testing the code. | |
358 | ||
359 | Using @code{(default-prec nil)} declaration makes it easier to | |
360 | discover this kind of problem systematically. It causes rules that | |
361 | lack a @var{precedence} modifier to have no precedence, even if the | |
362 | last terminal symbol mentioned in their components has a declared | |
363 | precedence. | |
364 | ||
365 | If @code{(default-prec nil)} is in effect, you must specify | |
366 | @var{precedence} for all rules that participate in precedence conflict | |
367 | resolution. Then you will see any shift/reduce conflict until you | |
368 | tell Wisent how to resolve it, either by changing your grammar or by | |
369 | adding an explicit precedence. This will probably add declarations to | |
370 | the grammar, but it helps to protect against incorrect rule | |
371 | precedences. | |
372 | ||
373 | The effect of @code{(default-prec nil)} can be reversed by giving | |
374 | @code{(default-prec t)}, which is the default. | |
375 | ||
376 | For more details, see @ref{Contextual Precedence, , , bison}, in the | |
377 | Bison manual. | |
378 | ||
379 | It is important to understand that @var{assocs} declarations defines | |
380 | associativity but also assign a precedence level to terminals. All | |
381 | terminals declared in the same @code{left}, @code{right} or | |
382 | @code{nonassoc} association get the same precedence level. The | |
383 | precedence level is increased at each new association. | |
384 | ||
385 | On the other hand, @var{precedence} explicitly assign the precedence | |
386 | level of the given terminal to a rule. | |
387 | ||
388 | @cindex semantic actions | |
389 | @item @anchor{action}action | |
390 | An action is an optional Emacs Lisp function call, like this: | |
391 | ||
392 | @code{(identity $1)} | |
393 | ||
394 | The result of an action determines the semantic value of a rule. | |
395 | ||
396 | From an implementation standpoint, the function call will be embedded | |
397 | in a lambda expression, and several useful local variables will be | |
398 | defined: | |
399 | ||
400 | @table @code | |
401 | @vindex $N | |
402 | @item $@var{n} | |
403 | Where @var{n} is a positive integer. Like in Bison, the value of | |
404 | @code{$@var{n}} is the semantic value of the @var{n}th element of | |
405 | @var{components}, starting from 1. It can be of any Lisp data | |
406 | type. | |
407 | ||
408 | @vindex $region@var{n} | |
409 | @item $regionN | |
410 | Where @var{n} is a positive integer. For each @code{$@var{n}} | |
411 | variable defined there is a corresponding @code{$region@var{n}} | |
412 | variable. Its value is a pair @code{(@var{start-pos} . | |
413 | @var{end-pos})} that represent the start and end positions (in the | |
414 | lexical input stream) of the @code{$@var{n}} value. It can be | |
415 | @code{nil} when the component positions are not available, like for an | |
416 | empty string component for example. | |
417 | ||
418 | @vindex $region | |
419 | @item $region | |
420 | Its value is the leftmost and rightmost positions of input data | |
421 | matched by all @var{components} in the rule. This is a pair | |
422 | @code{(@var{leftmost-pos} . @var{rightmost-pos})}. It can be | |
423 | @code{nil} when components positions are not available. | |
424 | ||
425 | @vindex $nterm | |
426 | @item $nterm | |
427 | This variable is initialized with the nonterminal symbol | |
428 | (@var{nonterm}) the rule belongs to. It could be useful to improve | |
429 | error reporting or debugging. It is also used to automatically | |
430 | provide incremental re-parse entry points for @semantic{} tags | |
431 | (@pxref{Wisent Semantic}). | |
432 | ||
433 | @vindex $action | |
434 | @item $action | |
435 | The value of @code{$action} is the symbolic name of the current | |
436 | semantic action (@pxref{Debugging actions}). | |
437 | @end table | |
438 | ||
439 | When an action is not specified a default value is supplied, it is | |
440 | @code{(identity $1)}. This means that the default semantic value of a | |
441 | rule is the value of its first component. Excepted for a rule | |
442 | matching the empty string, for which the default action is to return | |
443 | @code{nil}. | |
444 | @end table | |
445 | @end table | |
446 | ||
447 | @node Example, Compiling a grammar, Grammar format, Wisent Grammar | |
448 | @comment node-name, next, previous, up | |
449 | @section Example | |
450 | ||
451 | @cindex grammar example | |
452 | Here is an example to parse simple infix arithmetic expressions. See | |
453 | @ref{Infix Calc, , , bison}, in the Bison manual for details. | |
454 | ||
455 | @lisp | |
456 | @group | |
457 | '( | |
458 | ;; Terminals | |
459 | (NUM) | |
bfe6ffb6 | 460 | |
9e7abd17 EL |
461 | ;; Terminal associativity & precedence |
462 | ((nonassoc ?=) | |
463 | (left ?- ?+) | |
464 | (left ?* ?/) | |
465 | (left NEG) | |
466 | (right ?^)) | |
bfe6ffb6 | 467 | |
9e7abd17 EL |
468 | ;; Rules |
469 | (input | |
470 | ((line)) | |
471 | ((input line) | |
472 | (format "%s %s" $1 $2)) | |
473 | ) | |
474 | ||
475 | (line | |
476 | ((?;) | |
477 | (progn ";")) | |
478 | ((exp ?;) | |
479 | (format "%s;" $1)) | |
480 | ((error ?;) | |
481 | (progn "Error;"))) | |
482 | ) | |
483 | ||
484 | (exp | |
485 | ((NUM) | |
486 | (string-to-number $1)) | |
487 | ((exp ?= exp) | |
488 | (= $1 $3)) | |
489 | ((exp ?+ exp) | |
490 | (+ $1 $3)) | |
491 | ((exp ?- exp) | |
492 | (- $1 $3)) | |
493 | ((exp ?* exp) | |
494 | (* $1 $3)) | |
495 | ((exp ?/ exp) | |
496 | (/ $1 $3)) | |
497 | ((?- exp) [NEG] | |
498 | (- $2)) | |
499 | ((exp ?^ exp) | |
500 | (expt $1 $3)) | |
501 | ((?\( exp ?\)) | |
502 | (progn $2)) | |
503 | ) | |
504 | ) | |
505 | @end group | |
506 | @end lisp | |
507 | ||
508 | In the bison-like @dfn{WY} format (@pxref{Wisent Semantic}) the | |
509 | grammar looks like this: | |
510 | ||
511 | @example | |
512 | @group | |
513 | %token <number> NUM | |
514 | ||
515 | %nonassoc '=' ;; comparison | |
516 | %left '-' '+' | |
517 | %left '*' '/' | |
518 | %left NEG ;; negation--unary minus | |
519 | %right '^' ;; exponentiation | |
520 | ||
521 | %% | |
522 | ||
523 | input: | |
524 | line | |
525 | | input line | |
526 | (format "%s %s" $1 $2) | |
527 | ; | |
528 | ||
529 | line: | |
530 | ';' | |
531 | @{";"@} | |
532 | | exp ';' | |
533 | (format "%s;" $1) | |
534 | | error ';' | |
535 | @{"Error;"@} | |
536 | ; | |
537 | ||
538 | exp: | |
539 | NUM | |
540 | (string-to-number $1) | |
541 | | exp '=' exp | |
542 | (= $1 $3) | |
543 | | exp '+' exp | |
544 | (+ $1 $3) | |
545 | | exp '-' exp | |
546 | (- $1 $3) | |
547 | | exp '*' exp | |
548 | (* $1 $3) | |
549 | | exp '/' exp | |
550 | (/ $1 $3) | |
551 | | '-' exp %prec NEG | |
552 | (- $2) | |
553 | | exp '^' exp | |
554 | (expt $1 $3) | |
555 | | '(' exp ')' | |
556 | @{$2@} | |
557 | ; | |
558 | ||
559 | %% | |
560 | @end group | |
561 | @end example | |
562 | ||
563 | @node Compiling a grammar, Conflicts, Example, Wisent Grammar | |
564 | @comment node-name, next, previous, up | |
565 | @section Compiling a grammar | |
566 | ||
567 | @cindex automaton | |
568 | After providing a context-free grammar in a suitable format, it must | |
569 | be translated into a set of tables (an @dfn{automaton}) that will be | |
570 | used to derive the parser. Like Bison, Wisent translates grammars that | |
571 | must be @dfn{LALR(1)}. | |
572 | ||
573 | @cindex LALR(1) grammar | |
574 | @cindex look-ahead token | |
575 | A grammar is @acronym{LALR(1)} if it is possible to tell how to parse | |
576 | any portion of an input string with just a single token of look-ahead: | |
577 | the @dfn{look-ahead token}. See @ref{Language and Grammar, , , | |
578 | bison}, in the Bison manual for more information. | |
579 | ||
580 | @cindex grammar compilation | |
581 | Grammar translation (compilation) is achieved by the function: | |
582 | ||
583 | @cindex compiling a grammar | |
584 | @vindex wisent-single-start-flag | |
585 | @findex wisent-compile-grammar | |
586 | @defun wisent-compile-grammar grammar &optional start-list | |
587 | Compile @var{grammar} and return an @acronym{LALR(1)} automaton. | |
588 | ||
589 | Optional argument @var{start-list} is a list of start symbols | |
590 | (nonterminals). If @code{nil} the first nonterminal defined in the | |
591 | grammar is the default start symbol. If @var{start-list} contains | |
592 | only one element, it defines the start symbol. If @var{start-list} | |
593 | contains more than one element, all are defined as potential start | |
594 | symbols, unless @code{wisent-single-start-flag} is non-@code{nil}. In | |
595 | that case the first element of @var{start-list} defines the start | |
596 | symbol and others are ignored. | |
597 | ||
598 | The @acronym{LALR(1)} automaton is a vector of the form: | |
599 | ||
600 | @code{[@var{actions gotos starts functions}]} | |
601 | ||
602 | @table @var | |
603 | @item actions | |
604 | A state/token matrix telling the parser what to do at every state | |
605 | based on the current look-ahead token. That is shift, reduce, accept | |
606 | or error. See also @ref{Wisent Parsing}. | |
607 | ||
608 | @item gotos | |
609 | A state/nonterminal matrix telling the parser the next state to go to | |
610 | after reducing with each rule. | |
611 | ||
612 | @item starts | |
613 | An alist which maps the allowed start symbols (nonterminals) to | |
614 | lexical tokens that will be first shifted into the parser stack. | |
615 | ||
616 | @item functions | |
617 | An obarray of semantic action symbols. A semantic action is actually | |
618 | an Emacs Lisp function (lambda expression). | |
619 | @end table | |
620 | @end defun | |
621 | ||
622 | @node Conflicts, , Compiling a grammar, Wisent Grammar | |
623 | @comment node-name, next, previous, up | |
624 | @section Conflicts | |
625 | ||
626 | Normally, a grammar should produce an automaton where at each state | |
627 | the parser has only one action to do (@pxref{Wisent Parsing}). | |
628 | ||
629 | @cindex ambiguous grammar | |
630 | In certain cases, a grammar can produce an automaton where, at some | |
631 | states, there are more than one action possible. Such a grammar is | |
632 | @dfn{ambiguous}, and generates @dfn{conflicts}. | |
633 | ||
634 | @cindex deterministic automaton | |
635 | The parser can't be driven by an automaton which isn't completely | |
636 | @dfn{deterministic}, that is which contains conflicts. It is | |
637 | necessary to resolve the conflicts to eliminate them. Wisent resolves | |
638 | conflicts like Bison does. | |
639 | ||
640 | @cindex grammar conflicts | |
641 | @cindex conflicts resolution | |
642 | There are two sorts of conflicts: | |
643 | ||
644 | @table @dfn | |
645 | @cindex shift/reduce conflicts | |
646 | @item shift/reduce conflicts | |
647 | When either a shift or a reduction would be valid at the same state. | |
648 | ||
649 | Such conflicts are resolved by choosing to shift, unless otherwise | |
650 | directed by operator precedence declarations. | |
651 | See @ref{Shift/Reduce , , , bison}, in the Bison manual for more | |
652 | information. | |
653 | ||
654 | @cindex reduce/reduce conflicts | |
655 | @item reduce/reduce conflicts | |
656 | That occurs if there are two or more rules that apply to the same | |
657 | sequence of input. This usually indicates a serious error in the | |
658 | grammar. | |
659 | ||
660 | Such conflicts are resolved by choosing to use the rule that appears | |
661 | first in the grammar, but it is very risky to rely on this. Every | |
662 | reduce/reduce conflict must be studied and usually eliminated. See | |
663 | @ref{Reduce/Reduce , , , bison}, in the Bison manual for more | |
664 | information. | |
665 | @end table | |
666 | ||
667 | @menu | |
bfe6ffb6 GM |
668 | * Grammar Debugging:: |
669 | * Understanding the automaton:: | |
9e7abd17 EL |
670 | @end menu |
671 | ||
672 | @node Grammar Debugging | |
673 | @subsection Grammar debugging | |
674 | ||
675 | @cindex grammar debugging | |
676 | @cindex grammar verbose description | |
677 | To help writing a new grammar, @code{wisent-compile-grammar} can | |
678 | produce a verbose report containing a detailed description of the | |
679 | grammar and parser (equivalent to what Bison reports with the | |
680 | @option{--verbose} option). | |
681 | ||
682 | To enable the verbose report you can set to non-@code{nil} the | |
683 | variable: | |
684 | ||
685 | @vindex wisent-verbose-flag | |
686 | @deffn Option wisent-verbose-flag | |
687 | non-@code{nil} means to report verbose information on generated parser. | |
688 | @end deffn | |
689 | ||
690 | Or interactively use the command: | |
691 | ||
692 | @findex wisent-toggle-verbose-flag | |
693 | @deffn Command wisent-toggle-verbose-flag | |
694 | Toggle whether to report verbose information on generated parser. | |
695 | @end deffn | |
696 | ||
697 | The verbose report is printed in the temporary buffer | |
698 | @code{*wisent-log*} when running interactively, or in file | |
699 | @file{wisent.output} when running in batch mode. Different | |
700 | reports are separated from each other by a line like this: | |
701 | ||
702 | @example | |
703 | @group | |
704 | *** Wisent @var{source-file} - 2002-06-27 17:33 | |
705 | @end group | |
706 | @end example | |
707 | ||
708 | where @var{source-file} is the name of the Emacs Lisp file from which | |
709 | the grammar was read. See @ref{Understanding the automaton}, for | |
710 | details on the verbose report. | |
711 | ||
712 | @table @strong | |
713 | @item Please Note | |
714 | To help debugging the grammar compiler itself, you can set this | |
715 | variable to print the content of some internal data structures: | |
716 | ||
717 | @vindex wisent-debug-flag | |
718 | @defvar wisent-debug-flag | |
719 | non-@code{nil} means enable some debug stuff. | |
720 | @end defvar | |
721 | @end table | |
722 | ||
723 | @node Understanding the automaton | |
724 | @subsection Understanding the automaton | |
725 | ||
726 | @cindex understanding the automaton | |
727 | This section (took from the manual of Bison 1.49) describes how to use | |
728 | the verbose report printed by @code{wisent-compile-grammar} to | |
729 | understand the generated automaton, to tune or fix a grammar. | |
730 | ||
731 | We will use the following example: | |
732 | ||
733 | @example | |
734 | @group | |
735 | (let ((wisent-verbose-flag t)) ;; Print a verbose report! | |
736 | (wisent-compile-grammar | |
737 | '((NUM STR) ; %token NUM STR | |
738 | ||
bfe6ffb6 | 739 | ((left ?+ ?-) ; %left '+' '-'; |
9e7abd17 EL |
740 | (left ?*)) ; %left '*' |
741 | ||
742 | (exp ; exp: | |
743 | ((exp ?+ exp)) ; exp '+' exp | |
744 | ((exp ?- exp)) ; | exp '-' exp | |
745 | ((exp ?* exp)) ; | exp '*' exp | |
746 | ((exp ?/ exp)) ; | exp '/' exp | |
747 | ((NUM)) ; | NUM | |
748 | ) ; ; | |
749 | ||
750 | (useless ; useless: | |
751 | ((STR)) ; STR | |
752 | ) ; ; | |
753 | ) | |
754 | 'nil) ; no %start declarations | |
755 | ) | |
756 | @end group | |
757 | @end example | |
758 | ||
759 | When evaluating the above expression, grammar compilation first issues | |
760 | the following two clear messages: | |
761 | ||
762 | @example | |
763 | @group | |
764 | Grammar contains 1 useless nonterminals and 1 useless rules | |
765 | Grammar contains 7 shift/reduce conflicts | |
766 | @end group | |
767 | @end example | |
768 | ||
769 | The @samp{*wisent-log*} buffer details things! | |
770 | ||
771 | The first section reports conflicts that were solved using precedence | |
772 | and/or associativity: | |
773 | ||
774 | @example | |
775 | @group | |
776 | Conflict in state 7 between rule 1 and token '+' resolved as reduce. | |
777 | Conflict in state 7 between rule 1 and token '-' resolved as reduce. | |
778 | Conflict in state 7 between rule 1 and token '*' resolved as shift. | |
779 | Conflict in state 8 between rule 2 and token '+' resolved as reduce. | |
780 | Conflict in state 8 between rule 2 and token '-' resolved as reduce. | |
781 | Conflict in state 8 between rule 2 and token '*' resolved as shift. | |
782 | Conflict in state 9 between rule 3 and token '+' resolved as reduce. | |
783 | Conflict in state 9 between rule 3 and token '-' resolved as reduce. | |
784 | Conflict in state 9 between rule 3 and token '*' resolved as reduce. | |
785 | @end group | |
786 | @end example | |
787 | ||
788 | The next section reports useless tokens, nonterminal and rules (note | |
789 | that useless tokens might be used by the scanner): | |
790 | ||
791 | @example | |
792 | @group | |
793 | Useless nonterminals: | |
794 | ||
795 | useless | |
796 | ||
797 | ||
798 | Terminals which are not used: | |
799 | ||
800 | STR | |
801 | ||
802 | ||
803 | Useless rules: | |
804 | ||
805 | #6 useless: STR; | |
806 | @end group | |
807 | @end example | |
808 | ||
809 | The next section lists states that still have conflicts: | |
810 | ||
811 | @example | |
812 | @group | |
813 | State 7 contains 1 shift/reduce conflict. | |
814 | State 8 contains 1 shift/reduce conflict. | |
815 | State 9 contains 1 shift/reduce conflict. | |
816 | State 10 contains 4 shift/reduce conflicts. | |
817 | @end group | |
818 | @end example | |
819 | ||
820 | The next section reproduces the grammar used: | |
821 | ||
822 | @example | |
823 | @group | |
824 | Grammar | |
825 | ||
826 | Number, Rule | |
827 | 1 exp -> exp '+' exp | |
828 | 2 exp -> exp '-' exp | |
829 | 3 exp -> exp '*' exp | |
830 | 4 exp -> exp '/' exp | |
831 | 5 exp -> NUM | |
832 | @end group | |
833 | @end example | |
834 | ||
835 | And reports the uses of the symbols: | |
836 | ||
837 | @example | |
838 | @group | |
839 | Terminals, with rules where they appear | |
840 | ||
841 | $EOI (-1) | |
842 | error (1) | |
843 | NUM (2) 5 | |
844 | STR (3) 6 | |
845 | '+' (4) 1 | |
846 | '-' (5) 2 | |
847 | '*' (6) 3 | |
848 | '/' (7) 4 | |
849 | ||
850 | ||
851 | Nonterminals, with rules where they appear | |
852 | ||
853 | exp (8) | |
854 | on left: 1 2 3 4 5, on right: 1 2 3 4 | |
855 | @end group | |
856 | @end example | |
857 | ||
858 | The report then details the automaton itself, describing each state | |
859 | with it set of @dfn{items}, also known as @dfn{pointed rules}. Each | |
860 | item is a production rule together with a point (marked by @samp{.}) | |
861 | that the input cursor. | |
862 | ||
863 | @example | |
864 | @group | |
865 | state 0 | |
866 | ||
867 | NUM shift, and go to state 1 | |
868 | ||
869 | exp go to state 2 | |
870 | @end group | |
871 | @end example | |
872 | ||
873 | State 0 corresponds to being at the very beginning of the parsing, in | |
874 | the initial rule, right before the start symbol (@samp{exp}). When | |
875 | the parser returns to this state right after having reduced a rule | |
876 | that produced an @samp{exp}, it jumps to state 2. If there is no such | |
877 | transition on a nonterminal symbol, and the lookahead is a @samp{NUM}, | |
878 | then this token is shifted on the parse stack, and the control flow | |
879 | jumps to state 1. Any other lookahead triggers a parse error. | |
880 | ||
881 | In the state 1... | |
882 | ||
883 | @example | |
884 | @group | |
885 | state 1 | |
886 | ||
887 | exp -> NUM . (rule 5) | |
888 | ||
889 | $default reduce using rule 5 (exp) | |
890 | @end group | |
891 | @end example | |
892 | ||
893 | the rule 5, @samp{exp: NUM;}, is completed. Whatever the lookahead | |
894 | (@samp{$default}), the parser will reduce it. If it was coming from | |
895 | state 0, then, after this reduction it will return to state 0, and | |
896 | will jump to state 2 (@samp{exp: go to state 2}). | |
897 | ||
898 | @example | |
899 | @group | |
900 | state 2 | |
901 | ||
902 | exp -> exp . '+' exp (rule 1) | |
903 | exp -> exp . '-' exp (rule 2) | |
904 | exp -> exp . '*' exp (rule 3) | |
905 | exp -> exp . '/' exp (rule 4) | |
906 | ||
907 | $EOI shift, and go to state 11 | |
908 | '+' shift, and go to state 3 | |
909 | '-' shift, and go to state 4 | |
910 | '*' shift, and go to state 5 | |
911 | '/' shift, and go to state 6 | |
912 | @end group | |
913 | @end example | |
914 | ||
915 | In state 2, the automaton can only shift a symbol. For instance, | |
916 | because of the item @samp{exp -> exp . '+' exp}, if the lookahead if | |
917 | @samp{+}, it will be shifted on the parse stack, and the automaton | |
918 | control will jump to state 3, corresponding to the item | |
919 | @samp{exp -> exp . '+' exp}: | |
920 | ||
921 | @example | |
922 | @group | |
923 | state 3 | |
924 | ||
925 | exp -> exp '+' . exp (rule 1) | |
926 | ||
927 | NUM shift, and go to state 1 | |
928 | ||
929 | exp go to state 7 | |
930 | @end group | |
931 | @end example | |
932 | ||
933 | Since there is no default action, any other token than those listed | |
934 | above will trigger a parse error. | |
935 | ||
936 | The interpretation of states 4 to 6 is straightforward: | |
937 | ||
938 | @example | |
939 | @group | |
940 | state 4 | |
941 | ||
942 | exp -> exp '-' . exp (rule 2) | |
943 | ||
944 | NUM shift, and go to state 1 | |
945 | ||
946 | exp go to state 8 | |
947 | ||
948 | ||
949 | ||
950 | state 5 | |
951 | ||
952 | exp -> exp '*' . exp (rule 3) | |
953 | ||
954 | NUM shift, and go to state 1 | |
955 | ||
956 | exp go to state 9 | |
957 | ||
958 | ||
959 | ||
960 | state 6 | |
961 | ||
962 | exp -> exp '/' . exp (rule 4) | |
963 | ||
964 | NUM shift, and go to state 1 | |
965 | ||
966 | exp go to state 10 | |
967 | @end group | |
968 | @end example | |
969 | ||
970 | As was announced in beginning of the report, @samp{State 7 contains 1 | |
971 | shift/reduce conflict.}: | |
972 | ||
973 | @example | |
974 | @group | |
975 | state 7 | |
976 | ||
977 | exp -> exp . '+' exp (rule 1) | |
978 | exp -> exp '+' exp . (rule 1) | |
979 | exp -> exp . '-' exp (rule 2) | |
980 | exp -> exp . '*' exp (rule 3) | |
981 | exp -> exp . '/' exp (rule 4) | |
982 | ||
983 | '*' shift, and go to state 5 | |
984 | '/' shift, and go to state 6 | |
985 | ||
986 | '/' [reduce using rule 1 (exp)] | |
987 | $default reduce using rule 1 (exp) | |
988 | @end group | |
989 | @end example | |
990 | ||
991 | Indeed, there are two actions associated to the lookahead @samp{/}: | |
992 | either shifting (and going to state 6), or reducing rule 1. The | |
993 | conflict means that either the grammar is ambiguous, or the parser | |
994 | lacks information to make the right decision. Indeed the grammar is | |
995 | ambiguous, as, since we did not specify the precedence of @samp{/}, | |
996 | the sentence @samp{NUM + NUM / NUM} can be parsed as @samp{NUM + (NUM | |
997 | / NUM)}, which corresponds to shifting @samp{/}, or as @samp{(NUM + | |
998 | NUM) / NUM}, which corresponds to reducing rule 1. | |
999 | ||
1000 | Because in @acronym{LALR(1)} parsing a single decision can be made, | |
1001 | Wisent arbitrarily chose to disable the reduction, see | |
1002 | @ref{Conflicts}. Discarded actions are reported in between square | |
1003 | brackets. | |
1004 | ||
1005 | Note that all the previous states had a single possible action: either | |
1006 | shifting the next token and going to the corresponding state, or | |
1007 | reducing a single rule. In the other cases, i.e., when shifting | |
1008 | @emph{and} reducing is possible or when @emph{several} reductions are | |
1009 | possible, the lookahead is required to select the action. State 7 is | |
1010 | one such state: if the lookahead is @samp{*} or @samp{/} then the | |
1011 | action is shifting, otherwise the action is reducing rule 1. In other | |
1012 | words, the first two items, corresponding to rule 1, are not eligible | |
1013 | when the lookahead is @samp{*}, since we specified that @samp{*} has | |
1014 | higher precedence that @samp{+}. More generally, some items are | |
1015 | eligible only with some set of possible lookaheads. | |
1016 | ||
1017 | States 8 to 10 are similar: | |
1018 | ||
1019 | @example | |
1020 | @group | |
1021 | state 8 | |
1022 | ||
1023 | exp -> exp . '+' exp (rule 1) | |
1024 | exp -> exp . '-' exp (rule 2) | |
1025 | exp -> exp '-' exp . (rule 2) | |
1026 | exp -> exp . '*' exp (rule 3) | |
1027 | exp -> exp . '/' exp (rule 4) | |
1028 | ||
1029 | '*' shift, and go to state 5 | |
1030 | '/' shift, and go to state 6 | |
1031 | ||
1032 | '/' [reduce using rule 2 (exp)] | |
1033 | $default reduce using rule 2 (exp) | |
1034 | ||
1035 | ||
1036 | ||
1037 | state 9 | |
1038 | ||
1039 | exp -> exp . '+' exp (rule 1) | |
1040 | exp -> exp . '-' exp (rule 2) | |
1041 | exp -> exp . '*' exp (rule 3) | |
1042 | exp -> exp '*' exp . (rule 3) | |
1043 | exp -> exp . '/' exp (rule 4) | |
1044 | ||
1045 | '/' shift, and go to state 6 | |
1046 | ||
1047 | '/' [reduce using rule 3 (exp)] | |
1048 | $default reduce using rule 3 (exp) | |
1049 | ||
1050 | ||
1051 | ||
1052 | state 10 | |
1053 | ||
1054 | exp -> exp . '+' exp (rule 1) | |
1055 | exp -> exp . '-' exp (rule 2) | |
1056 | exp -> exp . '*' exp (rule 3) | |
1057 | exp -> exp . '/' exp (rule 4) | |
1058 | exp -> exp '/' exp . (rule 4) | |
1059 | ||
1060 | '+' shift, and go to state 3 | |
1061 | '-' shift, and go to state 4 | |
1062 | '*' shift, and go to state 5 | |
1063 | '/' shift, and go to state 6 | |
1064 | ||
1065 | '+' [reduce using rule 4 (exp)] | |
1066 | '-' [reduce using rule 4 (exp)] | |
1067 | '*' [reduce using rule 4 (exp)] | |
1068 | '/' [reduce using rule 4 (exp)] | |
1069 | $default reduce using rule 4 (exp) | |
1070 | @end group | |
1071 | @end example | |
1072 | ||
1073 | Observe that state 10 contains conflicts due to the lack of precedence | |
1074 | of @samp{/} wrt @samp{+}, @samp{-}, and @samp{*}, but also because the | |
1075 | associativity of @samp{/} is not specified. | |
1076 | ||
1077 | Finally, the state 11 (plus 12) is named the @dfn{final state}, or the | |
1078 | @dfn{accepting state}: | |
1079 | ||
1080 | @example | |
1081 | @group | |
1082 | state 11 | |
1083 | ||
1084 | $EOI shift, and go to state 12 | |
1085 | ||
1086 | ||
1087 | ||
1088 | state 12 | |
1089 | ||
1090 | $default accept | |
1091 | @end group | |
1092 | @end example | |
1093 | ||
1094 | The end of input is shifted @samp{$EOI shift,} and the parser exits | |
1095 | successfully (@samp{go to state 12}, that terminates). | |
1096 | ||
1097 | @node Wisent Parsing | |
1098 | @chapter Wisent Parsing | |
1099 | ||
1100 | @cindex bottom-up parser | |
1101 | @cindex shift-reduce parser | |
1102 | The Wisent's parser is what is called a @dfn{bottom-up} or | |
1103 | @dfn{shift-reduce} parser which repeatedly: | |
1104 | ||
1105 | @table @dfn | |
1106 | @cindex shift | |
1107 | @item shift | |
1108 | That is pushes the value of the last lexical token read (the | |
1109 | look-ahead token) into a value stack, and reads a new one. | |
1110 | ||
1111 | @cindex reduce | |
1112 | @item reduce | |
1113 | That is replaces a nonterminal by its semantic value. The values of | |
1114 | the components which form the right hand side of a rule are popped | |
1115 | from the value stack and reduced by the semantic action of this rule. | |
1116 | The result is pushed back on top of value stack. | |
1117 | @end table | |
1118 | ||
1119 | The parser will stop on: | |
1120 | ||
1121 | @table @dfn | |
1122 | @cindex accept | |
1123 | @item accept | |
1124 | When all input has been successfully parsed. The semantic value of | |
1125 | the start nonterminal is on top of the value stack. | |
1126 | ||
1127 | @cindex syntax error | |
1128 | @item error | |
1129 | When a syntax error (an unexpected token in input) has been detected. | |
1130 | At this point the parser issues an error message and either stops or | |
1131 | calls a recovery routine to try to resume parsing. | |
1132 | @end table | |
1133 | ||
1134 | @cindex table-driven parser | |
1135 | The above elementary actions are driven by the @acronym{LALR(1)} | |
1136 | automaton built by @code{wisent-compile-grammar} from a context-free | |
1137 | grammar. | |
1138 | ||
1139 | The Wisent's parser is entered by calling the function: | |
1140 | ||
1141 | @findex wisent-parse | |
1142 | @defun wisent-parse automaton lexer &optional error start | |
1143 | Parse input using the automaton specified in @var{automaton}. | |
1144 | ||
1145 | @table @var | |
1146 | @item automaton | |
1147 | Is an @acronym{LALR(1)} automaton generated by | |
1148 | @code{wisent-compile-grammar} (@pxref{Wisent Grammar}). | |
1149 | ||
1150 | @item lexer | |
1151 | Is a function with no argument called by the parser to obtain the next | |
1152 | terminal (token) in input (@pxref{Writing a lexer}). | |
1153 | ||
1154 | @item error | |
1155 | Is an optional reporting function called when a parse error occurs. | |
1156 | It receives a message string to report. It defaults to the function | |
1157 | @code{wisent-message} (@pxref{Report errors}). | |
1158 | ||
1159 | @item start | |
1160 | Specify the start symbol (nonterminal) used by the parser as its goal. | |
1161 | It defaults to the start symbol defined in the grammar | |
1162 | (@pxref{Wisent Grammar}). | |
1163 | @end table | |
1164 | @end defun | |
1165 | ||
1166 | The following two normal hooks permit to do some useful processing | |
1167 | respectively before to start parsing, and after the parser terminated. | |
1168 | ||
1169 | @vindex wisent-pre-parse-hook | |
1170 | @defvar wisent-pre-parse-hook | |
1171 | Normal hook run just before entering the @var{LR} parser engine. | |
1172 | @end defvar | |
1173 | ||
1174 | @vindex wisent-post-parse-hook | |
1175 | @defvar wisent-post-parse-hook | |
1176 | Normal hook run just after the @var{LR} parser engine terminated. | |
1177 | @end defvar | |
1178 | ||
1179 | @menu | |
bfe6ffb6 GM |
1180 | * Writing a lexer:: |
1181 | * Actions goodies:: | |
1182 | * Report errors:: | |
1183 | * Error recovery:: | |
1184 | * Debugging actions:: | |
9e7abd17 EL |
1185 | @end menu |
1186 | ||
1187 | @node Writing a lexer | |
1188 | @section What the parser must receive | |
1189 | ||
1190 | It is important to understand that the parser does not parse | |
1191 | characters, but lexical tokens, and does not know anything about | |
1192 | characters in text streams! | |
1193 | ||
1194 | @cindex lexical analysis | |
1195 | @cindex lexer | |
1196 | @cindex scanner | |
1197 | Reading input data to produce lexical tokens is performed by a lexer | |
1198 | (also called a scanner) in a lexical analysis step, before the syntax | |
1199 | analysis step performed by the parser. The parser automatically calls | |
1200 | the lexer when it needs the next token to parse. | |
1201 | ||
1202 | @cindex lexical tokens | |
1203 | A Wisent's lexer is an Emacs Lisp function with no argument. It must | |
1204 | return a valid lexical token of the form: | |
1205 | ||
1206 | @code{(@var{token-class value} [@var{start} . @var{end}])} | |
1207 | ||
1208 | @table @var | |
1209 | @item token-class | |
1210 | Is a category of lexical token identifying a terminal as specified in | |
1211 | the grammar (@pxref{Wisent Grammar}). It can be a symbol or a character | |
1212 | literal. | |
1213 | ||
1214 | @item value | |
1215 | Is the value of the lexical token. It can be of any valid Emacs Lisp | |
1216 | data type. | |
1217 | ||
1218 | @item start | |
1219 | @itemx end | |
1220 | Are the optionals beginning and end positions of @var{value} in the | |
1221 | input stream. | |
1222 | @end table | |
1223 | ||
1224 | When there are no more tokens to read the lexer must return the token | |
1225 | @code{(list wisent-eoi-term)} to each request. | |
1226 | ||
1227 | @vindex wisent-eoi-term | |
1228 | @defvar wisent-eoi-term | |
1229 | Predefined constant, End-Of-Input terminal symbol. | |
1230 | @end defvar | |
1231 | ||
1232 | @code{wisent-lex} is an example of a lexer that reads lexical tokens | |
1233 | produced by a @semantic{} lexer, and translates them into lexical tokens | |
1234 | suitable to the Wisent parser. See also @ref{Wisent Lex}. | |
1235 | ||
1236 | To call the lexer in a semantic action use the function | |
1237 | @code{wisent-lexer}. See also @ref{Actions goodies}. | |
1238 | ||
1239 | @node Actions goodies | |
1240 | @section Variables and macros useful in grammar actions. | |
1241 | ||
1242 | @vindex wisent-input | |
1243 | @defvar wisent-input | |
1244 | The last token read. | |
1245 | This variable only has meaning in the scope of @code{wisent-parse}. | |
1246 | @end defvar | |
1247 | ||
1248 | @findex wisent-lexer | |
1249 | @defun wisent-lexer | |
1250 | Obtain the next terminal in input. | |
1251 | @end defun | |
1252 | ||
1253 | @findex wisent-region | |
1254 | @defun wisent-region &rest positions | |
1255 | Return the start/end positions of the region including | |
1256 | @var{positions}. Each element of @var{positions} is a pair | |
1257 | @w{@code{(@var{start-pos} . @var{end-pos})}} or @code{nil}. The | |
1258 | returned value is the pair @w{@code{(@var{min-start-pos} . | |
1259 | @var{max-end-pos})}} or @code{nil} if no @var{positions} are | |
1260 | available. | |
1261 | @end defun | |
1262 | ||
1263 | @node Report errors | |
1264 | @section The error reporting function | |
1265 | ||
1266 | @cindex error reporting | |
1267 | When the parser encounters a syntax error it calls a user-defined | |
1268 | function. It must be an Emacs Lisp function with one argument: a | |
1269 | string containing the message to report. | |
1270 | ||
1271 | By default the parser uses this function to report error messages: | |
1272 | ||
1273 | @findex wisent-message | |
1274 | @defun wisent-message string &rest args | |
1275 | Print a one-line message if @code{wisent-parse-verbose-flag} is set. | |
1276 | Pass @var{string} and @var{args} arguments to @dfn{message}. | |
1277 | @end defun | |
1278 | ||
1279 | @table @strong | |
1280 | @item Please Note: | |
1281 | @code{wisent-message} uses the following function to print lexical | |
1282 | tokens: | |
1283 | ||
1284 | @defun wisent-token-to-string token | |
1285 | Return a printed representation of lexical token @var{token}. | |
1286 | @end defun | |
1287 | ||
1288 | The general printed form of a lexical token is: | |
1289 | ||
1290 | @w{@code{@var{token}(@var{value})@@@var{location}}} | |
1291 | @end table | |
1292 | ||
1293 | To control the verbosity of the parser you can set to non-@code{nil} | |
1294 | this variable: | |
1295 | ||
1296 | @vindex wisent-parse-verbose-flag | |
1297 | @deffn Option wisent-parse-verbose-flag | |
1298 | non-@code{nil} means to issue more messages while parsing. | |
1299 | @end deffn | |
1300 | ||
1301 | Or interactively use the command: | |
1302 | ||
1303 | @findex wisent-parse-toggle-verbose-flag | |
1304 | @deffn Command wisent-parse-toggle-verbose-flag | |
1305 | Toggle whether to issue more messages while parsing. | |
1306 | @end deffn | |
1307 | ||
1308 | When the error reporting function is entered the variable | |
1309 | @code{wisent-input} contains the unexpected token as returned by the | |
1310 | lexer. | |
1311 | ||
1312 | The error reporting function can be called from a semantic action too | |
1313 | using the special macro @code{wisent-error}. When called from a | |
1314 | semantic action entered by error recovery (@pxref{Error recovery}) the | |
1315 | value of the variable @code{wisent-recovering} is non-@code{nil}. | |
1316 | ||
1317 | @node Error recovery | |
1318 | @section Error recovery | |
1319 | ||
1320 | @cindex error recovery | |
1321 | The error recovery mechanism of the Wisent's parser conforms to the | |
1322 | one Bison uses. See @ref{Error Recovery, , , bison}, in the Bison | |
1323 | manual for details. | |
1324 | ||
1325 | @cindex error token | |
1326 | To recover from a syntax error you must write rules to recognize the | |
1327 | special token @code{error}. This is a terminal symbol that is | |
1328 | automatically defined and reserved for error handling. | |
1329 | ||
1330 | When the parser encounters a syntax error, it pops the state stack | |
1331 | until it finds a state that allows shifting the @code{error} token. | |
1332 | After it has been shifted, if the old look-ahead token is not | |
1333 | acceptable to be shifted next, the parser reads tokens and discards | |
1334 | them until it finds a token which is acceptable. | |
1335 | ||
1336 | @cindex error recovery strategy | |
1337 | Strategies for error recovery depend on the choice of error rules in | |
1338 | the grammar. A simple and useful strategy is simply to skip the rest | |
1339 | of the current statement if an error is detected: | |
1340 | ||
1341 | @example | |
1342 | @group | |
1343 | (stmnt (( error ?; )) ;; on error, skip until ';' is read | |
1344 | ) | |
1345 | @end group | |
1346 | @end example | |
1347 | ||
1348 | It is also useful to recover to the matching close-delimiter of an | |
1349 | opening-delimiter that has already been parsed: | |
1350 | ||
1351 | @example | |
1352 | @group | |
1353 | (primary (( ?@{ expr ?@} )) | |
1354 | (( ?@{ error ?@} )) | |
1355 | @dots{} | |
1356 | ) | |
1357 | @end group | |
1358 | @end example | |
1359 | ||
1360 | @cindex error recovery actions | |
1361 | Note that error recovery rules may have actions, just as any other | |
1362 | rules can. Here are some predefined hooks, variables, functions or | |
1363 | macros, useful in such actions: | |
1364 | ||
1365 | @vindex wisent-nerrs | |
1366 | @defvar wisent-nerrs | |
1367 | The number of parse errors encountered so far. | |
1368 | @end defvar | |
1369 | ||
1370 | @vindex wisent-recovering | |
1371 | @defvar wisent-recovering | |
1372 | non-@code{nil} means that the parser is recovering. | |
1373 | This variable only has meaning in the scope of @code{wisent-parse}. | |
1374 | @end defvar | |
1375 | ||
1376 | @findex wisent-error | |
1377 | @defun wisent-error msg | |
1378 | Call the user supplied error reporting function with message | |
1379 | @var{msg} (@pxref{Report errors}). | |
1380 | ||
1381 | For an example of use, @xref{wisent-skip-token}. | |
1382 | @end defun | |
1383 | ||
1384 | @findex wisent-errok | |
1385 | @defun wisent-errok | |
1386 | Resume generating error messages immediately for subsequent syntax | |
1387 | errors. | |
1388 | ||
1389 | The parser suppress error message for syntax errors that happens | |
1390 | shortly after the first, until three consecutive input tokens have | |
1391 | been successfully shifted. | |
1392 | ||
1393 | Calling @code{wisent-errok} in an action, make error messages resume | |
1394 | immediately. No error messages will be suppressed if you call it in | |
1395 | an error rule's action. | |
1396 | ||
1397 | For an example of use, @xref{wisent-skip-token}. | |
1398 | @end defun | |
1399 | ||
1400 | @findex wisent-clearin | |
1401 | @defun wisent-clearin | |
1402 | Discard the current lookahead token. | |
1403 | This will cause a new lexical token to be read. | |
1404 | ||
1405 | In an error rule's action the previous lookahead token is reanalyzed | |
1406 | immediately. @code{wisent-clearin} may be called to clear this token. | |
1407 | ||
1408 | For example, suppose that on a parse error, an error handling routine | |
1409 | is called that advances the input stream to some point where parsing | |
1410 | should once again commence. The next symbol returned by the lexical | |
1411 | scanner is probably correct. The previous lookahead token ought to | |
1412 | be discarded with @code{wisent-clearin}. | |
1413 | ||
1414 | For an example of use, @xref{wisent-skip-token}. | |
1415 | @end defun | |
1416 | ||
1417 | @findex wisent-abort | |
1418 | @defun wisent-abort | |
1419 | Abort parsing and save the lookahead token. | |
1420 | @end defun | |
1421 | ||
1422 | @findex wisent-set-region | |
1423 | @defun wisent-set-region start end | |
1424 | Change the region of text matched by the current nonterminal. | |
1425 | @var{start} and @var{end} are respectively the beginning and end | |
1426 | positions of the region occupied by the group of components associated | |
1427 | to this nonterminal. If @var{start} or @var{end} values are not a | |
1428 | valid positions the region is set to @code{nil}. | |
1429 | ||
1430 | For an example of use, @xref{wisent-skip-token}. | |
1431 | @end defun | |
1432 | ||
1433 | @vindex wisent-discarding-token-functions | |
1434 | @defvar wisent-discarding-token-functions | |
1435 | List of functions to be called when discarding a lexical token. | |
1436 | These functions receive the lexical token discarded. | |
1437 | When the parser encounters unexpected tokens, it can discards them, | |
1438 | based on what directed by error recovery rules. Either when the | |
1439 | parser reads tokens until one is found that can be shifted, or when an | |
1440 | semantic action calls the function @code{wisent-skip-token} or | |
1441 | @code{wisent-skip-block}. | |
1442 | For language specific hooks, make sure you define this as a local | |
1443 | hook. | |
1444 | ||
1445 | For example, in @semantic{}, this hook is set to the function | |
1446 | @code{wisent-collect-unmatched-syntax} to collect unmatched lexical | |
1447 | tokens (@pxref{Useful functions}). | |
1448 | @end defvar | |
1449 | ||
1450 | @findex wisent-skip-token | |
1451 | @defun wisent-skip-token | |
1452 | @anchor{wisent-skip-token} | |
1453 | Skip the lookahead token in order to resume parsing. | |
1454 | Return nil. | |
1455 | Must be used in error recovery semantic actions. | |
1456 | ||
1457 | It typically looks like this: | |
1458 | ||
1459 | @lisp | |
1460 | @group | |
1461 | (wisent-message "%s: skip %s" $action | |
1462 | (wisent-token-to-string wisent-input)) | |
1463 | (run-hook-with-args | |
1464 | 'wisent-discarding-token-functions wisent-input) | |
1465 | (wisent-clearin) | |
1466 | (wisent-errok))) | |
1467 | @end group | |
1468 | @end lisp | |
1469 | @end defun | |
1470 | ||
1471 | @findex wisent-skip-block | |
1472 | @defun wisent-skip-block | |
1473 | Safely skip a block in order to resume parsing. | |
1474 | Return nil. | |
1475 | Must be used in error recovery semantic actions. | |
1476 | ||
1477 | A block is data between an open-delimiter (syntax class @code{(}) and | |
1478 | a matching close-delimiter (syntax class @code{)}): | |
1479 | ||
1480 | @example | |
1481 | @group | |
1482 | (a parenthesized block) | |
1483 | [a block between brackets] | |
1484 | @{a block between braces@} | |
1485 | @end group | |
1486 | @end example | |
1487 | ||
1488 | The following example uses @code{wisent-skip-block} to safely skip a | |
1489 | block delimited by @samp{LBRACE} (@code{@{}) and @samp{RBRACE} | |
1490 | (@code{@}}) tokens, when a syntax error occurs in | |
1491 | @samp{other-components}: | |
1492 | ||
1493 | @example | |
1494 | @group | |
1495 | (block ((LBRACE other-components RBRACE)) | |
1496 | ((LBRACE RBRACE)) | |
1497 | ((LBRACE error) | |
1498 | (wisent-skip-block)) | |
1499 | ) | |
1500 | @end group | |
1501 | @end example | |
1502 | @end defun | |
1503 | ||
1504 | @node Debugging actions | |
1505 | @section Debugging semantic actions | |
1506 | ||
1507 | @cindex semantic action symbols | |
1508 | Each semantic action is represented by a symbol interned in an | |
1509 | @dfn{obarray} that is part of the @acronym{LALR(1)} automaton | |
1510 | (@pxref{Compiling a grammar}). @code{symbol-function} on a semantic | |
1511 | action symbol return the semantic action lambda expression. | |
1512 | ||
1513 | A semantic action symbol name has the form | |
1514 | @code{@var{nonterminal}:@var{index}}, where @var{nonterminal} is the | |
1515 | name of the nonterminal symbol the action belongs to, and @var{index} | |
1516 | is an action sequence number within the scope of @var{nonterminal}. | |
1517 | For example, this nonterminal definition: | |
1518 | ||
1519 | @example | |
1520 | @group | |
1521 | input: | |
1522 | line [@code{input:0}] | |
1523 | | input line | |
1524 | (format "%s %s" $1 $2) [@code{input:1}] | |
1525 | ; | |
1526 | @end group | |
1527 | @end example | |
1528 | ||
1529 | Will produce two semantic actions, and associated symbols: | |
1530 | ||
1531 | @table @code | |
1532 | @item input:0 | |
1533 | A default action that returns @code{$1}. | |
1534 | ||
1535 | @item input:1 | |
1536 | That returns @code{(format "%s %s" $1 $2)}. | |
1537 | @end table | |
1538 | ||
1539 | @cindex debugging semantic actions | |
1540 | Debugging uses the Lisp debugger to investigate what is happening | |
1541 | during execution of semantic actions. | |
1542 | Three commands are available to debug semantic actions. They receive | |
1543 | two arguments: | |
1544 | ||
1545 | @itemize @bullet | |
1546 | @item The automaton that contains the semantic action. | |
1547 | ||
1548 | @item The semantic action symbol. | |
1549 | @end itemize | |
1550 | ||
1551 | @findex wisent-debug-on-entry | |
1552 | @deffn Command wisent-debug-on-entry automaton function | |
1553 | Request @var{automaton}'s @var{function} to invoke debugger each time it is called. | |
1554 | @var{function} must be a semantic action symbol that exists in @var{automaton}. | |
1555 | @end deffn | |
1556 | ||
1557 | @findex wisent-cancel-debug-on-entry | |
1558 | @deffn Command wisent-cancel-debug-on-entry automaton function | |
1559 | Undo effect of @code{wisent-debug-on-entry} on @var{automaton}'s @var{function}. | |
1560 | @var{function} must be a semantic action symbol that exists in @var{automaton}. | |
1561 | @end deffn | |
1562 | ||
1563 | @findex wisent-debug-show-entry | |
1564 | @deffn Command wisent-debug-show-entry automaton function | |
1565 | Show the source of @var{automaton}'s semantic action @var{function}. | |
1566 | @var{function} must be a semantic action symbol that exists in @var{automaton}. | |
1567 | @end deffn | |
1568 | ||
1569 | @node Wisent Semantic | |
1570 | @chapter How to use Wisent with Semantic | |
1571 | ||
1572 | @cindex tags | |
1573 | This section presents how the Wisent's parser can be used to produce | |
1574 | @dfn{tags} for the @semantic{} tool set. | |
1575 | ||
1576 | @semantic{} tags form a hierarchy of Emacs Lisp data structures that | |
1577 | describes a program in a way independent of programming languages. | |
1578 | Tags map program declarations, like functions, methods, variables, | |
1579 | data types, classes, includes, grammar rules, etc.. | |
1580 | ||
1581 | @cindex WY grammar format | |
1582 | To use the Wisent parser with @semantic{} you have to define | |
1583 | your grammar in @dfn{WY} form, a grammar format very close | |
1584 | to the one used by Bison. | |
1585 | ||
1586 | Please @inforef{top, Semantic Grammar Framework Manual, grammar-fw} | |
1587 | for more information on @semantic{} grammars. | |
1588 | ||
1589 | @menu | |
bfe6ffb6 GM |
1590 | * Grammar styles:: |
1591 | * Wisent Lex:: | |
9e7abd17 EL |
1592 | @end menu |
1593 | ||
1594 | @node Grammar styles | |
1595 | @section Grammar styles | |
1596 | ||
1597 | @cindex grammar styles | |
1598 | @semantic{} parsing heavily depends on how you wrote the grammar. | |
1599 | There are mainly two styles to write a Wisent's grammar intended to be | |
1600 | used with the @semantic{} tool set: the @dfn{Iterative style} and the | |
1601 | @dfn{Bison style}. Each one has pros and cons, and in certain cases | |
1602 | it can be worth a mix of the two styles! | |
1603 | ||
1604 | @menu | |
bfe6ffb6 GM |
1605 | * Iterative style:: |
1606 | * Bison style:: | |
1607 | * Mixed style:: | |
1608 | * Start nonterminals:: | |
1609 | * Useful functions:: | |
9e7abd17 EL |
1610 | @end menu |
1611 | ||
1612 | @node Iterative style, Bison style, Grammar styles, Grammar styles | |
1613 | @subsection Iterative style | |
1614 | ||
1615 | @cindex grammar iterative style | |
1616 | The @dfn{iterative style} is the preferred style to use with @semantic{}. | |
1617 | It relies on an iterative parser back-end mechanism which parses start | |
1618 | nonterminals one at a time and automagically skips unexpected lexical | |
1619 | tokens in input. | |
1620 | ||
1621 | Compared to rule-based iterative functions (@pxref{Bison style}), | |
1622 | iterative parsers are better in that they can handle obscure errors | |
1623 | more cleanly. | |
1624 | ||
1625 | @cindex raw tag | |
1626 | Each start nonterminal must produces a @dfn{raw tag} by calling a | |
1627 | @code{TAG}-like grammar macro with appropriate parameters. See also | |
1628 | @ref{Start nonterminals}. | |
1629 | ||
1630 | @cindex expanded tag | |
1631 | Then, each parsing iteration automatically translates a raw tag into | |
1632 | @dfn{expanded tags}, updating the raw tag structure with internal | |
1633 | properties and buffer related data. | |
1634 | ||
1635 | After parsing completes, it results in a tree of expanded tags. | |
1636 | ||
1637 | The following example is a snippet of the iterative style Java grammar | |
1638 | provided in the @semantic{} distribution in the file | |
1639 | @file{semantic/wisent/java-tags.wy}. | |
1640 | ||
1641 | @example | |
1642 | @group | |
1643 | @dots{} | |
1644 | ;; Alternate entry points | |
1645 | ;; - Needed by partial re-parse | |
1646 | %start formal_parameter | |
1647 | @dots{} | |
1648 | ;; - Needed by EXPANDFULL clauses | |
1649 | %start formal_parameters | |
1650 | @dots{} | |
1651 | ||
1652 | formal_parameter_list | |
1653 | : PAREN_BLOCK | |
1654 | (EXPANDFULL $1 formal_parameters) | |
1655 | ; | |
1656 | ||
1657 | formal_parameters | |
1658 | : LPAREN | |
1659 | () | |
1660 | | RPAREN | |
1661 | () | |
1662 | | formal_parameter COMMA | |
1663 | | formal_parameter RPAREN | |
1664 | ; | |
1665 | ||
1666 | formal_parameter | |
1667 | : formal_parameter_modifier_opt type variable_declarator_id | |
1668 | (VARIABLE-TAG $3 $2 nil :typemodifiers $1) | |
1669 | ; | |
1670 | @end group | |
1671 | @end example | |
1672 | ||
1673 | @findex EXPANDFULL | |
1674 | It shows the use of the @code{EXPANDFULL} grammar macro to parse a | |
1675 | @samp{PAREN_BLOCK} which contains a @samp{formal_parameter_list}. | |
1676 | @code{EXPANDFULL} tells to recursively parse @samp{formal_parameters} | |
1677 | inside @samp{PAREN_BLOCK}. The parser iterates until it digested all | |
1678 | available input data inside the @samp{PAREN_BLOCK}, trying to match | |
1679 | any of the @samp{formal_parameters} rules: | |
1680 | ||
1681 | @itemize | |
1682 | @item @samp{LPAREN} | |
1683 | ||
1684 | @item @samp{RPAREN} | |
1685 | ||
1686 | @item @samp{formal_parameter COMMA} | |
1687 | ||
1688 | @item @samp{formal_parameter RPAREN} | |
1689 | @end itemize | |
1690 | ||
1691 | At each iteration it will return a @samp{formal_parameter} raw tag, | |
1692 | or @code{nil} to skip unwanted (single @samp{LPAREN} or @samp{RPAREN} | |
1693 | for example) or unexpected input data. Those raw tags will be | |
1694 | automatically expanded by the iterative back-end parser. | |
1695 | ||
1696 | @node Bison style | |
1697 | @subsection Bison style | |
1698 | ||
1699 | @cindex grammar bison style | |
1700 | What we call the @dfn{Bison style} is the traditional style of Bison's | |
1701 | grammars. Compared to iterative style, it is not straightforward to | |
1702 | use grammars written in Bison style in @semantic{}. Mainly because such | |
1703 | grammars are designed to parse the whole input data in one pass, and | |
1704 | don't use the iterative parser back-end mechanism (@pxref{Iterative | |
1705 | style}). With Bison style the parser is called once to parse the | |
1706 | grammar start nonterminal. | |
1707 | ||
1708 | The following example is a snippet of the Bison style Java grammar | |
1709 | provided in the @semantic{} distribution in the file | |
1710 | @file{semantic/wisent/java.wy}. | |
1711 | ||
1712 | @example | |
1713 | @group | |
1714 | %start formal_parameter | |
1715 | @dots{} | |
1716 | ||
1717 | formal_parameter_list | |
1718 | : formal_parameter_list COMMA formal_parameter | |
1719 | (cons $3 $1) | |
1720 | | formal_parameter | |
1721 | (list $1) | |
1722 | ; | |
1723 | ||
1724 | formal_parameter | |
1725 | : formal_parameter_modifier_opt type variable_declarator_id | |
1726 | (EXPANDTAG | |
1727 | (VARIABLE-TAG $3 $2 :typemodifiers $1) | |
1728 | ) | |
1729 | ; | |
1730 | @end group | |
1731 | @end example | |
1732 | ||
1733 | The first consequence is that syntax errors are not automatically | |
1734 | handled by @semantic{}. Thus, it is necessary to explicitly handle | |
1735 | them at the grammar level, providing error recovery rules to skip | |
1736 | unexpected input data. | |
1737 | ||
1738 | The second consequence is that the iterative parser can't do automatic | |
1739 | tag expansion, except for the start nonterminal value. It is | |
1740 | necessary to explicitly expand tags from concerned semantic actions by | |
1741 | calling the grammar macro @code{EXPANDTAG} with a raw tag as | |
1742 | parameter. See also @ref{Start nonterminals}, for incremental | |
1743 | re-parse considerations. | |
1744 | ||
1745 | @node Mixed style | |
1746 | @subsection Mixed style | |
1747 | ||
1748 | @cindex grammar mixed style | |
1749 | @example | |
1750 | @group | |
1751 | %start grammar | |
1752 | ;; Reparse | |
1753 | %start prologue epilogue declaration nonterminal rule | |
1754 | @dots{} | |
1755 | ||
1756 | %% | |
1757 | ||
1758 | grammar: | |
1759 | prologue | |
1760 | | epilogue | |
1761 | | declaration | |
1762 | | nonterminal | |
1763 | | PERCENT_PERCENT | |
1764 | ; | |
1765 | @dots{} | |
1766 | ||
1767 | nonterminal: | |
1768 | SYMBOL COLON rules SEMI | |
1769 | (TAG $1 'nonterminal :children $3) | |
1770 | ; | |
1771 | ||
1772 | rules: | |
1773 | lifo_rules | |
1774 | (apply 'nconc (nreverse $1)) | |
1775 | ; | |
1776 | ||
1777 | lifo_rules: | |
1778 | lifo_rules OR rule | |
1779 | (cons $3 $1) | |
1780 | | rule | |
1781 | (list $1) | |
1782 | ; | |
1783 | ||
1784 | rule: | |
1785 | rhs | |
1786 | (let* ((rhs $1) | |
1787 | name type comps prec action elt) | |
1788 | @dots{} | |
1789 | (EXPANDTAG | |
1790 | (TAG name 'rule :type type :value comps :prec prec :expr action) | |
1791 | )) | |
1792 | ; | |
1793 | @end group | |
1794 | @end example | |
1795 | ||
1796 | This example shows how iterative and Bison styles can be combined in | |
1797 | the same grammar to obtain a good compromise between grammar | |
1798 | complexity and an efficient parsing strategy in an interactive | |
1799 | environment. | |
1800 | ||
1801 | @samp{nonterminal} is parsed using iterative style via the main | |
1802 | @samp{grammar} rule. The semantic action uses the @code{TAG} macro to | |
1803 | produce a raw tag, automagically expanded by @semantic{}. | |
1804 | ||
1805 | But @samp{rules} part is parsed in Bison style! Why? | |
1806 | ||
1807 | Rule delimiters are the colon (@code{:}), that follows the nonterminal | |
1808 | name, and a final semicolon (@code{;}). Unfortunately these | |
1809 | delimiters are not @code{open-paren}/@code{close-paren} type, and the | |
1810 | Emacs' syntactic analyzer can't easily isolate data between them to | |
1811 | produce a @samp{RULES_PART} parenthesis-block-like lexical token. | |
1812 | Consequently it is not possible to use @code{EXPANDFULL} to iterate in | |
1813 | @samp{RULES_PART}, like this: | |
1814 | ||
1815 | @example | |
1816 | @group | |
1817 | nonterminal: | |
1818 | SYMBOL COLON rules SEMI | |
1819 | (TAG $1 'nonterminal :children $3) | |
1820 | ; | |
1821 | ||
1822 | rules: | |
1823 | RULES_PART ;; @strong{Map a parenthesis-block-like lexical token} | |
1824 | (EXPANDFULL $1 'rules) | |
1825 | ; | |
1826 | ||
1827 | rules: | |
1828 | COLON | |
1829 | () | |
1830 | OR | |
1831 | () | |
1832 | SEMI | |
1833 | () | |
1834 | rhs | |
1835 | rhs | |
1836 | (let* ((rhs $1) | |
1837 | name type comps prec action elt) | |
1838 | @dots{} | |
1839 | (TAG name 'rule :type type :value comps :prec prec :expr action) | |
1840 | ) | |
1841 | ; | |
1842 | @end group | |
1843 | @end example | |
1844 | ||
1845 | In such cases, when it is difficult for Emacs to obtain | |
1846 | parenthesis-block-like lexical tokens, the best solution is to use the | |
1847 | traditional Bison style with error recovery! | |
1848 | ||
1849 | In some extreme cases, it can also be convenient to extend the lexer, | |
1850 | to deliver new lexical tokens, to simplify the grammar. | |
1851 | ||
1852 | @node Start nonterminals | |
1853 | @subsection Start nonterminals | |
1854 | ||
1855 | @cindex start nonterminals | |
1856 | @cindex @code{reparse-symbol} property | |
1857 | When you write a grammar for @semantic{}, it is important to carefully | |
1858 | indicate the start nonterminals. Each one defines an entry point in | |
1859 | the grammar, and after parsing its semantic value is returned to the | |
1860 | back-end iterative engine. Consequently: | |
1861 | ||
1862 | @strong{The semantic value of a start nonterminal must be a produced | |
1863 | by a TAG like grammar macro}. | |
1864 | ||
1865 | Start nonterminals are declared by @code{%start} statements. When | |
1866 | nothing is specified the first nonterminal that appears in the grammar | |
1867 | is the start nonterminal. | |
1868 | ||
1869 | Generally, the following nonterminals must be declared as start | |
1870 | symbols: | |
1871 | ||
1872 | @itemize @bullet | |
1873 | @item The main grammar entry point | |
1874 | @quotation | |
1875 | Of course! | |
1876 | @end quotation | |
1877 | ||
1878 | @item nonterminals passed to @code{EXPAND}/@code{EXPANDFULL} | |
1879 | @quotation | |
1880 | These grammar macros recursively parse a part of input data, based on | |
1881 | rules of the given nonterminal. | |
1882 | ||
1883 | For example, the following will parse @samp{PAREN_BLOCK} data using | |
1884 | the @samp{formal_parameters} rules: | |
1885 | ||
1886 | @example | |
1887 | @group | |
1888 | formal_parameter_list | |
1889 | : PAREN_BLOCK | |
1890 | (EXPANDFULL $1 formal_parameters) | |
1891 | ; | |
1892 | @end group | |
1893 | @end example | |
1894 | ||
1895 | The semantic value of @samp{formal_parameters} becomes the value of | |
1896 | the @code{EXPANDFULL} expression. It is a list of @semantic{} tags | |
1897 | spliced in the tags tree. | |
1898 | ||
1899 | Because the automaton must know that @samp{formal_parameters} is a | |
1900 | start symbol, you must declare it like this: | |
1901 | ||
1902 | @example | |
1903 | @group | |
1904 | %start formal_parameters | |
1905 | @end group | |
1906 | @end example | |
1907 | @end quotation | |
1908 | @end itemize | |
1909 | ||
1910 | @cindex incremental re-parse | |
1911 | @cindex reparse-symbol | |
1912 | The @code{EXPANDFULL} macro has a side effect it is important to know, | |
1913 | related to the incremental re-parse mechanism of @semantic{}: the | |
1914 | nonterminal symbol parameter passed to @code{EXPANDFULL} also becomes | |
1915 | the @code{reparse-symbol} property of the tag returned by the | |
1916 | @code{EXPANDFULL} expression. | |
1917 | ||
1918 | When buffer's data mapped by a tag is modified, @semantic{} | |
1919 | schedules an incremental re-parse of that data, using the tag's | |
1920 | @code{reparse-symbol} property as start nonterminal. | |
1921 | ||
1922 | @strong{The rules associated to such start symbols must be carefully | |
1923 | reviewed to ensure that the incremental parser will work!} | |
1924 | ||
1925 | Things are a little bit different when the grammar is written in Bison | |
bfe6ffb6 | 1926 | style. |
9e7abd17 EL |
1927 | |
1928 | @strong{The @code{reparse-symbol} property is set to the nonterminal | |
1929 | symbol the rule that explicitly uses @code{EXPANDTAG} belongs to.} | |
1930 | ||
1931 | For example: | |
1932 | ||
1933 | @example | |
1934 | @group | |
1935 | rule: | |
1936 | rhs | |
1937 | (let* ((rhs $1) | |
1938 | name type comps prec action elt) | |
1939 | @dots{} | |
1940 | (EXPANDTAG | |
1941 | (TAG name 'rule :type type :value comps :prec prec :expr action) | |
1942 | )) | |
1943 | ; | |
1944 | @end group | |
1945 | @end example | |
1946 | ||
1947 | Set the @code{reparse-symbol} property of the expanded tag to | |
1948 | @samp{rule}. A important consequence is that: | |
1949 | ||
1950 | @strong{Every nonterminal having any rule that calls @code{EXPANDTAG} | |
1951 | in a semantic action, should be declared as a start symbol!} | |
1952 | ||
1953 | @node Useful functions | |
1954 | @subsection Useful functions | |
1955 | ||
1956 | Here is a description of some predefined functions it might be useful | |
1957 | to know when writing new code to use Wisent in @semantic{}: | |
1958 | ||
1959 | @findex wisent-collect-unmatched-syntax | |
1960 | @defun wisent-collect-unmatched-syntax input | |
1961 | Add @var{input} lexical token to the cache of unmatched tokens, in | |
1962 | variable @code{semantic-unmatched-syntax-cache}. | |
1963 | ||
1964 | See implementation of the function @code{wisent-skip-token} in | |
1965 | @ref{Error recovery}, for an example of use. | |
1966 | @end defun | |
1967 | ||
1968 | @node Wisent Lex | |
1969 | @section The Wisent Lex lexer | |
1970 | ||
1971 | @findex semantic-lex | |
1972 | The lexical analysis step of @semantic{} is performed by the general | |
1973 | function @code{semantic-lex}. For more information, @inforef{Writing | |
1974 | Lexers, ,semantic-langdev}. | |
1975 | ||
1976 | @code{semantic-lex} produces lexical tokens of the form: | |
1977 | ||
1978 | @example | |
1979 | @group | |
1980 | @code{(@var{token-class start} . @var{end})} | |
1981 | @end group | |
1982 | @end example | |
1983 | ||
1984 | @table @var | |
1985 | @item token-class | |
1986 | Is a symbol that identifies a lexical token class, like @code{symbol}, | |
1987 | @code{string}, @code{number}, or @code{PAREN_BLOCK}. | |
1988 | ||
1989 | @item start | |
1990 | @itemx end | |
1991 | Are the start and end positions of mapped data in the input buffer. | |
1992 | @end table | |
bfe6ffb6 | 1993 | |
9e7abd17 EL |
1994 | The Wisent's parser doesn't depend on the nature of analyzed input |
1995 | stream (buffer, string, etc.), and requires that lexical tokens have a | |
1996 | different form (@pxref{Writing a lexer}): | |
1997 | ||
1998 | @example | |
1999 | @group | |
2000 | @code{(@var{token-class value} [@var{start} . @var{end}])} | |
2001 | @end group | |
2002 | @end example | |
2003 | ||
2004 | @cindex lexical token mapping | |
2005 | @code{wisent-lex} is the default Wisent's lexer used in @semantic{}. | |
2006 | ||
2007 | @vindex wisent-lex-istream | |
2008 | @findex wisent-lex | |
2009 | @defun wisent-lex | |
2010 | Return the next available lexical token in Wisent's form. | |
2011 | ||
2012 | The variable @code{wisent-lex-istream} contains the list of lexical | |
2013 | tokens produced by @code{semantic-lex}. Pop the next token available | |
2014 | and convert it to a form suitable for the Wisent's parser. | |
2015 | @end defun | |
2016 | ||
2017 | Mapping of lexical tokens as produced by @code{semantic-lex} into | |
2018 | equivalent Wisent lexical tokens is straightforward: | |
2019 | ||
2020 | @example | |
2021 | @group | |
2022 | (@var{token-class start} . @var{end}) | |
2023 | @result{} (@var{token-class value start} . @var{end}) | |
2024 | @end group | |
2025 | @end example | |
2026 | ||
2027 | @var{value} is the input @code{buffer-substring} from @var{start} to | |
2028 | @var{end}. | |
2029 | ||
2030 | @node GNU Free Documentation License | |
2031 | @appendix GNU Free Documentation License | |
2032 | ||
bfe6ffb6 | 2033 | @include doclicense.texi |
9e7abd17 EL |
2034 | |
2035 | @node Index | |
2036 | @unnumbered Index | |
2037 | @printindex cp | |
2038 | ||
2039 | @iftex | |
2040 | @contents | |
2041 | @summarycontents | |
2042 | @end iftex | |
2043 | ||
2044 | @bye | |
2045 | ||
2046 | @c Following comments are for the benefit of ispell. | |
2047 | ||
2048 | @c LocalWords: Wisent automagically wisent Wisent's LALR obarray |