From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=HTML_MESSAGE autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 64AFDBC6B for ; Wed, 31 Oct 2007 05:22:26 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAHqgJ0eAKs4Fnmdsb2JhbACCcotzAgEBBwQGERg X-IronPort-AV: E=Sophos;i="4.21,349,1188770400"; d="scan'208,217";a="18788396" Received: from netscaler2.rice.edu (HELO mh1.mail.rice.edu) ([128.42.206.5]) by mail4-smtp-sop.national.inria.fr with ESMTP; 31 Oct 2007 05:21:11 +0100 Received: from mh1.mail.rice.edu (localhost.localdomain [127.0.0.1]) by mh1.mail.rice.edu (Postfix) with ESMTP id 704F2385E95 for ; Tue, 30 Oct 2007 23:11:10 -0500 (CDT) X-Virus-Scanned: by amavis-2.4.4 at mh1.mail.rice.edu Received: from mh1.mail.rice.edu ([127.0.0.1]) by mh1.mail.rice.edu (mh1.mail.rice.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id tywYl01s0Uj8 for ; Tue, 30 Oct 2007 23:11:10 -0500 (CDT) Received: from [10.194.94.87] (unknown [10.194.94.87]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by mh1.mail.rice.edu (Postfix) with ESMTP id 87135385E73 for ; Tue, 30 Oct 2007 23:11:09 -0500 (CDT) Mime-Version: 1.0 (Apple Message framework v752.3) In-Reply-To: <1193753915.47273d3bb15f2@webmail.in-berlin.de> References: <6C4DFFEF-0A5E-496F-9468-56693FFA4DC2@cs.rice.edu> <1193753915.47273d3bb15f2@webmail.in-berlin.de> Content-Type: multipart/alternative; boundary=Apple-Mail-60-748299630 Message-Id: <1A83BBA2-37FB-4E88-93C8-27D23FD4C271@cs.rice.edu> From: Angela Zhu Subject: Re: [Caml-list] Problem with precedence declaration in .mly file Date: Tue, 30 Oct 2007 23:11:04 -0500 To: caml-list@yquem.inria.fr X-Mailer: Apple Mail (2.752.3) X-Spam: no; 0.00; bandel:01 ocaml:01 parser:01 parser:01 interprets:01 atan:01 rhs:01 rhs:01 tokens:01 lexer:01 prec:01 one-to-one:01 mult:01 mult:01 bandel:01 --Apple-Mail-60-748299630 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed On Oct 30, 2007, at 9:18 AM, Oliver Bandel wrote: > Zitat von Angela Zhu : > >> Hi all, >> >> I have some problem with precedence declaration in OCaml parser. >> If I what to say exponential(ATOB) is prior to *(STAR) and / >> (DIVIDE), >> * and / are prior to +(PLUS) and -(MINUS), >> I wrote the following in the parser: >> >> >> /***** Precedence Rules *****/ >> ... >> %left PLUS MINUS >> %left STAR DIVIDE >> %left ATOB >> ... >> >> But I still have the following problems: >> (1) It appears that the parser >> reads "test = 2^2 + 7;" as "test = 2^9" instead of "test = 4+7", >> which >> would follow the conventional order of operations. >> >> (2)It also interprets "test = (1^2)/3 + 1;" as "test = (1 ^ 2 >> / (3 + 1));" >> >> Can any one help me to see why it happens? Why the precedence rules >> doesn't work? > [...] > > Precedences also can be created by sophisticated > organization of the grammar rules. But I want to avoid this. > > So, if your grammar rules may have a contradictory > meaning, then your parser works not as expected. > > In general I would use the precedence-declarations only, > when you run into parser conflicts, if you don't use them. > When developing a grammr, I would recommend, first to start > with the grammar rules, and add precedence-/associatitivity- > declarations, at the end, if really necessary. > > > What is the rest of your mly-file? > > A complete example would be helpful. Here is part of my .mly file: Beside the precedence issue, everything works fine. %{ open Past open Parsing open ParseError let pi = 4.0 *. atan 1.0;; let get_range n = { pos_start = Parsing.rhs_start_pos n; pos_end = Parsing.rhs_end_pos n; } let unclosed opening_name opening_num closing_name closing_num = raise(Error(Unclosed(get_range opening_num, opening_name, get_range closing_num, closing_name))) %} /* List of all tokens the lexer can output */ ... %token PLUS %token STAR %token MINUS %token DIVIDE %token AND %token OR ... %token ATOB /* A^B: exponential */ ... /***** Precedence Rules *****/ %left PLUS MINUS %left STAR DIVIDE %left ATOB %nonassoc prec_unary_minus %start prog %type prog %% /* Rules for parsing. The parsing rules should generally be in a */ /* one-to-one correspondence with the BNF */ /* type prog = Prog of consDeclare list * varDeclare list * inpDeclare list * sysDeclare list */ prog: exp: LPAREN exp RPAREN { $2 } | LPAREN exp error { unclosed "(" 1 ")" 3 } | exp PLUS exp { Add($1, $3) } | MINUS exp { Sub(Value(VFloat(0.0)), $2) } | exp MINUS exp { Sub($1, $3) } | exp DIVIDE exp { Divide($1, $3) } | exp STAR exp { Mult($1, $3) } | exp ATOB exp { Atob($1, $3) } | value PLUS exp { Add(Value($1), $3) } | value MINUS exp { Sub(Value($1), $3) } | value DIVIDE exp { Divide(Value($1), $3) } | value STAR exp { Mult(Value($1), $3) } | value ATOB exp { Atob(Value($1), $3) } ... | IDENT { Id($1) } | value { Value($1) } ; ... --Apple-Mail-60-748299630 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=ISO-8859-1
On Oct 30, 2007, = at 9:18 AM, Oliver Bandel wrote:

Zitat von Angela Zhu <angela.zhu@cs.rice.edu>:

Hi all,

I have = some problem with precedence declaration in OCaml parser.
If I what to say exponential(ATOB) is prior to = *(STAR) and / (DIVIDE),
=A0 * and / are prior to = +(PLUS)=A0 and = -(MINUS),
I wrote the following in the = parser:


/***** = Precedence Rules=A0 = *****/
...
%left = PLUS MINUS
%left STAR DIVIDE
%left ATOB
...

But I = still have the following problems:
(1) It = appears that the parser
reads "test =3D= 2^2 + 7;" as "test =3D 2^9" instead of "test =3D 4+7", which
would follow the conventional order of = operations.

(2)It also interprets "test =3D (1^2)/3 + 1;" as = "test =3D (1 ^ 2
/ (3 + 1));"

Can any = one help me to see why it happens? Why the precedence rules
doesn't work?
[...]

Precedences also can be created = by sophisticated
organization of the grammar = rules.
But I want to avoid this.

So, if your grammar rules may have a = contradictory
meaning, then your parser works = not as expected.

In general I would use the precedence-declarations = only,
when you run into parser = conflicts, if you don't use them.
When = developing a grammr, I would recommend, first to start
with the grammar rules, and add = precedence-/associatitivity-
declarations, = at the end, if really necessary.


What is the rest of your mly-file?

A = complete example would be helpful.
Here is part = of my .mly file:
Beside the precedence issue, everything works = fine.

=A0%{

open = Past
open = Parsing
open = ParseError

let pi =3D = 4.0 *. atan = 1.0;;

let get_range n =3D = {
=A0 pos_start =3D = Parsing.rhs_start_pos n;
=A0 = pos_end =3D Parsing.rhs_end_pos n;
}

let unclosed = opening_name opening_num closing_name closing_num = =3D
=A0 raise(Error(Unclosed(get_range opening_num, = opening_name,
=A0=A0 =A0 =A0 =A0 = =A0 =A0 =A0 =A0 =A0 =A0 =A0 get_range closing_num, = closing_name)))
%}

/* List of = all tokens the lexer can output */

...

%token PLUS
%token = STAR
%token = MINUS
%token = DIVIDE
%token = AND=
%token OR
...

%token ATOB=A0 /* A^B: = exponential */
...


/***** Precedence = Rules=A0= *****/
%left PLUS MINUS = =A0
%left STAR DIVIDE = =A0
%left = ATOB
%nonassoc = prec_unary_minus


%start = prog

%type = <Past.pprog> prog
%%
/* Rules for = parsing. The parsing rules should generally be in = a */
/* = one-to-one = correspondence with = the BNF */
/* = type prog =3D Prog = of consDeclare list = * varDeclare list * inpDeclare list * sysDeclare list = */




prog:

exp:
=A0=A0 = LPAREN exp RPAREN=A0 =A0 =A0 =A0 =A0 { = $2 }
=A0| = LPAREN exp error =A0 =A0 =A0 =A0 =A0 { unclosed = "(" = 1 ")" = 3 }
=A0| exp PLUS = exp= = = = = { = Add($1, $3) = }
=A0| MINUS = exp=A0= = = = = = { = Sub(Value(VFloat(0.0)), $2) = }
=A0| exp MINUS exp = =A0= =A0 =A0 =A0 =A0 =A0 { Sub($1, = $3) }
=A0| = exp DIVIDE exp { Divide($1, = $3) }
=A0| = exp STAR exp=A0 =A0 =A0 =A0 =A0 =A0 =A0 { = Mult($1, $3) = }
=A0| exp ATOB = exp=A0= =A0 =A0 =A0 =A0 =A0 =A0 { Atob($1, = $3) }


=A0| = value PLUS exp { Add(Value($1), $3) = }
=A0| value MINUS exp = =A0= =A0 =A0 =A0 =A0 =A0 { Sub(Value($1), $3) = }
=A0| value DIVIDE = exp= = = = { = Divide(Value($1), $3) = }
=A0| value STAR = exp=A0= =A0 =A0 =A0 =A0 =A0 =A0 { Mult(Value($1), $3) = }
=A0| value ATOB = exp=A0= =A0 =A0 =A0 =A0 =A0 =A0 { Atob(Value($1), $3) = }


...

=A0| = IDENT { Id($1) = }
=A0| = value { Value($1) = }

=A0

;


...




= --Apple-Mail-60-748299630--