AnaGram interim repo (temporary): doc/manual/xg-iii.tex annotate

annotate doc/manual/xg-iii.tex @ 21:1c9dac05d040

Add lint-style FALLTHROUGH annotations to fallthrough cases. (in the parse engine and thus the output code) Document this, because the old output causes warnings with gcc10.

author	David A. Holland
date	Mon, 13 Jun 2022 00:04:38 -0400
parents	13d2b8934445
children

rev	line source
0 13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	1 \chapter{Exploring Your Grammar III: Diagnostic Windows}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	2
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	3 If AnaGram finds problems with your grammar, it creates a number of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	4 windows to help you identify and correct the problems. These windows
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	5 are the \agwindow{Warnings} window, the \agwindow{Conflicts} window,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	6 the \agwindow{Resolved Conflicts} window, and the \agwindow{Keyword
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	7 Anomalies} window. To expand upon these windows, AnaGram also
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	8 provides, using the \agmenu{Auxiliary Windows} menu, the following
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	9 supporting windows: \agwindow{Conflict Trace}, \agwindow{Keyword
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	10 Anomaly Trace}, \agwindow{Reduction Trace}, \agwindow{Rule
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	11 Derivation}, \agwindow{Token Derivation} and \agwindow{Problem
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	12 States}. This chapter describes these windows and their use.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	13
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	14
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	15 \section{The Warnings Window}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	16 \index{Warnings}\index{Window}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	17
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	18 If while analyzing your syntax file, AnaGram finds something
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	19 suspicious, it issues a warning, regardless of the severity of the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	20 problem. The \agwindow{Warnings} window will pop up automatically
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	21 when the analysis has been completed. If the warning is for a syntax
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	22 error in your input file, you will have to fix it, because AnaGram
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	23 cannot successfully interpret your syntax file. Otherwise, no matter
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	24 how serious the warnings may be, AnaGram will create a parser if it is
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	25 instructed to do so. Thus, if you decide the warnings are of no
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	26 consequence, you may choose to ignore them. Note that AnaGram will
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	27 resolve shift-reduce conflicts by choosing the shift action. It will
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	28 resolve reduce-reduce conflicts by choosing the rule that occurred
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	29 first in the grammar.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	30
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	31 If you have \index{Syntax error}\index{Errors}syntax errors, AnaGram
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	32 will synchronize the cursor in the syntax file window with the cursor
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	33 in the \agwindow{Warnings} window so that as you move through the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	34 warning messages, the cursor in the syntax file window will move to
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	35 the point of the error.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	36
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	37 AnaGram's warning messages are listed, in alphabetical order, in
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	38 Appendix B, together with explanations of the messages and suggestions
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	39 as to what to do about them.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	40
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	41
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	42 \section{The Conflicts Window}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	43 \index{Conflicts}\index{Window}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	44
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	45 The \agwindow{Conflicts} window lists the conflicts which AnaGram
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	46 found in your grammar. The table identifies the parser states in
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	47 which it found conflicts. For each conflict state it identifies the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	48 reducing token for which it had more than one option, and the marked
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	49 rules which characterize each such option. If AnaGram was able to
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	50 resolve a conflict by using \agparam{precedence} or \agparam{sticky}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	51 declarations, the conflict will be listed in the \index{Resolved
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	52 Conflicts}\index{Window}\agwindow{Resolved Conflicts} window instead.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	53
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	54 The \agwindow{Conflicts} window and the \agwindow{Resolved Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	55 window each require several lines to display a conflict. For each
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	56 conflict, the first, or header, line identifies the conflict state and
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	57 the conflict token. The conflict token is a terminal token for which
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	58 there is more than one parser action consistent with the rules of the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	59 grammar. If both shift and reduce actions are consistent with the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	60 grammar, the conflict is a \agterm{shift-reduce} conflict. If more
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	61 than one reduce action is consistent with the grammar, the conflict is
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	62 said to be a \agterm{reduce-reduce} conflict.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	63
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	64 Following the header line, AnaGram lists the grammar rules which the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	65 conflict token could satisfy. The rules which correspond to shift
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	66 actions are listed first, followed by those which correspond to reduce
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	67 actions. Rules which correspond to shift actions have not yet been
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	68 completed and have a marked token, shown in a distinctive type face,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	69 which represents the next token expected. For such rules, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	70 conflict token is an instance of the marked token and can be shifted
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	71 into the input buffer. If the rule has been completely matched there
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	72 is no marked token and the conflict token can reduce the rule. In the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	73 following discussion, such a rule is referred to as a \agterm{conflict
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	74 rule}. If there is a more than one conflict rule, the conflict is
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	75 called a \agterm{reduce-reduce} conflict; otherwise it is a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	76 \agterm{shift-reduce} conflict. Although it is theoretically possible
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	77 for a conflict to be both a shift-reduce conflict and a reduce-reduce
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	78 conflict, it is not a common event.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	79
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	80 The \agmenu{Auxiliary Windows} menu for the \agwindow{Conflicts} window
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	81 provides eleven auxiliary windows to help you understand the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	82 circumstances of a conflict. Five of these windows address the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	83 conflict directly. These windows are the \agwindow{Conflict Trace}, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	84 \agwindow{Reduction Trace}, the \agwindow{Rule Derivation}, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	85 \agwindow{Token Derivation}, and the \agwindow{Problem States}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	86 windows. These windows are keyed to the conflict state, the conflict
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	87 token, and the conflict rule. If the cursor bar is not highlighting a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	88 conflict rule, AnaGram scans down the \agwindow{Conflicts} window for
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	89 the first conflict rule for the selected state and token. The use of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	90 these windows in analyzing conflicts is described below.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	91
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	92 The other windows in the \agmenu{Auxiliary Windows} menu have been
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	93 described in Chapter 6. These are the \agwindow{Expansion Chain}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	94 window, the \agwindow{Rule Context} window, the \agwindow{Reduction
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	95 States} window, the \agwindow{State Definition} window, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	96 \agwindow{State Expansion} window and the \agwindow{Token Usage}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	97 window. The \agwindow{Rule Context} window is keyed to the particular
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	98 rule highlighted by the cursor. The
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	99 \index{Expansion Chain}\index{Window}\agwindow{Expansion Chain} window
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	100 is keyed to the highlighted rule. If the highlighted rule is a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	101 characteristic rule no expansion chain is possible, so the option will
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	102 be greyed out. The \agwindow{Reduction States} window is keyed to the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	103 highlighted rule if it is a conflict rule, otherwise to the first
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	104 conflict rule following the highlighted line. The \agwindow{State
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	105 Definition} and \agwindow{State Expansion} windows are keyed to the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	106 conflict state. The \agwindow{Token Usage} window is keyed to the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	107 conflict token.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	108
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	109
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	110 \section{The Resolved Conflicts Window}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	111 \index{Resolved Conflicts}\index{Window}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	112
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	113 AnaGram creates the \agwindow{Resolved Conflicts} window only when the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	114 grammar it is analyzing has conflicts and when some of those conflicts
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	115 have been resolved by precedence rules (see Chapter 9) or by use of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	116 the \agparam{sticky} directive. In this case, it will list, in the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	117 \agwindow{Resolved Conflicts} window, the conflicts that were resolved
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	118 and the way in which they were resolved. The layout of the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	119 \agwindow{Resolved Conflicts} window is identical to that of the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	120 \agwindow{Conflicts} window with one exception. The rules which your
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	121 parser will observe, selected in accordance with your \agparam{sticky}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	122 declarations or precedence rules, are marked with asterisks. Those
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	123 which your parser will ignore will not be so marked. The
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	124 \agwindow{Auxiliary Windows} available from the \agwindow{Resolved
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	125 Conflicts} window are the same as those available from the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	126 \agwindow{Conflicts} window.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	127
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	128
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	129 \section{Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	130 \index{Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	131
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	132 Chapter 4 presented a brief introduction to the problem of conflicts
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	133 in a grammar. There, conflicts were simply classified as shift-reduce
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	134 conflicts or as reduce-reduce conflicts. This section examines
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	135 conflicts in somewhat greater detail. It looks at the causes of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	136 conflicts, how to identify the cause of a conflict and how to deal
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	137 with it.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	138
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	139 Conflicts occur when, in a particular state, a given token, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	140 \index{Conflict token}\index{Token}\agterm{conflict token}, reduces
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	141 more than one rule, or reduces a rule when the token could also be
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	142 shifted into the input buffer in accordance with another rule.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	143
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	144 Note that there are no shift-shift conflicts, that is, a particular
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	145 state could have several
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	146 \index{Characteristic rules}\index{Rules}characteristic rules
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	147 accepting the same token as a shift token. A conflict is always
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	148 associated with reduction. This is because LALR parsers keep track of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	149 multiple possibilities in the input stream as long as the input tokens
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	150 only cause shifts. At the point where a reduction occurs the parser
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	151 must be able to identify exactly one of the possibilities as
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	152 consistent with the input.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	153
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	154 \subsection{Shift-Reduce Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	155 \index{Shift-reduce conflict}\index{Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	156
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	157 Unless a conflict is deliberate, the fact that the conflict token
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	158 reduces a particular rule is usually a surprise. Although some
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	159 conflicts arise because an LALR-1 parser generator cannot look far
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	160 enough ahead, most shift-reduce conflicts result from true
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	161 \index{Ambiguities}ambiguities in your grammar. For example, an
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	162 erroneous Pascal grammar contained the following productions, which
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	163 illustrate one of the more common classes of shift-reduce conflicts:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	164
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	165 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	166 parameter list
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	167 -> expression
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	168 -> parameter list, expression
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	169 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	170
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	171 Pascal actually requires that the expressions in a parameter list be
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	172 separated by commas. In other words, the second rule should read:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	173
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	174 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	175 -> parameter list, comma, expression
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	176 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	177
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	178 Lacking a requirement for a comma, the erroneous rules specify that a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	179 parameter list is simply a sequence of expressions with nothing
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	180 separating them. For example, using this definition,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	181
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	182 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	183 (a + b) - (c * d)
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	184 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	185
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	186 can be interpreted either as one expression, if the minus sign is
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	187 interpreted as a subtraction operator, or as a sequence of two
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	188 expressions if it is interpreted as a unary minus sign.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	189
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	190 When AnaGram analyzed the grammar with the erroneous rule it found a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	191 conflict in the state where the minus sign was expected. If the minus
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	192 sign is the subtraction operator, it should be shifted onto the input
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	193 stack. On the other hand, if the minus sign is a unary minus sign,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	194 the sum \agcode{(a+b)} should be reduced to \agcode{expression}, and
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	195 then to \agcode{parameter list}. Thus, this ambiguity gives rise to a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	196 shift-reduce conflict, where it is impossible to determine a unique
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	197 parser action.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	198
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	199 \subsection{Identifying Ambiguities}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	200 \index{Ambiguities}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	201
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	202 Unfortunately, shift-reduce conflicts usually show up in parser states
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	203 which are far removed from the true source of the problem. When your
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	204 grammar has a shift-reduce conflict of the sort illustrated above,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	205 there may be no readily apparent link to the erroneous
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	206 production. AnaGram provides several options to help you establish the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	207 link, all available using the \agmenu{Auxiliary Windows} menu from the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	208 \agwindow{Conflicts} window. These options comprise two pre-built
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	209 grammar traces, the \agwindow{Conflict Trace} and the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	210 \agwindow{Reduction Trace}; two special windows called \agwindow{Rule
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	211 Derivation} and \agwindow{Token Derivation}; the \agwindow{Expansion
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	212 Chain} window and a special version of the \agwindow{Reduction States}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	213 window called the \agwindow{Problem States} window. The four trace
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	214 and derivation windows are coordinated, so that AnaGram actually
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	215 computes a mutually consistent set of four whenever you ask for one of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	216 them.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	217
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	218 The \agwindow{Conflict} and \agwindow{Reduction Traces} are simply
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	219 pre-initialized \agwindow{Grammar Traces} which you may use to become
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	220 more familiar with the circumstances of the conflict. Bear in mind,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	221 however, that unless you have set the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	222 \index{Traditional engine}\index{Configuration switches}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	223 \agparam{traditional engine} configuration switch,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	224 the traces will use compound actions, which in some cases will use the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	225 default resolution of conflicts. Therefore, unless you set
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	226 \agparam{traditional engine} it is not always possible to work through
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	227 an alternate resolution of a conflict.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	228
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	229 The
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	230 \index{Conflict Trace}\index{Trace}\index{Window}\agwindow{Conflict Trace}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	231 shows you one possible sequence of input which will lead to the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	232 conflict state. Unless a conflict results from a typo or other
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	233 clerical error, it is usually a surprise and not something you
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	234 anticipated. The \agwindow{Conflict Trace} helps you to understand
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	235 the context of the problem. It is often helpful to look at the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	236 \agwindow{Rule Stack} for the \agwindow{Conflict Trace} to see what
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	237 productions are involved in the conflict. You can inspect the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	238 \agwindow{State Definition} window for the conflict state to see why
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	239 the conflict token can be shifted.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	240
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	241 \index{Reduction Trace}\index{Trace}\index{Window}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	242 The \agwindow{Reduction Trace}, for a particular conflict rule,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	243 carries forward a \agwindow{Conflict Trace} by selecting the reduce
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	244 action. In other words, for a parser in the conflict state, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	245 \agwindow{Reduction Trace} shows the result of using the conflict
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	246 token as a reducing token. The trace shows the result of taking all
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	247 possible reductions until a state is reached where the lookahead token
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	248 will shift into the input buffer. If you compare the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	249 \agwindow{Reduction Trace} to the \agwindow{Conflict Trace} you will
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	250 notice that they start off with identical tokens. At some point they
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	251 diverge. All of the tokens in the \agwindow{Conflict Trace} following
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	252 this point have reduced to the token in the \agwindow{Reduction
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	253 Trace}. Usually there are no further tokens in the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	254 \agwindow{Reduction Trace}, but if there are, you will notice that
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	255 they are all zero-length tokens. That is, they all have a null
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	256 production, so that they come for free, as it were. If you press
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	257 Enter, to display the \agwindow{Select Input} window for the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	258 \agwindow{Reduction Trace}, you will see that the conflict token is
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	259 acceptable input.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	260
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	261 The \agwindow{Reduction Trace} illustrates the ambiguity in your
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	262 grammar that caused the conflict: One of the acceptable input tokens
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	263 in the final state of this trace cannot be distinguished from its
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	264 predecessor.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	265
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	266 The \index{Expansion Chain}\index{Window}\agwindow{Expansion Chain}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	267 window is extremely useful for indicating why a particular grammar
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	268 rule is an expansion rule in a particular state. Sometimes the chain
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	269 of substitutions to produce a given rule is quite long, and changes to
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	270 a grammar can have unexpected effects. The \agwindow{Expansion Chain}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	271 window enables you to see how a rule in a conflict state got to be
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	272 there.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	273
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	274 \index{Problem States}\index{Window}The \agwindow{Problem States}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	275 window for a conflict rule is essentially a trimmed
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	276 \agwindow{Reduction States} window which shows only those reduction
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	277 states in which the conflict token is acceptable input. Often it is
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	278 sufficient to look at the \agwindow{Problem States} window to see the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	279 source of the problem. The last state in the \agwindow{Reduction
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	280 Trace} window, will be, of course, one of the states in the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	281 \agwindow{Problem States} window.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	282
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	283 \subsection{Rule and Token Derivation Windows}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	284
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	285 If after inspecting the \agwindow{Problem States}, \agwindow{Conflict
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	286 Trace} and the \agwindow{Reduction Trace}, the conflict is still a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	287 mystery, you may pinpoint the problem by looking at the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	288 \agwindow{Rule} and \agwindow{Token Derivation} windows for the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	289 conflict. Both windows contain a sequence of rules, and both begin
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	290 with the same rule, the rule which is the root cause of the conflict.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	291 This rule is one of the characteristic rules of the last state in the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	292 \agwindow{Reduction Trace} and is the rule which produces the ambiguity.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	293
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	294 \index{Rule Derivation}\index{Window}In both windows, each rule,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	295 except the last line of the \agwindow{Rule Derivation}, contains a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	296 marked token in a distinctive typeface. The essence of the ambiguity
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	297 is that it is impossible to tell where in the input stream the marked
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	298 token in the top line of the \agwindow{Rule Derivation} ends and the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	299 marked token in the top line of the \agwindow{Token Derivation}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	300 begins.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	301
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	302 In both derivation windows, each line after the first consists of a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	303 rule produced by the marked token on the previous line. In the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	304 \agwindow{Rule Derivation}, except on the first line, the marked token
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	305 is either the last token in the rule, or all subsequent tokens have
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	306 null productions. The last rule in the derivation window is the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	307 conflict rule you selected in the \agwindow{Conflicts} window. Thus
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	308 the \agwindow{Rule Derivation} window shows you how the rule involved
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	309 in the conflict derives from the root.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	310
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	311 \index{Window}\index{Token Derivation}In the \agwindow{Token
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	312 Derivation} window, except on the first line, the marked token is
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	313 either the first token in the rule, or all preceding tokens have null
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	314 productions. The marked token in the last line of the list is the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	315 conflict token.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	316
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	317 The \agwindow{Rule Derivation} and \agwindow{Token Derivation} windows
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	318 each have five auxiliary windows. The \agwindow{Rule Context} window
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	319 is keyed simply to the highlighted rule. The other four windows, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	320 \agwindow{Expansion Rules} window, the \agwindow{Productions} window,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	321 the \agwindow{Set Elements} window, and the \agwindow{Token Usage}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	322 window are keyed to the marked token. Remember that there is no marked
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	323 token on the last line of the \agwindow{Rule Derivation} window.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	324
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	325 \subsection{Resolving Ambiguities}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	326 \index{Ambiguities}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	327
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	328 The shift-reduce conflict discussed earlier stemmed from an oversight
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	329 in writing a grammar: the grammar specified a list of items, in this
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	330 case expressions, which could not be distinguished without a separator
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	331 of some sort. This conflict can be resolved simply by rewriting the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	332 grammar to require a comma separating the expressions.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	333
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	334 A similar problem comes from specifying a list of lists without any
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	335 separator. Sometimes such a specification is made inadvertently. The
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	336 erroneous Pascal grammar cited above had such a conflict. Here are
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	337 the productions that caused trouble:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	338
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	339 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	340 declaration part
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	341 -> declaration section
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	342 -> declaration part, declaration section
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	343
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	344 declaration section
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	345 -> proc and func declaration part
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	346
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	347 proc and func declaration part
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	348 -> proc or func declaration
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	349 -> proc and func declaration part, proc or func declaration
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	350
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	351 proc or func declaration
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	352 -> proc declaration
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	353 -> func declaration
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	354 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	355
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	356 Of course, there are other productions for \agcode{declaration
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	357 section} so that this grammar looks perfectly reasonable on the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	358 surface. A \agcode{declaration part} is a sequence of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	359 \agcode{declaration sections}. One type of \agcode{declaration
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	360 section}, the \agcode{proc and func declaration part}, is a sequence
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	361 of procedure or function definitions. Unfortunately, if you have two
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	362 procedure definitions in a row, it could be interpreted as one
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	363 \agcode{proc and func declaration part} consisting of two declarations
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	364 or two \agcode{proc and func declaration parts} each consisting of one
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	365 declaration. The problem here is that there is a little too much
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	366 recursion. You can fix this problem by replacing
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	367
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	368 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	369 declaration section
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	370 -> proc and func declaration part
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	371
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	372 proc and func declaration part
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	373 -> proc or func declaration
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	374 -> proc and func declaration part, proc or func declaration
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	375 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	376
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	377 with
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	378
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	379 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	380 declaration section
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	381 -> proc or func declaration
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	382 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	383
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	384 After a little reflection you will see that this simplification, which
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	385 eliminates one source of recursion, entails no loss of generality.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	386
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	387 In the above examples, the ambiguities were the results of errors in
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	388 the specification of the grammar, and could be easily fixed by
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	389 correcting the grammar. Sometimes, however, ambiguities arise which
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	390 are not so easily corrected. Consider, for instance, a simple token
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	391 scanner:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	392
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	393 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	394 tokens
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	395 -> [token, white space?...]...
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	396
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	397 token
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	398 -> name
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	399 -> number
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	400 -> string
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	401 -> character constant
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	402 -> punctuation character
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	403 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	404
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	405 where \agcode{name}, \agcode{number}, etc., are defined in the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	406 conventional manner.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	407
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	408 Such token scanners are normally written using conventional
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	409 programming techniques, or using programs such as \agfile{lex} which
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	410 are based on the analysis of regular expressions. Such programs
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	411 simply work on a character by character basis and do not see that
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	412 ``maryjane'' could be interpreted as one name or as two, or as even
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	413 more, since the separating white space is declared to be optional.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	414 AnaGram, however, since it takes a broader view, sees that the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	415 specifications are basically ambiguous and complains. Note, however,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	416 that the default resolution of conflicts, in this case choosing the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	417 shift action, will provide a parser that does precisely what you would
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	418 normally intend. Thus, the major concern is to make sure that the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	419 conflicts caused by this situation do not mask other more serious
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	420 conditions.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	421
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	422 While it is possible to rewrite this grammar so that it is not
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	423 ambiguous, such a grammar would lack clarity and conciseness. AnaGram
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	424 provides two alternatives for dealing with this problem: the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	425 \index{Declaration}\index{Subgrammar declaration}\agparam{subgrammar}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	426 declaration and the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	427 \index{Sticky declaration}\index{Declaration}\agparam{sticky}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	428 declaration, which accomplish the desired end using very different
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	429 techniques.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	430
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	431 In the definition above, a grammar for token, taken all by itself,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	432 would not normally show any ambiguities. We could write a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	433 \index{Lexical scanner}lexical scanner that would identify a token,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	434 pass it on to the parser, and then go on to the next. We would never
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	435 worry about any ambiguities. In this situation, it is clear that what
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	436 we mean by \agcode{token} is defined entirely by the grammar for
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	437 \agcode{token}, not by its usage within the rest of the grammar. When
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	438 we say that we have a sequence of tokens, \agcode{token...}, we
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	439 usually mean that, of course, two tokens, such as ``mary'' and
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	440 ``jane'' have to be separated by punctuation or space to be
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	441 distinguished as separate tokens. The
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	442 \index{Declaration}\index{Subgrammar declaration}\agparam{subgrammar}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	443 declaration allows you to specify that a particular \index{Nonterminal
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	444 token}\index{Token}nonterminal token in your grammar is to be treated
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	445 as though it were defined by its own complete grammar, without regard
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	446 to its usage in the grander scheme of things. In the example above,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	447 add the following:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	448
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	449 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	450 [ subgrammar \bra token \ket ]
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	451 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	452
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	453 Now, when AnaGram conducts its search for reducing tokens, it will
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	454 limit its search to those it would find if your grammar consisted only
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	455 of the grammar rules necessary to define token. When it does this, it
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	456 never even finds the reducing tokens that appear to cause conflicts.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	457 When you fix a conflict with the \agparam{subgrammar} declaration, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	458 conflict vanishes entirely. It is not recorded in the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	459 \agwindow{Resolved Conflicts} window. For this reason, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	460 \agparam{subgrammar} declaration should be used only when you are
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	461 absolutely sure of the nature of the problem you are trying to solve.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	462
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	463 A somewhat more precise mechanism for dealing with the conflicts
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	464 described above is to declare name and number as \index{Sticky
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	465 declaration}\index{Declaration}\agparam{sticky}:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	466
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	467 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	468 [ sticky \bra name, number \ket ]
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	469 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	470
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	471 This means that whenever the last token in your parser's input buffer
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	472 is \agcode{name} or \agcode{number}, it will shift in any acceptable
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	473 input character, and will disregard conflicting reduce options.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	474 AnaGram will continue to identify conflicts in your grammar due to
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	475 this cause, but will record them in the \agwindow{Resolved Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	476 window. Any other conflicts you may have will still show up in the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	477 \agwindow{Conflicts} window.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	478
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	479 Sometimes it may be desirable to introduce ambiguities deliberately
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	480 into a grammar. For example, although it is easy enough to write
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	481 normal grammar rules for the conventional expression logic used in
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	482 programming languages, it is possible to produce a somewhat more
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	483 compact, faster running parser by writing an ambiguous grammar and
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	484 using AnaGram's precedence declarations to resolve the ambiguities.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	485 An example of this technique is given in Chapter 9.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	486
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	487 \subsection{Null Productions}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	488
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	489 \index{Null productions}\index{Production}Null productions can be a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	490 fertile source of conflicts. Fortunately, many of them can be easily
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	491 resolved by simply rewriting a few rules. Consider, for example, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	492 following:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	493
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	494 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	495 name
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	496 -> capital letter, letter..., white space
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	497
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	498 initial
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	499 -> capital letter, period, white space
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	500
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	501 full name
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	502 -> name, initial?, name
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	503 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	504
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	505 In this example, \agcode{initial?} is a virtual production which
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	506 AnaGram replaces with
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	507 % not ``with''...
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	508
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	509 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	510 initial?
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	511 ->
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	512 -> initial
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	513 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	514
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	515 so \agcode{initial?} involves a null production.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	516
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	517 Recall that LALR-1 parsers cannot look ahead more than one character.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	518 The problem with this grammar, then, is that given the input ``John
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	519 Q'', there is no way to tell whether the ``Q'' is an initial or the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	520 first letter of the last name. Is this ``John Q. Public'' or ``John
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	521 Quincy''? Adding another production for ``full name'' so that
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	522 ``initial'' need not be marked as optional allows the parser to defer
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	523 its decision:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	524
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	525 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	526 full name
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	527 -> name, name
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	528 -> name, initial, name
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	529 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	530
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	531 Notice that the technique here is to \emph{avoid a reduction} until
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	532 the parser has enough information to proceed.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	533
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	534 \subsection{Reduce-Reduce Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	535
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	536 \index{Reduce-reduce conflicts}\index{Conflicts}Reduce-reduce
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	537 conflicts are usually caused by the limited lookahead of LR-1 parsing.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	538 Very occasionally, you might find a grammar with a reduce-reduce
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	539 conflict that is caused by the LALR-1 approximation to LR-1 parsing
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	540 that AnaGram supports. Such conflicts are quite easy to resolve,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	541 however, by almost trivial rewriting.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	542
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	543 Reduce-reduce conflicts commonly involve productions that are
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	544 intrinsically indistinguishable, for instance:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	545
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	546 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	547 tweedledee
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	548 -> tiddly, wink
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	549
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	550 tweedledum
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	551 -> tiddly, wink
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	552 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	553
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	554 However, it may be possible to distinguish \agcode{tweedledee} from
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	555 \agcode{tweedledum} by context. Suppose
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	556
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	557 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	558 gibber
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	559 -> tweedledee, apples
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	560 -> tweedledum, oranges
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	561 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	562
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	563 Now if you can distinguish \agcode{apples} from \agcode{oranges} on
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	564 the basis of the very first character, your parser will be able to
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	565 tell \agcode{tweedledee} from \agcode{tweedledum}. If, on the other
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	566 hand, it takes more than one input character to tell whether you have
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	567 \agcode{apples} or \agcode{oranges}, you have a reduce-reduce conflict.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	568
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	569 This example, of course, is rather far-fetched, since the potential
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	570 confusion between \agcode{tweedledee} and \agcode{tweedledum} is
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	571 obvious. More commonly, the definitions and usage of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	572 \agcode{tweedledee} and \agcode{tweedledum} are physically far apart
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	573 in the grammar. At one place in a grammar:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	574
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	575 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	576 balderdash
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	577 -> tweedledee, apples
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	578 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	579
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	580 Elsewhere, seemingly unrelated:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	581
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	582 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	583 buncombe
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	584 -> tweedledum, oranges
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	585 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	586
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	587 In a dark corner:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	588
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	589 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	590 gossip
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	591 -> buncombe, slander
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	592 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	593
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	594 And in yet another dark corner:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	595
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	596 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	597 small talk
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	598 -> gossip
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	599 -> rumors
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	600 -> balderdash
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	601 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	602
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	603 Once again, if \agcode{apples} and \agcode{oranges} cannot be
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	604 distinguished by the very first character, you have a reduce-reduce
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	605 conflict that is somewhat harder to find than the one discussed above,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	606 simply because the trail is somewhat more complicated to follow.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	607
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	608 \subsection{Identifying Reduce-Reduce Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	609 \index{Reduce-reduce conflicts}\index{Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	610
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	611 Although the machinery described above for identifying shift-reduce
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	612 conflicts can be used to investigate reduce-reduce conflicts, many
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	613 yield to comparison of the \agwindow{Reduction States} windows for the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	614 two rules. For the two rules to be distinguishable, no token which is
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	615 acceptable input for any of the reduction states belonging to one rule
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	616 can be acceptable input for any reduction state belonging to the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	617 other.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	618
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	619 Therefore, when you have a reduce-reduce conflict, there is an overlap
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	620 among the tokens in the reduction states for one rule and the tokens
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	621 in the reduction states for the other rule. Often, however, there are
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	622 many reduction states which are irrelevant as far as a particular
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	623 conflict is concerned. So AnaGram provides a special window, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	624 \agwindow{Problem States} window, in the \agmenu{Auxiliary Windows}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	625 menu for the \agwindow{Conflicts} and \agwindow{Resolved Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	626 windows. The \agwindow{Problem States} window for a particular rule
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	627 lists those, and only those, reduction states for the rule for which
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	628 the conflict token is acceptable input. This usually reduces the size
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	629 of the table and often makes the source of the problem immediately
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	630 obvious.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	631
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	632 \subsection{Resolving Reduce-Reduce Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	633
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	634 If you build a parser for a grammar that includes a reduce-reduce
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	635 conflict, AnaGram will arbitrarily reduce the first rule it
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	636 encountered while reading your grammar, that is, the rule with the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	637 smaller rule number. In some circumstances this default may be
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	638 acceptable. In other circumstances more may be required.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	639
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	640 Often, it is possible to get rid of reduce-reduce conflicts by
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	641 rewriting your grammar so that tokens that were once reducing tokens
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	642 for a rule become part of the rule itself. Thus, in the previous
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	643 example, you could write:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	644
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	645 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	646 tweedledee
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	647 -> tiddly, wink, apples
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	648
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	649 tweedledum
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	650 -> tiddly, wink, oranges
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	651 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	652
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	653 In other words, if \agcode{apples} always follows \agcode{tweedledee},
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	654 you can move \agcode{apples} ``down'' in the grammar by making it part
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	655 of \agcode{tweedledee}. Moving tokens ``down'' in this manner always
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	656 reduces the likelihood of conflicts. But what if \agcode{apples}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	657 doesn't always follow \agcode{tweedledee}? Then it is sometimes
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	658 worthwhile to make two versions of \agcode{tweedledee}:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	659
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	660 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	661 simple tweedledee
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	662 -> tiddly, wink
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	663
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	664 complex tweedledee
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	665 -> tiddly, wink, apples
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	666 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	667
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	668 and in each circumstance use whichever is appropriate. As with the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	669 earlier shift-reduce example, the technique is to avoid any reduction
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	670 until the tokens can be distinguished.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	671
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	672 Sometimes, however, reduce-reduce conflicts reflect a language design
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	673 that really demands greater lookahead than can be accommodated with an
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	674 LR-1 parser. In these cases you have two options: you can consider a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	675 multi-stage parser or you can implement an ad hoc lookahead procedure.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	676 In the latter case, you can use semantically determined productions to
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	677 control your parser depending on the results of your lookahead
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	678 procedure.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	679
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	680 \subsection{Conflicts due to LALR-1 Simplifications}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	681 \index{LALR simplifications}\index{Conflicts}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	682
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	683 LALR-1 \index{Parser generator}parser generators occasionally report a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	684 reduce-reduce conflict where an LR-1 parser would successfully resolve
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	685 the conflict. How significant is this problem? An early prototype
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	686 version of AnaGram actually had full LR-1 capability. Unfortunately
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	687 LR-1 parsers are generally much bigger than LALR-1 parsers. Creating
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	688 them takes longer and more resources so that for given computer
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	689 resources an LALR-1 parser generator can handle larger, more complex
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	690 grammars than an LR-1 parser generator. To provide a compromise, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	691 prototype was modified to do an LALR-1 analysis first. Then, only if
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	692 there were reduce-reduce conflicts did it do an LR-1 analysis. Over a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	693 substantial period of testing, the only reduce-reduce conflicts that
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	694 were resolved by the LR-1 analysis were those that were created
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	695 deliberately as tests. Eventually the LR-1 capabilities were removed
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	696 from AnaGram since they added complexity without concomitant benefits.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	697 To understand why this is so, it is worthwhile to look at an example.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	698 Let us recall the definitions of \agcode{tweedledee} and
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	699 \agcode{tweedledum} made above:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	700
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	701 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	702 tweedledee
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	703 -> tiddly, wink
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	704 tweedledum
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	705 -> tiddly, wink
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	706 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	707
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	708 Remember that we defined gibber thus:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	709
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	710 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	711 gibber
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	712 -> tweedledee, apples
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	713 -> tweedledum, oranges
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	714 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	715
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	716 Now suppose that we also define jabber in a contrary way:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	717
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	718 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	719 jabber
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	720 -> tweedledee, oranges
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	721 -> tweedledum, apples
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	722 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	723
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	724 Now suppose we use \agcode{gibber} in one part of our grammar and
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	725 \agcode{jabber} in another, completely unrelated, part. An LR-1
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	726 parser generator would succeed in keeping \agcode{tweedledee} and
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	727 \agcode{tweedledum} straight in spite of our efforts to confuse it.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	728 An LALR-1 parser generator, however, succumbs to our efforts and
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	729 reports a conflict. A trivial rewrite of the grammar, however,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	730 removes the conflict:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	731
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	732 \begin{indentingcode}{0.4in}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	733 gibber tweedledee
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	734 -> tiddly, wink
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	735 gibber tweedledum
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	736 -> tiddly, wink
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	737
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	738 jabber tweedledee
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	739 -> tiddly, wink
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	740 jabber tweedledum
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	741 -> tiddly, wink
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	742
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	743 gibber
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	744 -> gibber tweedledee, apples
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	745 -> gibber tweedledum, oranges
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	746
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	747 jabber
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	748 -> jabber tweedledee, oranges
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	749 -> jabber tweedledum, apples
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	750 \end{indentingcode}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	751
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	752 The effect of this rewrite is to accomplish the same separation of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	753 states that an LR-1 parser generator would make.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	754
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	755 \section{Keyword Anomalies}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	756 \index{Keyword Anomalies}\index{Anomaly}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	757
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	758 In syntax directed parsing, it is assumed that input tokens can be
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	759 uniquely identified. In the case of keywords, however, there is the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	760 possibility that the individual characters making up the keyword, as
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	761 well as the keyword taken as a whole, could constitute legitimate
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	762 input under some circumstances. Thus keywords, though a powerful and
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	763 useful tool, are not completely consistent with the assumptions that
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	764 underlie syntax directed parsing. This can occasionally give rise to a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	765 type of conflict, diagnosed by AnaGram, called a \agterm{keyword
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	766 anomaly}. AnaGram is quite conservative in its diagnoses, so that many
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	767 keyword anomalies it reports are actually innocuous and can be safely
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	768 ignored. Nevertheless, anomalies should be investigated carefully.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	769
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	770 AnaGram only recognizes a keyword in those states where the keyword is
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	771 allowable input. If AnaGram recognizes a keyword, the keyword takes
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	772 precedence over the sequence of characters that constitute the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	773 keyword. If there are several allowable keywords, the longest takes
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	774 precedence.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	775
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	776 Under certain circumstances it is possible for a grammar to have a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	777 state where a particular keyword may or may not be allowable input
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	778 depending on how the parser gets to that state. That is, for some
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	779 sequences of tokens which lead to the state, the keyword is allowable,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	780 in others it isn't. In such a state, the keyword must always cause a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	781 reduction, since if the keyword were to shift, it would always be
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	782 allowable input. When AnaGram finds such a state in your parser, it
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	783 checks to see what the parser action would be if the parser ignored
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	784 the keyword and interpreted it in terms of its constituent
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	785 characters. If the parser action would be anything other than reducing
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	786 the same rule as the keyword or a syntax error, AnaGram will diagnose
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	787 a keyword anomaly in this state.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	788
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	789 To summarize, the nature of a keyword anomaly is this: It is possible
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	790 for your parser to get to the anomalous state by a route for which the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	791 keyword is not allowable. In the anomalous state, at least the first
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	792 constituent character of the keyword is allowable in its own right and
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	793 causes a parser action different from that caused by the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	794 keyword. Nonetheless, if the keyword should appear in the input, your
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	795 parser will recognize it, perform at least one reduction action, get
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	796 to a state where the keyword is not recognized, and finally, in the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	797 wrong state, will try to interpret the keyword in terms of its
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	798 constituent characters.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	799
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	800 Now, what do you do about a keyword anomaly? If in the anomalous state
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	801 the characters which constitute the keyword would never be
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	802 syntactically admissible as individual characters, the keyword anomaly
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	803 is innocuous in that the only problem is that the recognition of the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	804 syntax error is somewhat delayed. If however, the characters which
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	805 constitute the keyword are syntactically admissible, you have a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	806 problem that needs to be fixed.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	807
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	808 In many programming languages, many keywords are treated as
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	809 \agterm{reserved words}, that is, as words that may not be otherwise
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	810 used in a conforming program. Version 1.5 of AnaGram has added a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	811 \index{Reserve keywords}\agparam{reserve keywords} statement that you
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	812 can use to specify that the text of a keyword is \emph{never}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	813 admissible as individual characters. Thus you will never get a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	814 keyword anomaly diagnostic for a keyword that has been listed in a
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	815 \index{Reserve keywords}\agparam{reserve keywords} statement.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	816 The \agparam{reserve keywords} statement is described in greater
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	817 detail in \S 8.2.28.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	818 % XXX this is the only place in the manual (so far?) that uses the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	819 % \S section-symbol. (Also, this should be a tex crossreference.)
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	820
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	821 \subsection{The Keyword Anomalies Window}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	822 \index{Keyword Anomalies}\index{Window}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	823
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	824 If your grammar has a keyword anomaly, AnaGram will provide a warning
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	825 message and will create a \agwindow{Keyword Anomalies} window to
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	826 provide details about the anomalies in your grammar.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	827
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	828 Each entry in the \agwindow{Keyword Anomalies} window consists of two
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	829 lines. The first line identifies the state at which the anomaly
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	830 occurs and the offending keyword. The second line identifies the rule
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	831 which the keyword may erroneously reduce. The \agmenu{Auxiliary
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	832 Windows} menu provides three auxiliary windows keyed directly to the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	833 anomaly to help you determine the nature of the problem: the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	834 \agwindow{Keyword Anomaly Trace} window, the \agwindow{Reduction
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	835 Trace} window, and the \agwindow{Rule Derivation} window. In
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	836 addition, three other windows provide supporting information: the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	837 \agwindow{Reduction States} window, the \agwindow{Rule Context} window
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	838 and the \agwindow{State Definition} window. These windows are
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	839 discussed in Chapter 6.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	840
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	841 The \agwindow{Keyword Anomaly Trace} window, a pre-built
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	842 \agwindow{Grammar Trace}, shows a sequence of tokens that illustrates
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	843 one way to encounter the anomaly. The \agwindow{Reduction Trace}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	844 window shows the result of performing the reduction action. Just as
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	845 for conflicts, the true source of the problem is often at some remove
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	846 from the actual state in which the problem manifests itself. One of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	847 the characteristic rules for the last state in the \agwindow{Reduction
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	848 Trace} window is, in fact, the true source of the problem. The
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	849 \agwindow{Rule Derivation} window can show you which of the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	850 characteristic rules is the offending party and how the rule in the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	851 anomalous state derives from it.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	852
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	853 \subsection{Dealing with Keyword Anomalies}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	854
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	855 If your grammar has a keyword anomaly, you should study it carefully.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	856 It may be that the anomaly is completely innocuous, that is, the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	857 characters which constitute the keyword are not otherwise legitimate
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	858 input. In this case you can simply ignore the message.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	859
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	860 The basic approach to dealing with keyword anomalies is to revise your
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	861 grammar to make a better distinction between the contexts in which the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	862 keyword is acceptable and those in which it may be confused with
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	863 otherwise valid input. Several other techniques may be useful:
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	864
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	865 For an anomaly to occur, there must be, \emph{in the anomaly state},
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	866 an alternative interpretation of some of the initial characters of the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	867 keyword. If the anomaly occurs because you have several keywords that
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	868 begin in a similar manner, you may use the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	869 \index{Distinguish keywords}\index{Keywords}\agparam{distinguish keywords}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	870 statement (see Chapter 8) to keep them properly separated. Note that
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	871 having several keywords that begin with the same characters does
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	872 \emph{not} necessarily cause an anomaly.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	873
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	874 If the keyword is an alphabetic keyword that can follow conventional
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	875 variable name tokens, you may wish to use a \agparam{sticky}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	876 declaration or the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	877 \index{Distinguish lexemes}\index{Configuration switch}
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	878 \agparam{distinguish lexemes} switch
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	879 to inhibit recognition of the keyword when it is preceded immediately
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	880 by a name.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	881
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	882 If the keyword can be treated as a reserved word, the \index{Reserve
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	883 keywords}\agparam{reserve keywords} statement will eliminate the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	884 anomaly.

Mercurial > ~dholland > hg > ag > index.cgi

annotate doc/manual/xg-iii.tex @ 21:1c9dac05d040