yacc man page on Gentoo

Man page or keyword search:  
man Server   6889 pages
apropos Keyword Search (all sections)
Output format
Gentoo logo
[printable version]

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

PROLOG
       This  manual  page is part of the POSIX Programmer's Manual.  The Linux
       implementation of this interface may differ (consult the	 corresponding
       Linux  manual page for details of Linux behavior), or the interface may
       not be implemented on Linux.

NAME
       yacc — yet another compiler compiler (DEVELOPMENT)

SYNOPSIS
       yacc [−dltv] [−b file_prefix] [−p sym_prefix] grammar

DESCRIPTION
       The yacc utility shall read a description of a context-free grammar  in
       grammar and write C source code, conforming to the ISO C standard, to a
       code file, and optionally header information into a header file, in the
       current	directory.  The	 generated source code shall not depend on any
       undefined, unspecified, or implementation-defined behavior,  except  in
       cases  where  it	 is  copied  directly from the supplied grammar, or in
       cases that are documented by  the  implementation.  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
       POSIX.1‐2008,  Section  12.2,  Utility  Syntax  Guidelines,  except for
       Guideline 9.

       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 writ‐
		 ten.  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 con‐
		 structs. If this option is not	 present,  it  is  unspecified
		 whether  the  code  file or header file contains #line direc‐
		 tives. 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 vari‐
		 ables 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  compila‐
		 tion  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 com‐
		 pilation.

       −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 for‐
		 mat  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 vari‐
		 ables that are unset or null. (See the Base Definitions  vol‐
		 ume  of POSIX.1‐2008, Section 8.2, Internationalization Vari‐
		 ables for the precedence  of  internationalization  variables
		 used to determine the values of locale categories.)

       LC_ALL	 If  set  to  a non-empty string value, override the values of
		 all the other internationalization variables.

       LC_CTYPE	 Determine the locale for the interpretation of	 sequences  of
		 bytes of text data as characters (for example, single-byte as
		 opposed to  multi-byte	 characters  in	 arguments  and	 input
		 files).

       LC_MESSAGES
		 Determine the locale that should be used to affect the format
		 and contents  of  diagnostic  messages	 written  to  standard
		 error.

       NLSPATH	 Determine the location of message catalogs for the processing
		 of LC_MESSAGES.

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

	   setlocale(LC_ALL, "")

       and  thus  the  program generated by yacc shall also be affected by the
       contents of these variables at runtime.

ASYNCHRONOUS EVENTS
       Default.

STDOUT
       Not used.

STDERR
       If shift/reduce or reduce/reduce conflicts  are	detected  in  grammar,
       yacc  shall  write a report of those conflicts to the standard error in
       an unspecified format.

       Standard error shall also be used for diagnostic messages.

OUTPUT FILES
       The code file, the header file, and the description file shall be  text
       files. All are described in the following sections.

   Code File
       This  file  shall contain the C source code for the yyparse() function.
       It shall contain code for the various semantic actions with macro  sub‐
       stitution  performed  on	 them as described in the EXTENDED DESCRIPTION
       section. It also shall contain a copy of the #define statements in  the
       header  file.  If  a  %union  declaration  is used, the declaration for
       YYSTYPE shall also be included in this file.

   Header File
       The header file shall contain #define  statements  that	associate  the
       token numbers with the token names. This allows source files other than
       the code file to access the token codes. If  a  %union  declaration  is
       used, the declaration for YYSTYPE and an extern YYSTYPE yylval declara‐
       tion shall also be included in this file.

   Description File
       The description file shall be a text file containing a  description  of
       the  state  machine  corresponding  to the parser, using an unspecified
       format. Limits for internal tables (see Limits) shall also be reported,
       in  an  implementation-defined  manner.	(Some  implementations may use
       dynamic allocation techniques and have  no  specific  limit  values  to
       report.)

