yacc(pdf.php) - phpMan

YACC(1P)                   POSIX Programmer's Manual                  YACC(1P)

PROLOG
       This  manual  page is part of the POSIX Programmer's Manual.  The Linux
       implementation of this interface may differ (consult the  corresponding
       Linux  manual page for details of Linux behavior), or the interface may
       not be implemented on Linux.
NAME
       yacc - yet another compiler compiler (DEVELOPMENT)
SYNOPSIS
       yacc [-dltv][-b file_prefix][-p sym_prefix] grammar
DESCRIPTION
       The yacc utility shall read a description of a context-free grammar  in
       grammar and write C source code, conforming to the ISO C standard, to a
       code file, and optionally header information into a header file, in the
       current  directory. The C code shall define a function and related rou-
       tines and macros for an automaton that  executes  a  parsing  algorithm
       meeting the requirements in Algorithms .
       The  form  and  meaning  of  the  grammar are described in the EXTENDED
       DESCRIPTION section.
       The C source code and header file shall be produced in a form  suitable
       as input for the C compiler (see c99 ).
OPTIONS
       The  yacc  utility  shall  conform  to  the  Base Definitions volume of
       IEEE Std 1003.1-2001, Section 12.2, Utility Syntax Guidelines.
       The following options shall be supported:
       -b  file_prefix
              Use file_prefix instead of y as the prefix for all output  file-
              names.  The  code file y.tab.c, the header file y.tab.h (created
              when -d is specified), and the description file  y.output  (cre-
              ated  when  -v  is  specified),  shall be changed to file_prefix
              .tab.c, file_prefix .tab.h,  and  file_prefix  .output,  respec-
              tively.
       -d     Write the header file; by default only the code file is written.
              The #define statements associate the  token  codes  assigned  by
              yacc  with  the  user-declared  token  names. This allows source
              files other than y.tab.c to access the token codes.
       -l     Produce a code file that does not contain any #line  constructs.
              If  this  option  is  not present, it is unspecified whether the
              code file or header file contains #line directives. This  should
              only  be  used  after the grammar and the associated actions are
              fully debugged.
       -p  sym_prefix
              Use sym_prefix instead of yy as  the  prefix  for  all  external
              names  produced  by  yacc.  The names affected shall include the
              functions yyparse(), yylex(), and yyerror(), and  the  variables
              yylval,  yychar, and yydebug. (In the remainder of this section,
              the six symbols cited are referenced using their  default  names
              only  as  a  notational  convenience.)  Local  names may also be
              affected by the -p option; however,  the  -p  option  shall  not
              affect #define symbols generated by yacc.
       -t     Modify  conditional compilation directives to permit compilation
              of debugging code in the code file. Runtime debugging statements
              shall  always be contained in the code file, but by default con-
              ditional compilation directives prevent their compilation.
       -v     Write a file containing a description of the parser and a report
              of conflicts generated by ambiguities in the grammar.

OPERANDS
       The following operand is required:
       grammar
              A  pathname  of a file containing instructions, hereafter called
              grammar, for which a parser is to be created. The format for the
              grammar is described in the EXTENDED DESCRIPTION section.

STDIN
       Not used.
INPUT FILES
       The  file  grammar  shall  be a text file formatted as specified in the
       EXTENDED DESCRIPTION section.
ENVIRONMENT VARIABLES
       The following environment variables shall affect the execution of yacc:
       LANG   Provide a default value for the  internationalization  variables
              that  are  unset  or  null.  (See the Base Definitions volume of
              IEEE Std 1003.1-2001, Section  8.2,  Internationalization  Vari-
              ables  for the precedence of internationalization variables used
              to determine the values of locale categories.)
       LC_ALL If set to a non-empty string value, override the values  of  all
              the other internationalization variables.
       LC_CTYPE
              Determine  the  locale  for  the  interpretation of sequences of
              bytes of text data as characters (for  example,  single-byte  as
              opposed to multi-byte characters in arguments and input files).
       LC_MESSAGES
              Determine  the  locale  that should be used to affect the format
              and contents of diagnostic messages written to standard error.
       NLSPATH
              Determine the location of message catalogs for the processing of
              LC_MESSAGES .

       The LANG and LC_* variables affect the execution of the yacc utility as
       stated. The main() function defined in Yacc Library shall call:

              setlocale(LC_ALL, "")
       and thus the program generated by yacc shall also be  affected  by  the
       contents of these variables at runtime.
ASYNCHRONOUS EVENTS
       Default.
STDOUT
       Not used.
STDERR
       If  shift/reduce  or  reduce/reduce  conflicts are detected in grammar,
       yacc shall write a report of those conflicts to the standard  error  in
       an unspecified format.
       Standard error shall also be used for diagnostic messages.
OUTPUT FILES
       The  code file, the header file, and the description file shall be text
       files. All are described in the following sections.
   Code File
       This file shall contain the C source code for the  yyparse()  function.
       It  shall contain code for the various semantic actions with macro sub-
       stitution performed on them as described in  the  EXTENDED  DESCRIPTION
       section.  It also shall contain a copy of the #define statements in the
       header file. If a %union  declaration  is  used,  the  declaration  for
       YYSTYPE shall also be included in this file.
   Header File
       The  header  file  shall  contain #define statements that associate the
       token numbers with the token names. This allows source files other than
       the  code  file  to  access the token codes. If a %union declaration is
       used, the declaration for YYSTYPE and an extern YYSTYPE yylval declara-
       tion shall also be included in this file.
   Description File
       The  description  file shall be a text file containing a description of
       the state machine corresponding to the  parser,  using  an  unspecified
       format.  Limits  for  internal  tables  (see  Limits  )  shall  also be
       reported, in an implementation-defined  manner.  (Some  implementations
       may use dynamic allocation techniques and have no specific limit values
       to report.)
