Smalltalk › Squeak › Squeak - Dev

SmaCC: Shift/Reduce Conflict

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

9 messages Options

Alexandre Bergel

SmaCC: Shift/Reduce Conflict

Dear all,

I bumped into a conflict while writing a small grammar. Would be great to know why. The problem seems to come from the Assignment

I wish to parse the following:

myfunction (a, b, c){

3 + 10

var z

z = 50 + foo()

}

Parser:

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Program : FunctionDefinition * {SPProgram new functions: '1'};

FunctionDefinition :

Id Arguments "{"

ExpressionList

"}" {SPFunction new name: '1'; arguments: ('2' select: [:o| (o isKindOf: SmaCCToken) not]); expressions: '4'};

Arguments : "(" ArgumentList ")" {'2'};

ArgumentList : ArgumentList "," Id

| Id

| ;

ExpressionList:

Expression ExpressionList

| ;

Expression :

FunctionCall

| VariableDefinition

| Id "=" ExpressionWithValue {SPAssignment new name: '1'; expression: '3'}

| Expression "+" Number {SPAddition new left: '1'; right: '3'}

| Expression "-" Number {SPMinus new left: '1'; right: '3'}

| Number {'1'};

FunctionCall :

Id ArgumentsInCall {SPFunctionCall new name: '1'; arguments: '2'};

ArgumentsInCall :

"(" ArgumentsListInCall ")" {'2' select: [:o| (o isKindOf: SmaCCToken) not]};

ArgumentsListInCall :

ArgumentsListInCall "," Expression

| Expression

| ;

VariableDefinition :

"var" Id {SPVariableDefinition new name: '2'};

ExpressionWithValue :

ExpressionWithValue "+" Number {SPAddition new left: '1'; right: '3'}

| ExpressionWithValue "-" Number {SPMinus new left: '1'; right: '3'}

| Number {'1'};

Number : <number> {'1' value asNumber} ;

Id : <variable> {'1' value asString} ;

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Scanner:

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

<number> : [0-9]+;

<whitespace> : \s+;

<variable> : [a-zA-Z] \w* ;

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Regards,

Alexandre

_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:

Alexandre Bergel http://www.software-artist.eu

^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

Mathieu SUEN

Re: SmaCC: Shift/Reduce Conflict

Hi,

On Apr 23, 2007, at 11:51 AM, Alexandre Bergel wrote:

> FunctionDefinition :
> Id Arguments "{"
> ExpressionList
> "}" {SPFunction new name: '1'; arguments: ('2' select: [:o| (o
> isKindOf: SmaCCToken) not]); expressions: '4'};
>
> Arguments : "(" ArgumentList ")" {'2'};
>
> ArgumentList : ArgumentList "," Id
> | Id
> | ;
>
> ExpressionList:
> Expression ExpressionList
> | ;
>
> Expression :
> FunctionCall
> | VariableDefinition
> | Id "=" ExpressionWithValue {SPAssignment new name: '1';
> expression: '3'}
> | Expression "+" Number {SPAddition new left: '1'; right:
> '3'}
> | Expression "-" Number {SPMinus new left: '1'; right: '3'}
> | Number {'1'};
>

I suggest you to create a rule for the assignment.
You can write something like

Assignment :
Id "=" Expression;

> FunctionCall :
> Id ArgumentsInCall {SPFunctionCall new name: '1'; arguments: '2'};
>
> ArgumentsInCall :
> "(" ArgumentsListInCall ")" {'2' select: [:o| (o isKindOf:
> SmaCCToken) not]};
>
> ArgumentsListInCall :
> ArgumentsListInCall "," Expression
> | Expression
> | ;
>
> VariableDefinition :
> "var" Id {SPVariableDefinition new name: '2'};
>
> ExpressionWithValue :
> ExpressionWithValue "+" Number {SPAddition new left: '1';
> right: '3'}
> | ExpressionWithValue "-" Number {SPMinus new left: '1';
> right: '3'}
> | Number {'1'};

ExpressionWithValue always end up with a Number which is not what
your example saw.
Shift/Reduce dose not matter
You can still parse the expression and you have some rule to say if
you want to follow the longer rule or not (ie. Shift or reduce).
By default you SmaCC do a shift. Look at the tutorial pane in the UI
of SmaCC.

HTH

Math

Bergel, Alexandre

Re: SmaCC: Shift/Reduce Conflict

Hi Mathieu!

> I suggest you to create a rule for the assignment.
> You can write something like
>
> Assignment :
> Id "=" Expression;

If I add
Expression :
FunctionCall
| Assignment
| ...

