[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
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] 1 points · Oct 2020
"!(...)" 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:
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] 1 points · Oct 2020
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:
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.