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