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

Hi,
I am currently redesign my old compiler written in python by the use of pyl. The current code is attached.
1.) a comment
2.) global variable declaration
"""
// comment 1
global {
// comment 2
integer a;
integer a[2345];
// comment 3
}
"""
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 }
| 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 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]

Hi,
I am currently redesign my old compiler written in python by the use of pyl. The current code is
attached.
| startElement
| start startElement
startElement : comment
startElement : global { 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

[j***@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