Re: Another bison problem

[Hans Aberg]

At 15:57 +0300 2003/04/02, Andrei Harangus wrote:
>    Hy,   After solving the previous problem I would  like to direct your
>attention to a more complicated one. I am writing a rather large grammar
>that  generates shift/reduce and reduce/reduce conflicts: ... call : ID
>'(' call_list ')'  {;} call_list : expr ',' call_list           | call
>',' call_list           |  expr           |  call ;   expr : ...      |
>call <-- HERE  IT DOES ; ...   I know that the grammar is ambiguous,  but
>I was wondering wether just by defining operator priorities I could solve
>the problem (which I wasn't  able to do), or I'll have to change the
>grammar (and I don't know how).

You are mixing together "call" and "expr" without thinking about their
exact relation, it seems. It looks to me as though your "call" is something
like the definition of a "structure" in a Prolog grammar, so I attach such
a grammar I once made. It has some extensions typical for expressions using
precedence rules, you might be able to copy over and change relevant parts.
Just start at
  structure:
    ...
    | atom term_sequence
    ...
and trace the rules to extract the parts that might be relevant to you.


%token help_key
%token quit_key
%token show_substitutions_key, no_show_substitutions_key
%token debug_key "debug"

%token show_key "??"

%token Prolog_key "Prolog"
%token query_key "?-"
%token query_pure_key "?+"
%token query_Andorra_key "?*"

%token if_key ":-"
%token cut_key "!"

%token variable_name "variable name"
%token atom_name "atom name"
%token integer_value
%token list_concat "++"

%token solve_key "solve"
%token axiom_key "axiom"
%token definition_key "definition"
%token theorem_key "theorem"
%token proof_key "proof"

%token identifier_key "identifier"

%token all_key "all"
%token implies_key "=>"
%token impliedby_key "<="
%token in_key "in"


%nonassoc '='
%nonassoc "in"

%left '+' '-'
%right UMINUS
%left "++"

%%
file:
    file_contents { }
  |               { }
  | error {
      clp_parser_context = 0;
      YYABORT;
    }

file_contents:
    file_contents command { }
  | command               { }

command:
    help_key { clp::help(std::cout); }
  | quit_key { std::cout << "Thank you and goodbye." << std::endl;
std::exit(EXIT_SUCCESS); }
  | show_substitutions_key { clp::show_substitutions = true; }
  | no_show_substitutions_key { clp::show_substitutions = false; }
  | show_key { db->show(std::cout); }
  | debug_key '-' { clp::debug_unification = false; }
  | debug_key '+' { clp::debug_unification = true; }
  | "Prolog" Prolog_clause { clp_parser_context = 0;
db->addClause($2.clause); }
  | "Prolog" '{' Prolog_clauses '}' { clp_parser_context = 0; }
  | Prolog_query { clp_parser_context = 0; }
  | "solve" query { }
  | "axiom" clause { clp_parser_variables.clear(); db->addClause($2.clause); }

Prolog_clauses:
    Prolog_clause { db->addClause($1.clause); }
  | Prolog_clauses Prolog_clause { db->addClause($2.clause); }

Prolog_clause:
    structure '.' { $$.clause = $1.term; }
  | structure Prolog_if_clause '.' { $$.clause = clp::Clause($1.term,
$2.termlist); }

clause:
    structure '.' { $$.clause = $1.term; }
  | variables_declaration structure '.' {
      if ($1.termlist.empty())
        $$.clause = $2.term;
      $$.clause = clp::Clause($2.term, $1.termlist);
    }
  | variables_declaration structure "<=" termlist '.' {
      $4.termlist.insert($4.termlist.begin(), $1.termlist.begin(),
$1.termlist.end());
      $$.clause = clp::Clause($2.term, $4.termlist); }
  | variables_declaration termlist "=>" structure '.' {
      $2.termlist.insert($2.termlist.begin(), $1.termlist.begin(),
$1.termlist.end());
      $$.clause = clp::Clause($4.term, $2.termlist); }

variables_declaration:
    "all" { clp_parser_variables.clear(); } identifier_list in_set ':' {
      $$.termlist = $4.termlist;
    }

in_set:
      { }
  | "in" atom {
      std::set<std::string>::iterator i = clp_parser_variables.begin(), i1
= clp_parser_variables.end();
      for (; i != i1; ++i) {
        $1.termlist.push_back(new clp::variable(0, *i));
        $$.termlist.push_back(
          new clp::Structure($2.text, $1.termlist));
        $1.termlist.clear();
      }
    }

identifier_list:
    atom_name { clp_parser_variables.insert($1.text); }
  | identifier_list ',' atom_name { clp_parser_variables.insert($3.text); }

structure:
    atom { $$.term = new clp::Structure($1.text); }
  | atom term_sequence { $$.term = new clp::Structure($1.text, $2.termlist); }
  | term "in" atom {
      $1.termlist.push_back($1.term);
      $$.term = new clp::Structure($3.text, $1.termlist);
    }
  | term '=' term {
      $1.termlist.push_back($1.term);
      $1.termlist.push_back($3.term);
      $$.term = new clp::Structure("=", $1.termlist);
    }

atom:
    atom_name { $$.text = $1.text; }

Prolog_if_clause:
    ":-" termlist { $$.termlist = $2.termlist; }

term_sequence:
    '(' termlist ')' { $$.termlist = $2.termlist; }

termlist:
    term              { $$.termlist.push_back($1.term); }
  | termlist ',' term { $$.termlist = $1.termlist;
$$.termlist.push_back($3.term); }

term:
    variable_name { $$.term = new clp::variable(0, $1.text); }
  | integer_value { $$.term = new clp::integer($1.number); }
  | structure { $$.term = $1.term; }
  | list { $$.term = $1.term; }
  | term "++" term { $$.term = new clp::list_concatenation($1.term, $3.term); }
  | term '+' term { $$.term = new clp::integer_addition($1.term, $3.term); }
  | term '-' term { $$.term = new clp::integer_addition($1.term,
    new clp::integer_negative($3.term)); }
  | '-' term  %prec UMINUS { $$.term = new clp::integer_negative($2.term); }

list:
    '[' termlist ']' { $$.term = new clp::list($2.termlist); }
  | '[' ']' { $$.term = new clp::list(); }
  | '[' termlist '|' term ']' { $$.term = new
clp::list_constructor($2.termlist, $4.term); }

Prolog_query:
    "?-" termlist '.' { db->demonstrate($2.termlist); }
  | "?+" termlist '.' { db->demonstrate($2.termlist, clp::Database::pure); }
  | "?*" termlist '.' { db->demonstrate($2.termlist, clp::Database::Andorra); }

query:
    termlist '.' { db->demonstrate($1.termlist); }
  | variables_declaration termlist '.' {
      $2.termlist.insert($2.termlist.begin(), $1.termlist.begin(),
$1.termlist.end());
      clp_parser_variables.clear();
      db->demonstrate($2.termlist);
    }

%%