Resolving conflict in simple grammar, please help

Jun 23, 2013 at 10:51 PM
Hi,
I am trying to implement grammar for a simple language.
Source file is composed of variable declarations first and routine declarations next.
PROGRAM.Rule = MakeStarRule(PROGRAM, MODULE_CONTENT);
MODULE_CONTENT.Rule =  "MODULE" + VAR_DECL_LIST + ROUTINE_LIST;

BASIC_TYPE = ToTerm("int") | "float";

VAR_DECL_LIST.Rule = MakeStarRule(VAR_DECL_LIST, VAR_DECL);
VAR_DECL.Rule = BASIC_TYPE + identifier

ROUTINE_LIST.Rule = MakeStarRule(ROUTINE_LIST, ROUTINE);
ROUTINE.Rule = BASIC_TYPE + "FUNC" + identifier + BODY;
My problem is that variable declaration and routine definition starts with basic type.
This causes shift reduce conflict at "int" and "float".
Is there a mechanism for solving this implemented?
I tried to use CustomActionHere at the beginning of BASIC_TYPE:
BASIC_TYPE =CustomActionHere(this.ResolveFundTypeConflict) + (ToTerm("CARD") | "CHAR" | "BYTE" | "INT");
private void ResolveFundTypeConflict(ParsingContext context, CustomParserAction customAction)
{
    var scanner = context.Parser.Scanner;
    Token token = null;
    if (context.CurrentParserInput.Term.Name == "Unnamed0")
    {
        scanner.BeginPreview();
        token = scanner.GetToken(); 
        scanner.EndPreview(true);
    }
    ParserAction action;
    if (token.Text != "FUNC")
        action = customAction.ShiftActions.First(a => a.Term.Name == "Unnamed0");
    else
    {
        action = customAction.ReduceActions.First();
    }
    action.Execute(context);
}
but after reduce BASIC_TYPE token seems to be already eaten and parsing starts at FUNC
causing error.
Please help
Regards
Tristan
Jun 24, 2013 at 11:28 AM
Here is an example code causing shift-resolve conflict in my grammar:

MODULE

BYTE TMP
INT TMP2

BYTE FUNC TEST(INT A)
RETURN

I want all variables to be declared before routines declaration start.
I can't change the grammar because I am working on a crosscompiler for existing language (ACTION for 8-bit Atari)
Cheers
Tristan
Coordinator
Jun 25, 2013 at 5:08 AM
try the following:
  1. Use MakePlusRule for both var and routine lists
  2. Express 'optional' nature of both lists directly in rule for module:
    module.Rule = 'MODULE' + module_body;
    module_body.Rule = var_decl_list | routine_list | var_decl_list + routine_list | Empty;
that should solve the problem (my WAG, did not test it, but feels like it should work). If you have more that 2 subsection, that would become a problem, but for just 2 it should work
Roman
Jun 26, 2013 at 11:06 AM
Thank you, it worked like a charm :) I think I understand what you did.
Now I have two more conflicts right below, can you have a look at that too please?
Shift-reduce conflicts on inputs: CARD CHAR BYTE INT
The problem lies at routine level. I made routine a root to isolate it.
I think the collision is at FUNC_DECL and SYSTEM_DECL (both can start with a type):
            this.Root = ROUTINE_LIST;
            ROUTINE_LIST.Rule = MakePlusRule(ROUTINE_LIST, ROUTINE);
            ROUTINE.Rule = (PROC_DECL | FUNC_DECL) + ROUTINE_BODY;
            ROUTINE_BODY.Rule = SYSTEM_DECL_LIST | STATEMENTS | SYSTEM_DECL_LIST + STATEMENTS | Empty;

            PROC_DECL.Rule = "PROC" + identifier + "(" + PARAM_DECL_LIST + ")";
            FUNC_DECL.Rule = FUND_TYPE + "FUNC" + identifier + "(" + PARAM_DECL_LIST + ")";
            PARAM_DECL_LIST.Rule = MakeStarRule(PARAM_DECL_LIST, PARAM_DECL);
            PARAM_DECL.Rule = ...;

            SYSTEM_DECL_LIST.Rule = MakePlusRule(SYSTEM_DECL_LIST, SYSTEM_DECL);
            SYSTEM_DECL.Rule = VAR_DECL | RECORD_DEF;
            VAR_DECL.Rule = FUND_DECL | POINTER_DECL | ARRAY_DECL | RECORD_DECL;
            FUND_DECL.Rule = FUND_TYPE + FUND_IDENT_LIST;

            // statements
            STATEMENTS.Rule = MakePlusRule(STATEMENTS, STATEMENT);
            STATEMENT.Rule = EXIT_STAT | ASSIGN_STAT | RETURN_STAT | ROUTINE_CALL_STAT | DO_OR_UNTIL_LOOP_STAT | WHILE_LOOP_STAT | FOR_LOOP_STAT | IF_STAT | CODE_BLOCK_STAT;
some example code presenting the problem:
INT FUNC F1(BYTE A)
INT TEST=2
RETURN A+TEST

INT FUNC F2(BYTE A)

INT FUNC F3(BYTE A)
INT TEST2=2

PROC F3(BYTE A)
Routine can be declared with empty body (something like forward declaration)
Routine also don't have to end with RETURN.
The example code is perfectly correct from the grammar point of view.

Can you think about it please?
Regards
Tristan
Coordinator
Jun 27, 2013 at 3:10 AM
come on man, try to solve it yourself, i hope you got the idea - just refactor the rules. Google (like 'resolving shift-reduce conflicts'), get some ideas. Try/fail/google/retry loop. Don't think I have some secret knowledge, it's all about general principles about LALR and LALR grammars, conflicts and adjusting grammars to fit LALR limitations