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