Man Linux: Main Page and Category List

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
       routines  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
              filenames. The  code  file  y.tab.c,  the  header  file  y.tab.h
              (created  when  -d  is  specified),  and  the  description  file
              y.output (created when -v is specified),  shall  be  changed  to
              file_prefix .tab.c, file_prefix .tab.h, and file_prefix .output,
              respectively.

       -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
              conditional 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
              Variables  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
       substitution 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
       declaration 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
       language 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
       analyzer 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
       programs  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
       particular, 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
       arguments.  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
       purposes 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,
       number, 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
       precedence or binding strength. %left denotes  that  the  operators  on
       that  line  are  left  associative,  and %right similarly denotes right
       associative 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
       cannot 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
       various 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
       perform 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
       sections.

       The  application  shall  ensure  that  the  declarations   section   is
       terminated 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
       literals participate in the formation  of  the  grammar;  the  semantic
       actions  and precedence rules are used in other ways. The colon and the
       semicolon 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>
       information 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
       output,  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
              generated.

       $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
              generated.

       $<tag>number

              These correspond exactly to the  corresponding  symbols  without
              the  tag  inclusion,  but  allow  for  strict type checking (and
              preclude 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 number is not positive.

       $<tag>$
              This  imposes  on  the  reference  the  type of the union member
              referenced 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
              symbolic  representation,  but  need  to  be   given   different
              precedences,  or  where  the  handling  of  an ambiguous if-else
              construction is necessary.  The reserved symbol %prec can appear
              immediately  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 literal. 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
       description.

       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
              inclusion 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)
       conflict. 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
       symbol,  both  a  shift  action  and  a  reduce action are possible.  A
       reduce/reduce conflict is  where,  for  a  given  state  and  lookahead
       symbol, 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
           precedences are the same, then  the  associativity  is  used;  left
           associative  implies  reduce,  right associative implies shift, and
           non-associative 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
       analyzer 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
       recovering 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.
       Otherwise, 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
       symbol  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
       associated  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
       chosen by yacc, or chosen by the user.  In  either  case,  the  #define
       construct  of  C  is  used  to  allow  yylex()  to return these numbers
       symbolically.  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
       accessible 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
              standard 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
       YYDEBUG is not already defined at compilation time (using  the  c99  -D
       YYDEBUG  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
       specified 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
                                  specified 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
       produced 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
       impractically 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
       languages.  They are all reasonably orthogonal. In particular, a parser
       generator that accepts the  full  range  of  LR(1)  grammars  need  not
       generate  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 compression 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 generated) 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
       impractically 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
       Pennello  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, particularly 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
       program), conflict results.   While  the  solution  is  not  historical
       practice, 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
       terminated 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
       substituted,  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
       reference an  ISO C  standard  union  member,  in  practice  conforming
       implementations  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
       unambiguously. 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
       appropriate.

       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
       implementation-defined because all aspects of  these  limits  are  also
       implementation-defined. Some implementations may use dynamic allocation
       techniques 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
       listing 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
       output  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 .