K-user mailing list

[Radu Mereuta <headness13 AT gmail.com>]

First, an answer to Grigore:

That's the way SDF works, it applies the priority/associativity filters all the time. That is the semantics of SDF. We can't really change that because right now we partially rely on the SDF parser to apply those filters. We want this because it is fast. Applying them much later (after the Parse Forrest has been instantiated) would make parsing MUCH MUCH slower (exponential times in most cases - depending on the grammar).

Now an explanation for Daniele:

You are right, you don't need a relation between 'fcall' and 'array' because they cannot cause ambiguities. Problems start to appear when you have combinations with binary operators. Example:

syntax Exp ::= Exp "+" Exp | Exp "[" Exp "]"

An input of the form: "a + b [ c ]" is ambiguous because it can be parsed in two ways:  (a + b) [ c ] and  a + (b [ c ])

A priority filter in SDF (we implemented a similar system in SDF) is a simple function that traverses the parse forest and rejects erroneous branches. For the example above we will have:

amb( _[_](_+_(a, b), c),

        _+_(a, _[_](b, c)))

To solve this you can add in K a relation like this:

syntax priorities _[_] > _+_ // or 'syntax priorities array > plus' if you tag your productions with array and plus.

The filter will look at that relation and whenever finds plus as a parent of array, will reject that branch.

What was happening in your example was that you had a relation between two productions that would reject the tree that you actually wanted.

In your example you could use the verbose way of specifying precedences using tags. Remember though that the priority relation is transitively closed.

From this I can acknowledge that we have some problems with the way that we show ambiguities. We are working on this.

Also we have some problems with the documentation. I think you would have had a much better time if we would have explained in details the way the parser works. We are also working on a manual.

Meanwhile feel free to ask us anything you don't find clear. We take users feedback very serious. Many of the tools features have been requested and shaped by users feedback.

Radu

K dev

On Wed, Feb 6, 2013 at 8:38 PM, Rosu, Grigore <grosu AT illinois.edu> wrote:

Don't worry, Daniele, parsing confuses us all.

 

However, your example raises an interesting point: we should probably use the filters only when we have ambiguities, not all the times.  I think Radu is just using SDF out-of-the-box, so if SDF applies the filters all the time then so does K.  Radu, would it be posssible to change the way we apply the ambiguity filters?

 

Grigore

 

 

---

From: k-user-bounces AT cs.uiuc.edu [k-user-bounces AT cs.uiuc.edu] on behalf of Daniele Filaretti [dfilaretti AT gmail.com]
Sent: Wednesday, February 06, 2013 12:34 PM
To: Radu Mereuta
Cc: k-user AT cs.uiuc.edu
Subject: Re: [K-user] parsing error?

On 6 Feb 2013, at 18:19, Radu Mereuta <headness13 AT gmail.com> wrote:

Are you sure you don't have a priority relation between fcall and array? That might reject the correct parsing tree, and would explain why it works with [bracket].

Oh, well, in fact I had a precedence (I forgot to mention in my question). 

It was 

Exp[Exp] > Id (Exps)

And yes, if I remove the precedence it works. 

To be honest I don't understand why, parsing issues always confuse me :) 

(I mean, my _expression_ -- foo()[0] is an Exp[Exp]. And Exp[Exp] has the precedence. So there should not be any ambiguity I guess?)

Anyway, thanks a lot! 

Cheers, 

Daniele

On Wed, Feb 6, 2013 at 8:06 PM, Daniele Filaretti <dfilaretti AT gmail.com> wrote:

Hi all,
here is another question for you K hackers!

Let say my grammar contains something that looks like

> syntax Exp ::=
>    …
>    | Id "(" Exps ")" // function call
>    | Exp "[" Exp "]"  [seqstrict] // reading a field from an array (the first Exp must evaluate to an array value, the second to a key value)
>    …

and suppose I write a function, "foo()" that returns an array. Now, if in my program I write something like

> foo()[0];

I get a parsing error:

> [Error] Critical: Parse error: Syntax error near unexpected character ';'
>       File: test.php
>       Location: (5,9,5,9)


As an experiment, I tried to add

> syntax Exp ::= "(" Exp ")" [bracket]

and then, if I evaluate

> (foo())[0]:


it works!

Am I missing something or is a parsing problem?

Thanks a lot!

Cheers,
Daniele


_______________________________________________
k-user mailing list
k-user AT cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/k-user