1

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?

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
ansjob
  • 175
  • 7

2 Answers2

3

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.

msw
  • 42,753
  • 9
  • 87
  • 112
  • Thanks for your reply. I know this, but I want to be compatible with the book on software semantics I'm studying as much as possible, and they interpret code this way. – ansjob Apr 28 '13 at 12:10
  • Then you've got an ambiguous grammar and you can't get what you want with a regular language. It is possible (e.g. Perl) to have a non-regular language that can be *consistently* parsed, but it has to restart productions which makes for a wildly irregular parser. Take your pick. – msw Apr 28 '13 at 12:59
  • You are absolutely correct, and it seems I will not have to travel down that path (see my own answer). Thank you for taking time with this! – ansjob Apr 28 '13 at 13:26
0

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!

ansjob
  • 175
  • 7