EXTENDED DESCRIPTION
       The  yacc  command  accepts a language that is used to define a grammar
       for a target language to be parsed by the tables and code generated  by
       yacc.   The  language accepted by yacc as a grammar for the target lan‐
       guage is described below using the yacc input language itself.

       The input grammar includes rules describing the input structure of  the
       target  language and code to be invoked when these rules are recognized
       to provide the associated semantic action.  The	code  to  be  executed
       shall appear as bodies of text that are intended to be C-language code.
       These bodies of text shall not contain C-language trigraphs. The C-lan‐
       guage inclusions are presumed to form a correct function when processed
       by yacc into its output files. The code included in this way  shall  be
       executed during the recognition of the target language.

       Given  a grammar, the yacc utility generates the files described in the
       OUTPUT FILES section. The code file can be compiled  and	 linked	 using
       c99.   If the declaration and programs sections of the grammar file did
       not include definitions of main(), yylex(), and yyerror(), the compiled
       output  requires	 linking  with	externally  supplied versions of those
       functions. Default versions of main() and yyerror() are supplied in the
       yacc  library  and  can	be linked in by using the −l y operand to c99.
       The yacc library interfaces need not support interfaces with other than
       the default yy symbol prefix. The application provides the lexical ana‐
       lyzer function, yylex(); the lex utility is  specifically  designed  to
       generate such a routine.

   Input Language
       The  application shall ensure that every specification file consists of
       three sections in order: declarations,  grammar	rules,	and  programs,
       separated by double <percent-sign> characters ("%%").  The declarations
       and programs sections can be empty. If the latter is empty, the preced‐
       ing "%%" 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>, <newline>, and <form-feed>	character  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 let‐
       ters  are distinct.  Conforming applications shall not use names begin‐
       ning 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 cho‐
       sen 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-quote
       characters. All of the escape sequences supported  for  character  con‐
       stants by the ISO C standard shall be supported by yacc.

       The  relationship  with	the  lexical  analyzer	is discussed in detail
       below.

       The application shall ensure that the NUL  character  is	 not  used  in
       grammar rules or literals.

   Declarations Section
       The  declarations  section is used to define the symbols used to define
       the target language and their relationship with each other. In particu‐
       lar, much of the additional information required to resolve ambiguities
       in the context-free grammar for the target language is provided here.

       Usually yacc assigns the relationship between  the  symbolic  names  it
       generates  and their underlying numeric value. The declarations section
       makes it possible to control the assignment of these values.

       It is also possible to keep semantic information	 associated  with  the
       tokens currently on the parse stack in a user-defined C-language union,
       if the members of the union are associated with the  various  names  in
       the grammar. The declarations section provides for this as well.

       The  first group of declarators below all take a list of names as argu‐
       ments. That list can optionally be preceded by the name of  a  C	 union
       member  (called	a  tag	below)	appearing  within '<' and '>'.	(As an
       exception to the typographical conventions of the rest of  this	volume
       of  POSIX.1‐2008, in this case <tag> does not represent a metavariable,
       but the literal angle bracket characters surrounding a symbol.) The use
       of  tag	specifies  that	 the tokens named on this line shall be of the
       same C type as the union member referenced by tag.  This	 is  discussed
       in more detail below.

       For  lists used to define tokens, the first appearance of a given token
       can be followed by a positive integer (as a string of decimal  digits).
       If  this	 is done, the underlying value assigned to it for lexical pur‐
       poses shall be taken to be that number.

       The following declares name to be a token:

	   %token [<tag>] name [number] [name [number]]...

       If tag is present, the C type for all tokens  on	 this  line  shall  be
       declared to be the type referenced by tag.  If a positive integer, num‐
       ber, follows a name, that value shall be assigned to the token.

       The following declares name to be a token, and  assigns	precedence  to
       it:

	   %left [<tag>] name [number] [name [number]]...
	   %right [<tag>] name [number] [name [number]]...

       One or more lines, each beginning with one of these symbols, can appear
       in this section. All tokens on the same line have the  same  precedence
       level  and  associativity;  the lines are in order of increasing prece‐
       dence or binding strength.  %left denotes that the  operators  on  that
       line  are left associative, and %right similarly denotes right associa‐
       tive operators. If tag is present, it shall declare a C type for	 names
       as described for %token.

       The following declares name to be a token, and indicates that this can‐
       not be used associatively:

	   %nonassoc [<tag>] name [number] [name [number]]...

       If the parser encounters associative use of this token  it  reports  an
       error.  If  tag	is  present,  it  shall	 declare a C type for names as
       described for %token.

       The following declares that union member names are  non-terminals,  and
       thus it is required to have a tag field at its beginning:

	   %type <tag> name...

       Because	it  deals with non-terminals only, assigning a token number or
       using a literal is also prohibited. If this construct is present,  yacc
       shall  perform  type  checking;	if  this construct is not present, the
       parse stack shall hold only the int type.

       Every name used in grammar not defined by a %token, %left,  %right,  or
       %nonassoc  declaration  is  assumed to represent a non-terminal symbol.
       The yacc utility shall report an error for any non-terminal symbol that
       does not appear on the left side of at least one grammar rule.

       Once  the  type, precedence, or token number of a name is specified, it
       shall not be changed. If the first declaration  of  a  token  does  not
       assign  a  token	 number,  yacc	shall assign a token number. Once this
       assignment is made, the token number shall not be changed  by  explicit
       assignment.

       The following declarators do not follow the previous pattern.

       The  following  declares	 the non-terminal name to be the start symbol,
       which represents the largest, most general structure described  by  the
       grammar rules:

	   %start name

       By  default,  it	 is the left-hand side of the first grammar rule; this
       default can be overridden with this declaration.

       The following declares the yacc value stack to be a union of the	 vari‐
       ous types of values desired.

	   %union { body of union (in C) }

       The  body of the union shall not contain unbalanced curly brace prepro‐
       cessing tokens.

       By default, the values returned by actions (see below) and the  lexical
       analyzer	 shall be of type int.	The yacc utility keeps track of types,
       and it shall insert corresponding union member names in order  to  per‐
       form strict type checking of the resulting parser.

       Alternatively,  given  that  at	least one <tag> construct is used, the
       union can be declared in a header file (which shall be included in  the
       declarations  section  by using a #include construct within %{ and %}),
       and a typedef used to define  the  symbol  YYSTYPE  to  represent  this
       union.  The  effect  of %union is to provide the declaration of YYSTYPE
       directly from the yacc input.

       C-language declarations and definitions can appear in the  declarations
       section, enclosed by the following marks:

	   %{ ... %}

       These  statements  shall	 be copied into the code file, and have global
       scope within it so that they can be used in the rules and program  sec‐
       tions.  The statements shall not contain "%}" outside a comment, string
       literal, or multi-character constant.

       The application shall ensure that the declarations  section  is	termi‐
       nated by the token %%.

   Grammar Rules in yacc
       The  rules  section  defines the context-free grammar to be accepted by
       the function yacc generates, and associates with those rules C-language
       actions and additional precedence information. The grammar is described
       below, and a formal definition follows.

       The rules section is comprised of one or more grammar rules. A  grammar
       rule has the form:

	   A : BODY ;

       The  symbol  A  represents  a  non-terminal name, and BODY represents a
       sequence of zero or more names, literals, and semantic actions that can
       then be followed by optional precedence rules.  Only the names and lit‐
       erals participate in the formation of the grammar; the semantic actions
       and precedence rules are used in other ways. The <colon> and the <semi‐
       colon> are yacc punctuation. If there are  several  successive  grammar
       rules  with  the	 same left-hand side, the <vertical-line> ('|') can be
       used to avoid rewriting the left-hand side; in  this  case  the	<semi‐
       colon> 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	 lexi‐
		 cally 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	 vari‐
		 ables.	 An  action  is	 one  or more C statements enclosed in
		 curly braces '{' and '}'.  The statements shall  not  contain
		 unbalanced curly brace preprocessing tokens.

		 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 cur‐
			   rent 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 deter‐
			   mined, a diagnostic message may be generated.

		 $<tag>number
			   These correspond exactly to the corresponding  sym‐
			   bols	 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 par‐
			   ticularly 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-termi‐
		 nal symbol on the left-hand side. The semantic action associ‐
		 ated  with  the  new rule shall be equivalent to the original
		 action. The use of actions within rules might introduce  con‐
		 flicts 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 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  follow‐
		 ing 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) con‐
       flict.  The  yacc  utility  shall  resolve  all conflicts, using either
       default rules or user-specified precedence rules.

       Conflicts are either shift/reduce conflicts or reduce/reduce conflicts.
       A  shift/reduce conflict is where, for a given state and lookahead sym‐
       bol,  both  a  shift  action  and  a  reduce  action  are  possible.  A
       reduce/reduce  conflict	is where, for a given state and lookahead sym‐
       bol, reductions by two different rules are possible.

       The rules below describe how to specify what actions  to	 take  when  a
       conflict	 occurs.  Not  all  shift/reduce conflicts can be successfully
       resolved this way because the conflict may be due  to  something	 other
       than  ambiguity,	 so  incautious	 use of these facilities can cause the
       language accepted by the parser to be much different  from  that	 which
       was intended. The description file shall contain sufficient information
       to understand the cause of the conflict. Where ambiguity is the	reason
       either  the  default  or explicit rules should be adequate to produce a
       working parser.

       The declared precedences and associativities (see Declarations Section)
       are used to resolve parsing conflicts as follows:

	1. A  precedence  and  associativity  is  associated with each grammar
	   rule; it is the precedence and associativity of the last  token  or
	   literal  in	the body of the rule. If the %prec keyword is used, it
	   overrides this default. Some grammar	 rules	might  not  have  both
	   precedence and associativity.

	2. If  there is a shift/reduce conflict, and both the grammar rule and
	   the input symbol have precedence and associativity associated  with
	   them,  then	the conflict is resolved in favor of the action (shift
	   or reduce) associated with the higher  precedence.  If  the	prece‐
	   dences  are the same, then the associativity is used; left associa‐
	   tive implies reduce, right associative implies shift, and non-asso‐
	   ciative implies an error in the string being parsed.

	3. When	 there	is  a shift/reduce conflict that cannot be resolved by
	   rule 2, the shift is done. Conflicts resolved this way are  counted
	   in the diagnostic output described in Error Handling.

	4. When	 there is a reduce/reduce conflict, a reduction is done by the
	   grammar rule that occurs earlier in the input  sequence.  Conflicts
	   resolved this way are counted in the diagnostic output described in
	   Error Handling.

       Conflicts resolved by precedence or associativity shall not be  counted
       in  the	shift/reduce  and  reduce/reduce conflicts reported by yacc on
       either standard error or in the description file.

   Error Handling
       The token error shall be reserved for error handling.  The  name	 error
       can  be used in grammar rules. It indicates places where the parser can
       recover from a syntax error. The default value of error shall  be  256.
       Its  value  can be changed using a %token declaration. The lexical ana‐
       lyzer should not return the value of error.

       The parser shall detect a syntax error when it is in a state where  the
       action  associated  with	 the  lookahead	 symbol	 is error.  A semantic
       action can cause the parser to initiate error handling by executing the
       macro  YYERROR.	When  YYERROR  is executed, the semantic action passes
       control back to the parser. YYERROR cannot be used outside of  semantic
       actions.

       When  the  parser  detects  a syntax error, it normally calls yyerror()
       with the character string "syntax error"	 as  its  argument.  The  call
       shall  not  be  made  if the parser is still recovering from a previous
       error when the error is detected. The parser is considered to be recov‐
       ering  from a previous error until the parser has shifted over at least
       three normal input symbols since the  last  error  was  detected	 or  a
       semantic	 action	 has executed the macro yyerrok.  The parser shall not
       call yyerror() when YYERROR is executed.

       The macro function YYRECOVERING shall return 1 if a  syntax  error  has
       been detected and the parser has not yet fully recovered from it.  Oth‐
       erwise, zero shall be returned.

       When a syntax error is detected by the parser, the parser  shall	 check
       if  a  previous syntax error has been detected. If a previous error was
       detected, and if no normal input symbols have been  shifted  since  the
       preceding error was detected, the parser checks if the lookahead symbol
       is an endmarker (see Interface to the Lexical Analyzer).	 If it is, the
       parser  shall  return  with  a non-zero value. Otherwise, the lookahead
       symbol shall be discarded and normal parsing shall resume.

       When YYERROR is executed or when the parser detects a syntax error  and
       no  previous error has been detected, or at least one normal input sym‐
       bol has been shifted since the previous error was detected, the	parser
       shall  pop  back	 one state at a time until the parse stack is empty or
       the current state allows a shift over error.  If the parser empties the
       parse stack, it shall return with a non-zero value. Otherwise, it shall
       shift over error and then resume normal parsing. If the parser reads  a
       lookahead symbol before the error was detected, that symbol shall still
       be the lookahead symbol when parsing is resumed.

       The macro yyerrok in a semantic action shall cause the parser to act as
       if it has fully recovered from any previous errors. The macro yyclearin
       shall cause the parser to discard the current lookahead token.  If  the
       current	lookahead token has not yet been read, yyclearin shall have no
       effect.

       The macro YYACCEPT shall cause the parser  to  return  with  the	 value
       zero.  The  macro  YYABORT shall cause the parser to return with a non-
       zero value.

   Interface to the Lexical Analyzer
       The yylex() function is an integer-valued function that returns a token
       number representing the kind of token read. If there is a value associ‐
       ated with the token returned by yylex()	(see  the  discussion  of  tag
       above), it shall be assigned to the external variable yylval.

       If the parser and yylex() do not agree on these token numbers, reliable
       communication between them cannot occur.	 For  (single-byte  character)
       literals, the token is simply the numeric value of the character in the
       current character set.  The numbers for other tokens can either be cho‐
       sen  by	yacc,  or chosen by the user. In either case, the #define con‐
       struct of C is used to allow yylex() to return these  numbers  symboli‐
       cally.  The  #define  statements	 are  put  into the code file, and the
       header file if that file is requested. The set of characters  permitted
       by  yacc	 in  an	 identifier  is larger than that permitted by C. Token
       names found to contain such characters shall not	 be  included  in  the
       #define declarations.

       If the token numbers are chosen by yacc, the tokens other than literals
       shall be assigned numbers  greater  than	 256,  although	 no  order  is
       implied.	 A  token can be explicitly assigned a number by following its
       first appearance in the declarations section with a number.  Names  and
       literals	 not  defined  this  way  retain their default definition. All
       token numbers assigned by yacc shall be unique and  distinct  from  the
       token  numbers used for literals and user-assigned tokens. If duplicate
       token numbers cause conflicts in parser generation, yacc	 shall	report
       an  error; otherwise, it is unspecified whether the token assignment is
       accepted or an error is reported.

       The end of the input is marked by a special token called the endmarker,
       which  has  a  token number that is zero or negative. (These values are
       invalid for any other token.) All lexical analyzers shall  return  zero
       or  negative as a token number upon reaching the end of their input. If
       the tokens up to, but excluding, the endmarker form  a  structure  that
       matches	the  start  symbol,  the parser shall accept the input. If the
       endmarker is seen in any other  context,	 it  shall  be	considered  an
       error.

   Completing the Program
       In  addition  to	 yyparse()  and	 yylex(),  the functions yyerror() and
       main() are required to make a complete  program.	 The  application  can
       supply main() and yyerror(), or those routines can be obtained from the
       yacc library.

   Yacc Library
       The following functions shall appear only in the yacc library  accessi‐
       ble through the −l y operand to c99; they can therefore be redefined by
       a conforming application:

       int main(void)
	     This function shall call yyparse() and exit with  an  unspecified
	     value. Other actions within this function are unspecified.

       int yyerror(const char *s)
	     This function shall write the NUL-terminated argument to 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	 YYDE‐
       BUG  is not already defined at compilation time (using the c99 −D YYDE‐
       BUG option, for example), YYDEBUG shall be set explicitly to  1.	  When
       −t is not specified, the code file shall be built such that, if YYDEBUG
       is not already defined, it shall be set explicitly to zero.

       The format of the debugging output is unspecified but includes at least
       enough  information  to determine the shift and reduce actions, and the
       input symbols. It also provides information about error recovery.

   Algorithms
       The parser constructed by yacc implements an LALR(1) parsing  algorithm
       as  documented  in the literature. It is unspecified whether the parser
       is table-driven or direct-coded.

       A parser generated by yacc shall never request  an  input  symbol  from
       yylex()	while  in  a state where the only actions other than the error
       action are reductions by a single rule.

       The literature of parsing theory defines these concepts.

   Limits
       The yacc utility may have several internal tables. The minimum maximums
       for these tables are shown in the following table. The exact meaning of
       these values is implementation-defined. The implementation shall define
       the  relationship  between  these values and between them and any error
       messages that the implementation may generate  should  it  run  out  of
       space  for any internal structure. An implementation may combine groups
       of these resources into a single pool as long as the total available to
       the  user  does	not  fall below the sum of the sizes 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  pro‐
       duced if the −v flag is present.

       The following sections are informative.

