If conflict resolution makes states unreachable, remove those states,

[bison.git] / tests / existing.at

# Exercising Bison on actual grammars.                   -*- Autotest -*-

# Copyright (C) 1989, 1990, 1991, 1992, 2000, 2001, 2002, 2003, 2004, 2005
# Free Software Foundation, Inc.

# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2, or (at your option)
# any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
# 02110-1301, USA.

AT_BANNER([[Existing Grammars.]])
## ----------------- ##
## GNU AWK Grammar.  ##
## ----------------- ##

AT_SETUP([GNU AWK Grammar])

# We have been careful to strip all the actions excepts the
# mid-rule actions.  We rely on %expect to check that there are
# indeed 65 SR conflicts.
#
# Bison was once wrong, due to an incorrect computation of nullable.
# It reported 485 SR conflicts!

AT_DATA([[input.y]],
[[%expect 65

%token FUNC_CALL NAME REGEXP
%token ERROR
%token YNUMBER YSTRING
%token RELOP APPEND_OP
%token ASSIGNOP MATCHOP NEWLINE CONCAT_OP
%token LEX_BEGIN LEX_END LEX_IF LEX_ELSE LEX_RETURN LEX_DELETE
%token LEX_WHILE LEX_DO LEX_FOR LEX_BREAK LEX_CONTINUE
%token LEX_PRINT LEX_PRINTF LEX_NEXT LEX_EXIT LEX_FUNCTION
%token LEX_GETLINE LEX_NEXTFILE
%token LEX_IN
%token LEX_AND LEX_OR INCREMENT DECREMENT
%token LEX_BUILTIN LEX_LENGTH

/* Lowest to highest */
%right ASSIGNOP
%right '?' ':'
%left LEX_OR
%left LEX_AND
%left LEX_GETLINE
%nonassoc LEX_IN
%left FUNC_CALL LEX_BUILTIN LEX_LENGTH
%nonassoc ','
%nonassoc MATCHOP
%nonassoc RELOP '<' '>' '|' APPEND_OP TWOWAYIO
%left CONCAT_OP
%left YSTRING YNUMBER
%left '+' '-'
%left '*' '/' '%'
%right '!' UNARY
%right '^'
%left INCREMENT DECREMENT
%left '$'
%left '(' ')'
%%

start
	: opt_nls program opt_nls
	;

program
	: rule
	| program rule
	| error
	| program error
	| /* empty */
	;

rule
	: LEX_BEGIN {} action
	| LEX_END {}   action
	| LEX_BEGIN statement_term
	| LEX_END statement_term
	| pattern action
	| action
	| pattern statement_term
	| function_prologue function_body
	;

func_name
	: NAME
	| FUNC_CALL
	| lex_builtin
	;

lex_builtin
	: LEX_BUILTIN
	| LEX_LENGTH
	;

function_prologue
	: LEX_FUNCTION {} func_name '(' opt_param_list r_paren opt_nls
	;

function_body
	: l_brace statements r_brace opt_semi opt_nls
	| l_brace r_brace opt_semi opt_nls
	;

pattern
	: exp
	| exp ',' exp
	;

regexp
	/*
	 * In this rule, want_regexp tells yylex that the next thing
	 * is a regexp so it should read up to the closing slash.
	 */
	: '/' {} REGEXP '/'
	;

action
	: l_brace statements r_brace opt_semi opt_nls
	| l_brace r_brace opt_semi opt_nls
	;

statements
	: statement
	| statements statement
	| error
	| statements error
	;

statement_term
	: nls
	| semi opt_nls
	;

statement
	: semi opt_nls
	| l_brace r_brace
	| l_brace statements r_brace
	| if_statement
	| LEX_WHILE '(' exp r_paren opt_nls statement
	| LEX_DO opt_nls statement LEX_WHILE '(' exp r_paren opt_nls
	| LEX_FOR '(' NAME LEX_IN NAME r_paren opt_nls statement
	| LEX_FOR '(' opt_exp semi opt_nls exp semi opt_nls opt_exp r_paren opt_nls statement
	| LEX_FOR '(' opt_exp semi opt_nls semi opt_nls opt_exp r_paren opt_nls statement
	| LEX_BREAK statement_term
	| LEX_CONTINUE statement_term
	| print '(' expression_list r_paren output_redir statement_term
	| print opt_rexpression_list output_redir statement_term
	| LEX_NEXT statement_term
	| LEX_NEXTFILE statement_term
	| LEX_EXIT opt_exp statement_term
	| LEX_RETURN {} opt_exp statement_term
	| LEX_DELETE NAME '[' expression_list ']' statement_term
	| LEX_DELETE NAME  statement_term
	| exp statement_term
	;

print
	: LEX_PRINT
	| LEX_PRINTF
	;

if_statement
	: LEX_IF '(' exp r_paren opt_nls statement
	| LEX_IF '(' exp r_paren opt_nls statement
	     LEX_ELSE opt_nls statement
	;

nls
	: NEWLINE
	| nls NEWLINE
	;

opt_nls
	: /* empty */
	| nls
	;

input_redir
	: /* empty */
	| '<' simp_exp
	;

output_redir
	: /* empty */
	| '>' exp
	| APPEND_OP exp
	| '|' exp
	| TWOWAYIO exp
	;

opt_param_list
	: /* empty */
	| param_list
	;

param_list
	: NAME
	| param_list comma NAME
	| error
	| param_list error
	| param_list comma error
	;

/* optional expression, as in for loop */
opt_exp
	: /* empty */
	| exp
	;

opt_rexpression_list
	: /* empty */
	| rexpression_list
	;

rexpression_list
	: rexp
	| rexpression_list comma rexp
	| error
	| rexpression_list error
	| rexpression_list error rexp
	| rexpression_list comma error
	;

opt_expression_list
	: /* empty */
	| expression_list
	;

expression_list
	: exp
	| expression_list comma exp
	| error
	| expression_list error
	| expression_list error exp
	| expression_list comma error
	;

/* Expressions, not including the comma operator.  */
exp	: variable ASSIGNOP {} exp
	| '(' expression_list r_paren LEX_IN NAME
	| exp '|' LEX_GETLINE opt_variable
	| exp TWOWAYIO LEX_GETLINE opt_variable
	| LEX_GETLINE opt_variable input_redir
	| exp LEX_AND exp
	| exp LEX_OR exp
	| exp MATCHOP exp
	| regexp
	| '!' regexp %prec UNARY
	| exp LEX_IN NAME
	| exp RELOP exp
	| exp '<' exp
	| exp '>' exp
	| exp '?' exp ':' exp
	| simp_exp
	| exp simp_exp %prec CONCAT_OP
	;

rexp
	: variable ASSIGNOP {} rexp
	| rexp LEX_AND rexp
	| rexp LEX_OR rexp
	| LEX_GETLINE opt_variable input_redir
	| regexp
	| '!' regexp %prec UNARY
	| rexp MATCHOP rexp
	| rexp LEX_IN NAME
	| rexp RELOP rexp
	| rexp '?' rexp ':' rexp
	| simp_exp
	| rexp simp_exp %prec CONCAT_OP
	;

simp_exp
	: non_post_simp_exp
	/* Binary operators in order of decreasing precedence.  */
	| simp_exp '^' simp_exp
	| simp_exp '*' simp_exp
	| simp_exp '/' simp_exp
	| simp_exp '%' simp_exp
	| simp_exp '+' simp_exp
	| simp_exp '-' simp_exp
	| variable INCREMENT
	| variable DECREMENT
	;

non_post_simp_exp
	: '!' simp_exp %prec UNARY
	| '(' exp r_paren
	| LEX_BUILTIN
	  '(' opt_expression_list r_paren
	| LEX_LENGTH '(' opt_expression_list r_paren
	| LEX_LENGTH
	| FUNC_CALL '(' opt_expression_list r_paren
	| variable
	| INCREMENT variable
	| DECREMENT variable
	| YNUMBER
	| YSTRING
	| '-' simp_exp    %prec UNARY
	| '+' simp_exp    %prec UNARY
	;

opt_variable
	: /* empty */
	| variable
	;

variable
	: NAME
	| NAME '[' expression_list ']'
	| '$' non_post_simp_exp
	;

l_brace
	: '{' opt_nls
	;

r_brace
	: '}' opt_nls
	;

r_paren
	: ')'
	;

opt_semi
	: /* empty */
	| semi
	;

semi
	: ';'
	;

comma	: ',' opt_nls
	;

%%
]])