Assignment :
Id "=" Expression;

Then it loops... Hence a conflict.

> ExpressionWithValue always end up with a Number which is not what
> your example saw.
> Shift/Reduce dose not matter
> You can still parse the expression and you have some rule to say if
> you want to follow the longer rule or not (ie. Shift or reduce).
> By default you SmaCC do a shift. Look at the tutorial pane in the
> UI of SmaCC.

Are you saying that my grammar is well written and the conflict I
have cannot be removed properly ?

Thanks,
Alexandre

--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel http://www.software-artist.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

John Brant

Re: SmaCC: Shift/Reduce Conflict

In reply to this post by Alexandre Bergel

Alexandre Bergel wrote:

> Dear all,
>
> I bumped into a conflict while writing a small grammar. Would be great
> to know why. The problem seems to come from the Assignment
> I wish to parse the following:
> myfunction (a, b, c){
> 3 + 10
> var z
> z = 50 + foo()
> }

How do you wish to parse:

myfunction (a, b, c) {
var z
z = 1 + 2
}

You can parse "z = 1 + 2" multiple ways:
(z = 1) + 2
or
z = (1 + 2)

The default behavior of SmaCC picks the shift action over the reduce
action, so the second choice is the one that it picks.

To fix this problem you can
A) ignore it, if you want the second choice
B) change your grammar to remove the ambiguity
C) add a precedence rule to tell SmaCC the priority of the +, -, and =
tokens
The SmaCC tutorial has an example of both B & C.

John Brant

J J-6

Re: SmaCC: Shift/Reduce Conflict

In reply to this post by Mathieu SUEN

So is SmaCC a parser combinator? Or is it some other style?

>From: Mathieu Suen <[hidden email]>
>Reply-To: The general-purpose Squeak developers
>list<[hidden email]>
>To: The general-purpose Squeak developers
>list<[hidden email]>
>Subject: Re: SmaCC: Shift/Reduce Conflict
>Date: Mon, 23 Apr 2007 13:50:59 +0200
>
>Hi,
>
>On Apr 23, 2007, at 11:51 AM, Alexandre Bergel wrote:
>
>>FunctionDefinition :
>> Id Arguments "{"
>> ExpressionList
>> "}" {SPFunction new name: '1'; arguments: ('2' select: [:o| (o isKindOf:
>>SmaCCToken) not]); expressions: '4'};
>>
>>Arguments : "(" ArgumentList ")" {'2'};
>>
>>ArgumentList : ArgumentList "," Id
>> | Id
>> | ;
>>
>>ExpressionList:
>> Expression ExpressionList
>> | ;
>>
>>Expression :
>> FunctionCall
>> | VariableDefinition
>> | Id "=" ExpressionWithValue {SPAssignment new name: '1'; expression:
>>'3'}
>> | Expression "+" Number {SPAddition new left: '1'; right: '3'}
>> | Expression "-" Number {SPMinus new left: '1'; right: '3'}
>> | Number {'1'};
>>
>
>I suggest you to create a rule for the assignment.
>You can write something like
>
>Assignment :
> Id "=" Expression;
>
>
>>FunctionCall :
>> Id ArgumentsInCall {SPFunctionCall new name: '1'; arguments: '2'};
>>
>>ArgumentsInCall :
>> "(" ArgumentsListInCall ")" {'2' select: [:o| (o isKindOf: SmaCCToken)
>>not]};
>>
>>ArgumentsListInCall :
>> ArgumentsListInCall "," Expression
>> | Expression
>> | ;
>>
>>VariableDefinition :
>> "var" Id {SPVariableDefinition new name: '2'};
>>
>>ExpressionWithValue :
>> ExpressionWithValue "+" Number {SPAddition new left: '1';
>>right: '3'}
>> | ExpressionWithValue "-" Number {SPMinus new left: '1'; right:
>>'3'}
>> | Number {'1'};
>
>
>
>ExpressionWithValue always end up with a Number which is not what your
>example saw.
>Shift/Reduce dose not matter
>You can still parse the expression and you have some rule to say if you
>want to follow the longer rule or not (ie. Shift or reduce).
>By default you SmaCC do a shift. Look at the tutorial pane in the UI of
>SmaCC.
>
>
>HTH
>
> Math
>
>
>

_________________________________________________________________
Download Messenger. Join the im Initiative. Help make a difference today.
http://im.live.com/messenger/im/home/?source=TAGHM_APR07

Igor Stasenko

Re: SmaCC: Shift/Reduce Conflict

In reply to this post by Bergel, Alexandre

