[Help] generation of bytecode for a custom language

Hi, first of all say that I don't know if this is the right place to ask for help, so if not it would be great to be pointed where I should post this.

I'm trying to generate bytecode for a given virtual machine directly from Bison, however I can't find a way to do it without hitting conflicts.

There is a snippet of code of what I'm having trouble to compile, a list of concurrent actions:

!(a=10+3) || ( !(b=11+2) ; !(c=12+1) ) || !(d=1) 

The expected bytecode is the following:

TASK 2 NULL NULL;
ADD 1 10 3;
SET 1 'a' NULL;
TASK 4 NULL NULL;
ADD 2 11 2;
SET 2 'b' NULL;
ADD 3 12 1;
SET 3 'c' NULL;
TASK 2 NULL NULL;
LOADK 4 1 NULL;
SET 4 'd' NULL;
EXEC_TASK NULL NULL;

And that is the relevant grammar subset I have, where lies the problem:

actionList
  : BRACKET_START_ actionList BRACKET_END_ {}
  | concurrentActionList {}
  | sequentialActionList {}
  | action               {}
  ;
concurrentActionList
  : concurrentActionListPartial {
        emit(EXEC_TASK, NULL,NULL);
    }
  ;
concurrentActionListPartial
  : concurrentActionListPartial OP_CONCURRENT_ {
        $<instrPartial>$.instr = emit(TASK,255,NULL,NULL);
        $<instrPartial>$.instr_num = currentInstrNumber();
    } actionList {
        int field_a = currentInstrNumber() - $<instrPartial>3.instr_num;
        instr_set_field_A($<instrPartial>3.instr, field_a);
    }
  | {
        $<instrPartial>$.instr = emit(TASK,255,NULL,NULL);
        $<instrPartial>$.instr_num = currentInstrNumber();
    } actionList OP_CONCURRENT_ {
        int field_a = currentInstrNumber() - $<instrPartial>1.instr_num;
        instr_set_field_A($<instrPartial>1.instr, field_a);

        $<instrPartial>$.instr = emit(TASK,255,NULL,NULL);
        $<instrPartial>$.instr_num = currentInstrNumber();
    } actionList {
        int field_a = currentInstrNumber() - $<instrPartial>4.instr_num;
        instr_set_field_A($<instrPartial>4.instr, field_a);
    }
  ;
sequentialActionList
  : sequentialActionListPartial {}
  ;
sequentialActionListPartial
  : sequentialActionListPartial OP_SEQUENCE_ actionList {}
  | actionList OP_SEQUENCE_ actionList {}
  ;
action
  : OP_END_ {}
  | tell {}
  | call {}
  | localDecl {}
  | conditional {}
  | globalChoice {}
  | instaChoice {}
  ;

I tried a few other rewrites, but I end with conflicts. The number of conflicts is so high to copy here.

If I remove the mid-rules it is reduced to only two conflicts between concurrentActionListPartial and concurrentActionList:

Estado 16

   11 concurrentActionList: concurrentActionListPartial .
   14 concurrentActionListPartial: concurrentActionListPartial . OP_OR_ $@2 actionList

    OP_OR_  desplazar e ir al estado 41

    OP_OR_    [reduce usando la regla 11 (concurrentActionList)]
    $default  reduce usando la regla 11 (concurrentActionList)


Estado 17

   12 sequentialActionList: sequentialActionListPartial .
   16 sequentialActionListPartial: sequentialActionListPartial . OP_SEQUENCE_ actionList

    OP_SEQUENCE_  desplazar e ir al estado 42

    OP_SEQUENCE_  [reduce usando la regla 12 (sequentialActionList)]
    $default      reduce usando la regla 12 (sequentialActionList)

I have permission to slightly change the syntax of the language if absolutely needed, so I obliged that concurrent actions to be enclosed between parentheses, it resolves the conflicts between concurrentActionListPartial and concurrentActionList, but not those introduced by the mid-action rule.

I think the big culprit is the mid-rule action at start of rule. Since there is no preceding terminal, it would not have a way to know what to do, right? With conditionals I have very similar grammar with the difference that there the mid-action rule is preceded by a terminal. Is it possible to rewrite it with a terminal at start?, I have not found any alternative.

Is it resolvable? I'm pretty sure the language is type 2 so Bison must be the right tool, right?

Generating first an ast and then generate code from it would help with those problems, or would be only displacing the problem?

I'm really lost with these, so any help is truly welcome.

Edit: there was an error on the first block code

3 comments · 90% upvoted · other discussions

comments

[deleted]

I have permission to slightly change the syntax of the language if absolutely needed,

So someone else devised the grammar? If so, was it free of conflicts, or has it never been tested?

(What actually is the synax anyway - in English: I get a=10+3, but what are "!" and "||"? There's nothing in the bytecode to suggest they have the same meanings as C.

I don't know Bison and don't normally use formal grammars so can't help with that part.)

echoAnother [OP]

"!(...)" are any action that modifies the program state. Currently only variable assigment.

"... || ..." are a list of actions that must be executed concurrently.

The grammar was devised, but not given. So the bison grammar was written from zero. It was extracted from example programs, like:

mult(N,M,Z,S) {
    if (M=1)? then
        !(Z=N) || 
        !(S=1)
    else
        exists(M',Z',S')(
            !(M’=M-1) ||
            mult(N,M’,Z,S) ||
            ?(S’=1) -> ( !(Z=N+Z’) ||
                           !(S=1) )
        )
}
[mult(2,3,Res,Aux)]

and some pseudo bnf figure:

https://storage.ancarbel.dns-cloud.net/f/069f681035814f8fa904

Who devised it says that the language is context insensitive, but was never checked.

[deleted]

I assume the {} in that text means actions to be executed to output code. But it doesn't get that far because a conflict is reported first? You might try - temporarily - taking out the {...} stuff. Here I've removed {} too, but if that's not allowed, then put empty {} back in:

​

actionList
  : BRACKET_START_ actionList BRACKET_END_
  | concurrentActionList
  | sequentialActionList
  | action              
  ;
concurrentActionList
  : concurrentActionListPartial
  ;
concurrentActionListPartial
  : concurrentActionListPartial OP_CONCURRENT_ actionList
  | actionList OP_CONCURRENT_ actionList
  ;
sequentialActionList
  : sequentialActionListPartial
  ;
sequentialActionListPartial
  : sequentialActionListPartial OP_SEQUENCE_ actionList
  | actionList OP_SEQUENCE_ actionList
  ;
action
  : OP_END_
  | tell
  | call
  | localDecl
  | conditional
  | globalChoice
  | instaChoice
  ;

So, here, I guess "|" gives alternatives, and the sequences end with ";". Words in capitals refer to actual symbols. But I'm not seeing one for ";" (eg. SEMI_COLON); should that be here? (Edit: that must be OP_SEQUENCE_!)

Anyway I thought that this might make it easier to see if it's correct. Personally, although I'm only guessing at this notation, to me it looks a little ambiguous.

For example, given the very first symbol of input, how easily can it tell which of the first four categories (apart from "(" which is easy) of actionlist it is? What are the rules for mixing a concurrent sequence (A || B || C) with a sequential one (A ; B ; C)?

In your example it seems that ";" is expected to bind more tightly (has higher precedence) than "||" , but I'm not seeing that.