Shift Reduce Conflicts

Question

Below the grammar i make.

1. S' -> sqf
2. sqf -> declarations
3. declarations -> declaration
4. declarations -> declaration declarations
5. declaration -> relation
6. declaration -> norelation
7. relation -> head body
8. norelation -> relatts
9. norelation -> reldata
10. norelation -> relatts reldata
11. head -> relname attributes
12. body -> reldata
13. body -> empty
14. relname -> RELKW IDENTIFIER
15. attributes -> relatts
16. attributes -> empty
17. relatts -> attname
18. relatts -> attname relatts
19. reldata -> DATAKW tuples
20. reldata -> DATAKW
21. tuples -> tuple
22. tuples -> tuple tuples
23. attname -> ATTKW IDENTIFIER
24. tuple -> VALUE
25. empty ->

The problem is that the grammar is ambiguous because for some rules there are shift/reduce conflicts. Particularly

at the rules below for DATAKW we have shift/reduce conflict

• relation -> head body
• body -> reldata
• body -> empty
• reldata -> DATAKW tuples
• reldata -> DATAKW
• *empty -> *

at the rules below for DATAKW we have shift/reduce conflict

• norelation -> relatts
• norelation -> relatts reldata
• reldata -> DATAKW tuples
• reldata -> DATAKW

at the rules below for ATTKW we have shift/reduce conflict

• head -> relname attributes
• attributes -> relatts
• attributes -> empty
• relatts -> attname
• relatts -> attname relatts
• *empty -> *
• attname -> ATTKW IDENTIFIER

at the rules below for ATTKW we have shift/reduce conflict

• relatts -> attname
• relatts -> attname relatts
• relatts -> attname
• relatts -> attname relatts
• attname -> ATTKW IDENTIFIER

Can anyone help me to solve that conflicts, please.

Answer 1

A problem is that the grammar cannot determine where one declaration ends and the next one begins.

A simple instance of this general problem: norelation can be just a relatts which can be a list of attnames. So if you have two consecutive norelation, that could be two sequences of attnames. How can you distinguish two consecutive sequences from one longer sequence? Or three shorter ones? Etc.

There are many other instances of the same issue.

Unless you've transcribed the language incorrectly, this is a problem of language design, and semicolons are a common solution.