> > Assignment :
> > Id "=" Expression;
>
> If I add
> Expression :
> FunctionCall
> | Assignment
> | ...
>
> Assignment :
> Id "=" Expression;
>

Try this one instead:

AssignPart :
Id "="
| AssignPart Id "="
;

Expression:
AssignPart ExpressionTail
| ExpressionTail

ExpressionTail:
| Function
| BinaryOp
| ...
| ExpressionTail Function
| ExpressionTail BinaryOp
..

This will remove shitf/reduce conflicts.

The main reason why its occurs is when you write something like this:

Expression:
FixedPattern
| FixedPattern Expression

this will force parser to shift and to grow its stack.
but if you write :

Expression:
FixedPattern
| Expression FixedPattern

parser will reduce faster.

Bergel, Alexandre

Re: SmaCC: Shift/Reduce Conflict

I solved my problem.

Thanks to all of you.

Alexandre

On 23 Apr 2007, at 18:40, sig wrote:

>> > Assignment :
>> > Id "=" Expression;
>>
>> If I add
>> Expression :
>> FunctionCall
>> | Assignment
>> | ...
>>
>> Assignment :
>> Id "=" Expression;
>>
>
> Try this one instead:
>
> AssignPart :
> Id "="
> | AssignPart Id "="
> ;
>
> Expression:
> AssignPart ExpressionTail
> | ExpressionTail
>
>
> ExpressionTail:
> | Function
> | BinaryOp
> | ...
> | ExpressionTail Function
> | ExpressionTail BinaryOp
> ..
>
> This will remove shitf/reduce conflicts.
>
> The main reason why its occurs is when you write something like this:
>
> Expression:
> FixedPattern
> | FixedPattern Expression
>
> this will force parser to shift and to grow its stack.
> but if you write :
>
> Expression:
> FixedPattern
> | Expression FixedPattern
>
> parser will reduce faster.
>

--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel http://www.software-artist.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

Mathieu SUEN

Re: SmaCC: Shift/Reduce Conflict

Cool I am interested how?

Mth

On Apr 24, 2007, at 9:31 AM, Bergel, Alexandre wrote:

> I solved my problem.
>
> Thanks to all of you.
>
> Alexandre
>
>
> On 23 Apr 2007, at 18:40, sig wrote:
>
>>> > Assignment :
>>> > Id "=" Expression;
>>>
>>> If I add
>>> Expression :
>>> FunctionCall
>>> | Assignment
>>> | ...
>>>
>>> Assignment :
>>> Id "=" Expression;
>>>
>>
>> Try this one instead:
>>
>> AssignPart :
>> Id "="
>> | AssignPart Id "="
>> ;
>>
>> Expression:
>> AssignPart ExpressionTail
>> | ExpressionTail
>>
>>
>> ExpressionTail:
>> | Function
>> | BinaryOp
>> | ...
>> | ExpressionTail Function
>> | ExpressionTail BinaryOp
>> ..
>>
>> This will remove shitf/reduce conflicts.
>>
>> The main reason why its occurs is when you write something like this:
>>
>> Expression:
>> FixedPattern
>> | FixedPattern Expression
>>
>> this will force parser to shift and to grow its stack.
>> but if you write :
>>
>> Expression:
>> FixedPattern
>> | Expression FixedPattern
>>
>> parser will reduce faster.
>>
>
> --
> _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
> Alexandre Bergel http://www.software-artist.eu
> ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
>
>
>
>

Bergel, Alexandre

Re: SmaCC: Shift/Reduce Conflict

Those comments helped me:

> You can parse "z = 1 + 2" multiple ways:
> (z = 1) + 2
> or
> z = (1 + 2)

>> The main reason why its occurs is when you write something like this:
>>
>> Expression:
>> FixedPattern
>> | FixedPattern Expression
>>
>> this will force parser to shift and to grow its stack.

It was not clear to me.

My grammar contains something like:
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Expression :

Id "=" Expression {SPAssignment new name: '1'; expression: '3'}
| Conditional {'1'}
| VariableDefinition {SPVariableDefinition new name: '1'}
| BinaryOp {'1'}
| Term {'1'}
;
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

The conflict disappeared.
Thanks for you help Mathieu

Alexandre

On 24 Apr 2007, at 10:43, Mathieu Suen wrote:

>>> The main reason why its occurs is when you write something like
>>> this:
>>>
>>> Expression:
>>> FixedPattern
>>> | FixedPattern Expression
>>>
>>> this will force parser to shift and to grow its stack.

--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel http://www.software-artist.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.