# Pass plenty of options, to exercise plenty of code, even if we
# don't actually check the output.  But SEGV is watching us, and
# so might do dmalloc.
AT_CHECK([[bison --verbose --defines input.y]])

AT_CLEANUP

## ----------------- ##
## GNU Cim Grammar.  ##
## ----------------- ##

AT_SETUP([GNU Cim Grammar])

# GNU Cim, the GNU Simula 87 Compiler.

# Bison was once wrong, due to an incorrect computation of the RR conflicts.
# It reported 80 SR && 99 RR conflicts instead of 78/10!!!

AT_DATA([[input.y]],
[[%union {}

%token
	HACTIVATE HAFTER /*HAND*/ HARRAY HAT
	HBEFORE HBEGIN HBOOLEAN
	HCHARACTER HCLASS /*HCOMMENT*/ HCONC
	HDELAY HDO
	HELSE HEND HEQ /*HEQV*/ HEXTERNAL
	HFOR
	HGE HGO HGOTO HGT
	HHIDDEN
	HIF /*HIMP*/ HIN HINNER HINSPECT HINTEGER HIS
	HLABEL HLE HLONG HLT
	HNAME HNE HNEW HNONE /*HNOT*/ HNOTEXT
	/*HOR*/ HOTHERWISE
	HPRIOR HPROCEDURE HPROTECTED
	HQUA
	HREACTIVATE HREAL HREF
	HSHORT HSTEP HSWITCH
	HTEXT HTHEN HTHIS HTO
	HUNTIL
	HVALUE HVAR HVIRTUAL
	HWHEN HWHILE

	HASSIGNVALUE HASSIGNREF
	/*HDOT*/ HPAREXPSEPARATOR HLABELSEPARATOR HSTATEMENTSEPARATOR
	HBEGPAR HENDPAR
	HEQR HNER
	HADD HSUB HMUL HDIV HINTDIV HEXP
	HDOTDOTDOT

%token HIDENTIFIER
%token HBOOLEANKONST HINTEGERKONST HCHARACTERKONST
%token HREALKONST
%token HTEXTKONST


%right HASSIGN
%left   HORELSE
%left   HANDTHEN
%left   HEQV
%left   HIMP
%left   HOR
%left   HAND

%left   HNOT

%left HVALRELOPERATOR HREFRELOPERATOR HOBJRELOPERATOR

%left	HCONC

%left HTERMOPERATOR
%left UNEAR
%left HFACTOROPERATOR
%left         HPRIMARYOPERATOR

%left   HQUA

%left   HDOT

%start  MAIN_MODULE
%%
/* GRAMATIKK FOR PROGRAM MODULES */
MAIN_MODULE     :       {}
			MODULS
		|	error HSTATEMENTSEPARATOR MBEE_DECLSTMS
		;
EXT_DECLARATION	:	HEXTERNAL
			MBEE_TYPE
			HPROCEDURE
				{}
			EXT_LIST
		|
			HEXTERNAL
			HIDENTIFIER
			HPROCEDURE
				{}
			HIDENTIFIER {}
			EXTERNAL_KIND_ITEM
		|	HEXTERNAL
			HCLASS
				{}
			EXT_LIST

		;
EXTERNAL_KIND_ITEM:	EXT_IDENT
			HOBJRELOPERATOR
				{}
			MBEE_TYPE HPROCEDURE
			HIDENTIFIER
				{}
			HEADING EMPTY_BLOCK
				{}
/*		|
			EXT_IDENT
				{}
			MBEE_REST_EXT_LIST
		;
MBEE_REST_EXT_LIST:	/* EMPTY
		|	HPAREXPSEPARATOR EXT_KIND_LIST
		;
EXT_KIND_LIST	:	EXT_KIND_ITEM
		|	EXT_KIND_LIST HPAREXPSEPARATOR EXT_KIND_ITEM
		;
EXT_KIND_ITEM	:	HIDENTIFIER
			EXT_IDENT
				{}*/
		;
EMPTY_BLOCK	:	/*EMPT*/
		|	HBEGIN HEND
		;
EXT_LIST	:	EXT_ITEM
		|	EXT_LIST HPAREXPSEPARATOR EXT_ITEM
		;
EXT_ITEM	:	HIDENTIFIER
			EXT_IDENT
		;
EXT_IDENT	:	/* EMPTY */
		|	HVALRELOPERATOR {}
			HTEXTKONST
		;
/* GRAMATIKK FOR TYPER */
NO_TYPE         :       /*EMPT*/
		;
MBEE_TYPE       :       NO_TYPE
		|       TYPE
		;
TYPE            :       HREF HBEGPAR
			HIDENTIFIER
				{}
			HENDPAR
		|       HTEXT
		|       HBOOLEAN
		|       HCHARACTER
		|       HSHORT HINTEGER
		|       HINTEGER
		|       HREAL
		|       HLONG HREAL
		;

/* GRAMATIKK FOR DEL AV SETNINGER */
MBEE_ELSE_PART  :       /*EMPT*/
/*		|	HELSE
			HIF
			EXPRESSION
			HTHEN   {}
			BLOCK   {}
			MBEE_ELSE_PART          {}*/
		|       HELSE   {}
			BLOCK
		;
FOR_LIST        :       FOR_LIST_ELEMENT
		|       FOR_LIST_ELEMENT
			HPAREXPSEPARATOR
			FOR_LIST
		;
FOR_LIST_ELEMENT:       EXPRESSION
			MBEE_F_L_EL_R_PT
		;
MBEE_F_L_EL_R_PT:       /*EMPT*/
		|       HWHILE
			EXPRESSION
		|       HSTEP
			EXPRESSION
			HUNTIL
			EXPRESSION
		;
GOTO            :       HGO
			HTO
		|       HGOTO
		;
CONN_STATE_R_PT :       WHEN_CLAUSE_LIST
		|       HDO   {}
			BLOCK
		;
WHEN_CLAUSE_LIST:       HWHEN
			HIDENTIFIER
			HDO    {}
			BLOCK
		|       WHEN_CLAUSE_LIST
			HWHEN
			HIDENTIFIER
			HDO    {}
			BLOCK
		;
MBEE_OTWI_CLAUS :       /*EMPT*/
		|       HOTHERWISE {}

			BLOCK
		;
ACTIVATOR	:	HACTIVATE
		|	HREACTIVATE
		;
SCHEDULE	:	/*EMPT*/
		|	ATDELAY EXPRESSION	{}
			PRIOR
		|	BEFOREAFTER		{}
			EXPRESSION
		;
ATDELAY		:	HAT
		|	HDELAY
		;
BEFOREAFTER	:	HBEFORE
		|	HAFTER
		;
PRIOR		:	/*EMPT*/
		|	HPRIOR
		;
/* GRAMATIKK FOR SETNINGER OG DEKLARASJONER */
MODULSTATEMENT  :       HWHILE
			EXPRESSION
			HDO     {}
			BLOCK
		|       HIF
			EXPRESSION
			HTHEN   {}
			BLOCK   {}
			MBEE_ELSE_PART
		|       HFOR
			HIDENTIFIER
			HASSIGN {}
			FOR_LIST
			HDO     {}
			BLOCK
		|       GOTO
			EXPRESSION
		|       HINSPECT
			EXPRESSION              {}
			CONN_STATE_R_PT
				{}
			MBEE_OTWI_CLAUS
		|       HINNER
		|       HIDENTIFIER
			HLABELSEPARATOR
				{}
			DECLSTATEMENT
		|       EXPRESSION_SIMP
			HBEGIN
				{}
			IMPORT_SPEC_MODULE
				{}
			MBEE_DECLSTMS
			HEND
		|	EXPRESSION_SIMP HBEGIN error HSTATEMENTSEPARATOR
			MBEE_DECLSTMS HEND
		|	EXPRESSION_SIMP HBEGIN error HEND
		|       EXPRESSION_SIMP
		|	ACTIVATOR EXPRESSION SCHEDULE
		|       HBEGIN
				{}
			MBEE_DECLSTMS
			HEND
		|       MBEE_TYPE HPROCEDURE
			HIDENTIFIER
				{}
			HEADING BLOCK
		|       HIDENTIFIER
			HCLASS
			NO_TYPE
				{}
			IMPORT_SPEC_MODULE
			HIDENTIFIER
				{}
			HEADING
			BLOCK
		|       HCLASS
			NO_TYPE
			HIDENTIFIER
				{}
			HEADING
			BLOCK
		|       EXT_DECLARATION
		|       /*EMPT*/
		;
IMPORT_SPEC_MODULE:
		;
DECLSTATEMENT	:	MODULSTATEMENT
		|       TYPE
			HIDENTIFIER
			MBEE_CONSTANT
			HPAREXPSEPARATOR
				{}
			IDENTIFIER_LISTC
		|       TYPE
			HIDENTIFIER
			MBEE_CONSTANT
		|       MBEE_TYPE
			HARRAY  {}
			ARR_SEGMENT_LIST
		|       HSWITCH
			HIDENTIFIER
			HASSIGN {}
			SWITCH_LIST
		;
BLOCK           :       DECLSTATEMENT
		|       HBEGIN MBEE_DECLSTMS HEND
		|	HBEGIN error HSTATEMENTSEPARATOR MBEE_DECLSTMS HEND
		|	HBEGIN error HEND
		;
MBEE_DECLSTMS   :       MBEE_DECLSTMSU
		;
MBEE_DECLSTMSU  :       DECLSTATEMENT
		|       MBEE_DECLSTMSU
			HSTATEMENTSEPARATOR
			DECLSTATEMENT
		;
MODULS		:	MODULSTATEMENT
		|	MODULS HSTATEMENTSEPARATOR MODULSTATEMENT
		;
/* GRAMATIKK FOR DEL AV DEKLARASJONER */
ARR_SEGMENT_LIST:       ARR_SEGMENT
		|       ARR_SEGMENT_LIST
			HPAREXPSEPARATOR
			ARR_SEGMENT
		;
ARR_SEGMENT	:       ARRAY_SEGMENT
			HBEGPAR
			BAUND_PAIR_LIST HENDPAR
		;
ARRAY_SEGMENT   :       ARRAY_SEGMENT_EL        {}

		|       ARRAY_SEGMENT_EL
			HPAREXPSEPARATOR
			ARRAY_SEGMENT
		;
ARRAY_SEGMENT_EL:       HIDENTIFIER
		;
BAUND_PAIR_LIST :       BAUND_PAIR
		|       BAUND_PAIR
			HPAREXPSEPARATOR
			BAUND_PAIR_LIST
		;
BAUND_PAIR      :       EXPRESSION
			HLABELSEPARATOR
			EXPRESSION
		;
SWITCH_LIST     :       EXPRESSION
		|       EXPRESSION
			HPAREXPSEPARATOR
			SWITCH_LIST
		;
HEADING         :       MBEE_FMAL_PAR_P HSTATEMENTSEPARATOR {}
			MBEE_MODE_PART  {}
			MBEE_SPEC_PART  {}
			MBEE_PROT_PART  {}
			MBEE_VIRT_PART
		;
MBEE_FMAL_PAR_P :       /*EMPT*/
		|       FMAL_PAR_PART
		;
FMAL_PAR_PART   :       HBEGPAR NO_TYPE
			MBEE_LISTV HENDPAR
		;
MBEE_LISTV      :       /*EMPT*/
		|       LISTV
		;
LISTV           :       HIDENTIFIER
		|	FPP_CATEG HDOTDOTDOT
		|       HIDENTIFIER     {}
			HPAREXPSEPARATOR LISTV
		|       FPP_SPEC
		|       FPP_SPEC
			HPAREXPSEPARATOR LISTV
		;
FPP_HEADING     :       HBEGPAR NO_TYPE
			FPP_MBEE_LISTV HENDPAR
		;
FPP_MBEE_LISTV  :       /*EMPT*/
		|       FPP_LISTV
		;
FPP_LISTV       :	FPP_CATEG HDOTDOTDOT
		|       FPP_SPEC
		|       FPP_SPEC
			HPAREXPSEPARATOR LISTV
		;
FPP_SPEC        :       FPP_CATEG SPECIFIER HIDENTIFIER
		|	FPP_CATEG FPP_PROC_DECL_IN_SPEC
		;
FPP_CATEG       :       HNAME HLABELSEPARATOR
		|       HVALUE HLABELSEPARATOR
		|       HVAR HLABELSEPARATOR
		|       /*EMPT*/
		;
FPP_PROC_DECL_IN_SPEC:	MBEE_TYPE HPROCEDURE
			HIDENTIFIER
					{}
			FPP_HEADING {} { /* Yes, two "final" actions. */ }
		;
IDENTIFIER_LISTV:       HIDENTIFIER
		|	HDOTDOTDOT
		|       HIDENTIFIER     {}
			HPAREXPSEPARATOR IDENTIFIER_LISTV
		;
MBEE_MODE_PART  :       /*EMPT*/
		|       MODE_PART
		;
MODE_PART       :       NAME_PART
		|       VALUE_PART
		|       VAR_PART
		|       NAME_PART VALUE_PART
		|       VALUE_PART NAME_PART
		|       NAME_PART VAR_PART
		|       VAR_PART NAME_PART
		|       VALUE_PART VAR_PART
		|       VAR_PART VALUE_PART
		|       VAR_PART NAME_PART VALUE_PART
		|       NAME_PART VAR_PART VALUE_PART
		|       NAME_PART VALUE_PART VAR_PART
		|       VAR_PART VALUE_PART NAME_PART
		|       VALUE_PART VAR_PART NAME_PART
		|       VALUE_PART NAME_PART VAR_PART
		;
NAME_PART       :       HNAME           {}
			IDENTIFIER_LISTV
			HSTATEMENTSEPARATOR
		;
VAR_PART        :       HVAR            {}
			IDENTIFIER_LISTV
			HSTATEMENTSEPARATOR
		;
VALUE_PART      :       HVALUE          {}
			IDENTIFIER_LISTV HSTATEMENTSEPARATOR
		;
MBEE_SPEC_PART  :       /*EMPT*/
		|       SPEC_PART
		;
SPEC_PART       :       ONE_SPEC
		|       SPEC_PART ONE_SPEC
		;
ONE_SPEC	:	SPECIFIER IDENTIFIER_LIST HSTATEMENTSEPARATOR
		|	NO_TYPE HPROCEDURE HIDENTIFIER HOBJRELOPERATOR
			  {}
			PROC_DECL_IN_SPEC HSTATEMENTSEPARATOR
		|       FPP_PROC_DECL_IN_SPEC HSTATEMENTSEPARATOR
		|       MBEE_TYPE HPROCEDURE HIDENTIFIER HSTATEMENTSEPARATOR
		|       MBEE_TYPE HPROCEDURE HIDENTIFIER HPAREXPSEPARATOR
			IDENTIFIER_LIST HSTATEMENTSEPARATOR
		;
SPECIFIER       :       TYPE
		|       MBEE_TYPE
			HARRAY
		|       HLABEL
		|       HSWITCH
		;
PROC_DECL_IN_SPEC:	MBEE_TYPE HPROCEDURE
			HIDENTIFIER
					{}
			HEADING
					{}
			MBEE_BEGIN_END
		;
MBEE_BEGIN_END	:	/* EMPTY */
		|	HBEGIN HEND
		;
MBEE_PROT_PART  :       /*EMPT*/
		|       PROTECTION_PART
		;
PROTECTION_PART :       PROT_SPECIFIER IDENTIFIER_LIST
			HSTATEMENTSEPARATOR
		|       PROTECTION_PART  PROT_SPECIFIER
			IDENTIFIER_LIST HSTATEMENTSEPARATOR
		;
PROT_SPECIFIER  :       HHIDDEN
		|       HPROTECTED
		|       HHIDDEN
			HPROTECTED
		|       HPROTECTED
			HHIDDEN
		;
MBEE_VIRT_PART  :       /*EMPT*/
		|       VIRTUAL_PART
		;
VIRTUAL_PART    :       HVIRTUAL
			HLABELSEPARATOR
			MBEE_SPEC_PART
		;
IDENTIFIER_LIST :       HIDENTIFIER
		|       IDENTIFIER_LIST HPAREXPSEPARATOR
			HIDENTIFIER
		;
IDENTIFIER_LISTC:       HIDENTIFIER
			MBEE_CONSTANT
		|       IDENTIFIER_LISTC HPAREXPSEPARATOR
			HIDENTIFIER
			MBEE_CONSTANT
		;
MBEE_CONSTANT	:	/* EMPTY */
		|	HVALRELOPERATOR
				{}
			EXPRESSION
		;

/* GRAMATIKK FOR UTTRYKK */
EXPRESSION      :       EXPRESSION_SIMP
		|       HIF
			EXPRESSION
			HTHEN
			EXPRESSION
			HELSE
			EXPRESSION
		;
EXPRESSION_SIMP :	EXPRESSION_SIMP
			HASSIGN
			EXPRESSION
		|

			EXPRESSION_SIMP
			HCONC
			EXPRESSION_SIMP
		|       EXPRESSION_SIMP HOR
			HELSE
			EXPRESSION_SIMP
			%prec HORELSE
		|       EXPRESSION_SIMP HAND
			HTHEN
			EXPRESSION_SIMP
			%prec HANDTHEN
		|       EXPRESSION_SIMP
			HEQV EXPRESSION_SIMP
		|       EXPRESSION_SIMP
			HIMP EXPRESSION_SIMP
		|       EXPRESSION_SIMP
			HOR EXPRESSION_SIMP
		|       EXPRESSION_SIMP
			HAND EXPRESSION_SIMP
		|       HNOT EXPRESSION_SIMP
		|       EXPRESSION_SIMP
			HVALRELOPERATOR
			EXPRESSION_SIMP
		|       EXPRESSION_SIMP
			HREFRELOPERATOR
			EXPRESSION_SIMP
		|       EXPRESSION_SIMP
			HOBJRELOPERATOR
			EXPRESSION_SIMP
		|       HTERMOPERATOR
			EXPRESSION_SIMP %prec UNEAR
		|       EXPRESSION_SIMP
			HTERMOPERATOR
			EXPRESSION_SIMP
		|       EXPRESSION_SIMP
			HFACTOROPERATOR
			EXPRESSION_SIMP
		|       EXPRESSION_SIMP
			HPRIMARYOPERATOR
			EXPRESSION_SIMP
		|       HBEGPAR
			EXPRESSION HENDPAR
		|       HTEXTKONST
		|       HCHARACTERKONST
		|       HREALKONST
		|       HINTEGERKONST
		|       HBOOLEANKONST
		|       HNONE
		|       HIDENTIFIER
				{}
			MBEE_ARG_R_PT
		|       HTHIS HIDENTIFIER
		|       HNEW
			HIDENTIFIER
			ARG_R_PT
		|       EXPRESSION_SIMP
			HDOT
			EXPRESSION_SIMP
		|       EXPRESSION_SIMP
			HQUA HIDENTIFIER
		;
ARG_R_PT        :       /*EMPTY*/
		|       HBEGPAR
			ARGUMENT_LIST HENDPAR
		;
MBEE_ARG_R_PT   :       /*EMPTY*/
		|       HBEGPAR
			ARGUMENT_LIST HENDPAR
		;
ARGUMENT_LIST   :       EXPRESSION
		|       EXPRESSION
			HPAREXPSEPARATOR
			ARGUMENT_LIST
		;
%%
]])

