Unix/Linux Go Back    


POSIX 1003.1 - man page for yacc (posix section 1posix)

Linux & Unix Commands - Search Man Pages
Man Page or Keyword Search:   man
Select Man Page Set:       apropos Keyword Search (sections above)


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

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 func-
       tion 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  descrip-
	      tion  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 state-
	      ments  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 compila-
	      tion.

       -v     Write  a file containing a description of the parser and a report of conflicts gen-
	      erated 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, Inter-
	      nationalization 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  interna-
	      tionalization 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  argu-
	      ments and input files).

       LC_MESSAGES
	      Determine the locale that should be used to affect the format and contents of diag-
	      nostic 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 implementa-
       tions 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 pro-
       cessed by yacc into its output files. The code included in this way shall be executed dur-
       ing the recognition of the target language.

       Given  a  grammar, the yacc utility generates the files described in the OUTPUT FILES sec-
       tion. 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 yyer-
       ror(), 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 gener-
       ate 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 pre-
       ceding "%%" 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. Com-
       ments 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 applica-
       tions 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  sup-
       ported 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 liter-
       als.

   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  asso-
       ciated  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  opera-
       tors  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 associa-
       tively:

	      %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 declara-
       tion 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  over-
       ridden 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 prece-
       dence 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 nota-
       tion 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; lit-
	      eral 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 pro-
       vide 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 subpro-
       grams, 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 nega-
	      tive. 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  bot-
	      tom 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 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 check-
       ing 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 par-
	      ticular grammar rule. Examples of this are in cases where a unary and binary opera-
	      tor  have  the  same symbolic representation, but need to be given different prece-
	      dences, 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 ter-
       minated 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 declara-
       tions  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  fol-
       lows.

       IDENTIFIER
	      This  corresponds to the concept of name, given previously. It also includes liter-
	      als 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  con-
       flict.  Where  ambiguity is the reason either the default or explicit rules should be ade-
       quate 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 prece-
	   dence 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  descrip-
       tion file.

   Error Handling
       The  token error shall be reserved for error handling. The name error can be used in gram-
       mar 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 nor-
       mal 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  looka-
       head 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 represent-
       ing 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  state-
       ments  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 lexi-
       cal 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  rou-
       tines 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 infor-
       mation 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 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 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 implementa-
       tion  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  prece-
       dence  adjusted. This is handled by the %prec advisory symbol associated with the particu-
       lar 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 orthog-
       onal. 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  han-
       dles.  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  com-
       plex  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  previ-
       ously  cited identifies a bug (an over-simplification of the computation of LALR(1) looka-
       head 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 multi-
       ple  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 cor-
       rects 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 implemen-
       tation 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 semi-
       colon, 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  exam-
       ple, %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 avail-
       able 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 orig-
       inal Standard can be obtained online at http://www.opengroup.org/unix/online.html .

IEEE/The Open Group			       2003					  YACC(P)
Unix & Linux Commands & Man Pages : ©2000 - 2017 Unix and Linux Forums


All times are GMT -4. The time now is 08:17 AM.