APPLICATION USAGE
       Historical  implementations  experience	name  conflicts	 on  the names
       yacc.tmp, yacc.acts, yacc.debug, y.tab.c, y.tab.h, and y.output if more
       than one copy of yacc is running in a single directory at one time. The
       −b option was added to overcome this problem. The  related  problem  of
       allowing	 multiple  yacc	 parsers  to  be  placed  in the same file was
       addressed by adding a −p option to override the	previously  hard-coded
       yy variable prefix.

       The  description of the −p option specifies the minimal set of function
       and variable names that cause conflict when multiple parsers are linked
       together.  YYSTYPE does not need to be changed. Instead, the programmer
       can use −b to give the header files  for	 different  parsers  different
       names,  and  then  the  file  with  the	yylex() for a given parser can
       include the header for that parser. Names such  as  yyclearerr  do  not
       need  to	 be changed because they are used only in the actions; they do
       not have linkage. It is	possible  that	an  implementation  has	 other
       names, either internal ones for implementing things such as yyclearerr,
       or providing non-standard features that it wants to change with −p.

       Unary operators that are the same token as a binary operator in general
       need  their  precedence adjusted. This is handled by the %prec advisory
       symbol associated with the particular grammar rule defining that	 unary
       operator.  (See	Grammar Rules in yacc.)	 Applications are not required
       to use this operator for unary operators, but the grammars that do  not
       require it are rare.