EXTENDED DESCRIPTION
       The yacc command accepts a language that is used to  define  a  grammar
       for  a target language to be parsed by the tables and code generated by
       yacc. The language accepted by yacc as a grammar for  the  target  lan-
       guage is described below using the yacc input language itself.
       The  input grammar includes rules describing the input structure of the
       target language and code to be invoked when these rules are  recognized
       to  provide  the  associated  semantic  action. The code to be executed
       shall appear as bodies of text that are intended to be C-language code.
       The  C-language inclusions are presumed to form a correct function when
       processed by yacc into its output files. The code included in this  way
       shall be executed during the recognition of the target language.
       Given  a grammar, the yacc utility generates the files described in the
       OUTPUT FILES section. The code file can be compiled  and  linked  using
       c99.  If  the declaration and programs sections of the grammar file did
       not include definitions of main(), yylex(), and yyerror(), the compiled
       output  requires  linking  with  externally  supplied versions of those
       functions. Default versions of main() and yyerror() are supplied in the
       yacc  library  and  can  be linked in by using the -l y operand to c99.
       The yacc library interfaces need not support interfaces with other than
       the default yy symbol prefix. The application provides the lexical ana-
       lyzer function, yylex(); the lex utility is  specifically  designed  to
       generate such a routine.
   Input Language
       The  application shall ensure that every specification file consists of
       three sections in order: declarations,  grammar  rules,  and  programs,
       separated  by  double percent signs ( "%%" ). The declarations and pro-
       grams sections can be empty. If the latter is empty, the preceding "%%"
       mark separating it from the rules section can be omitted.
       The  input  is  free  form  text following the structure of the grammar
       defined below.
   Lexical Structure of the Grammar
       The <blank>s, <newline>s, and <form-feed>s  shall  be  ignored,  except
       that  the  application shall ensure that they do not appear in names or
       multi-character  reserved  symbols.  Comments  shall  be  enclosed   in
       "/* ... */", and can appear wherever a name is valid.
       Names  are  of  arbitrary length, made up of letters, periods ( '.'  ),
       underscores ( '_' ), and non-initial digits.  Uppercase  and  lowercase
       letters  are  distinct.  Conforming  applications  shall  not use names
       beginning in yy or YY since the yacc parser uses such  names.  Many  of
       the  names  appear in the final output of yacc, and thus they should be
       chosen to conform with any additional rules created by the  C  compiler
       to be used. In particular they appear in #define statements.
       A literal shall consist of a single character enclosed in single-quotes
       ( '" ). All of the escape sequences supported for  character  constants
       by the ISO C standard shall be supported by yacc.
       The  relationship  with  the  lexical  analyzer  is discussed in detail
       below.
       The application shall ensure that the NUL  character  is  not  used  in
       grammar rules or literals.
   Declarations Section
       The  declarations  section is used to define the symbols used to define
       the target language and their relationship with each other. In particu-
       lar, much of the additional information required to resolve ambiguities
       in the context-free grammar for the target language is provided here.
       Usually yacc assigns the relationship between  the  symbolic  names  it
       generates  and their underlying numeric value. The declarations section
       makes it possible to control the assignment of these values.
       It is also possible to keep semantic information  associated  with  the
       tokens currently on the parse stack in a user-defined C-language union,
       if the members of the union are associated with the  various  names  in
       the grammar. The declarations section provides for this as well.
       The  first group of declarators below all take a list of names as argu-
       ments.  That list can optionally be preceded by the name of a  C  union
       member  (called  a  tag  below)  appearing  within '<' and '>' . (As an
       exception to the typographical conventions of the rest of  this  volume
       of  IEEE Std 1003.1-2001,  in  this  case  <tag>  does  not represent a
       metavariable, but the literal angle bracket  characters  surrounding  a
       symbol.)  The  use  of tag specifies that the tokens named on this line
       shall be of the same C type as the union member referenced by tag. This
       is discussed in more detail below.
       For  lists used to define tokens, the first appearance of a given token
       can be followed by a positive integer (as a string of decimal  digits).
       If  this  is done, the underlying value assigned to it for lexical pur-
       poses shall be taken to be that number.
       The following declares name to be a token:

              %token [<tag>] name [number][name [number]]...
       If tag is present, the C type for all tokens  on  this  line  shall  be
       declared  to be the type referenced by tag. If a positive integer, num-
       ber, follows a name, that value shall be assigned to the token.
       The following declares name to be a token, and  assigns  precedence  to
       it:

              %left [<tag>] name [number][name [number]]...
              %right [<tag>] name [number][name [number]]...
       One or more lines, each beginning with one of these symbols, can appear
       in this section. All tokens on the same line have the  same  precedence
       level  and  associativity;  the lines are in order of increasing prece-
       dence or binding strength. %left denotes that  the  operators  on  that
       line  are left associative, and %right similarly denotes right associa-
       tive operators. If tag is present, it shall declare a C type for  names
       as described for %token.
       The following declares name to be a token, and indicates that this can-
       not be used associatively:

              %nonassoc [<tag>] name [number][name [number]]...
       If the parser encounters associative use of this token  it  reports  an
       error.  If  tag  is  present,  it  shall  declare a C type for names as
       described for %token.
       The following declares that union member names are  non-terminals,  and
       thus it is required to have a tag field at its beginning:

              %type <tag> name...
       Because  it  deals with non-terminals only, assigning a token number or
       using a literal is also prohibited. If this construct is present,  yacc
       shall  perform  type  checking;  if  this construct is not present, the
       parse stack shall hold only the int type.
       Every name used in grammar not defined by a %token, %left,  %right,  or
       %nonassoc  declaration  is  assumed to represent a non-terminal symbol.
       The yacc utility shall report an error for any non-terminal symbol that
       does not appear on the left side of at least one grammar rule.
       Once  the  type, precedence, or token number of a name is specified, it
       shall not be changed. If the first declaration  of  a  token  does  not
       assign  a  token  number,  yacc shall assign a token number.  Once this
       assignment is made, the token number shall not be changed  by  explicit
       assignment.
       The following declarators do not follow the previous pattern.
       The  following  declares  the non-terminal name to be the start symbol,
       which represents the largest, most general structure described  by  the
       grammar rules:

              %start name
       By  default,  it  is the left-hand side of the first grammar rule; this
       default can be overridden with this declaration.
       The following declares the yacc value stack to be a union of the  vari-
       ous types of values desired:

              %union { body of union (in C) }
       By  default, the values returned by actions (see below) and the lexical
       analyzer shall be of type int. The yacc utility keeps track  of  types,
       and  it  shall insert corresponding union member names in order to per-
       form strict type checking of the resulting parser.
       Alternatively, given that at least one <tag>  construct  is  used,  the
       union  can be declared in a header file (which shall be included in the
       declarations section by using a #include construct within %{  and  %}),
       and  a  typedef  used  to  define  the symbol YYSTYPE to represent this
       union. The effect of %union is to provide the  declaration  of  YYSTYPE
       directly from the yacc input.
       C-language  declarations and definitions can appear in the declarations
       section, enclosed by the following marks:

              %{ ... %}
       These statements shall be copied into the code file,  and  have  global
       scope  within it so that they can be used in the rules and program sec-
       tions.
       The application shall ensure that the declarations  section  is  termi-
       nated by the token %%.
   Grammar Rules in yacc
       The  rules  section  defines the context-free grammar to be accepted by
       the function yacc generates, and associates with those rules C-language
       actions   and   additional  precedence  information.   The  grammar  is
       described below, and a formal definition follows.
       The rules section is comprised of one or more grammar rules. A  grammar
       rule has the form:

              A : BODY ;
       The  symbol  A  represents  a  non-terminal name, and BODY represents a
       sequence of zero or more names, literals, and semantic actions that can
       then  be followed by optional precedence rules. Only the names and lit-
       erals participate in the formation of the grammar; the semantic actions
       and  precedence  rules  are used in other ways. The colon and the semi-
       colon are yacc punctuation. If there  are  several  successive  grammar
       rules with the same left-hand side, the vertical bar '|' can be used to
       avoid rewriting the left-hand side; in this case the semicolon  appears
       only after the last rule. The BODY part can be empty (or empty of names
       and literals) to indicate that  the  non-terminal  symbol  matches  the
       empty string.
       The  yacc utility assigns a unique number to each rule. Rules using the
       vertical bar notation are distinct rules. The number  assigned  to  the
       rule appears in the description file.
       The elements comprising a BODY are:
       name, literal
              These form the rules of the grammar: name is either a token or a
              non-terminal; literal stands  for  itself  (less  the  lexically
              required quotation marks).
       semantic action
              With  each  grammar  rule,  the user can associate actions to be
              performed each time the rule is recognized in the input process.
              (Note  that  the  word "action" can also refer to the actions of
              the parser-shift, reduce, and so on.)
       These actions can return values and can obtain the values  returned  by
       previous actions. These values are kept in objects of type YYSTYPE (see
       %union). The result value of the action shall  be  kept  on  the  parse
       stack  with  the  left-hand  side  of the rule, to be accessed by other
       reductions as part of their right-hand side.  By using the <tag> infor-
       mation provided in the declarations section, the code generated by yacc
       can be strictly type checked  and  contain  arbitrary  information.  In
       addition, the lexical analyzer can provide the same kinds of values for
       tokens, if desired.
       An action is an arbitrary C statement and as such can do input or  out-
       put,  call  subprograms, and alter external variables. An action is one
       or more C statements enclosed in curly braces '{' and '}' .
       Certain pseudo-variables can be used in the action.  These  are  macros
       for access to data structures known internally to yacc.
       $$
              The  value  of  the  action can be set by assigning it to $$. If
              type checking is enabled  and  the  type  of  the  value  to  be
              assigned  cannot be determined, a diagnostic message may be gen-
              erated.
       $number
              This refers to the value returned by the component specified  by
              the  token number in the right side of a rule, reading from left
              to right; number can be zero or negative. If number is  zero  or
              negative,  it refers to the data associated with the name on the
              parser's stack preceding the  leftmost  symbol  of  the  current
              rule.  (That  is,  "$0" refers to the name immediately preceding
              the leftmost name in  the  current  rule  to  be  found  on  the
              parser's  stack  and "$-1" refers to the symbol to its left.) If
              number refers to an element past the current point in the  rule,
              or  beyond  the bottom of the stack, the result is undefined. If
              type checking is enabled  and  the  type  of  the  value  to  be
              assigned  cannot be determined, a diagnostic message may be gen-
              erated.
       $<tag>number
              These correspond exactly to the  corresponding  symbols  without
              the  tag inclusion, but allow for strict type checking (and pre-
              clude unwanted type conversions). The effect is that  the  macro
              is  expanded  to  use  tag to select an element from the YYSTYPE
              union (using dataname.tag). This is particularly useful if  num-
              ber is not positive.
       $<tag>$
              This  imposes on the reference the type of the union member ref-
              erenced by tag. This construction is applicable when a reference
              to a left context value occurs in the grammar, and provides yacc
              with a means for selecting a type.

       Actions can occur anywhere in a rule (not just at the end);  an  action
       can  access  values  returned  by  actions to its left, and in turn the
       value it returns can be accessed by actions to its  right.   An  action
       appearing  in the middle of a rule shall be equivalent to replacing the
       action with a new non-terminal symbol and adding  an  empty  rule  with
       that  non-terminal  symbol  on  the left-hand side. The semantic action
       associated with the new  rule  shall  be  equivalent  to  the  original
       action.  The use of actions within rules might introduce conflicts that
       would not otherwise exist.
       By default, the value of a rule shall be the value of the first element
       in  it.  If the first element does not have a type (particularly in the
       case of a literal) and type checking is turned on by  %type,  an  error
       message shall result.
       precedence
              The  keyword  %prec  can  be used to change the precedence level
              associated with a particular grammar rule. Examples of this  are
              in  cases  where  a unary and binary operator have the same sym-
              bolic representation, but need  to  be  given  different  prece-
              dences,  or where the handling of an ambiguous if-else construc-
              tion is necessary.  The reserved symbol %prec can appear immedi-
              ately  after the body of the grammar rule and can be followed by
              a token name or a literal. It shall cause the precedence of  the
              grammar  rule to become that of the following token name or lit-
              eral. The action for the rule as a whole can follow %prec.

       If a program section follows, the application  shall  ensure  that  the
       grammar rules are terminated by %%.
   Programs Section
       The programs section can include the definition of the lexical analyzer
       yylex(), and any other  functions;  for  example,  those  used  in  the
       actions  specified in the grammar rules.  It is unspecified whether the
       programs section precedes or follows the semantic actions in the output
       file;  therefore, if the application contains any macro definitions and
       declarations intended to apply to the code in the semantic actions,  it
       shall place them within "%{ ... %}" in the declarations section.
   Input Grammar
       The following input to yacc yields a parser for the input to yacc. This
       formal syntax takes precedence over the preceding text syntax  descrip-
       tion.
       The  lexical  structure is defined less precisely; Lexical Structure of
       the Grammar defines most terms. The correspondence between the previous
       terms and the tokens below is as follows.
       IDENTIFIER
              This  corresponds  to  the concept of name, given previously. It
              also includes literals as defined previously.
       C_IDENTIFIER
              This is a name, and additionally it is known to be followed by a
              colon.  A literal cannot yield this token.
       NUMBER A string of digits (a non-negative decimal integer).
       TYPE, LEFT, MARK, LCURL, RCURL
              These correspond directly to %type, %left, %%, %{, and %}.
       { ... }
              This  indicates C-language source code, with the possible inclu-
              sion of '$' macros as discussed previously.

              /* Grammar for the input to yacc. */
              /* Basic entries. */
              /* The following are recognized by the lexical analyzer. */

              %token    IDENTIFIER      /* Includes identifiers and literals */
              %token    C_IDENTIFIER    /* identifier (but not literal)
                                           followed by a :. */
              %token    NUMBER          /* [0-9][0-9]* */

              /* Reserved words : %type=>TYPE %left=>LEFT, and so on */

              %token    LEFT RIGHT NONASSOC TOKEN PREC TYPE START UNION

              %token    MARK            /* The %% mark. */
              %token    LCURL           /* The %{ mark. */
              %token    RCURL           /* The %} mark. */

              /* 8-bit character literals stand for themselves; */
              /* tokens have to be defined for multi-byte characters. */

              %start    spec

              %%

              spec  : defs MARK rules tail
                    ;
              tail  : MARK
                    {
                      /* In this action, set up the rest of the file. */
                    }
                    | /* Empty; the second MARK is optional. */
                    ;
              defs  : /* Empty. */
                    |    defs def
                    ;
              def   : START IDENTIFIER
                    |    UNION
                    {
                      /* Copy union definition to output. */
                    }
                    |    LCURL
                    {
                      /* Copy C code to output file. */
                    }
                      RCURL
                    |    rword tag nlist
                    ;
              rword : TOKEN
                    | LEFT
                    | RIGHT
                    | NONASSOC
                    | TYPE
                    ;
              tag   : /* Empty: union tag ID optional. */
                    | '<' IDENTIFIER '>'
                    ;
              nlist : nmno
                    | nlist nmno
                    ;
              nmno  : IDENTIFIER         /* Note: literal invalid with % type. */
                    | IDENTIFIER NUMBER  /* Note: invalid with % type. */
                    ;

              /* Rule section */

              rules : C_IDENTIFIER rbody prec
                    | rules  rule
                    ;
              rule  : C_IDENTIFIER rbody prec
                    | '|' rbody prec
                    ;
              rbody : /* empty */
                    | rbody IDENTIFIER
                    | rbody act
                    ;
              act   : '{'
                      {
                        /* Copy action, translate $$, and so on. */
                      }
                      '}'
                    ;
              prec  : /* Empty */
                    | PREC IDENTIFIER
                    | PREC IDENTIFIER act
                    | prec ';'
                    ;
   Conflicts
       The parser produced for an input grammar may contain  states  in  which
       conflicts  occur.  The  conflicts  occur  because  the  grammar  is not
       LALR(1). An ambiguous grammar always contains at least one LALR(1) con-
       flict.  The  yacc  utility  shall  resolve  all conflicts, using either
       default rules or user-specified precedence rules.
       Conflicts are either shift/reduce conflicts or reduce/reduce conflicts.
       A  shift/reduce conflict is where, for a given state and lookahead sym-
       bol, both  a  shift  action  and  a  reduce  action  are  possible.   A
       reduce/reduce  conflict  is where, for a given state and lookahead sym-
       bol, reductions by two different rules are possible.
       The rules below describe how to specify what actions  to  take  when  a
       conflict  occurs.  Not  all  shift/reduce conflicts can be successfully
       resolved this way because the conflict may be due  to  something  other
       than  ambiguity,  so  incautious  use of these facilities can cause the
       language accepted by the parser to be much different  from  that  which
       was intended. The description file shall contain sufficient information
       to understand the cause of the conflict. Where ambiguity is the  reason
       either  the  default  or explicit rules should be adequate to produce a
       working parser.
       The declared precedences and associativities (see Declarations  Section
       ) are used to resolve parsing conflicts as follows:
        1. A  precedence  and  associativity  is  associated with each grammar
           rule; it is the precedence and associativity of the last  token  or
           literal  in  the body of the rule. If the %prec keyword is used, it
           overrides this default. Some grammar  rules  might  not  have  both
           precedence and associativity.
        2. If  there is a shift/reduce conflict, and both the grammar rule and
           the input symbol have precedence and associativity associated  with
           them,  then  the conflict is resolved in favor of the action (shift
           or reduce) associated with the higher  precedence.  If  the  prece-
           dences  are the same, then the associativity is used; left associa-
           tive implies reduce, right associative implies shift, and non-asso-
           ciative implies an error in the string being parsed.
        3. When  there  is  a shift/reduce conflict that cannot be resolved by
           rule 2, the shift is done. Conflicts resolved this way are  counted
           in the diagnostic output described in Error Handling .
        4. When  there is a reduce/reduce conflict, a reduction is done by the
           grammar rule that occurs earlier in the input sequence.   Conflicts
           resolved this way are counted in the diagnostic output described in
           Error Handling .
       Conflicts resolved by precedence or associativity shall not be  counted
       in  the  shift/reduce  and  reduce/reduce conflicts reported by yacc on
       either standard error or in the description file.
   Error Handling
       The token error shall be reserved for error handling.  The  name  error
       can  be used in grammar rules. It indicates places where the parser can
       recover from a syntax error. The default value of error shall  be  256.
       Its  value  can be changed using a %token declaration. The lexical ana-
       lyzer should not return the value of error.
       The parser shall detect a syntax error when it is in a state where  the
       action associated with the lookahead symbol is error. A semantic action
       can cause the parser to initiate error handling by executing the  macro
       YYERROR.  When  YYERROR is executed, the semantic action passes control
       back to the parser. YYERROR cannot be used outside of semantic actions.
       When the parser detects a syntax error,  it  normally  calls  yyerror()
       with  the  character  string  "syntax error"  as its argument. The call
       shall not be made if the parser is still  recovering  from  a  previous
       error when the error is detected. The parser is considered to be recov-
       ering from a previous error until the parser has shifted over at  least
       three  normal  input  symbols  since  the  last error was detected or a
       semantic action has executed the macro yyerrok. The  parser  shall  not
       call yyerror() when YYERROR is executed.
       The  macro  function  YYRECOVERING shall return 1 if a syntax error has
       been detected and the parser has not yet fully recovered from it.  Oth-
       erwise, zero shall be returned.
       When  a  syntax error is detected by the parser, the parser shall check
       if a previous syntax error has been detected. If a previous  error  was
       detected,  and  if  no normal input symbols have been shifted since the
       preceding error was detected, the parser checks if the lookahead symbol
       is an endmarker (see Interface to the Lexical Analyzer ). If it is, the
       parser shall return with a non-zero  value.  Otherwise,  the  lookahead
       symbol shall be discarded and normal parsing shall resume.
       When  YYERROR is executed or when the parser detects a syntax error and
       no previous error has been detected, or at least one normal input  sym-
       bol  has been shifted since the previous error was detected, the parser
       shall pop back one state at a time until the parse stack  is  empty  or
       the current state allows a shift over error.  If the parser empties the
       parse stack, it shall return with a non-zero value. Otherwise, it shall
       shift  over error and then resume normal parsing. If the parser reads a
       lookahead symbol before the error was detected, that symbol shall still
       be the lookahead symbol when parsing is resumed.
       The macro yyerrok in a semantic action shall cause the parser to act as
       if it has fully recovered from any previous errors. The macro yyclearin
       shall  cause  the parser to discard the current lookahead token. If the
       current lookahead token has not yet been read, yyclearin shall have  no
       effect.
       The  macro  YYACCEPT  shall  cause  the parser to return with the value
       zero. The macro YYABORT shall cause the parser to return  with  a  non-
       zero value.
   Interface to the Lexical Analyzer
       The yylex() function is an integer-valued function that returns a token
       number representing the kind of token read. If there is a value associ-
       ated  with  the  token  returned  by yylex() (see the discussion of tag
       above), it shall be assigned to the external variable yylval.
       If the parser and yylex() do not agree on these token numbers, reliable
       communication  between  them  cannot occur. For (single-byte character)
       literals, the token is simply the numeric value of the character in the
       current  character set. The numbers for other tokens can either be cho-
       sen by yacc, or chosen by the user. In either case,  the  #define  con-
       struct  of  C is used to allow yylex() to return these numbers symboli-
       cally.  The #define statements are put into  the  code  file,  and  the
       header  file if that file is requested. The set of characters permitted
       by yacc in an identifier is larger than  that  permitted  by  C.  Token
       names  found  to  contain  such characters shall not be included in the
       #define declarations.
       If the token numbers are chosen by yacc, the tokens other than literals
       shall  be  assigned  numbers  greater  than  256,  although no order is
       implied. A token can be explicitly assigned a number by  following  its
       first  appearance  in the declarations section with a number. Names and
       literals not defined this way  retain  their  default  definition.  All
       token  numbers  assigned  by yacc shall be unique and distinct from the
       token numbers used for literals and user-assigned tokens. If  duplicate
       token  numbers  cause conflicts in parser generation, yacc shall report
       an error; otherwise, it is unspecified whether the token assignment  is
       accepted or an error is reported.
       The end of the input is marked by a special token called the endmarker,
       which has a token number that is zero or negative.  (These  values  are
       invalid  for  any other token.) All lexical analyzers shall return zero
       or negative as a token number upon reaching the end of their input.  If
       the  tokens  up  to, but excluding, the endmarker form a structure that
       matches the start symbol, the parser shall accept  the  input.  If  the
       endmarker  is  seen  in  any  other  context, it shall be considered an
       error.
   Completing the Program
       In addition to yyparse()  and  yylex(),  the  functions  yyerror()  and
       main()  are  required  to  make a complete program. The application can
       supply main() and yyerror(), or those routines can be obtained from the
       yacc library.
   Yacc Library
       The  following functions shall appear only in the yacc library accessi-
       ble through the -l y operand to c99; they can therefore be redefined by
       a conforming application:
       int  main(void)
              This  function shall call yyparse() and exit with an unspecified
              value. Other actions within this function are unspecified.
       int  yyerror(const char *s)
              This function shall write the NUL-terminated argument  to  stan-
              dard error, followed by a <newline>.

       The  order  of  the -l y and -l l operands given to c99 is significant;
       the application shall either provide its own main() function or  ensure
       that -l y precedes -l l.
   Debugging the Parser
       The  parser  generated  by  yacc shall have diagnostic facilities in it
       that can be optionally enabled at either compile time or at runtime (if
       enabled at compile time). The compilation of the runtime debugging code
       is under the control of YYDEBUG, a preprocessor symbol. If YYDEBUG  has
       a non-zero value, the debugging code shall be included. If its value is
       zero, the code shall not be included.
       In parsers where the debugging code has been included, the external int
       yydebug  can  be  used to turn debugging on (with a non-zero value) and
       off (zero value) at runtime. The initial  value  of  yydebug  shall  be
       zero.
       When  -t is specified, the code file shall be built such that, if YYDE-
       BUG is not already defined at compilation time (using the c99 -D  YYDE-
       BUG option, for example), YYDEBUG shall be set explicitly to 1. When -t
       is not specified, the code file shall be built such that, if YYDEBUG is
       not already defined, it shall be set explicitly to zero.
       The format of the debugging output is unspecified but includes at least
       enough information to determine the shift and reduce actions,  and  the
       input symbols. It also provides information about error recovery.
   Algorithms
       The  parser constructed by yacc implements an LALR(1) parsing algorithm
       as documented in the literature. It is unspecified whether  the  parser
       is table-driven or direct-coded.
       A  parser  generated  by  yacc shall never request an input symbol from
       yylex() while in a state where the only actions other  than  the  error
       action are reductions by a single rule.
       The literature of parsing theory defines these concepts.
   Limits
       The yacc utility may have several internal tables. The minimum maximums
       for these tables are shown in the following table. The exact meaning of
       these  values  is  implementation-defined.   The  implementation  shall
       define the relationship between these values and between them  and  any
       error  messages  that the implementation may generate should it run out
       of space for any internal  structure.  An  implementation  may  combine
       groups  of  these  resources  into  a  single pool as long as the total
       available to the user does not fall below the sum of the  sizes  speci-
       fied by this section.
                           Table: Internal Limits in yacc
                        Minimum
           Limit        Maximum   Description
           {NTERMS}     126       Number of tokens.
           {NNONTERM}   200       Number of non-terminals.
           {NPROD}      300       Number of rules.
           {NSTATES}    600       Number of states.
           {MEMSIZE}    5200      Length of rules. The total length, in
                                  names (tokens and non-terminals), of all
                                  the rules of the grammar. The left-hand
                                  side is counted for each rule, even if
                                  it is not explicitly repeated, as speci-
                                  fied in Grammar Rules in yacc .
           {ACTSIZE}    4000      Number of actions. "Actions" here (and
                                  in the description file) refer to parser
                                  actions (shift, reduce, and so on) not
                                  to semantic actions defined in Grammar
                                  Rules in yacc .
EXIT STATUS
       The following exit values shall be returned:
        0     Successful completion.
       >0     An error occurred.

CONSEQUENCES OF ERRORS
       If any errors are encountered, the run is aborted and yacc exits with a
       non-zero  status.  Partial code files and header files may be produced.
       The summary information in the description file shall  always  be  pro-
       duced if the -v flag is present.
       The following sections are informative.
APPLICATION USAGE
       Historical  implementations  experience  name  conflicts  on  the names
       yacc.tmp, yacc.acts, yacc.debug, y.tab.c, y.tab.h, and y.output if more
       than one copy of yacc is running in a single directory at one time. The
       -b option was added to overcome this problem. The  related  problem  of
       allowing  multiple  yacc  parsers  to  be  placed  in the same file was
       addressed by adding a -p option to override the  previously  hard-coded
       yy variable prefix.
       The  description of the -p option specifies the minimal set of function
       and variable names that cause conflict when multiple parsers are linked
       together.  YYSTYPE does not need to be changed. Instead, the programmer
       can use -b to give the header files  for  different  parsers  different
       names,  and  then  the  file  with  the  yylex() for a given parser can
       include the header for that parser. Names such  as  yyclearerr  do  not
       need  to  be changed because they are used only in the actions; they do
       not have linkage. It is  possible  that  an  implementation  has  other
       names, either internal ones for implementing things such as yyclearerr,
       or providing non-standard features that it wants to change with -p.
       Unary operators that are the same token as a binary operator in general
       need  their  precedence adjusted. This is handled by the %prec advisory
       symbol associated with the particular grammar rule defining that  unary
       operator.  (See  Grammar Rules in yacc .) Applications are not required
       to use this operator for unary operators, but the grammars that do  not
       require it are rare.
EXAMPLES
       Access  to the yacc library is obtained with library search operands to
       c99. To use the yacc library main():

              c99 y.tab.c -l y
       Both the lex library and the yacc library contain  main().   To  access
       the yacc main():

              c99 y.tab.c lex.yy.c -l y -l l
       This  ensures  that  the  yacc  library  is searched first, so that its
       main() is used.
       The historical yacc libraries have contained two simple functions  that
       are  normally coded by the application programmer.  These functions are
       similar to the following code:

              #include <locale.h>
              int main(void)
              {
                  extern int yyparse();

                  setlocale(LC_ALL, "");

                  /* If the following parser is one created by lex, the
                     application must be careful to ensure that LC_CTYPE
                     and LC_COLLATE are set to the POSIX locale. */
                  (void) yyparse();
                  return (0);
              }

              #include <stdio.h>

              int yyerror(const char *msg)
              {
                  (void) fprintf(stderr, "%s\n", msg);
                  return (0);
              }
RATIONALE
       The references in may be helpful in constructing the parser  generator.
       The  referenced  DeRemer  and Pennello article (along with the works it
       references) describes a technique to generate parsers that  conform  to
       this volume of IEEE Std 1003.1-2001.  Work in this area continues to be
       done, so implementors should consult current  literature  before  doing
       any  new implementations. The original Knuth article is the theoretical
       basis for this kind of parser, but the tables it generates are  imprac-
       tically  large  for  reasonable  grammars  and  should not be used. The
       "equivalent to" wording is intentional to assure that the  best  tables
       that are LALR(1) can be generated.
       There  has been confusion between the class of grammars, the algorithms
       needed to generate parsers, and the algorithms needed to parse the lan-
       guages.  They  are  all  reasonably orthogonal. In particular, a parser
       generator that accepts the full range of LR(1) grammars need not gener-
       ate a table any more complex than one that accepts SLR(1) (a relatively
       weak class of LR grammars) for a grammar that  happens  to  be  SLR(1).
       Such  an implementation need not recognize the case, either; table com-
       pression can yield the SLR(1) table (or one  even  smaller  than  that)
       without  recognizing  that the grammar is SLR(1). The speed of an LR(1)
       parser for any class is dependent more upon  the  table  representation
       and  compression  (or  the code generation if a direct parser is gener-
       ated) than upon the class of grammar that the table generator handles.
       The speed of the parser generator is somewhat dependent upon the  class
       of  grammar  it handles. However, the original Knuth article algorithms
       for constructing LR parsers were judged by its author to  be  impracti-
       cally slow at that time. Although full LR is more complex than LALR(1),
       as computer speeds and algorithms improve, the difference (in terms  of
       acceptable wall-clock execution time) is becoming less significant.
       Potential  authors  are  cautioned that the referenced DeRemer and Pen-
       nello article previously cited identifies a bug (an over-simplification
       of  the  computation  of LALR(1) lookahead sets) in some of the LALR(1)
       algorithm statements that preceded it to publication. They should  take
       the time to seek out that paper, as well as current relevant work, par-
       ticularly Aho's.
       The -b option was added to provide a  portable  method  for  permitting
       yacc  to  work on multiple separate parsers in the same directory. If a
       directory contains more than one yacc grammar, and  both  grammars  are
       constructed  at  the  same  time (by, for example, a parallel make pro-
       gram), conflict results.  While the solution is  not  historical  prac-
       tice,  it  corrects  a  known deficiency in historical implementations.
       Corresponding changes were made to all  sections  that  referenced  the
       filenames  y.tab.c  (now  "the  code  file"),  y.tab.h (now "the header
       file"), and y.output (now "the description file").
       The grammar for yacc input is based on  System  V  documentation.   The
       textual  description shows there that the ';' is required at the end of
       the rule. The grammar and the implementation do not require this.  (The
       use of C_IDENTIFIER causes a reduce to occur in the right place.)
       Also, in that implementation, the constructs such as %token can be ter-
       minated by a semicolon, but this is not permitted by the  grammar.  The
       keywords  such  as  %token can also appear in uppercase, which is again
       not discussed. In most places where '%' is used,  '\'  can  be  substi-
       tuted,  and  there are alternate spellings for some of the symbols (for
       example, %LEFT can be "%<" or even "\<" ).
       Historically, <tag> can contain any characters  except  '>',  including
       white  space, in the implementation. However, since the tag must refer-
       ence an ISO C standard union member, in practice conforming implementa-
       tions  need  to  support  only the set of characters for ISO C standard
       identifiers in this context.
       Some historical implementations are known to accept  actions  that  are
       terminated  by  a period. Historical implementations often allow '$' in
       names. A conforming implementation does not need to support  either  of
       these behaviors.
       Deciding when to use %prec illustrates the difficulty in specifying the
       behavior of yacc. There may be situations in which the grammar is  not,
       strictly speaking, in error, and yet yacc cannot interpret it unambigu-
       ously. The resolution  of  ambiguities  in  the  grammar  can  in  many
       instances  be  resolved  by  providing  additional information, such as
       using %type or %union declarations. It is often easier and  it  usually
       yields  a  smaller parser to take this alternative when it is appropri-
       ate.
       The size and execution time of a program produced without  the  runtime
       debugging  code  is  usually  smaller and slightly faster in historical
       implementations.
       Statistics messages from several historical implementations include the
       following types of information:

              n/512 terminals, n/300 non-terminals
              n/600 grammar rules, n/1500 states
              n shift/reduce, n reduce/reduce conflicts reported
              n/350 working sets used
              Memory: states, etc. n/15000, parser n/15000
              n/600 distinct lookahead sets
              n extra closures
              n shift entries, n exceptions
              n goto entries
              n entries saved by goto default
              Optimizer space used: input n/15000, output n/15000
              n table entries, n zero
              Maximum spread: n, Maximum offset: n
       The report of internal tables in the description file is left implemen-
       tation-defined because all aspects of these limits are also implementa-
       tion-defined.  Some  implementations  may  use dynamic allocation tech-
       niques and have no specific limit values to report.
       The format of the y.output file is not given because  specification  of
       the  format was not seen to enhance applications portability. The list-
       ing is primarily intended to help human users understand and debug  the
       parser;  use  of  y.output  by a conforming application script would be
       unusual. Furthermore, implementations have not produced consistent out-
       put  and  no  popular  format  was apparent. The format selected by the
       implementation should be human-readable, in addition to the requirement
       that it be a text file.
       Standard  error reports are not specifically described because they are
       seldom of use to conforming applications and there  was  no  reason  to
       restrict implementations.
       Some  implementations  recognize  "={"  as equivalent to '{' because it
       appears in historical documentation. This construction  was  recognized
       and documented as obsolete as long ago as 1978, in the referenced Yacc:
       Yet Another  Compiler-Compiler.  This  volume  of  IEEE Std 1003.1-2001
       chose to leave it as obsolete and omit it.
       Multi-byte  characters should be recognized by the lexical analyzer and
       returned as tokens. They should not be returned as multi-byte character
       literals.  The  token error that is used for error recovery is normally
       assigned the value 256 in  the  historical  implementation.  Thus,  the
       token  value  256,  which is used in many multi-byte character sets, is
       not available for use as the value of a user-defined token.
FUTURE DIRECTIONS
       None.
SEE ALSO
       c99, lex
COPYRIGHT
       Portions of this text are reprinted and reproduced in  electronic  form
       from IEEE Std 1003.1, 2003 Edition, Standard for Information Technology
       -- Portable Operating System Interface (POSIX),  The  Open  Group  Base
       Specifications  Issue  6,  Copyright  (C) 2001-2003 by the Institute of
       Electrical and Electronics Engineers, Inc and The Open  Group.  In  the
       event of any discrepancy between this version and the original IEEE and
       The Open Group Standard, the original IEEE and The Open Group  Standard
       is  the  referee document. The original Standard can be obtained online
       at http://www.opengroup.org/unix/online.html .

IEEE/The Open Group                  2003                             YACC(1P)