1
votes

Background:

I'm taking a class in software semantics, and we are supposed to create a small compiler and runtime for a toy language called while. We were given a code skeleton for Java, but we are allowed to use whatever language we want. I saw this as an opportunity to rehearse grammars, and thought it'd be cool to do the lab in C++ instead.

Now, I'm having some problems setting up the precedence rules for my statements. Here is my BNFC grammar file right now:

SSkip.  Stmt    ::= "skip";
SAss.   Stmt    ::= VarName ":=" AExp;
SIf.    Stmt1   ::= "if" BExp "then" Stmt "else" Stmt;
SWhile. Stmt1   ::= "while" BExp "do" Stmt;
SComp.  Stmt    ::= Stmt ";" Stmt;
coercions Stmt 1;

token VarName   (letter (letter | digit) *);

EAdd.   AExp    ::= AExp "+" AExp1;
ESub.   AExp    ::= AExp "-" AExp1;
EMul.   AExp1   ::= AExp1 "*" AExp2;
EDiv.   AExp1   ::= AExp1 "/" AExp2;
EInt.   AExp2   ::= Integer;
EVar.   AExp2   ::= VarName;

coercions   AExp    2;

BTrue.  BExp1   ::= "true";
BFalse. BExp1   ::= "false";
BNeg.   BExp    ::= "not" BExp;
BConj.  BExp    ::= BExp "and" BExp;
BLeq.   BExp    ::= AExp "<=" AExp;

coercions BExp 1;

What I want is the input

while true do skip; x:=y

to be parsed according to my compound rule into something like

(SComp [SWhile [BTrue] [SSkip]] [(SAss "x" [EVar "y"])])

That is, I want the assignment to not be part of the loop body. However, what I get is

(SWhile [BTrue] [(SComp SSkip (SAss "x" [(EVar "y")]))])

As you can see, the body of the while-loop consists of the compound statement, which is not what I wanted. How should I set up my precedence rules to reach this effect?

2

2 Answers

3
votes

I think the problem is that an Scomp is a type of Stmt with no way to lexically distinguish it from a simple Stmt.

If the rule was

Scomp. Stmt ::= "{" Stmt ";" Stmt "}";

There would be no ambiguity. There's a reason that compound statements in any regular language you know have begin and end markers; this is it.

0
votes

It turns out I had misunderstood my assignment, sort of. The precedence rules I described are the ones presented in my course book, but since my primary concern is being compatible with the parser we were given from the teacher, I tried it on the code above, and it parses the assignment into the body as well.

The program I wanted to write should "simply" have been:

(while true do skip) ; x := y

But hey, at least it's compatible!