EXAMPLES
       Access  to the yacc library is obtained with library search operands to
       c99.  To use the yacc library main():

	   c99 y.tab.c −l y

       Both the lex library and the yacc library contain  main().   To	access
       the yacc main():

	   c99 y.tab.c lex.yy.c −l y −l l

       This  ensures  that  the	 yacc  library	is searched first, so that its
       main() is used.

       The historical yacc libraries have contained two simple functions  that
       are  normally  coded by the application programmer. These functions are
       similar to the following code:

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

	       setlocale(LC_ALL, "");

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

	   #include <stdio.h>

	   int yyerror(const char *msg)
	   {
	       (void) fprintf(stderr, "%s\n", msg);
	       return (0);
	   }

RATIONALE
       The references in Referenced Documents 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 POSIX.1‐2008. 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 lan‐
       guages.	They  are  all	reasonably orthogonal. In particular, a parser
       generator that accepts the full range of LR(1) grammars need not gener‐
       ate a table any more complex than one that accepts SLR(1) (a relatively
       weak class of LR grammars) for a grammar that  happens  to  be  SLR(1).
       Such  an implementation need not recognize the case, either; table com‐
       pression can yield the SLR(1) table (or one  even  smaller  than	 that)
       without	recognizing that the grammar is SLR(1).	 The speed of an LR(1)
       parser for any class is dependent more upon  the	 table	representation
       and  compression	 (or  the code generation if a direct parser is gener‐
       ated) than upon the class of grammar that the table generator handles.

       The speed of the parser generator is somewhat dependent upon the	 class
       of  grammar  it handles. However, the original Knuth article algorithms
       for constructing LR parsers were judged by its author to	 be  impracti‐
       cally slow at that time. Although full LR is more complex than LALR(1),
       as computer speeds and algorithms improve, the difference (in terms  of
       acceptable wall-clock execution time) is becoming less significant.

       Potential  authors  are	cautioned that the referenced DeRemer and Pen‐
       nello article previously cited identifies a bug (an over-simplification
       of  the	computation  of LALR(1) lookahead sets) in some of the LALR(1)
       algorithm statements that preceded it to publication. They should  take
       the time to seek out that paper, as well as current relevant work, par‐
       ticularly Aho's.

       The −b option was added to provide a  portable  method  for  permitting
       yacc  to	 work on multiple separate parsers in the same directory. If a
       directory contains more than one yacc grammar, and  both	 grammars  are
       constructed  at	the  same  time (by, for example, a parallel make pro‐
       gram), conflict results. While the solution is not historical practice,
       it  corrects  a known deficiency in historical implementations.	Corre‐
       sponding changes were made to all sections that	referenced  the	 file‐
       names  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 tex‐
       tual description shows there that the ';' is required at the end of the
       rule. The grammar and the implementation do not require this. (The  use
       of C_IDENTIFIER causes a reduce to occur in the right place.)

       Also, in that implementation, the constructs such as %token can be ter‐
       minated by a <semicolon>, but this is not permitted by the grammar. The
       keywords	 such  as  %token can also appear in uppercase, which is again
       not discussed. In most places where '%' is  used,  <backslash>  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 refer‐
       ence an ISO C standard union member, in practice conforming implementa‐
       tions  need  to	support	 only the set of characters for ISO C standard
       identifiers in this context.

       Some historical implementations are known to accept  actions  that  are
       terminated  by  a period. Historical implementations often allow '$' in
       names. A conforming implementation does not need to support  either  of
       these behaviors.

       Deciding when to use %prec illustrates the difficulty in specifying the
       behavior of yacc.  There may be situations in which the grammar is not,
       strictly speaking, in error, and yet yacc cannot interpret it unambigu‐
       ously. The resolution  of  ambiguities  in  the	grammar	 can  in  many
       instances  be  resolved	by  providing  additional information, such as
       using %type or %union declarations. It is often easier and  it  usually
       yields  a  smaller parser to take this alternative when it is appropri‐
       ate.

       The size and execution time of a program produced without  the  runtime
       debugging  code	is  usually  smaller and slightly faster in historical
       implementations.

       Statistics messages from several historical implementations include the
       following types of information:

	   n/512 terminals, n/300 non-terminals
	   n/600 grammar rules, n/1500 states
	   n shift/reduce, n reduce/reduce conflicts reported
	   n/350 working sets used
	   Memory: states, etc. n/15000, parser n/15000
	   n/600 distinct lookahead sets
	   n extra closures
	   n shift entries, n exceptions
	   n goto entries
	   n entries saved by goto default
	   Optimizer space used: input n/15000, output n/15000
	   n table entries, n zero
	   Maximum spread: n, Maximum offset: n

       The report of internal tables in the description file is left implemen‐
       tation-defined because all aspects of these limits are also implementa‐
       tion-defined.  Some  implementations  may  use dynamic allocation tech‐
       niques and have no specific limit values to report.

       The format of the y.output file is not given because  specification  of
       the  format was not seen to enhance applications portability. The list‐
       ing is primarily intended to help human users understand and debug  the
       parser;	use  of	 y.output  by a conforming application script would be
       unusual. Furthermore, implementations have not produced consistent out‐
       put  and	 no  popular  format  was apparent. The format selected by the
       implementation should be human-readable, in addition to the requirement
       that it be a text file.

       Standard	 error reports are not specifically described because they are
       seldom of use to conforming applications and there  was	no  reason  to
       restrict implementations.

       Some  implementations  recognize	 "={"  as equivalent to '{' because it
       appears in historical documentation. This construction  was  recognized
       and documented as obsolete as long ago as 1978, in the referenced Yacc:
       Yet Another Compiler-Compiler. This volume  of  POSIX.1‐2008  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

       The Base Definitions volume of  POSIX.1‐2008,  Chapter  8,  Environment
       Variables, Section 12.2, Utility Syntax Guidelines

COPYRIGHT
       Portions	 of  this text are reprinted and reproduced in electronic form
       from IEEE Std 1003.1, 2013 Edition, Standard for Information Technology
       --  Portable  Operating	System	Interface (POSIX), The Open Group Base
       Specifications Issue 7, Copyright (C) 2013 by the Institute of Electri‐
       cal  and	 Electronics  Engineers,  Inc  and  The	 Open Group.  (This is
       POSIX.1-2008 with the 2013 Technical Corrigendum	 1  applied.)  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.unix.org/online.html .

       Any typographical or formatting errors that appear  in  this  page  are
       most likely to have been introduced during the conversion of the source
       files to man page format. To report such errors,	 see  https://www.ker‐
       nel.org/doc/man-pages/reporting_bugs.html .

IEEE/The Open Group		     2013			      YACC(1P)
[top]

List of man pages available for Gentoo

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Tweet
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
....................................................................
Vote for polarhome
Free Shell Accounts :: the biggest list on the net