shift / reduce error

[Stefan J]

Hi,

I am currently redesign my old compiler written in python by the use of pyl. The current code is attached.

First I want to explain the goal:

This compiler should create an AST which is used to translate a domain specific language in to some kind of assembler. Actual there are two elements given in the grammar:
1.) a comment
2.) global variable declaration

The global variable declaration can contain a list of variables. It is also allowed to write comments. A listing of the text can look like this:
"""
// comment 1

global {
    // comment 2
    integer a;
    integer a[2345];
    // comment 3
}
"""

I have some problems by defining the grammar rules. I give a short pseudo listing:

start :
 | startElement
 | start startElement

startElement : comment
startElement : global { varList }

varList :
 | varListElement
 | varList varListElement

varListElement : comment
varListElement : type name ;
varListElement: type name [ number ] ;

As you can see it is very simple. I did not understand the error (4 Shift / Reduce Erros). Maybe you can help me.

Thanks and have a nice weekend!
Stefan

[John Pote]

I know it takes time to do but trimming down the source code to the minimum required to expose the problem might help you understand the problem (and its solution) and the rest of us to help you as quickly as possible. We could cut and paste the code into a file, run PLY on the file and hopefully duplicate the problem. Seeing the actual code and the error message would similarly help.

Anyway, I've annotated you pseudo code as to where the problem might be. Or you could decide to leave the conflict in your grammar and accept the default behaviour of PLY.

BTW you might consider removing comments at the lexical stage. Saves your grammar having to account for comments almost everywhere.

Regards,

John

On 23 Aug 2013, at 13:53, Stefan J <stefan...@gmail.com> wrote:

Hi,

I am currently redesign my old compiler written in python by the use of pyl. The current code is attached.

First I want to explain the goal:

This compiler should create an AST which is used to translate a domain specific language in to some kind of assembler. Actual there are two elements given in the grammar:
1.) a comment
2.) global variable declaration

The global variable declaration can contain a list of variables. It is also allowed to write comments. A listing of the text can look like this:
"""
// comment 1

global {
    // comment 2
    integer a;
    integer a[2345];
    // comment 3
}
"""

I have some problems by defining the grammar rules. I give a short pseudo listing:

start : /** try removing this empty production, does it make the conflict go away? Is it necessary or are you trying to allow for a source file with neither comment or global at the beginning?  **/

 | startElement
 | start startElement

startElement : comment
startElement : global { varList }

varList :
 | varListElement
 | varList varListElement

varListElement : comment
varListElement : type name ;
varListElement: type name [ number ] ;

As you can see it is very simple. I did not understand the error (4 Shift / Reduce Erros). Maybe you can help me.

Thanks and have a nice weekend!
Stefan

--
You received this message because you are subscribed to the Google Groups "ply-hack" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ply-hack+u...@googlegroups.com.
To post to this group, send email to ply-...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ply-hack/559b5ca0-7f7c-4bf5-9711-581add0d035d%40googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
<ALc2.py>

[A.T.Hofkamp]

On 08/23/2013 02:53 PM, Stefan J wrote:
> Hi,
>
> I am currently redesign my old compiler written in python by the use of pyl. The current code is
> attached.

> start :
> | startElement
> | start startElement
>
> startElement : comment
> startElement : global { varList }
>
> varList :
> | varListElement
> | varList varListElement
>
> varListElement : comment
> varListElement : type name ;
> varListElement: type name [ number ] ;
>
> As you can see it is very simple. I did not understand the error (4 Shift / Reduce Erros). Maybe you
> can help me.

I threw the thing in bison, and it gave me the grammar below, and also 4 shift/reduce errors.

Grammar

0 $accept: start $end

1 start: /* empty */
2 | startElement
3 | start startElement

4 startElement: COMMENT
5 | GLOBAL CUROPEN varList CURCLOSE

6 varList: /* empty */
7 | varListElement
8 | varList varListElement

9 varListElement: COMMENT
10 | TYPE NAME
11 | TYPE NAME SQOPEN NUMBER SQCLOSE

It also tells where they are:

State 0 conflicts: 2 shift/reduce
State 5 conflicts: 2 shift/reduce


The problem is in the start productions and the varList productions.
As you can see there are 3 production rules, one for 0 elements, one for 1 element, and the general
case.

The problem is caused by the fact that you have two ways to derive 1 element, namely as 1 element,
or as 0 elements and 1 application of the general case.

I think you want to remove the 1 element production rules.

Albert

[john...@jptechnical.co.uk]

I tried your psuedo code in PLY with and duplicated the 4 shift/reduce conflicts
-------------------------------
def p_start(p):
    """start :
            | startElem
            | start startElem
    """
    pass

def p_startElem(p):
    """startElem : COMMENT
                 | GLOBAL '{' varList '}'
    """
    pass

def p_varList(p):
    """varList :
               | varListElem
               | varList varListElem
    """
    pass

def p_varListElem(p):
    """varListElem : COMMENT
                   | INTEGER ID ';'
                   | INTEGER ID '[' NUMBER ']' ';'
    """
    pass

-------------------------------

I then restructured the 'start' production as follows
-------------------------------
def p_start(p):
    """start :
             | startElems
    """
    pass

def p_startElems(p):
    """startElems : startElem
                  | startElems startElem
    """
    pass

def p_startElem(p):
    """startElem : COMMENT
                 | GLOBAL '{' varList '}'
    """
    pass

-------------------------------

Doing the same for the 'varList' removes all the conflicts. This structure has the advantage that the <empty> production case only reduces when there are no start elements in the text being parsed. This would be useful if you wanted an action to be performed only when there are no start elements. Similarly you could perform an action when there are 1 or more start elements,
def p_startEmpty(p):
    """start :
    """
    #action(s) for no start elements

def p_start(p):
    """start : startElems
    """
    #action(s) for 1 or more start elements

Regards,
John