Ply is reporting that the it has encountered numerous shift/reduce conflicts while using the grammar I've entered to build a LALR parser.
Right now I'm trying to resolve these conflicts but whatever I do makes the situation worse. first I used C language (my grammar is almost identical to a programming language grammar like a mix of C and Python) precedence table to set precedence tuple in my parser identical to that order:
precedence = (
# ('left', 'ELSE'),
# ('left', 'ID')
# ('left', 'INTEGERNUMBER')
# ('left', 'FLOATNUMBER')
# ('left', 'SEMICOLON')
# ('left', 'ERROR')
('left', 'COMMA'),
('right', 'ASSIGN'),
('left', 'OR'),
('left', 'AND'),
('left', 'EQ', 'NE'),
('left', 'GE', 'GT'),
('left', 'LE', 'LT'),
('left', 'SUM', 'SUB'),
('left', 'MUL', 'DIV', 'MOD'),
('right', 'NOT'),
('left', 'LCB', 'RCB'), #left curly brace...
('left', 'LSB', 'RSB'), #left square bracket..
('left', 'LRB', 'RRB'), #left round bracket...
)
It did help and eliminated about 40 out 90 conflicts. The next step I tried to remove left recursions from grammars which contained left recursion. I did that for one or two of the productions using an online tool but it added a lot of shift-reduce conflicts and a few reduce/reduce conflicts, I'm not really good at these things so I was skeptical whether I should continue eliminating all left recursions from all productions to see the result or the early bad result was a stop sign.
I also did some searching and read that left recursions don't break LALR gramamrs, and precedence and associativity are powerful enough to resolve these conflicts.
Below is one of the states in which there are dozens of conflicts:
state 82
(45) exp -> exp operator exp .
(45) exp -> exp . operator exp
(46) exp -> exp . relop exp
(54) operator -> . OR
(55) operator -> . AND
(56) operator -> . SUM
(57) operator -> . SUB
(58) operator -> . MUL
(59) operator -> . DIV
(60) operator -> . MOD
(65) relop -> . GT
(66) relop -> . LT
(67) relop -> . NE
(68) relop -> . EQ
(69) relop -> . LE
(70) relop -> . GE
! shift/reduce conflict for OR resolved as shift
! shift/reduce conflict for AND resolved as shift
! shift/reduce conflict for SUM resolved as shift
! shift/reduce conflict for SUB resolved as shift
! shift/reduce conflict for MUL resolved as shift
! shift/reduce conflict for DIV resolved as shift
! shift/reduce conflict for MOD resolved as shift
! shift/reduce conflict for GT resolved as shift
! shift/reduce conflict for LT resolved as shift
! shift/reduce conflict for NE resolved as shift
! shift/reduce conflict for EQ resolved as shift
! shift/reduce conflict for LE resolved as shift
! shift/reduce conflict for GE resolved as shift
RSB reduce using rule 45 (exp -> exp operator exp .)
SEMICOLON reduce using rule 45 (exp -> exp operator exp .)
COMMA reduce using rule 45 (exp -> exp operator exp .)
RRB reduce using rule 45 (exp -> exp operator exp .)
OR shift and go to state 54
AND shift and go to state 55
SUM shift and go to state 56
SUB shift and go to state 57
MUL shift and go to state 58
DIV shift and go to state 59
MOD shift and go to state 60
GT shift and go to state 61
LT shift and go to state 62
NE shift and go to state 63
EQ shift and go to state 64
LE shift and go to state 65
GE shift and go to state 66
! OR [ reduce using rule 45 (exp -> exp operator exp .) ]
! AND [ reduce using rule 45 (exp -> exp operator exp .) ]
! SUM [ reduce using rule 45 (exp -> exp operator exp .) ]
! SUB [ reduce using rule 45 (exp -> exp operator exp .) ]
! MUL [ reduce using rule 45 (exp -> exp operator exp .) ]
! DIV [ reduce using rule 45 (exp -> exp operator exp .) ]
! MOD [ reduce using rule 45 (exp -> exp operator exp .) ]
! GT [ reduce using rule 45 (exp -> exp operator exp .) ]
! LT [ reduce using rule 45 (exp -> exp operator exp .) ]
! NE [ reduce using rule 45 (exp -> exp operator exp .) ]
! EQ [ reduce using rule 45 (exp -> exp operator exp .) ]
! LE [ reduce using rule 45 (exp -> exp operator exp .) ]
! GE [ reduce using rule 45 (exp -> exp operator exp .) ]
operator shift and go to state 52
relop shift and go to state 53
And Here are some of the productions that I think are related to above state:
exp → lvalue=exp | exp operator exp |exp relop exp|
const | lvalue | ID(explist) | LRB exp RRB | ID() | SUB exp | NOT exp
operator → OR | AND | SUM | SUB | MUL | DIV | MOD
relop → GE | LT | NE | EQ | LE | GE
const → INTEGERNUMBER | FLOATNUMBER | TRUE | FALSE
lvalue → ID | ID LSB exp RSB
EDIT: below is the complete list of warnings:
WARNING: Conflicts:
WARNING:
WARNING: shift/reduce conflict for VOID in state 0 resolved as shift
WARNING: shift/reduce conflict for INTEGER in state 0 resolved as shift
WARNING: shift/reduce conflict for FLOAT in state 0 resolved as shift
WARNING: shift/reduce conflict for BOOLEAN in state 0 resolved as shift
WARNING: shift/reduce conflict for INTEGER in state 45 resolved as shift
WARNING: shift/reduce conflict for FLOAT in state 45 resolved as shift
WARNING: shift/reduce conflict for BOOLEAN in state 45 resolved as shift
WARNING: shift/reduce conflict for RETURN in state 72 resolved as shift
WARNING: shift/reduce conflict for WHILE in state 72 resolved as shift
WARNING: shift/reduce conflict for FOR in state 72 resolved as shift
WARNING: shift/reduce conflict for IF in state 72 resolved as shift
WARNING: shift/reduce conflict for PRINT in state 72 resolved as shift
WARNING: shift/reduce conflict for ID in state 72 resolved as shift
WARNING: shift/reduce conflict for LRB in state 72 resolved as shift
WARNING: shift/reduce conflict for SUB in state 72 resolved as shift
WARNING: shift/reduce conflict for NOT in state 72 resolved as shift
WARNING: shift/reduce conflict for LCB in state 72 resolved as shift
WARNING: shift/reduce conflict for INTEGERNUMBER in state 72 resolved as shift
WARNING: shift/reduce conflict for FLOATNUMBER in state 72 resolved as shift
WARNING: shift/reduce conflict for TRUE in state 72 resolved as shift
WARNING: shift/reduce conflict for FALSE in state 72 resolved as shift
WARNING: shift/reduce conflict for OR in state 82 resolved as shift
WARNING: shift/reduce conflict for AND in state 82 resolved as shift
WARNING: shift/reduce conflict for SUM in state 82 resolved as shift
WARNING: shift/reduce conflict for SUB in state 82 resolved as shift
WARNING: shift/reduce conflict for MUL in state 82 resolved as shift
WARNING: shift/reduce conflict for DIV in state 82 resolved as shift
WARNING: shift/reduce conflict for MOD in state 82 resolved as shift
WARNING: shift/reduce conflict for GT in state 82 resolved as shift
WARNING: shift/reduce conflict for LT in state 82 resolved as shift
WARNING: shift/reduce conflict for NE in state 82 resolved as shift
WARNING: shift/reduce conflict for EQ in state 82 resolved as shift
WARNING: shift/reduce conflict for LE in state 82 resolved as shift
WARNING: shift/reduce conflict for GE in state 82 resolved as shift
WARNING: shift/reduce conflict for OR in state 83 resolved as shift
WARNING: shift/reduce conflict for AND in state 83 resolved as shift
WARNING: shift/reduce conflict for SUM in state 83 resolved as shift
WARNING: shift/reduce conflict for SUB in state 83 resolved as shift
WARNING: shift/reduce conflict for MUL in state 83 resolved as shift
WARNING: shift/reduce conflict for DIV in state 83 resolved as shift
WARNING: shift/reduce conflict for MOD in state 83 resolved as shift
WARNING: shift/reduce conflict for GT in state 83 resolved as shift
WARNING: shift/reduce conflict for LT in state 83 resolved as shift
WARNING: shift/reduce conflict for NE in state 83 resolved as shift
WARNING: shift/reduce conflict for EQ in state 83 resolved as shift
WARNING: shift/reduce conflict for LE in state 83 resolved as shift
WARNING: shift/reduce conflict for GE in state 83 resolved as shift
WARNING: shift/reduce conflict for ELIF in state 121 resolved as shift
Thank you so much in advance.
Since + and * are syntactically different, you cannot clump them together in a single syntactic category (operator).
They are syntactically different precisely because the operators have different precedences. (Or, to put it more accurately, we usually describe the syntactic difference as a difference in precedence). For example, the expressions a - b * c and a - b - c are syntactically different, in that in the first one, the syntax for N - N allows the second N to cover b * c, while in the second one b - c is not permitted as an expansion of the second N. Collecting all operators together into a single operator non-terminal thus conflates different syntactic constructs in a way that makes it impossible to produce a correct parse with the grammar.
In order to use precedence declarations to resolve an ambiguous grammar, you must make the actual operator tokens visible in the production:
exp: exp '+' exp | exp '-' exp | exp '*' exp …
(Note: I used quoted literal tokens in the above, instead of insisting on names. The use of literal tokens is more readable and requires much less boilerplate in your lexer description. It also allows Ply to create a more efficient lexer. See the Ply manual.)
Do not try to eliminate left recursion. Without left recursion, you cannot correctly write the syntax of left-associative operators (which is to say, most operators). LALR parsers prefer left-recursive rules. They are not your problem.