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

annotate doc/manual/xg-iii.tex @ 2:4b08ee1ecb99

Adjust install notes to clarify that Wine applies only to the Windows build. (Thanks to Perry Metzger for test-driving.)

author	David A. Holland
date	Sun, 26 Apr 2009 17:58:26 -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 @ 2:4b08ee1ecb99