Mercurial > ~dholland > hg > ag > index.cgi
view doc/manual/sf.tex @ 19:db7ff952e01e
both mansupps seem to be html
author | David A. Holland |
---|---|
date | Tue, 31 May 2022 02:06:45 -0400 |
parents | 13d2b8934445 |
children |
line wrap: on
line source
\chapter{Syntax Files} \index{Syntax file}\index{File} Input files to AnaGram are called \agterm{syntax files}. A syntax file comprises a grammar and associated C or C++ code. The grammar consists of a number of productions along with supportng information such as configuration sections and definitions of character sets. The associated code consists of reduction procedures (see \S 8.2.13) and embedded C or C++ code (\S 8.2.17). This chapter explains the rules for writing syntax files acceptable to AnaGram. The rules for interfacing your parser to the balance of your program are given in Chapter 9. \section{Lexical Conventions} \index{Lexical conventions} \subsection{Statements} \index{Statements} For purposes of this manual, AnaGram statements are considered to be productions, definition statements, configuration sections, and blocks of embedded C or C++ code, all discussed individually below. Each statement must begin on a new line. It is a good idea to separate statements visually in your file by using blank lines freely. There are generally no restrictions on the \index{Statements}\index{Order of statements}order of statements in a syntax file. Good programming practice, however, suggests that definitions and configuration sections should precede the grammar itself. \subsection{Spaces and Tabs} \index{Spaces}\index{Tabs} AnaGram allows spaces and tabs to be used freely to improve the readability of grammars. Spaces and tabs are ignored, except when embedded in a token name, in a character set definition, or in a keyword. Within a token name, any sequence of spaces and tabs counts as a single space. \subsection{Continuation Lines} \index{Continuation lines} AnaGram statements normally end with a newline character or the end of file. If AnaGram encounters the end of a line and the statement it is reading appears to be complete, it will not look for a continuation. To continue a statement to another line, just make sure that what you have on the first line is clearly incomplete. For example, \begin{indentingcode}{0.4in} prep phrase -> preposition, "the", noun \end{indentingcode} looks complete to AnaGram, whereas \begin{indentingcode}{0.4in} prep phrase -> preposition, "the", noun, \end{indentingcode} looks incomplete because of the dangling comma at the end. \subsection{Comments} \index{Comments} AnaGram accepts comments in accordance with the rules of C and C++, that is, normal C comments bracketed with \agcode{/*} and \agcode{*/}, as well as comments which begin with \agcode{//} and continue to the end of line. AnaGram also observes these conventions when skipping over embedded C code. Since the ANSI standard for C insists that normal C comments do not nest, AnaGram, by default, disallows nested comments. You may, however, set a configuration parameter, \index{Nest comments}\index{Configuration switches}\index{Comments} \agparam{nest comments}, to allow nested comments. See Appendix A. In any case, AnaGram will use the same convention for embedded C as it uses for AnaGram proper. You can change the convention in the middle of the file if necessary. AnaGram treats each comment delimited with \agcode{/*} and \agcode{*/} as though it were a single space. You can even put such comments in the middle of token names if you should want to. A comment that begins with \agcode{//} is treated as though the end of line occurred at the \agcode{//}. \subsection{Blank Lines and Form Feeds} \index{Blank lines} Because blank lines and form feeds are visual separators, AnaGram will not skip either looking for a continuation line. Therefore blank lines and form feeds can occur only between AnaGram statements, not in the middle of a statement. It is a good idea to separate groups of productions with a blank line or two, lest an accidental dangling comma make AnaGram think the beginning of the next production is a continuation of the present one. \section{Elements of Grammars} \subsection{Names} \index{Name}\index{Token} You may use names to represent tokens, character sets, keywords and \index{Virtual productions}\index{Production}virtual productions. Names follow the same general rules as for any programming language, with the notable exception that they may have embedded white space. Names are made up of letters, digits, or underscores. They may not begin with a digit. Any sequence of embedded spaces, tabs or comments counts as a single space. AnaGram distinguishes between upper and lower case\index{Case sensitivity}, so that \agcode{Word} and \agcode{word} are different names. There is no particular limit to the length of a name. There are no reserved words as such, although \agcode{grammar}, \agcode{eof}, and \agcode{error} will be treated as reserved words unless you take special action by setting appropriate configuration parameters. The names AnaGram uses for \index{Configuration parameters}configuration parameters follow the same rules as for other names, except that \index{Case sensitivity}case is ignored. \subsection{Reserved Words} \index{Reserved words}\index{Words} % XXX shouldn't that be \index{Grammar token}? AnaGram treats tokens with the names \index{Grammar}\agcode{grammar}, \index{Eof token}\index{Token}\agcode{eof}, and \index{Error token}\index{Token}\agcode{error} in a special manner unless certain measures are taken. Since you can override AnaGram's use of these names, they are not reserved words in the true sense. If your grammar has a token named \agcode{grammar}, AnaGram will take that token to be the grammar token for your grammar unless you set the \index{Token}\index{Grammar token}\index{Configuration parameters} \agparam{grammar token} configuration parameter or mark some other token as the grammar token using ``\index{ \_dol}\$''.% See below ???. If your grammar has a token named \agcode{error} and you take no further steps, AnaGram will assume you wish to use error token resynchronization in case of \index{Syntax error}\index{Errors}syntax error. See Chapter 9. If you wish to use some other token as an error token you may select it using the \index{Configuration parameters}\index{Token}\index{Error token} \agparam{error token} configuration parameter. If you wish to use \agcode{error} as a token name, but do not want error token resynchronization, you may set the \agparam{error token} configuration parameter to any name that is not used in your grammar. You may then use \agcode{error} as a token name without causing AnaGram to include error token resynchronization in your parser. \index{Resynchronization} If you select automatic resynchronization or error token resynchronization (see Chapter 9), AnaGram will look for a token called \agcode{eof} to use as an end of file indicator. You may either name your end of file token \agcode{eof} or you may set the \agparam{eof token} configuration parameter with the name of your end of file token. \subsection{Variable Names} \index{Name}\index{C variable names} With AnaGram you can associate C/C++ variable names with the \index{Semantic value}\index{Token}\index{Value}semantic values of tokens for use in your \index{Reduction procedure}reduction procedures. Each name follows the corresponding token in the grammar rule on the right of the production, separated from the token by a colon. AnaGram allows variable names made up of letters, digits, and underscores. They may not begin with a digit. Embedded spaces, tabs or comments, are not allowed, of course. AnaGram imposes no restriction on length, but uses your variable names just as you have written them in the code it generates to call reduction procedures. Remember that your compiler may have a limit on the length of variable names. Also, AnaGram itself uses C variable names beginning with \agcode{ag{\us}}. It is therefore wise to avoid using names of this form. \subsection{Terminal Tokens} \index{Terminal token}\index{Token} A \agterm{terminal token} is a token which does not appear on the left side of a production. It represents, therefore, a basic unit of input to your parser. You have several options with respect to terminal tokens. If the input to your parser consists of ASCII characters, you may define terminal tokens explicitly as ASCII characters or as sets of ASCII characters. If you have an input procedure which produces numeric codes, you may define the terminal tokens directly in terms of these numeric codes. On the other hand, you may leave the terminal tokens completely undefined. In this case, you must provide an input procedure which can determine the appropriate \index{Token}\index{Token number}\index{Number}token numbers. It is an all or none situation. If you provide any explicit definitions, you must provide them for all terminal tokens. Input procedures and token input are discussed in Chapter 9. Examples of non-character input may be found in the Macro Preprocessor example in the \agfile{examples/mpp} directory on your AnaGram distribution disk.% Further examples are given in Chapter ???. % XXX change ``on ...distribution disk'' to ``in ...distribution''. \subsection{Character Representations} \index{Character representations} In specifying admissible input characters you may use \index{Character constants}character constants following the normal C conventions. Remember that a character constant may specify only a single character. Although some C compilers will allow constructs such as \agcode{'mv'}, AnaGram doesn't allow this. AnaGram recognizes the same escape sequences as C, including octal and hex sequences, even though this is, strictly speaking, unnecessary. The escape sequences AnaGram recognizes are: % % It would be nice to be able to just write this and tell latex to set % it in three columns. but no... that would be too easy. % % %\begin{tabular}{ll} %\agcode{{\bs}a}&alert (bell) character\\ %\agcode{{\bs}b}&backspace\\ %\agcode{{\bs}f}&formfeed\\ %\agcode{{\bs}n}&newline\\ %\agcode{{\bs}r}&carriage return\\ %\agcode{{\bs}t}&horizontal tab\\ %\agcode{{\bs}v}&vertical tab\\ %\agcode{{\bs\bs}}&backslash\\ %\agcode{{\bs}?}&question mark\\ %\agcode{{\bs}'}&single quote\\ %\agcode{{\bs}"}&double quote\\ %\agcode{{\bs}ooo}&octal number\\ %\agcode{{\bs}xhh}&hexadecimal number\\ %\end{tabular} \begin{indenting}{0.4in} \begin{tabular}{llllll} \agcode{{\bs}a}&alert (bell) character& \agcode{{\bs}t}&horizontal tab& \agcode{{\bs}'}&single quote\\ \agcode{{\bs}b}&backspace& \agcode{{\bs}v}&vertical tab& \agcode{{\bs}"}&double quote\\ \agcode{{\bs}f}&formfeed& \agcode{{\bs\bs}}&backslash& \agcode{{\bs}\textit{ooo}}&octal number\\ \agcode{{\bs}n}&newline& \agcode{{\bs}?}&question mark& \agcode{{\bs}x\textit{hh}}&hexadecimal number\\ \agcode{{\bs}r}&carriage return\\ \end{tabular} \end{indenting} \bigskip The octal escape sequence allows up to three octal digits, in accordance with ANSI specifications for C. The hexadecimal numbers may contain an arbitrary number of digits; however AnaGram will truncate the result to sixteen bits. A backslash followed by any character other than those listed above will cause a syntax error. You may also represent characters by writing the numeric code explicitly, in decimal, octal, or hexadecimal representations. AnaGram follows the C conventions for integer constants: a leading \agcode{0} means the number is octal, a leading \agcode{0x} or \agcode{0X} means it is hexadecimal. The hex digits \agcode{a-f} may be either upper or lower case\index{Case sensitivity}. Numbers may be preceded by an optional minus sign. If your parser uses a pre-existing \index{Lexical scanner}lexical scanner and you wish to use the code numbers it generates to identify tokens, you may simply treat those code numbers as character numbers. You may use the numbers directly in your productions, or you may use definition statements to name them. You may also use an \agparam{enum} statement within a configuration section to attach names to the code numbers. % XXX shouldn't this use of enum be indexed? AnaGram also allows a special notation for control characters. You may represent a control character by using the ``\^{}'' character preceding any printing ascii character. Thus you can write \agcode{\^{}z} or \agcode{\^{}Z} to represent the DOS end-of-file character. Notice that quotation marks are not necessary. Examples of character representations: \begin{indenting}{0.4in} \begin{tabular}{cccc} \agcode{'K'}&\agcode{-1}&\agcode{0}&\agcode{'{\bs}t'}\\ \agcode{\^{}J}&\agcode{'{\bs}xff'}&\agcode{077}&\agcode{0XF3}\\ \end{tabular} \end{indenting} \subsection{Character Ranges} \index{Character range}\index{Range} It is convenient to be able to specify ranges of characters when writing a grammar. AnaGram supports several ways of representing ranges of characters. The first is an extension of the notation for character constants: \agcode{'a-z'} is the set of lower case characters. You can even use escape sequences such as \agcode{'{\bs}n-{\bs}r'} if you like. The order of characters used to specify the range is immaterial: \agcode{'z-a'} is the same as \agcode{'a-z'}. AnaGram will, however, issue a warning just in case the unusual order results from a clerical error. The second way to specify a range is by using two arbitrary character representations, as described above, separated by two dots. For example, \agcode{\^{}C..\^{}Z}, \agcode{3..26}, \agcode{3..032}, \agcode{3..0x1a}, and \agcode{\^{}C..0x1a}, all represent the same range of characters. Similarly, \agcode{'A-F'}, \agcode{'A'..'F'}, \agcode{0101..0106}, \agcode{0x41..0x46}, \agcode{65..70}, and \agcode{65..'F'} all represent the same range of characters. \subsection{Character Sets} \index{Character sets} If you provide explicit definitions for terminal tokens, the basic input unit for your parser will be considered a character set, even if your input procedure provides numeric codes that are not actually characters. As a terminal token, a character set will be matched by any input character that is a member of the set. Character sets may be named in definition statements, but they may also appear on the right sides of productions without being named. A character set may consist of one or more characters. You can specify a character set that consists of a single character by using any of the character representation methods described above. You can specify a set consisting of a range of characters by using any of the representations of character ranges described above. \index{Character sets} To specify more complicated sets, you can write \index{Expressions}\index{Set expressions}expressions using conventional set theoretic operations. In AnaGram input, these operations are specified as follows: \index{Union}\index{Difference}\index{Intersection}\index{Complement} \begin{indenting}{0.4in} \begin{tabular}{cl} \agcode{A + B}&(union)\\ \agcode{A - B}&(difference)\\ \agcode{A \& B}&(intersection)\\ \agcode{\~{}A}&(complement)\\ \end{tabular} \end{indenting} where \agcode{A} and \agcode{B} are arbitrary sets. Union and difference have the same precedence. Intersection has higher precedence and complement has the highest precedence. Thus in the expression \begin{indentingcode}{0.4in} A + \~{}B\&C \end{indentingcode} the complement operation is performed first, then the intersection, and finally the union. Watch out! In an AnaGram syntax file \agcode{65 + 97} represents the character set which consists of lower case \agcode{a} and upper case \agcode{A}. It does not represent 162, the sum of 65 and 97. Parentheses may be used to force the order of evaluation: \begin{indentingcode}{0.4in} \~{}(A \& (B+C)) \end{indentingcode} In this example the union of \agcode{B} and \agcode{C} is calculated, then the intersection of this set with \agcode{A} is calculated, and finally the complement is evaluated. The computation of the \index{Complement}complement of a \index{Character sets}set requires a definition of the \index{Universe}universe of set elements. AnaGram will define the universe to be the set of unsigned 8-bit characters, unless one or more characters outside that range have been specified. In that case, the universe will consist of all characters on the interval defined by the lesser of zero and the lowest character code used and the greater of 255 and the highest character code used. The complement of a character set is everything in this universe except the characters in the set. Characters which make up part of the character universe, but are not legitimate input according to your grammar, are lumped together into a special token which will cause an error if it occurs in your input. When your parser reads an input character, it uses that character to index a conversion table in order to determine the appropriate \index{Token number}\index{Token}\index{Number}token number. If the \index{Range}\index{Test range}\index{Configuration switches} \agparam{test range} configuration switch is on, its default setting, your parser will include code to verify that the character is in bounds before it indexes the conversion table. If you are satisfied that checking bounds is unnecessary, you may turn the \agparam{test range} switch off and get a slightly higher level of performance from your parser. For efficient processing, it is well to keep the number of tokens to a minimum. Therefore if you have a choice between defining a construct as a token, with a production, or a set, with a definition, the set is to be preferred. Some useful character sets are: \begin{indenting}{0.4in} \begin{tabular}{ll} \agcode{'a-z' + 'A-Z'}&Alphabetic characters\\ \agcode{'a-f' + 'A-F'}&Hex digits\\ \agcode{'0-9'}&Decimal digits\\ \agcode{0..127}&ASCII character set\\ \agcode{32..126}&Printing ASCII characters\\ \agcode{\~{}'{\bs}n'}&Anything but newline\\ \agcode{\^{}Z}&Windows/DOS end of file indicator\\ \agcode{-1}&Stream I/O end of file indicator\\ \agcode{0}&String terminator\\ \agcode{32..126 - 'a-z' - 'A-Z' - '0-9'}&Punctuation\\ \end{tabular} \end{indenting} \bigskip % XXX ``punctuation'' is wrong; it should subtract off space too Note that \agcode{'a-z'} is a range of characters but \agcode{32..126 - 'a-z'} is a set difference. When AnaGram encounters a character set in a grammar rule, it assigns a token number to the character set. If it has previously seen the same character set it will assign the same token number; however, it assigns the same token number only if the set expressions are obviously the same. Thus, AnaGram will assign the same token number every time it sees \agcode{A + B}, but will assign a different token number if it sees \agcode{B + A}. Only when AnaGram has finished scanning the entire syntax file can it actually evaluate the character sets. If it finds that several different tokens all refer to the same character set, it will create a single token that represents the true character set and create \index{Shell productions}\index{Production}``shell productions'' for the others. \index{Character sets}If the character sets you use in your grammar overlap, they do not properly represent \index{Terminal token}\index{Token}terminal tokens. To deal with this situation, AnaGram identifies all overlaps among character sets and extends your grammar by adding a number of extra productions. For instance, suppose your grammar uses the following character sets as though they were terminal tokens: \begin{indentingcode}{0.4in} 'a-z' + 'A-Z' '0-9' '0-7' 'a-f' + 'A-F' \end{indentingcode} AnaGram will then modify your grammar by adding the following productions: \begin{indentingcode}{0.4in} 'a-z' + 'A-Z' -> 'a-f' + 'A-F' | 'g-z' + 'G-Z' '0-9' -> '0-7' + '8-9' \end{indentingcode} Although the tokens \agcode{'a-z' + 'A-Z'} and \agcode{'0-9'} are technically now \index{Nonterminal token}\index{Token}nonterminal tokens, for purposes of determining the \index{Token}\index{Data type}data type of their \index{Semantic value}\index{token}\index{Value}semantic values, AnaGram continues to regard them as terminal tokens. This \index{Partition}\index{Universe}\index{Character universe} ``partitioning'' of the character universe is described in Chapter 6. \subsection{Keyword Strings} \index{Keywords} In your grammar, AnaGram recognizes character strings within double quotes (e.g., \agcode{"IF"}) as keywords. The strings follow the same syntactic rules as strings in C. The same escape sequences are honored. AnaGram does not, however, allow for the concatenation of adjacent strings. Note that AnaGram strings are used only for the definition of keywords in your grammar, not for messages to be displayed or printed. Keyword strings may not include null characters and must be at least one character long. You may have any number of keywords. Each is treated as a single terminal token. A keyword may be given a name by means of a definition statement. Keywords may appear in virtual productions. AnaGram's keyword recognition works in the following way. First, for each state in your parser, AnaGram prepares a list of all the keywords that are admissible in that state. Your parser will recognize a keyword \emph{only} if it is in an appropriate state; otherwise it will appear to be an anonymous sequence of characters. Your parser, in any state, checks for keywords it expects before it checks for acceptable characters. That is, \emph{keywords take precedence} over simple characters. It does not look for keywords that would not be acceptable input. The parser will do whatever lookahead is necessary in order to pick up the entire keyword. Thus if the character \agcode{I} and the keyword \agcode{IF} are both legitimate input at some point, \agcode{IF} will be recognized, if present, in preference to \agcode{I}. If several admissible keywords match the input, such as \agcode{IF} and \agcode{IFF}, the parser will select the longest match, \agcode{IFF} in this example. AnaGram does not incorporate keywords into its character sets. Keywords stand apart and should not appear in definitions of character sets. In particular, they are not considered as belonging to the complement of a character set. Thus for the production \begin{indentingcode}{0.4in} next char -> \~{}('{\bs}n' + \^{}Z) \end{indentingcode} a keyword would not be considered legitimate input. Note also that a keyword consisting of a single character does not belong to the character universe. Because of this fact, AnaGram's treatment of \agcode{'X'} and \agcode{"X"} is very different. If this seems confusing at first, try using only keywords which are at least two characters long until you have some experience with them. AnaGram's keyword recognition logic normally does not make any assumptions about what precedes or follows a keyword. Thus if \agcode{int} is a keyword, your parser will be capable of plucking it out of a string of characters such as \agcode{disintegrate} if, according to your grammar, it could follow \agcode{dis}. The \agparam{sticky} declaration and the \agparam{distinguish keywords} statement, described below, can prevent such unwanted recognition of keywords. A keyword following a \agparam{sticky} token will not be recognized if the first character of the keyword can be shifted in as part of the \agparam{sticky} token. The \agparam{distinguish keywords} statement prevents recognition of a keyword if it is followed immediately by a character of the sort that makes up the keyword. \subsection{Type Specifications For Tokens} \index{Token}\index{Token type}\index{Type declarations} When you write productions or token declarations (see below), AnaGram allows you to specify the data type\index{Token}\index{Data type} of the \index{Semantic value}\index{Token}\index{Value}semantic value of a token by using a C or C++ data type specification. The restrictions are that AnaGram does not allow specification of array or function types, nor explicit structure types. Types that are defined with typedef statements, structure definitions, or class definitions, including template classes, in your embedded C or C++ are acceptable. Thus the following specifications, for example, are acceptable: \begin{indentingcode}{0.4in} void int char * unsigned long *near static float *far my{\us}type double * struct descriptor struct widget * vector <double> * \end{indentingcode} On the other hand, the following specifications are \emph{not} valid: \begin{indentingcode}{0.4in} int[20] int *(int, unsigned char) \bra int x,y; float z; \ket struct \bra int k; float z; \ket \end{indentingcode} Note that AnaGram itself does nothing with the type specifications. It simply passes them on to your compiler as appropriate. \subsection{Productions} \index{Production} Productions are the basic units of a grammar. A production consists of a left side and a right side. \index{Left side}The left side of a production consists of one or more token names, joined by commas, optionally preceded by a type specification enclosed in parentheses. \index{Right side}The right side begins with an arrow and may either begin on the same line as the left side or on a new line. For example: \begin{indentingcode}{0.4in} program -> statement list, eof expression -> expression, plus, term (int) variable name, function name -> name:n = look{\us}up(n); \end{indentingcode} The part of the right side of a production following the arrow is called a \index{Grammar rule}\index{Rule}\agterm{grammar rule}, discussed below. A production need not have a right side at all. In this case, it is simply called a \index{Declaration}\index{Token}\agterm{token declaration}. AnaGram assigns \index{Token number}\index{Token}\index{Number}token numbers to the token names on the left side, and, if there is a type specification, records the data type for each of the tokens declared. Declarations of this sort are most useful when using input from a \index{Lexical scanner}lexical scanner. See Chapter 9 for a discussion of techniques for interfacing a lexical scanner to your parser. If you do not intend to use a lexical scanner you will have no need for token declarations. If you do not explicitly specify the type for the \index{Semantic value}\index{Token}\index{Value}semantic value of a token, it will be determined by the configuration parameter \index{Default token type}\index{Configuration parameters}\index{Token} \agparam{default token type} if it is a \index{Nonterminal token}\index{Token}nonterminal token or by the \index{Configuration parameters}configuration parameter \index{Input token type}\index{Default input type}\agparam{default input type} if it is a \index{Token}terminal token. \agparam{Default token type} defaults to \agcode{void}. \agparam{Default input type} defaults to \agcode{int}. If a production has more than one token on the left side, as in the third example above, it is called a \index{Semantically determined production}\index{Production} \agterm{semantically determined production}. Semantically determined productions are a useful tool for exerting semantic control over syntactic analysis. A semantically determined production should have a reduction procedure which determines on a case by case basis which of the tokens on the left side should be taken as the reduction token. If there is no reduction procedure, or if the reduction procedure does not make a choice, the reduction token will be the first syntactically correct token on the left side of the production. In the example above, \agcode{variable name} will be the reduction token unless \agcode{look{\us}up} changes it to \agcode{function name}. Semantically determined productions are discussed more fully in Chapter 9. If several productions have the same left side, it does not need to be repeated. Subsequent right hand sides must each start on a new line. For example: \begin{indentingcode}{0.4in} integer -> digit -> integer, digit name -> letter -> name, letter -> name, digit \end{indentingcode} On the other hand, you do not have to group productions with the same left side. You could write the above productions as follows, although it would certainly not be good programming practice: \begin{indentingcode}{0.4in} name -> name, digit integer -> integer, digit name -> name, letter integer -> digit name -> letter \end{indentingcode} Nevertheless, there are a few occasions involving complex cross recursions and semantically determined productions where it is not possible to group productions neatly. The right side of a production can be empty. Such a production is called a \index{Null productions}\index{Production}\agterm{null production}. Null productions are useful to denote an optional element in a grammar, or a list that may be empty. For example: \begin{indentingcode}{0.4in} optional widget -> -> widget optional qualifiers -> -> optional qualifiers, qualifier \end{indentingcode} A second way to write multiple productions with the same left side uses the \index{Vertical bar}\index{|}vertical bar character, ``$|$'', to separate the grammar rules. The productions given above for \agcode{name}, \agcode{optional widget}, and \agcode{optional qualifiers} can also be written: \begin{indentingcode}{0.4in} name -> letter | name, letter | name, digit optional widget -> | widget optional qualifiers -> | optional qualifiers, qualifier \end{indentingcode} Note that a null production cannot \emph{follow} a vertical bar. A token that has a null production is called a \index{Zero length token}\index{Token}\agterm{zero length token}, since it can be represented by an empty sequence of input characters, that is to say, by nothing at all. Furthermore, even if a token doesn't have any null productions, if it has at least one rule consisting entirely of zero length tokens it is also a zero length token. In the Token Table window, AnaGram notes which tokens are zero length, because they can be a source of conflicts. \subsection{Grammar Token} Every grammar must have a single token which produces the entire grammar. This token is variously called the \index{Token}\index{Grammar token}\agterm{grammar token}, the \index{Goal token}\agterm{goal token} or the \index{Start token}\agterm{start token}. AnaGram provides several methods you may use to specify which token in your grammar is the grammar token. You may simply use the name \agcode{grammar} for the grammar token. If you wish to use some other more descriptive name for your grammar token, you may mark it with a following dollar sign when it appears on the left side of a production. Alternatively, you may set the \index{Grammar token}\index{Configuration parameters}\agparam{grammar token} configuration parameter to specify the grammar token. Here are examples of the methods: \begin{indentingcode}{0.4in} grammar -> [statement | newline]/... program \$ -> [statement | newline]/... {}[ grammar token = program ] program -> [statement | newline]/... \end{indentingcode} If you should use more than one of these techniques, AnaGram resolves the issue in the following manner: A marked token or a configuration parameter setting always takes precedence over simply naming a token \agcode{grammar}. If you mark more than one token or set the configuration parameter more than once, the last setting or mark wins. \subsection{Grammar Rules} \index{Rule}\index{Grammar rule} The part of a production to the right of the arrow is more often called a \agterm{grammar rule}, or simply \agterm{rule}. A grammar rule is a sequence of \index{Rule elements}\agterm{rule elements}, joined by commas, as in the examples of productions given above. Rule elements are token names, character set expressions, virtual productions, or immediate actions (see below). Each rule element may be optionally followed by a parameter assignment. The entire rule may be followed by an optional reduction procedure. A \index{Parameter assignment}parameter assignment is a colon followed by a C variable name. Here are some examples of rule elements with parameter assignments: \begin{indentingcode}{0.4in} '0-9':d integer:n expression:x declaration:declaration{\us}descriptor \end{indentingcode} The parameters you assign to tokens in your grammar rule become the formal parameters for your \index{Reduction procedure}reduction procedure. The data type\index{Data type}\index{Reduction procedure arguments} of the parameter is determined by the data type for the semantic value of the token to which it is assigned. If your grammar rule has parameter assignments, but does not have a reduction procedure, AnaGram will give you a warning in case the lack of a reduction procedure is an oversight. If you don't need a reduction procedure you may safely ignore the warning. On the other hand, AnaGram has no way to determine whether you have failed to make necessary parameter assignments. You won't find out until you compile your parser, when your compiler will give you error messages for undefined symbols. AnaGram assigns a unique rule number to each rule in your grammar. Rules are numbered sequentially as they are encountered in the syntax file. AnaGram constructs rule zero itself. Rule zero normally has a single element, the grammar token, unless you have a \agparam{disregard} statement in your grammar. In this case there will be two elements. \subsection{Reduction Procedures} \index{Reduction procedure} % XXX somewhere in here it ought to say something like % ``in the parsing literature reduction procedures are often known as % \agterm{semantic actions}.'' % Note that R. says there's some subtle difference between the usual % concept of semantic action and AG's concept of reduction procedure. % I don't know what this difference is and I hope she can recall it. % % D. thinks this note ought to be at the end; R. wants it at the top. A \agterm{reduction procedure} is a piece of C code which optionally follows a production. The code is executed when your parser identifies the production in its input. There are two forms for reduction procedures, a short form and a long form. The short form consists of a single C expression. The long form consists of an arbitrary block of C code. When AnaGram builds a parser, it inspects the grammar rule to which the procedure is attached and identifies the parameters for the procedure. It uses these parameters as the formal parameters for the procedure. If the \index{Macros}\index{Allow macros}\index{Configuration switches} \agparam{allow macros} configuration switch has not been turned off, AnaGram codes the reduction procedure as a macro definition whenever possible. Otherwise AnaGram codes it as a function definition. AnaGram builds the name for a reduction procedure by appending its internal procedure number to the string \agcode{ag{\us}rp{\us}}. Thus reduction procedures are numbered in the order in which they are encountered in the syntax file. Both long and short form reduction procedures are preceded by an equal sign which follows the production. The short form consists of a C or C++ expression terminated by a semicolon. When the grammar rule is reduced, the expression will be evaluated and its value will become the value of the reduction token. The expression and the terminating semicolon must be entirely on a single line. Note that, if you really need to make the expression longer than will fit on one line, you can embed a newline in a comment. Some examples of short form reduction procedures are: % XXX is there anything we can do about the ugly underscores? \begin{indentingcode}{0.4in} =0; =1; =10*n + d-'0'; = special{\us}processor(first{\us}parameter, second{\us}parameter); =word{\us}count++; =widget(constant{\us}1*parameter{\us}1 + constant{\us}2*parameter{\us}2 /* {} */ + constant{\us}3*parameter{\us}3); \end{indentingcode} A long form reduction procedure consists of an arbitrary block of C or C++ code, enclosed in braces (\bra \ket). AnaGram will code the reduction procedure as a function. To return a value for the reduction token, simply use the \agcode{return} statement. There are effectively no restrictions on the content or length of a reduction procedure. Of course, if there are unbalanced braces, unterminated comments or unterminated string literals, AnaGram will not be able to determine where the reduction procedure ends. AnaGram treats \index{Comments}nested comments within a reduction procedure according to the value of the \index{Nest comments}\index{Configuration switches}\agparam{nest comments} configuration switch at the point where it encounters the reduction procedure. From a practical point of view it is not usually good practice to have a reduction procedure that is more than a few lines long since a long procedure will hamper your overall view of your grammar. Long reduction procedures should be written as separate named functions, and should either be included in the embedded C portion of your syntax file or should be included in a wholly separate module. Here is an example of a long form reduction procedure: \begin{indentingcode}{0.4in} =\bra if (flag) \bra total += x; return identify(x); \ket else \bra total = 0; flag = 1; return init{\us}table(x); \ket \ket \end{indentingcode} If a rule does not have a reduction procedure, the semantic value of the reduction token will be set to the \index{Semantic value}\index{Token}\index{Value}semantic value of the first token in the rule, unless the rule is a \index{Null productions}null production. In the latter case, the value of the reduction token will be set to zero. % XXX and what if zero isn't a valid value for the type? a compiler % error will occur. % XXX add something like % % Variables appearing in reduction procedures which do not have a % parameter assignment in the corresponding grammar rule can be % declared globally or (file)-statically in your embedded C, or % alternatively could be added to the parser control block using % the \agparam{extend pcb} statement (q.v. | See Section ....). % (Reword this.) % % Should also discuss the sequencing of reduction procedure calls % so that people understand what happens if you use such variables. % % also ``A reduction procedure can be used to terminate parsing for % semantic reasons''. % \subsection{Immediate Actions} \index{Immediate action}\index{Action} An immediate action is a rule element that consists of executable C or C++ code embedded within a grammar rule to be executed when it is encountered. An immediate action is denoted by the use of an exclamation point, \index{!}``!''. The content of an immediate action may be written following the rules for either long form or short form reduction procedures. As with any other rule element, it must be separated from preceding and following rule elements by commas. In the grammar for a simple desk calculator, one might write \begin{indentingcode}{0.4in} transaction -> !printf('\#');, expression:x = printf("\%d{\bs}n", x); \end{indentingcode} % XXX s/apparent/visible/ Notice that the only apparent difference between an immediate action and a reduction procedure is that the immediate action is preceded by ``!'' instead of ``=''. The immediate action must be followed by a comma to separate it from the following rule element. Immediate actions may also be used in definitions: \begin{indentingcode}{0.4in} prompt = !printf('\#'); \end{indentingcode} AnaGram implements an immediate action by creating a special token for it. AnaGram then creates a single null production for the token. Finally, the immediate action is implemented as the reduction procedure for the null production. For example, you could implement \agcode{prompt} by writing a null production with a reduction procedure: \begin{indentingcode}{0.4in} prompt -> = printf('\#'); \end{indentingcode} This production would be equivalent to the definition above. There are two ways, however, in which immediate actions differ from the equivalent null production. Immediate actions may access any parameter assignments which precede them in the rule in which they occur. On the other hand, there is no way to assign a data type to the semantic value, if any, returned by the immediate action. Therefore, the type is determined by your setting of the \index{Default token type}\index{Configuration parameters} \agparam{default token type} configuration parameter. \subsection{Virtual Productions} \index{Virtual productions}\index{Production} Virtual productions are a convenient short form notation for common grammatical constructs involving choice and repetition. The notation represents an extension of notation commonly used in programming manuals. A virtual production may be written in a grammar rule at any place where you could write a token name, even within another virtual production. Note that use of virtual productions is never \emph{required}, since the equivalent productions can always be written out explicitly instead. When AnaGram encounters a virtual production, it replaces the virtual production with a new token and writes appropriate productions for the new token. When you look at your syntax tables using AnaGram windows, you will see the productions that AnaGram generates. AnaGram keeps a record of virtual productions, so that generally if you use the same virtual production a second time, you get the same set of tokens and productions that were generated the first time it was used. This is not the case if the virtual productions contain reduction procedures or immediate actions, since AnaGram is not equipped to determine whether two pieces of C code are equivalent. Thus, a virtual production that contains a reduction procedure will be unique and will not be reused. One disadvantage of virtual productions is that there is no way to specify the data type of the \index{Semantic value}\index{Virtual production}semantic value of a virtual production. Therefore, if you have a reduction procedure within a virtual production, its return value must be consistent with the type defined by the \index{Default token type}\index{Configuration parameters}\agparam{default token type} configuration parameter. The simplest virtual production is the \index{Token}\index{Optional token}\agterm{optional token}. If \agcode{x} is an arbitrary token name or set expression, you can indicate an optional \agcode{x} by writing \index{?}\agcode{x?}. You may also indicate a repetition of \agcode{x} by using the ellipsis with either \agcode{x} or \agcode{x?}. \index{...}\index{Ellipsis}Thus \agcode{x...} represents one or more instances of \agcode{x} and \index{?...}\agcode{x?...} represents zero or more instances of \agcode{x}. For example: \begin{indentingcode}{0.4in} '+'? \end{indentingcode} can be used to represent an optional plus sign, that is, a choice between a plus sign and nothing at all. Similarly, \begin{indentingcode}{0.4in} '{\bs}n'?... \end{indentingcode} represents an optional sequence of newline characters. \index{Brackets}\index{Braces}\index{\_opb\_clb}\index{[]} The next category of virtual productions uses brackets or braces to indicate a choice among a number of enclosed grammar rules separated by vertical bars. A single rule may also be enclosed. Note that \emph{rules}, with following reduction procedures, are allowed, not simply tokens. Braces are used to indicate that one option must be chosen. Brackets are used to indicate the choice is optional, i.e. may be omitted altogether. The ellipsis following a set of options within brackets or braces indicates the option may be repeated an indefinite number of times. You can use braces to indicate a simple choice among a number of options. A Cobol grammar offers the following choice of equivalent keywords: \begin{indentingcode}{0.4in} \bra "RECORD", "IS"? | "RECORDS", "ARE"? \ket \end{indentingcode} \index{\_opb\_clb...}\index{ []...} You may use the ellipsis with braces to indicate an arbitrary positive number of repetitions of the choice: \begin{indentingcode}{0.4in} {\bra}type specifier | storage class specifier{\ket}... \end{indentingcode} This expression requires at least one type specifier or storage class specifier, but will accept any number. \index{[]} To make a choice optional, use brackets instead of braces. An example, again drawn from a Cobol grammar, is: \begin{indentingcode}{0.4in} {}["LIMIT", "IS"? | "LIMITS", "ARE"?] \end{indentingcode} \index{[]...} Ellipses may be used with brackets to indicate an arbitrary number of choices that may be omitted altogether: \begin{indentingcode}{0.4in} {}[argument, [',', argument]...] \end{indentingcode} This expression describes an optional argument list with arguments separated by commas. If you use a null production within braces, it must be the first option: \begin{indentingcode}{0.4in} \bra | '+' | '-' \ket \end{indentingcode} Normally, you would do this only if you wanted to attach a reduction procedure to the null production. Note that if you include a null production within braces, and add an ellipsis after the closing brace for repetition, your grammar will be ambiguous. Just exactly how many times does the null production occur? Use brackets instead, and omit the null production. Null productions are not allowed with brackets, since they would be intrinsically ambiguous. The options within braces or brackets may be grammar rules of any length or complexity and may themselves contain virtual productions of arbitrary complexity. Nevertheless, in practice, clarity suffers as soon as the options get very complex. Virtual productions are most important and useful when used in simple situations. In those situations they will enhance the clarity of your grammar. Here is an example that is moderately complex, even though each rule consists of a single token: \begin{indentingcode}{0.4in} \bra{\bra}"on" | "true"\ket = 1; | {\bra}"off" | "false"\ket = 0; | integer\ket \end{indentingcode} This example can be used to allow as input either an integer or, for special cases, keywords. You could write this option out in the following way: \begin{indentingcode}{0.4in} p1 -> p2 = 1; -> p3 = 0; -> integer p2 -> "on" -> "true" p3 -> "off" -> "false" \end{indentingcode} The final category of virtual production provides a notation for \index{Alternating sequence}\agterm{alternating sequences}. An alternating sequence is a set of choices which may be repeated arbitrarily subject to the side condition that no choice may follow itself, in other words, that the choices must alternate. Alternating sequences are written with either brackets or braces depending on whether the sequence is optional or not, followed by \index{/...}``\agcode{/...}''. Note that the choices themselves may allow sequences. For example: \begin{indentingcode}{0.4in} program -> [statement | newline...]/..., eof \end{indentingcode} represents a sequence of statements separated by one or more newlines. Any two statements must be separated by one or more newline characters, and newlines may also appear at the beginning and the end of the program. Null productions are not allowed within alternating sequences, since they are intrinsically ambiguous in all cases. \subsection{Definition Statements} \index{Definitions}\index{Definition statement}\index{Statement} A definition statement is simply a shorthand way of naming a character set, a \index{Virtual productions}\index{Production}virtual production, a keyword string, or an immediate action. It can also be used for providing an alternate name for a token. Definitions have the form: \begin{indentingcode}{0.4in} name = \codemeta{character set} name = \codemeta{virtual production} name = \codemeta{keyword} name = \codemeta{immediate action} name = \codemeta{token name} \end{indentingcode} The name may be any name acceptable to AnaGram. The name can then be used anywhere you might have used the expression on the right side. \index{!}For example: \begin{indentingcode}{0.4in} upper case letter = 'A-Z' lower case letter = 'a-z' letter = upper case letter + lower case letter statement list = statement?... while keyword = "WHILE" prompt = !printf("Please enter name:"); \end{indentingcode} It is important to recognize that a definition statement that names a set does not define a token. A token is defined only when the set is used in a grammar rule, and then only if the set is used directly, not in combination with some other set. Furthermore, if you use a character set directly in a grammar rule, and in some other rule you use a name that refers to the same set of characters, you will get two different tokens. For example, if you have defined \agcode{upper case letter} as in the above example and use both \agcode{upper case letter} and \agcode{'A-Z'} in grammar rules, AnaGram will assign different \index{Token number}\index{Token}\index{Number}token numbers to accommodate any differences in attributes you may assign to the tokens. Renaming tokens is a convenient way to connect two independently written portions of a grammar. % See the C grammar in the EXAMPLES directory of your distribution % disk for an example. \subsection{Embedded C} \index{Embedded C} You may encapsulate C or C++ code in your syntax file by enclosing it in braces (\bra \ket). Such pieces of code are copied to the parser file untouched, in the order they are found in the syntax file. There may be any number of such pieces of embedded C. The only restriction is that they must not start on the same line as some other AnaGram statement, and following AnaGram statements must also start on fresh lines. Normally, the blocks of embedded C in your syntax file are copied to the parser file \emph{following} a set of definitions and declarations AnaGram needs for the code it generates. However, if the \emph{first} statement in your \index{Syntax file}syntax file is a block of embedded C, it will \emph{precede} AnaGram's definitions and declarations. This block of embedded C is called the \index{Prologue}\index{C prologue}``C prologue''. There are two main reasons for this special treatment. First, you may want to have a title and \index{Copyright notice}copyright notice in your parser. If you include them in an initial block of embedded C they will be right at the beginning of both your syntax file and your parser file. Second, if some of your tokens have data type\index{Token}\index{Data type}s other than those predefined in C or C++, you may include the definitions here, so they will be available to the code AnaGram generates. AnaGram scans embedded C only insofar as is necessary to find the closing right brace. Therefore any braces used within embedded C must balance properly. AnaGram skips braces enclosed in character constants and string literals, as well as braces enclosed in comments. It also recognizes C++ style comments that begin with \agcode{//}. \index{Comments}Treatment of nested versus non-nested comments is controlled by the \index{Nest comments}\index{Configuration switches}\agparam{nest comments} configuration parameter. AnaGram will use the status of this parameter in effect at the beginning of the section of embedded C. AnaGram, of course, can be confused by unterminated strings, unbalanced brackets, and unterminated comments. The most likely outcome, in such a situation, is that AnaGram will encounter the end of file looking for the end of the embedded C. Should this happen, AnaGram will identify the beginning of the piece of embedded C which caused the problem. The code you include as embedded C, of course, has to coexist with the code AnaGram generates. In order to keep the potential for conflicts to a minimum, all variables and functions which AnaGram defines begin either with the name of your parser or with the letters \agcode{ag{\us}}. You should avoid variable names which begin with these letters. Reduction procedures are copied to the \index{Parser file}\index{File}parser file in the order in which they are defined \emph{following} all of the embedded C. Thus your reduction procedures may freely use variables and macros defined anywhere in your embedded C. \subsection{Configuration Sections} \index{Configuration section} A configuration section is a special section of your syntax file enclosed in brackets. Within a configuration section you may set the values of configuration parameters or switches, or you may use one or more of several available attribute statements to specify special treatment for certain tokens. There can be as many or as few configuration sections in your syntax file as you wish. Each configuration section must begin on a new line. Any AnaGram statement which follows a configuration section must also begin on a new line. Within a configuration section, each parameter setting and each attribute statement must begin on a new line. The rules for using comments and continuation lines are the same as for the rest of AnaGram. Configuration parameters control the way AnaGram interprets your syntax file and the way it builds your parser. A full discussion of the use of configuration parameters, including a complete discussion of each parameter and its default value, is given in Appendix A. \index{Attribute statements}\index{Statement} Attribute statements comprise the \index{Precedence declarations}precedence declarations \agparam{left}, \agparam{right}, and \agparam{nonassoc}; the \agparam{sticky} declaration; the \agparam{distinguish keywords} statement; the \agparam{hidden} declaration; the \agparam{disregard} and \agparam{lexeme} statements; the \agparam{enum} statement; the \index{Reserve keywords}\agparam{reserve keywords} declaration; and the \index{Rename macro}\agparam{rename macro} statement. The precedence declarations and the \index{Sticky declaration}\index{Declaration}\agparam{sticky} declaration may be used to resolve conflicts in your grammar. The \agparam{distinguish keywords} statement may be used to control keyword recognition. The \index{Hidden declaration}\index{Declaration}\agparam{hidden} declaration causes certain token names not to be used when your parser produces \index{Syntax error}\index{Errors}\index{Error messages}syntax error messages. You may use the \agparam{disregard} and \agparam{lexeme} statements to cause your parser to skip automatically over certain tokens in its input. The \agparam{enum} statement is almost identical to the enum statement in C. It can be used to assign names to input codes in grammars which are taking input from a \index{Lexical scanner}lexical scanner or another parser. The \index{Reserve keywords}\agparam{reserve keywords} declaration allows you to specify certain keywords as reserved words. The \index{Rename macro}\agparam{rename macro} statement allows you to override the names AnaGram uses for various macro definitions it creates in the code it generates. Attribute statements are discussed below. Except for \agparam{disregard} and \agparam{rename macro} statements, attribute statements accept lists of operands enclosed in braces (\bra \ket) and separated by commas. A dangling comma following the last item in a list will be ignored. \subsection{Setting Configuration Parameters} \index{Configuration parameters}\index{Parameters} Each configuration parameter has a name that follows the AnaGram conventions for symbol names, except that AnaGram ignores case\index{Case sensitivity} when looking up configuration parameter names. There are a number of varieties of configuration parameters. The simplest, \index{Configuration switches}\index{Switches}configuration switches, simply turn some feature of AnaGram on or off. These parameters need simply be stated to turn the feature on, or negated with the tilde (\agcode{\~{}}) to turn the feature off: \begin{indentingcode}{0.4in} nest comments \end{indentingcode} causes AnaGram to allow nested comments, and \begin{indentingcode}{0.4in} \~{}nest comments \end{indentingcode} causes AnaGram to disallow nested comments. You may also set or reset configuration switches with explicit on or off values: \begin{indentingcode}{0.4in} nest comments = on nest comments = off \end{indentingcode} The remaining configuration parameters are assigned values using a simple assignment statement. Depending on the parameter, the value it takes may be the name of a token, a C variable name, a C or C++ data type, a string constant or an integer. String constants are written using the same rules as keyword strings, described above. \begin{indentingcode}{0.4in} grammar token = program parser name = widget default token type = void * header file name = "widget.h" parser stack size = 50 \end{indentingcode} A number of string-valued \index{Configuration parameters}configuration parameters are used to determine file names and variable names. In these parameters, the \index{\#}``\#'', \index{\_dol}``\$'', and ``\index{ \_prc}\%'' characters are used as wild cards. In file name specifications and the specification of the name of your parser, ``\#'' will be replaced by the name of your syntax file. In other function and variable names AnaGram creates while building your parser, ``\$'' will be replaced by the name of your parser. When building enumeration constants for the names of the tokens in your grammar, ``\%'' will be replaced by the name of the token. Note that when entering a Windows/DOS path name as a value for a file name parameter you must quote any backslashes in the path name. For example, \begin{indentingcode}{0.4in} coverage file name = "f:{\bs\bs}sna{\bs\bs}foo.nrc" \end{indentingcode} \subsection{Precedence Declarations} \index{Precedence declarations} AnaGram allows you to resolve shift-reduce conflicts by assigning precedence levels to operators. There are three precedence declarations available, beginning with the keywords \index{Left}\agparam{left}, \index{Right}\agparam{right}, and \index{Nonassoc}\agparam{nonassoc} respectively. Each such declaration consists of the appropriate keyword and a list of tokens enclosed in braces (\bra \ket). All the tokens in the list have the same precedence, higher than tokens in any previous declaration and lower than in any subsequent declaration. If the keyword is \agparam{left}, the tokens will group to the left. If it is \agparam{right}, they will group to the right. If it is \agparam{nonassoc} (for non-associative) no grouping will be assumed. Precedence declarations must be included in a configuration section. Here are precedence declarations appropriate to a simple desk calculator program: \begin{indentingcode}{0.4in} {}[ left \bra '+', '-' \ket left \bra star, '/', '\%' \ket right \bra unary minus \ket ] unary minus = '-' \end{indentingcode} Note that \agcode{unary minus} and \agcode{'-'} can have different precedence. Precedence declarations are one of the few instances in AnaGram where the \index{Statements}\index{Order of statements}order of statements is significant. The use of precedence declarations is discussed in Chapter 9. \subsection{``Sticky'' Declarations} \index{Sticky declaration}\index{Declaration} AnaGram provides another means for resolving shift-reduce conflicts. You may characterize any token as ``sticky''. Then, in the case of a \index{Shift-reduce conflict}\index{Conflicts}shift-reduce conflict where a ``sticky'' token is the last token in the input buffer, the conflict will be resolved by selecting the shift operation. Intuitively, you may think of this as though the ``sticky'' token adheres to and draws in any subsequent input that it can. ``Sticky'' declarations are included in configuration sections. They begin with the keyword \agcode{sticky} followed by a list of tokens, separated by commas inside braces (\bra \ket). Suppose, for instance, you wished to pick up a line of text, skipping any leading space or tab characters. You might write the following syntax: \begin{indentingcode}{0.4in} white space = ' ' + '{\bs}t' text char -> \~{}'{\bs}n':c = do{\us}something(c); line -> leading white space, text char?..., '{\bs}n' leading white space -> -> leading white space, white space \end{indentingcode} Unfortunately, this syntax is ambiguous, since space and tab are legitimate instances of both leading white space and text char. What you really want to do is to skip white space until you find a non-blank character and then you want to accept all characters to the end of the line. There are two ways to address the problem. The first is to define a special token for the first non-blank character and, using it, to write an unambiguous grammar. This approach, while laudable, is tedious and prolix. Instead, use \agparam{sticky} to resolve the problem: \begin{indentingcode}{0.4in} {}[ sticky \bra leading white space \ket ] \end{indentingcode} Now when AnaGram analyzes your grammar, and encounters the ambiguity, it will understand that a blank or tab that could be treated either as leading white space or the as the first text character should be treated as white space. Since \agcode{leading white space} is ``sticky'', any subsequent white space adheres to it. As with conflicts resolved with precedence levels, AnaGram lists all conflicts that it resolves using \agcode{sticky} in the \index{Resolved Conflicts}\index{Window}\agwindow{Resolved Conflicts Table}, so you can verify that the conflicts have been correctly resolved. An important use of sticky tokens is to inhibit the recognition of following \index{Keywords}keywords. Following a sticky token, a keyword, which, according to your grammar, would otherwise be legitimate input, will not be recognized if a shift action is possible for the first character of the keyword. For example, imagine that \agcode{name} has been defined in the conventional way, and there exists a production with name followed immediately by the keyword \agcode{int}. Then if, in your input, the word \agcode{print} were to occur, your grammar would parse it as a name, \agcode{pr}, followed by the keyword \agcode{int}. If you make \agcode{name} sticky, however, the first letter of \agcode{int} will be seen to be an acceptable character for \agcode{name} and the keyword will not be recognized. Your parser will then recognize the \agcode{name} as \agcode{print}. \subsection{Distinguish Keywords Statement} \index{Distinguish keywords}\index{Keywords} Distinguish keywords statements are occasionally needed to prevent keyword recognition. You may, for example, wish to prevent the recognition of the keyword \agcode{int} when it occurs embedded in a word such as \agcode{interval}. Of course, you need to do this only if both the keyword and the other word are both legitimate input at the same point in your grammar. A distinguish keywords statement can prevent recognition of a keyword which is embedded in another word provided at least one character of the other word follows the keyword. The distinguish keywords statement has the form: \begin{indentingcode}{0.4in} distinguish keywords \bra \codemeta{list of character sets} \ket \end{indentingcode} AnaGram compares all the characters in each keyword to the characters included in each character set in turn. If it finds that all the characters in a keyword are members of a particular set, it tells the keyword recognition logic to try to match the keyword only against the longest sequence of characters drawn from the specified set. In other words, in order for a keyword to be recognized, the keyword \emph{must} be followed by a character \emph{not} in the set. The set associated with a keyword is the first one in the list which contains all the characters found in the keyword. If you have more than one \agparam{distinguish keywords} statement in your grammar, the lists are tried in the order in which they appear in the grammar. The purpose of the \agparam{distinguish keywords} statement is to enable your parser to distinguish a keyword from the same sequence of characters embedded within another sequence. Thus suppose that \agcode{int} is a keyword, and, according to your grammar, could appear in the same place as the word \agcode{integral}. If you don't want it to be recognized as a keyword in these circumstances, you would write the following distinguish statement: \begin{indentingcode}{0.4in} distinguish keywords \bra 'a-z'+'A-Z' \ket \end{indentingcode} To also inhibit recognition of \agcode{int} within \agcode{print}, you would combine the use of the distinguish keywords statement with the \agparam{sticky} declaration. \subsection{``Hidden'' Declarations} \index{Hidden declaration}\index{Declaration} AnaGram provides an optional \index{Error diagnosis}error diagnosis feature for your parser (see Chapter 9). The \agparam{hidden} declaration allows you to identify tokens that you do not wish to be used in making up \index{Diagnostic messages}diagnostic messages. These tokens are tokens whose names would not mean anything to your users. The format of a ``hidden'' declaration is the same as that of precedence and ``sticky'' declarations. Within a configuration section, the keyword ``hidden'' is followed by a list of tokens. For example: \begin{indentingcode}{0.4in} {}[ hidden \bra comment head \ket ] comment -> comment head, "*/" comment head -> "/*" -> comment head, \~{}eof \end{indentingcode} This is an AnaGram representation of ANSI standard C comments (non-nested). In this example the token \agcode{comment head} exists only for convenience in writing the grammar and has no particular meaning to an end user. On the other hand, he knows what the word \agcode{comment} refers to. The ``hidden'' attribute will cause AnaGram's diagnostic builder, by backing up the stack until it finds a non-hidden token, to eschew \agcode{comment head} in favor of \agcode{comment}. % XXX eschew obfuscation. how about ``avoid''? \subsection{Disregard Statement} The purpose of the \index{Disregard statement}\index{Statement}\agparam{disregard} statement is to skip over uninteresting \index{White space}white space and comments in your input files. The disregard statement allows you to specify a token that should be passed over in the input to your parser. The statement takes the form: \begin{indentingcode}{0.4in} disregard ws \end{indentingcode} where \agcode{ws} is a token name or character set. Disregard statements may be placed in any configuration section. You may have more than one disregard statement in your grammar. If you do, AnaGram will create a shell production. For example, suppose you write: \begin{indentingcode}{0.4in} {}[ disregard alpha disregard beta ] \end{indentingcode} AnaGram will proceed as though you had written: \begin{indentingcode}{0.4in} gamma -> alpha | beta {}[ disregard gamma ] \end{indentingcode} It frequently happens that you wish your parser to disregard blanks or comments, except that white space within names, numbers, strings, and other elementary constructs is subject to special rules and thus should not be disregarded blindly. In this case, you can use the \agparam{lexeme} statement to declare these constructs off limits for the disregard statement. Within these constructs, the disregard statement will be inoperative and the admissibility of white space will be determined solely by the productions which define these constructs. Outside those productions which define lexemes, you should not generally use a token which is supposed to be disregarded. If you do, your grammar will have conflicts, since the token could satisfy both the explicit usage and the implicit rules set up by the disregard statement. Such conflicts, however, are resolved automatically in favor of your explicit use of the token. The conflicts will appear in the \agwindow{Resolved Conflicts} window. % XXX I'm not sure that's still true. In order to implement the disregard statement AnaGram will redefine some tokens in your grammar. For example, \agcode{+} may be redefined to consist of a simple plus sign followed by optional white space: \begin{indentingcode}{0.4in} '+' -> '+'\%, white space?... \end{indentingcode} The percent sign is used to indicate the original, simple plus sign without the optional white space attached. You will probably notice the percent sign appearing in some windows and traces. In earlier versions of AnaGram, the degree sign, ``\agcode{\degrees}'', was used rather than ``\agcode{\%}''. \subsection{Lexeme Statement} The ``lexeme'' \index{Statement}\index{Lexeme statement}statement is used to fine-tune the disregard statement. The lexeme statement takes the form: \begin{indentingcode}{0.4in} {}[ lexeme \bra \codemeta{nonterminal token list} \ket ] \end{indentingcode} where \textit{nonterminal token list} is a list of nonterminal tokens separated by commas. Lexeme statements may be placed in any configuration section, and there may be any number of them. When you specify that a token is to be disregarded, AnaGram rewrites your grammar so that the token will be passed over whenever it occurs at the beginning of a file or following a lexical unit, or \agterm{lexeme}. If you have no \agparam{lexeme} statement, then the lexemes in your grammar are just the terminal tokens. The \agparam{lexeme} statement allows you to specify that certain nonterminal tokens are also to be treated as lexemes. This means that the disregard token will be skipped following the lexeme, but not between the characters that constitute the lexeme. Lexemes correspond to the tokens that a lexical scanner, if you were using one, would commonly identify and pass to a parser as single tokens. You don't usually wish to disregard white space within these tokens. For example, in a grammar for a conventional programming language where blank characters are to be disregarded, you might include: \begin{indentingcode}{0.4in} {}[ lexeme \bra string, character constant, name, number \ket ] \end{indentingcode} since blank characters must not be overlooked within strings and character constants and should not be permitted within names or numbers. Normally, AnaGram considers the disregard token to be optional; however there are circumstances where treating the disregard token as optional would lead to conflicts: two successive names, or two successive numbers, for example. In this case, you would like to require that the lexemes be separated by instances of the disregard token. To do this, simply set the \index{Distinguish lexemes}\index{Configuration switches} \agparam{distinguish lexemes} configuration switch. When this switch is set, AnaGram will ensure that disregard tokens will be required in those situations where making them optional would lead to conflicts. White space may be used explicitly within definitions of lexeme tokens in your grammar if desired, without causing conflicts. Thus, if you wish to allow embedded space in variable names, you might write: \begin{indentingcode}{0.4in} {}[ disregard space lexeme \bra variable name \ket ] space = ' ' + '{\bs}t' letter = 'a-z' + 'A-Z' digit = '0-9' variable name -> letter -> variable name, letter + digit -> variable name, space..., letter + digit \end{indentingcode} \subsection{Enum Statement} \index{Enum statement}\index{Enumeration}\index{Token} The \agparam{enum} statement follows rules nearly identical to those for C and C++. This makes it possible to copy an enum statement from your syntax file to a program file written in either C or C++, without any need for editing. The only differences are that AnaGram makes no provision for blank lines within the enumeration list, nor does it accept a type name. The \agparam{enum} statement is equivalent to a corresponding set of definition statements. It is especially useful when a parser is accepting token input from another program, a \index{Lexical scanner}lexical scanner, for example. Using the enum statement you may conveniently define all the identification codes for the input tokens. Each entry in an enum statement may be either a name, or a name followed by an ``='' sign and a character representation. If there is a character representation the name is assigned the value of the specified character. Otherwise it is assigned a value one more than that assigned to the previous name. If the first name in the list is not given an explicit value, it will be given the value zero. For example: \begin{indentingcode}{0.4in} {}[ enum \bra eof, a,b,c, blank = '\ ', x, y \ket ] \end{indentingcode} is equivalent to the following definition statements \begin{indentingcode}{0.4in} eof = 0 a = 1 b = 2 c = 3 blank = '\ ' x = 33 y = 34 \end{indentingcode} \subsection{Subgrammar Declarations} \index{Subgrammar declaration}\index{Declaration} A \agparam{subgrammar} declaration can be a useful way to deal with conflicts in certain situations. It tells AnaGram to treat the tokens listed in the declaration as though they were each grammar tokens, each specifying a complete subgrammar in itself, and, in determining shift and reduction actions, to ignore the usage of the tokens in the larger grammar. In some cases it is perfectly reasonable to ignore usage. The most common example occurs when building a lexical scanner for a language such as C as in the example in Section 7.4.4. In this case, you can write a complete grammar for a C token with no difficulty. But if you try to extend it to a sequence of tokens, you get scores of conflicts. This situation arises because you specify that any C token can follow another, when in actual practice, an identifier, for example, cannot follow another identifier without some intervening space or punctuation. It is theoretically possible, but in practice quite awkward, to write a grammar for a sequence of tokens so that there are no conflicts. The subgrammar declaration provides a way around this problem by telling AnaGram that when it is looking for reducing tokens for any rule produced directly or indirectly by a subgrammar token, it should disregard the usage of the token and only consider usage internal to the definition of the subgrammar token, as though the subgrammar token were the start token of the grammar. The subgrammar declaration is made in a configuration section and consists of the keyword \agcode{subgrammar} followed by a list of one or more nonterminal token names, separated by commas and enclosed in braces (\bra \ket). For example: \begin{indentingcode}{0.4in} {}[ subgrammar \bra C token, word \ket ] \end{indentingcode} Since the subgrammar statement changes the way AnaGram determines reducing tokens, it should be used with caution. You should be sure that the conflicts you are eliminating are really inconsequential. \subsection{Reserve Keywords Declaration} \index{Reserve keywords}\index{Keywords}\index{Keyword anomalies} The \agparam{reserve keywords} declaration can be used to specify a list of keywords that are reserved and cannot be used except as explicitly specified in the grammar. This enables AnaGram to avoid issuing meaningless keyword anomaly diagnostics (see \S 7.5). AnaGram does not automatically presume that keywords are also reserved words, since in many grammars there is no need to specify reserved words. The reserve keywords declaration is made in a configuration section and consists of the words \agcode{reserve keywords} followed by a list of one or more keyword strings, separated by commas and enclosed in braces (\bra \ket). For example: \begin{indentingcode}{0.4in} {}[ reserve keywords \bra "int", "char", "float", "double" \ket ] \end{indentingcode} \subsection{Rename Macro Statement} \index{Rename macro}\index{Macros} AnaGram uses a number of macros in its generated code. It is possible, therefore, to run into naming collisions with other components of your program. The \agparam{rename macro} statement allows you to change the name AnaGram uses for a particular macro to avoid these problems. For example, the Windows NT operating system uses \agcode{CONTEXT} structures to perform various internal operations. If you use the context tracking option (see \S 9.5.4) your parser will have a macro called \agcode{CONTEXT}. To avoid the name collision, add the following statement to any configuration section in your grammar: \begin{indentingcode}{0.4in} rename macro CONTEXT AG{\us}CONTEXT \end{indentingcode} Then, simply use \agcode{AG{\us}CONTEXT} where you would otherwise have used \agcode{CONTEXT}.