Mercurial > ~dholland > hg > ag > index.cgi
diff doc/manual/xg-i.tex @ 0:13d2b8934445
Import AnaGram (near-)release tree into Mercurial.
author | David A. Holland |
---|---|
date | Sat, 22 Dec 2007 17:52:45 -0500 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/manual/xg-i.tex Sat Dec 22 17:52:45 2007 -0500 @@ -0,0 +1,575 @@ +\chapter{Exploring Your Grammar I: Traces} + +\section{Introduction} + +AnaGram provides two important facilities to help you become familiar +with the workings of your parser: the File Trace and the Grammar +Trace. The File Trace takes its input from a test file and, under +your control, parses the input in accordance with your grammar. The +Grammar Trace is completely interactive. In each state it presents +you with a list of acceptable tokens and lets you select the one you +wish. The File Trace lets you see how your grammar will deal with a +specific input file. The Grammar Trace lets you answer ``what if?'' +questions. + +AnaGram also provides several ready-made traces to help you deal with +specific problems. The +\index{Error Trace}\index{Trace}\index{Window}\agwindow{Error Trace} +can show you why your parser has diagnosed a syntax error. The +\index{Conflict Trace}\index{Trace}\index{Window}\agwindow{Conflict +Trace} and +\index{Reduction Trace}\index{Trace}\index{Window}\agwindow{Reduction +trace} can help you identify the sources of ambiguities in your +grammar. The +\index{Keyword Anomaly Trace}\index{Trace}\index{Window}\agwindow{Keyword +Anomaly Trace} can help you understand the genesis of a keyword +anomaly in your grammar. In addition, the +\index{Trace}\index{Auxiliary Trace}\index{Window}\agmenu{Auxiliary Trace} +selection in the +\agmenu{Auxiliary Windows} popup menu enables you to get a trace to +any state you wish or to transmute a File Trace into a Grammar Trace. + +The trace functions serve several purposes. They are an ideal way to +learn how syntax directed parsing works since they make each step +clearly visible. They are also useful in determining whether your +grammar works as you wish it to. You can try your grammar out on real +data before you actually build a parser. If your grammar has +problems, such as conflicts, you can use the trace functions to track +down the problems, to understand them, and to verify your corrections. + +You may have any number of File and Grammar Traces active +simultaneously. + +Remember that AnaGram usually uses short-cut parsing actions whenever +possible. If you wish to see just the standard four parsing actions, +you may want to set the \agparam{traditional engine} switch. This +will, however, substantially increase the size of your parser and +reduce its performance. + +\section{Trace Windows} + +The \agwindow{File} and \agwindow{Grammar Trace} windows normally each +contain three panes: the \agwindow{Parser Stack} pane, an input pane, +and the \agwindow{Rule Stack} pane. If your grammar uses semantically +determined productions, the Reduction Choices pane will appear when +necessary to allow you to select a reduction token. + +% XXX s/some point/a point/ +In the File Trace, the input, or \index{Test File pane}\agwindow{Test +File}, pane displays the test file. You need only double click on +some point in the pane to test your grammar up to that point in the +file. Differently colored backgrounds are used to distinguish the +part of the file that has been parsed from the part that has not yet +been parsed. + +In the Grammar Trace, the input, or \index{Allowable Input +pane}\agwindow{Allowable Input}, pane displays a list of tokens which +are allowable input in the current state of the parser. You may +select tokens from the \agwindow{Allowable Input} pane, one by one, or +use the text entry field to type input to be parsed. + +The active pane has a distinctively colored title panel and cursor +bar, except for the \agwindow{Test File} pane in the \agwindow{File +Trace} which has no cursor bar. You can use the tab key to tab among +the panes. The function of other keyboard keys depends on which pane +is active. + +Along the bottom of the trace windows is a toolbar which provides +status information as well as control buttons. + +\subsection{Parser Stack Pane} + +The \index{Parser Stack pane}\agwindow{Parser Stack} pane, the upper +left pane of the \agwindow{File Trace} and \agwindow{Grammar Trace} +windows, displays the parser stack for the current trace. + +Each line corresponds to one level in the parser state stack, showing +the stack index, the parser state for that level, and the token which +was seen at that state. The last line of the stack, the lookahead +line, corresponds to the current state of the parser. Since no input +has yet been processed for this state, the token, if any, which +appears at this level is a lookahead token. + +In the File Trace, the token on the lookahead line corresponds to the +character at the parse location in the Test File pane. In the Grammar +Trace, the lookahead line is empty whenever all previous input to the +parser has been completely parsed, otherwise it will display the most +recently selected input token. + +If you move the cursor in the Parser Stack pane of a File Trace, the +text that makes up the selected token will be highlighted in the Test +File pane. You can back the parse up to any desired stack level by +double clicking at the beginning of the token text in the Test File +pane. + +Similarly, if you move the cursor bar in the Parser Stack pane of a +Grammar Trace, the \index{Allowable Input pane}\agwindow{Allowable +Input} pane will change to display the allowable tokens in the +selected state. The previously selected token will be highlighted. +Then, double click on any token in the Allowable Input pane to back +the parse up and choose a token a second time. + +The \index{Rule Stack pane}\agwindow{Rule Stack} pane (see below) of +the \agwindow{File} or \agwindow{Grammar Trace} is also synched to the +\agwindow{Parser Stack} pane. If the syntax file window is visible, +it will be synched to show the rule currently selected in the +\agwindow{Rule Stack} pane. Note that rules that have been +automatically generated by the expansion of virtual productions cannot +be synched, so the top line of the syntax file will be highlighted +instead. + +If you right-click on a highlighted line in the Parser Stack pane, you +will get a pop-up menu to give you more information. In particular +you can get an \agwindow{Auxiliary Trace} starting at the current +point in your \agwindow{File} or \agwindow{Grammar Trace}, so you can +explore various possibilities without losing your position in the old +trace. + +\subsection{Rule Stack Pane} + +The \index{Rule Stack pane}Rule Stack pane appears across the bottom +of a \agwindow{Grammar Trace} or \agwindow{File Trace} window. It +provides an alternate view of the parser stack for the trace, showing, +for each state, rules instead of the tokens that you see in the +\agwindow{Parser Stack} pane. Because it is synched with the syntax +file window, the \agwindow{Rule Stack} makes it easy to see the +relationship between the trace and your grammar. + +For each level of the parser stack, the \agwindow{Rule Stack} shows +the parser state number and all the active rules. The active rules at +any state consist of all the expansion rules for the state that are +consistent with the input at all subsequent states. + +Except for the last level of the stack, each rule has a +\index{Token}\agterm{marked token}, which in the default +configuration is displayed in bold, italic type. The significance of +the marked token is that all tokens in the rule to the left of the +marked token have already been matched in the input, and the input in +subsequent levels is consistent so far with the marked token. As more +input is processed, rules that are inconsistent with the new input are +deleted from the display. + +The last level of the stack shows the current state of the parser and +the rules against which the lookahead token will be matched. At this +level, there may be rules with no marked tokens. These are rules +which have been matched exactly in the input. If there is more than +one such rule, at the next parser step the parser will use the +lookahead token to determine which rule to reduce. + +In the last level of the stack, marked tokens represent the input the +parser expects to see next. + +The \agwindow{Rule Stack} pane is synched with the syntax file window +if it is visible so that the rule highlighted in the \agwindow{Rule +Stack} can be seen in context in the syntax file. For rules that +AnaGram generated automatically to implement virtual productions or +the disregard statement, the cursor bar will move to the top of the +syntax file window. + +The \agwindow{Rule Stack} pane is also synched with the other panes in +the trace. As you move the cursor bar in the \agwindow{Rule Stack}, +the cursor bar in the \agwindow{Parser Stack} pane will track the +stack level in the \agwindow{Rule Stack}. In a \agwindow{File Trace}, +text will be highlighted in the \agwindow{Test File} pane +corresponding to the selected token in the \agwindow{Parser Stack} +pane. In a \agwindow{Grammar Trace}, the marked token in the +highlighted rule will be highlighted in the \agwindow{Allowable Input} +pane. + +Clicking the right mouse button in the \agwindow{Rule Stack} pane pops +up an \agmenu{Auxiliary Windows} menu to give you more information +about the highlighted rule. The \agmenu{Auxiliary Windows} menu +offers four choices keyed to the marked token: \agmenu{Expansion +Rules}, \agmenu{Productions}, \agmenu{Set Elements} and \agmenu{Token +Usage}. The \agmenu{Keywords}, \agmenu{State Definition} and +\agmenu{State Expansion} options are keyed to the state number. The +\agmenu{Expansion Chain} and \agmenu{Rule Context} options are keyed +to the highlighted rule. Note that by the very nature of the rule +stack, a completed rule may occur only at the last level. + +\subsection{Reduction Choices Pane} +\index{Reduction Choices pane} + +The \agwindow{File Trace} and \agwindow{Grammar Trace} display a +\agwindow{Reduction Choices} pane when they need to reduce a +semantically determined production. The rule to be reduced is +highlighted in the \agwindow{Rule Stack} pane. The syntax file +window, if visible, will show this rule highlighted if it is one that +appears directly in your grammar. + +The \agwindow{Reduction Choices} pane lists all possible reduction +tokens for the specified rule. The first reduction token that is +admissible in the current context is highlighted and it appears as the +lookahead token in the \agwindow{Parser Stack} pane. In the +\agwindow{File Trace}, text that comprises the entire rule is +highlighted in the \agwindow{Test File} pane. + +Select the desired reduction token before continuing with the parse. + +If you select a token and it does not appear as the lookahead token, +it is not syntactically correct in the current context. If you try to +proceed with the parse, you will get a selection error. + +\subsection{Parse Status} +\index{Parse Status} + +Both the \agwindow{File} and \agwindow{Grammar Trace} have a +\agwindow{Parse Status field} on the toolbar at the bottom of the +window to indicate the current state of the parser. The possible +values are as follows: +\begin{itemize} +\item \agmenu{Ready}: The parser is ready for input. +\item \agmenu{Running}: The parser is processing input. +\item \agmenu{Parse Complete}: According to the grammar, no further +input is expected. Click on reset or reload to restart the parse. +\item \agmenu{Syntax error}: A syntax error has been encountered. The +parser cannot go any further. +\item \agmenu{Unexpected end of file}: The parser has reached the end +of the actual input but the grammar still expects more. +\item \agmenu{Select reduction token}: The parser encountered a +semantically determined production. Select a reduction token from the +\agwindow{Reduction Choices} pane. +\item \agmenu{Selection error}: The reduction token selected from the +Reduction Choices pane was not allowable input in the present +state. Select another reduction token. +\end{itemize} + + +\section{File Trace} +\index{File Trace}\index{Trace}\index{Window} + +\subsection{Starting File Trace} + +To do a \agwindow{File Trace} you must first analyze the grammar you +wish to use. Then select \agmenu{File Trace} from the \agmenu{Action} +menu. Select a file for parsing and the trace will begin. If you +have not analyzed a grammar or if your grammar does not accept ASCII +characters the \agmenu{File Trace} option will be grayed out. You may +provide a mask for the test file name by setting the +\index{Test file mask}\index{Configuration parameters}\agparam{test +file mask} configuration parameter in your syntax file (see Appendix +A, Configuration Parameters). AnaGram normally reads test files in +text mode, that is, carriage return characters are stripped. If you do +not want carriage return characters removed, you should set the +\index{Test file binary}\index{Configuration switches}\agparam{test +file binary} configuration switch. + +\subsection{Test File Pane} + +The file under test is displayed in the input pane in the upper right +of the \agwindow{File Trace} window. To parse to a specific point in +the file, double click at that point. If you double click at a point +that precedes the current parse location, the parse will back up to +that point. You may also use the cursor keys to control the parse. +As long as the parse location and the cursor are synchronized the +parse will track the cursor when you move the cursor using the cursor +keys. + +If the parse encounters a syntax error, it will not be able to go +beyond the location of the error. In this situation, moving the +cursor right or down will cause the cursor position to differ from the +parse location. The parse and cursor positions can also differ if you +single click anywhere in the Test File pane. + +If the parse location and the cursor are thus not synchronized, the +\agmenu{Single Step} button will be replaced with a \index{Synch +Parse}\agmenu{Synch Parse} button. Click on the \agmenu{Synch Parse} +button to get the cursor and the parse back in synch. Of course, the +parse will still not be able to proceed past a syntax error. + +In the \agwindow{Test File} pane, you can distinguish text that has +been parsed from unparsed text because it is shown in a different +color. (The default background color for parsed text is lighter.) +Initially no text has been parsed, and the caret is positioned at the +beginning of the file. The \index{Parse Location}\agwindow{Parse +Location} box at the lower left of \agwindow{File Trace} will show +\textit{1:1} for line 1, column 1. The \agwindow{Parse Status} box +next to it will say \agmenu{Ready}. + +If your grammar uses semantically determined productions, the parse +will halt when one is encountered and the \agwindow{Reduction Choices} +pane will be displayed so you may select the appropriate reduction +token. + +% XXX index Reload? +At any time you can click on the \index{Reset}\agmenu{Reset} button to +reset the parse to the beginning of the test file. If you modify the +test file, you can click on the \agmenu{Reload} button to load the +modified file and reset the parse. + +Normally, AnaGram reads test files in ``text'' mode, discarding +carriage return characters. If your parser needs to recognize carriage +return characters explicitly, you should turn the \index{test file +binary}\agparam{test file binary} configuration switch on. + +\subsection{File Trace Toolbar} + +The File Trace window has a toolbar at the very bottom of the window +which provides parse status information as described above and +contains buttons to help control the parse. The buttons are as +follows: + +\begin{itemize} +\item \index{Single Step}\agmenu{Single Step}: Advances the parse one +parser action at a time. +\item \index{Synch Parse}\agmenu{Synch Parse}: Replaces the \agmenu{Single +Step} button when the blinking cursor and the parse location do not +coincide. Clicking on the \agmenu{Synch Parse} button will cause the +parse to back up to the blinking cursor, if the blinking cursor +precedes the parse location, or parse to the blinking cursor +otherwise. If the parser encounters a syntax error before reaching +the cursor, the parse will stop at the error and the parse will still +not be in synch with the cursor. +\item \index{Parse File}\agmenu{Parse File}: Parses all the way to the +end of file. The parse will not stop until it encounters a syntax +error, a semantically determined production, or the end of file. +\item \index{Reset}\agmenu{Reset}: Resets the parse to its initial +state. +\item \index{Reload}\agmenu{Reload}: Reloads the test file from +disk. This is useful if you have edited the test file since you last +loaded it into the \agwindow{File Trace}. +\end{itemize} + + +\section{Grammar Trace} +\index{Grammar Trace}\index{Trace}\index{Window} + +A \agwindow{Grammar Trace} can be selected from either the +\agmenu{Action} menu or the \agwindow{Control Panel} toolbar. With +it, you can examine the workings of your parser in detail. Using +various options, you can set up representations of the +\index{Parser state stack}\index{State stack}\index{Stack}parser state +stack and parser state as they might appear in the course of execution +of your parser. You can then examine the possible inputs and the +changes to the state and the state stack caused by any input you +choose. + +Several of AnaGram's debugging facilities employ a ready-made +\agwindow{Grammar Trace} to direct you to the source of trouble. +These are the \agwindow{Conflict Trace}, the \agwindow{Reduction +Trace}, the \agwindow{Error Trace}, the \agwindow{Keyword Anomaly +Trace}, and the \agwindow{Auxiliary Trace}. + +AnaGram now provides a text entry field where you can enter input text for a +\agwindow{Grammar Trace}, in addition to choosing tokens from +\agwindow{Allowable Input}. This means +you can run a \agwindow{Grammar Trace} like a \agwindow{File Trace} +where the test file is replaced by text you can type in. This is a +very convenient way to check out your grammar. + +\subsection{Allowable Input Pane} +\index{Allowable Input pane} + +The upper right pane of the \agwindow{Grammar Trace} window lists the +allowable input tokens for the current state of the grammar. The +current state is the state selected by the cursor bar in the +\agwindow{Parser Stack} pane. + +The tokens in the \agwindow{Allowable Input} pane are listed in two +groups: first, the terminal tokens allowable in this state, and +second, the nonterminal tokens. Between these two groups of tokens is +inserted a line which is either an option for a default reduction, or +declares that there is no default action. + +Double click, press Enter, or click the \agmenu{Proceed} button to +parse the highlighted token. When all parse actions triggered by the +highlighted token have been completed, all panes of the trace will be +redrawn to show the new state of the parser. + +If you wish to see the results of a single parser action, click on the +\agmenu{Single Step} button. The parser will perform a single parser +action. If the token you selected was not shifted in, it will now be +displayed as the lookahead token on the last line, the lookahead line, +in the \agwindow{Parser Stack} pane, and will be preselected in the +\agwindow{Allowable Input} pane. Because AnaGram, by default, uses a +number of compound parser actions, this situation does not arise very +often unless you have set the +\index{traditional engine}\agparam{traditional engine} switch or reset +the \index{default reductions}\agparam{default reductions} switch. +Usually you will want to select the same token to proceed, but it is +not necessary. + +% XXX the << and >> render really poorly. They should be italic, too, +% but I can't get them to set that way. +The \agwindow{Allowable Input} pane also displays the parser action +associated with a specific token, and its result, provided it is not a +compound action. The parser action field for a token may be +interpreted as follows: If this token would cause a shift to a new +state, the action field is $>>$ followed by the new state number. If +the token would cause a reduction, the action field is $<<$ followed +by a rule number to show the rule reduced. If the parser action is a +compound action, the action field is blank. If the token would cause +the grammar to be accepted, the action field is \textit{Accept}. + +If a parser action requires the reduction of a semantically determined +production, the \agwindow{Reduction Choices} pane will open. Select a +reduction token to continue. + +Note that selecting a token in \agwindow{Allowable Input} can cause a +syntax error under certain circumstances. This can happen only if the +following conditions are all true: + +\begin{itemize} +\item the indicated operation is a reduction, +\item the reduction token for the rule being reduced has been used in +several different contexts in the grammar, +\item and the specified token may follow it in some contexts and not +in others. +\end{itemize} + +\subsection{Text Entry Field} +\index{Text Entry field} + +It is sometimes more convenient to enter text in the text entry field +on the \agwindow{Grammar Trace} toolbar than to select individual +tokens from the \agwindow{Allowable Input} pane. By entering text you +can proceed quickly to the state you want without having to choose +each individual token en route. + +After entering text, press Enter or click on the \agmenu{Proceed} +button to parse the text. The text will be parsed in its entirety +unless a syntax error or semantically determined production is +encountered. + +Click on the \agmenu{Single Step} button to work slowly through the +text step by step. + +\subsection{Grammar Trace Toolbar} + +The Grammar Trace window has a toolbar at the very bottom of the +window which provides parse status information as described above and +contains buttons to help control the parse. The buttons are as +follows: + +\begin{itemize} +\item \index{Proceed}\agmenu{Proceed}: Parses the token selected in +\agwindow{Reduction Choices} if that pane is active, or the token +selected in \agwindow{Allowable Input} if that pane is active, or the +content of the text entry field if that is active. The parse +continues until the input has been entirely shifted in, a semantically +determined production has been encountered, or a syntax error has +been encountered. +\item \index{Single Step}\agmenu{Single Step}: Advances the parse one +parser action at a time. Input is taken as for the \agmenu{Proceed} +button. +\item \index{Reset}\agmenu{Reset}: Reset the parse to its initial +state. This is especially useful if the \agwindow{Grammar Trace} is +one of the pre-built traces discussed below. In such a trace the +initial state can be quite complex. +\end{itemize} + + +\section{Other Traces} + +\subsection{Error Trace} +\index{Error Trace}\index{Trace}\index{Window} + +An \agwindow{Error Trace} is a preset \agwindow{Grammar Trace} +designed to help you deal with errors your parser encounters during +operation. If the +\index{Error trace}\index{Configuration switches}\agparam{error trace} +configuration switch is set when AnaGram builds a parser, whenever the +parser detects: +\begin{itemize} +\item a \index{Syntax error}\index{Errors}syntax error +\item a parser stack overflow, or +\item a reduction token error +\end{itemize} +it will write the current state stack to a file with the extension +\index{etr}\index{File extension}\agfile{.etr} and the name of the +parser file. If such a file already exists, it will be overwritten. + +When you analyze the grammar, AnaGram will enable the \agmenu{Error +Trace} option in the \agmenu{Browse} menu. When you select the +\agmenu{Error Trace} option, you can select an error trace file. +AnaGram will use it to create a grammar trace which reproduces the +state of the parser at the time of the error. You may then work with +the trace as with any other grammar trace. The \agmenu{Reset} button +will restore the trace to its initial condition. + +Note that when the syntax file is modified, an error trace file may +become invalid. If you try to load an error trace file that is older +than the syntax file, AnaGram will pop up a message box to warn you. + +\subsection{Conflict and Reduction Traces} +\index{Conflict Trace}\index{Trace}\index{Window} +\index{Reduction Trace}\index{Trace}\index{Window} + +The \agwindow{Conflict Trace} and its companion, the +\agwindow{Reduction Trace}, are ready-made \agwindow{Grammar Traces} +which can be invoked from a \agwindow{Conflicts} window or a +\agwindow{Resolved Conflicts} window using the \agmenu{Auxiliary +Windows} menu. The \agwindow{Conflict Trace} shows one way out of +perhaps many ways to get to the conflict state highlighted in the +\agwindow{Conflicts} window. The \agwindow{Reduction Trace} +progresses one step farther than the \agwindow{Conflict Trace}, +showing the result of selecting a reduce action in the conflict state. +You can manipulate both traces just as you would a regular grammar +trace. The \agmenu{Reset} button will reset the trace to its original +condition. + +\agwindow{Conflict} and \agwindow{Reduction Trace} windows may be +obtained only from the \agwindow{Conflicts} window or the +\agwindow{Resolved Conflicts} window using the \agmenu{Auxiliary +Windows} popup menu. For more information see the section on +conflicts in Chapter 7. + +\subsection{Keyword Anomaly Trace} +\index{Keyword Anomaly Trace}\index{Trace}\index{Window} + +The \agwindow{Keyword Anomaly Trace} is another ready-made grammar +trace which is invoked from a \agwindow{Keyword Anomalies} window +using the \agmenu{Auxiliary Windows} popup menu. It shows one way out +of perhaps many to get to the anomaly highlighted in the +\agwindow{Keyword Anomalies} window. You can manipulate the +\agwindow{Keyword Anomaly Trace} in the same way that you would a +regular grammar trace. The \agmenu{Reset} button will restore the +trace to its original configuration. + +The \agwindow{Keyword Anomaly Trace} may be obtained only from the +\agmenu{Auxiliary Windows} popup menu in the \agwindow{Keyword +Anomalies} window. For more information see the section on keyword +anomalies in Chapter 7. + +\subsection{Auxiliary Trace} +\index{Auxiliary Trace}\index{Trace} + +For many AnaGram windows, an \agwindow{Auxiliary Trace} is one of the +options on the right mouse button pop up menu. In most cases this is +simply a pre-built \agwindow{Grammar Trace} that leads to the state +specified by the highlighted line in the window. In the case of the +\agwindow{File} and \agwindow{Grammar Traces}, selecting an +\agwindow{Auxiliary Trace} from the \agwindow{Parser Stack} pane popup +menu gives you a \agwindow{Grammar Trace} with the same +\agwindow{Parser Stack} pane as the original \agwindow{Trace}. + +When using a \agwindow{File} or \agwindow{Grammar Trace}, an +\agwindow{Auxiliary Trace} can be useful for comparing the results at +a particular point of diverging input streams. + + +\section{Trace Coverage} +\index{Trace Coverage}\index{Window}\index{Coverage} + +When you run either \agwindow{File Trace} or \agwindow{Grammar Trace}, +AnaGram counts the number of times each rule is reduced. You can +display these counts by selecting the \agmenu{Trace Coverage} window +in the \agmenu{Browse} menu. The window displays all of the rules in +your grammar in the order in which they were encountered in your +syntax file. The window is synched to your syntax file window so that +you can easily see each rule in context. The first column of the +table gives the number of times this rule has been reduced by the +\agwindow{File Trace} process since you last analyzed your grammar. +Note that if, when tracing a file, you back up and try a portion of +input over and over, the counts for the rules involved will be +inflated relative to the other rules in the grammar. Thus, the +primary use of the \agwindow{Trace Coverage} table is to determine +whether there are rules that are not tested at all. Because AnaGram +normally uses a number of short-cut actions in its parsing tables, +some rules will not be counted even though they are obviously found in +the grammar. These rules all have length zero or one and have no +reduction procedures. If you set the +\index{rule coverage}\index{configuration parameters}\agparam{rule coverage} +configuration switch, AnaGram will turn off some of the optimization +so that you will get a more accurate count. +% XXX shouldn't ``found in the grammar'' above be ``found in the input''?