# Pass plenty of options, to exercise plenty of code, even if we
# don't actually check the output.  But SEGV is watching us, and
# so might do dmalloc.
AT_CHECK([[bison --verbose --defines input.y]], 0, [],
[[input.y: conflicts: 78 shift/reduce, 10 reduce/reduce
]])

AT_CHECK([[grep '^State.*conflicts:' input.output]], 0,
[[State 64 conflicts: 14 shift/reduce
State 164 conflicts: 1 shift/reduce
State 201 conflicts: 33 shift/reduce, 4 reduce/reduce
State 206 conflicts: 1 shift/reduce
State 240 conflicts: 1 shift/reduce
State 335 conflicts: 9 shift/reduce, 2 reduce/reduce
State 356 conflicts: 1 shift/reduce
State 360 conflicts: 9 shift/reduce, 2 reduce/reduce
State 427 conflicts: 9 shift/reduce, 2 reduce/reduce
]])

AT_CLEANUP

## ----------------- ##
## GNU pic Grammar.  ##
## ----------------- ##

AT_SETUP([GNU pic Grammar])

# GNU pic, part of groff.

# Bison once reported shift/reduce conflicts that it shouldn't have.

AT_DATA([[input.y]],
[[%union {}

%token LABEL
%token VARIABLE
%token NUMBER
%token TEXT
%token COMMAND_LINE
%token DELIMITED
%token ORDINAL
%token TH
%token LEFT_ARROW_HEAD
%token RIGHT_ARROW_HEAD
%token DOUBLE_ARROW_HEAD
%token LAST
%token UP
%token DOWN
%token LEFT
%token RIGHT
%token BOX
%token CIRCLE
%token ELLIPSE
%token ARC
%token LINE
%token ARROW
%token MOVE
%token SPLINE
%token HEIGHT
%token RADIUS
%token WIDTH
%token DIAMETER
%token FROM
%token TO
%token AT
%token WITH
%token BY
%token THEN
%token SOLID
%token DOTTED
%token DASHED
%token CHOP
%token SAME
%token INVISIBLE
%token LJUST
%token RJUST
%token ABOVE
%token BELOW
%token OF
%token THE
%token WAY
%token BETWEEN
%token AND
%token HERE
%token DOT_N
%token DOT_E
%token DOT_W
%token DOT_S
%token DOT_NE
%token DOT_SE
%token DOT_NW
%token DOT_SW
%token DOT_C
%token DOT_START
%token DOT_END
%token DOT_X
%token DOT_Y
%token DOT_HT
%token DOT_WID
%token DOT_RAD
%token SIN
%token COS
%token ATAN2
%token LOG
%token EXP
%token SQRT
%token K_MAX
%token K_MIN
%token INT
%token RAND
%token SRAND
%token COPY
%token THRU
%token TOP
%token BOTTOM
%token UPPER
%token LOWER
%token SH
%token PRINT
%token CW
%token CCW
%token FOR
%token DO
%token IF
%token ELSE
%token ANDAND
%token OROR
%token NOTEQUAL
%token EQUALEQUAL
%token LESSEQUAL
%token GREATEREQUAL
%token LEFT_CORNER
%token RIGHT_CORNER
%token NORTH
%token SOUTH
%token EAST
%token WEST
%token CENTER
%token END
%token START
%token RESET
%token UNTIL
%token PLOT
%token THICKNESS
%token FILL
%token COLORED
%token OUTLINED
%token SHADED
%token ALIGNED
%token SPRINTF
%token COMMAND

%left '.'

/* this ensures that plot 17 "%g" parses as (plot 17 "%g") */
%left PLOT
%left TEXT SPRINTF

/* give text adjustments higher precedence than TEXT, so that
box "foo" above ljust == box ("foo" above ljust)
*/

%left LJUST RJUST ABOVE BELOW

%left LEFT RIGHT
/* Give attributes that take an optional expression a higher
precedence than left and right, so that eg `line chop left'
parses properly. */
%left CHOP SOLID DASHED DOTTED UP DOWN FILL COLORED OUTLINED
%left LABEL

%left VARIABLE NUMBER '(' SIN COS ATAN2 LOG EXP SQRT K_MAX K_MIN INT RAND SRAND LAST
%left ORDINAL HERE '`'

%left BOX CIRCLE ELLIPSE ARC LINE ARROW SPLINE '[' /* ] */

/* these need to be lower than '-' */
%left HEIGHT RADIUS WIDTH DIAMETER FROM TO AT THICKNESS

/* these must have higher precedence than CHOP so that `label %prec CHOP'
works */
%left DOT_N DOT_E DOT_W DOT_S DOT_NE DOT_SE DOT_NW DOT_SW DOT_C
%left DOT_START DOT_END TOP BOTTOM LEFT_CORNER RIGHT_CORNER
%left UPPER LOWER NORTH SOUTH EAST WEST CENTER START END

%left ','
%left OROR
%left ANDAND
%left EQUALEQUAL NOTEQUAL
%left '<' '>' LESSEQUAL GREATEREQUAL

%left BETWEEN OF
%left AND

%left '+' '-'
%left '*' '/' '%'
%right '!'
%right '^'

%%

top:
	optional_separator
	| element_list
	;

element_list:
	optional_separator middle_element_list optional_separator
	;

middle_element_list:
	element
	| middle_element_list separator element
	;

optional_separator:
	/* empty */
	| separator
	;

separator:
	';'
	| separator ';'
	;

placeless_element:
	VARIABLE '=' any_expr
	| VARIABLE ':' '=' any_expr
	| UP
	| DOWN
	| LEFT
	| RIGHT
	| COMMAND_LINE
	| COMMAND print_args
	| PRINT print_args
	| SH
		{}
	  DELIMITED
	| COPY TEXT
	| COPY TEXT THRU
		{}
	  DELIMITED
		{}
	  until
	| COPY THRU
		{}
	  DELIMITED
		{}
	  until
	| FOR VARIABLE '=' expr TO expr optional_by DO
		{}
	  DELIMITED
	| simple_if
	| simple_if ELSE
		{}
	  DELIMITED
	| reset_variables
	| RESET
	;

reset_variables:
	RESET VARIABLE
	| reset_variables VARIABLE
	| reset_variables ',' VARIABLE
	;

print_args:
	print_arg
	| print_args print_arg
	;

print_arg:
	expr							%prec ','
	| text
	| position						%prec ','
	;

simple_if:
	IF any_expr THEN
		{}
	DELIMITED
	;

until:
	/* empty */
	| UNTIL TEXT
	;

any_expr:
	expr
	| text_expr
	;

text_expr:
	text EQUALEQUAL text
	| text NOTEQUAL text
	| text_expr ANDAND text_expr
	| text_expr ANDAND expr
	| expr ANDAND text_expr
	| text_expr OROR text_expr
	| text_expr OROR expr
	| expr OROR text_expr
	| '!' text_expr
	;

optional_by:
	/* empty */
	| BY expr
	| BY '*' expr
	;

element:
	object_spec
	| LABEL ':' optional_separator element
	| LABEL ':' optional_separator position_not_place
	| LABEL ':' optional_separator place
	| '{}'
		{}
	  optional_element
	| placeless_element
	;

optional_element:
	/* empty */
	| element
	;

object_spec:
	BOX
	| CIRCLE
	| ELLIPSE
	| ARC
	| LINE
	| ARROW
	| MOVE
	| SPLINE
	| text							%prec TEXT
	| PLOT expr
	| PLOT expr text
	| '['
		{}
	  element_list ']'
	| object_spec HEIGHT expr
	| object_spec RADIUS expr
	| object_spec WIDTH expr
	| object_spec DIAMETER expr
	| object_spec expr					%prec HEIGHT
	| object_spec UP
	| object_spec UP expr
	| object_spec DOWN
	| object_spec DOWN expr
	| object_spec RIGHT
	| object_spec RIGHT expr
	| object_spec LEFT
	| object_spec LEFT expr
	| object_spec FROM position
	| object_spec TO position
	| object_spec AT position
	| object_spec WITH path
	| object_spec WITH position				%prec ','
	| object_spec BY expr_pair
	| object_spec THEN
	| object_spec SOLID
	| object_spec DOTTED
	| object_spec DOTTED expr
	| object_spec DASHED
	| object_spec DASHED expr
	| object_spec FILL
	| object_spec FILL expr
	| object_spec SHADED text
	| object_spec COLORED text
	| object_spec OUTLINED text
	| object_spec CHOP
	| object_spec CHOP expr
	| object_spec SAME
	| object_spec INVISIBLE
	| object_spec LEFT_ARROW_HEAD
	| object_spec RIGHT_ARROW_HEAD
	| object_spec DOUBLE_ARROW_HEAD
	| object_spec CW
	| object_spec CCW
	| object_spec text					%prec TEXT
	| object_spec LJUST
	| object_spec RJUST
	| object_spec ABOVE
	| object_spec BELOW
	| object_spec THICKNESS expr
	| object_spec ALIGNED
	;

text:
	TEXT
	| SPRINTF '(' TEXT sprintf_args ')'
	;

sprintf_args:
	/* empty */
	| sprintf_args ',' expr
	;

position:
	position_not_place
	| place
	;

position_not_place:
	expr_pair
	| position '+' expr_pair
	| position '-' expr_pair
	| '(' position ',' position ')'
	| expr between position AND position
	| expr '<' position ',' position '>'
	;

between:
	BETWEEN
	| OF THE WAY BETWEEN
	;

expr_pair:
	expr ',' expr
	| '(' expr_pair ')'
	;

place:
	/* line at A left == line (at A) left */
	label							%prec CHOP
	| label corner
	| corner label
	| corner OF label
	| HERE
	;

label:
	LABEL
	| nth_primitive
	| label '.' LABEL
	;

ordinal:
	ORDINAL
	| '`' any_expr TH
	;

optional_ordinal_last:
	LAST
	| ordinal LAST
	;

nth_primitive:
	ordinal object_type
	| optional_ordinal_last object_type
	;

object_type:
	BOX
	| CIRCLE
	| ELLIPSE
	| ARC
	| LINE
	| ARROW
	| SPLINE
	| '[' ']'
	| TEXT
	;

label_path:
	'.' LABEL
	| label_path '.' LABEL
	;

relative_path:
	corner							%prec CHOP
	/* give this a lower precedence than LEFT and RIGHT so that
	   [A: box] with .A left == [A: box] with (.A left) */
	| label_path						%prec TEXT
	| label_path corner
	;

path:
	relative_path
	| '(' relative_path ',' relative_path ')'
		{}
	/* The rest of these rules are a compatibility sop. */
	| ORDINAL LAST object_type relative_path
	| LAST object_type relative_path
	| ORDINAL object_type relative_path
	| LABEL relative_path
	;

corner:
	DOT_N
	| DOT_E
	| DOT_W
	| DOT_S
	| DOT_NE
	| DOT_SE
	| DOT_NW
	| DOT_SW
	| DOT_C
	| DOT_START
	| DOT_END
	| TOP
	| BOTTOM
	| LEFT
	| RIGHT
	| UPPER LEFT
	| LOWER LEFT
	| UPPER RIGHT
	| LOWER RIGHT
	| LEFT_CORNER
	| RIGHT_CORNER
	| UPPER LEFT_CORNER
	| LOWER LEFT_CORNER
	| UPPER RIGHT_CORNER
	| LOWER RIGHT_CORNER
	| NORTH
	| SOUTH
	| EAST
	| WEST
	| CENTER
	| START
	| END
	;

expr:
	VARIABLE
	| NUMBER
	| place DOT_X
	| place DOT_Y
	| place DOT_HT
	| place DOT_WID
	| place DOT_RAD
	| expr '+' expr
	| expr '-' expr
	| expr '*' expr
	| expr '/' expr
	| expr '%' expr
	| expr '^' expr
	| '-' expr						%prec '!'
	| '(' any_expr ')'
	| SIN '(' any_expr ')'
	| COS '(' any_expr ')'
	| ATAN2 '(' any_expr ',' any_expr ')'
	| LOG '(' any_expr ')'
	| EXP '(' any_expr ')'
	| SQRT '(' any_expr ')'
	| K_MAX '(' any_expr ',' any_expr ')'
	| K_MIN '(' any_expr ',' any_expr ')'
	| INT '(' any_expr ')'
	| RAND '(' any_expr ')'
	| RAND '(' ')'
	| SRAND '(' any_expr ')'
	| expr '<' expr
	| expr LESSEQUAL expr
	| expr '>' expr
	| expr GREATEREQUAL expr
	| expr EQUALEQUAL expr
	| expr NOTEQUAL expr
	| expr ANDAND expr
	| expr OROR expr
	| '!' expr
	;
]])

# Pass plenty of options, to exercise plenty of code, even if we
# don't actually check the output.  But SEGV is watching us, and
# so might do dmalloc.
AT_CHECK([[bison --verbose --defines input.y]], 0, [],
[[input.y:453.11-48: warning: rule never reduced because of conflicts: path: ORDINAL LAST object_type relative_path
]])

AT_CLEANUP