CSE 401: Compilers

Details / Extended CFG for PL/0 using Yacc

I wrote a yacc grammar to capture what I thought I meant in the English spec of the extended pl0 project. I did this in yacc so that:

• the students could see a yacc example;
• I could check the grammar using a tool;
• I did not have the time to write html to make it pretty.

• precedence

      and < or < add < mul < ...
  

  this was unclear in the English spec of the extended language
• The initial BNF on the web page had ';' used as statement terminators. I've been thinking they were separators all along.
• There were some typos in the original spec:
  • bad font for := for Lvalue := Expr
  • typo AssignStsmt
• it would be nice if we could parenthesize in test expressions, viz:

    if ((a < b) and (c < d)) or (q > r)
  

  but this is currently unallowed.

/*
 * Copyright (c) 1997 by Robert R. Henry
 *
 * @(#)$Header: /a/www/www/htdocs/education/courses/401/97au/details/RCS/bnf_extended.html,v 1.1 1997/10/27 22:37:19 rrh Exp rrh $
 */
/*
 * yacc coding restrictions
 *   comments as in C
 *   declare all terminals with '%term'
 *   %% separates grammar declarations from grammar
 *   
 * yacc coding conventions used in this document
 *   non terminals in upper case
 *   terminals in lower case
 *   non terminals denoting optional X are named OptX
 *   one production/rule per line
 *   make empty rules obvious (using a comment with body empty)
 *   alternatives start with '|'
 */

/* ---- KeyWords used for declarations and statements ---- */
%term module
%term var
%term procedure
%term int
%term begin
%term end
%term const
%term type
%term set
%term of
%term if
%term then
%term else
%term while
%term do
%term return
%term for
%term switch
%term default
%term case

/* ---- KeyWords used for operators ---- */
%term output
%term input
%term odd
%term in
%term card
%term or
%term and

/* ---- identifiers and integers, as assembled by scanner ---- */
%term id
%term integer

/* ---- named special character sequences, as assembled by scanner */
%term gets	/* := */
%term lessthan	/* <= */
%term gtrthan	/* >= */
%term neq	/* <> */
%term range	/* .. */

%%
/* ---- Declarations ---- */
Program :
  module id ';' Block id '.'
;
Block :
  DeclList begin StmtList end
;
DeclList :	/* 0 or more Decl */
  DeclList Decl ';'
| /*empty*/
;
Decl :
  ConstDecl
| TypeDecl
| VarDecl
| ProcDecl
;

ConstDecl :
  const ConstDeclItemList
;
ConstDeclItemList :	/* 1 or more ConstDeclItem */
  ConstDeclItem
| ConstDeclItemList ',' ConstDeclItem
;
ConstDeclItem :
  id ':' Type '=' ConstExpr
;
ConstExpr :		/* check for const'edness must be done semantically */
  Expr
;
TypeDecl :
  type id '=' ConstExpr range ConstExpr
| type id '=' set of id
;

VarDecl :
  var VarDeclItemList
;
VarDeclItemList :	/* 1 or more VarDeclItemList */
  VarDeclItem
| VarDeclItemList ',' VarDeclItem
;
VarDeclItem :
  id ':' Type
;
ProcDecl :
  procedure id '(' OptFormalDeclList ')' OptReturnType ';' Block id
;
OptFormalDeclList :
  FormalDeclList
| /* empty */
;
FormalDeclList :	/* 1 or more comma separated */
  FormalDecl
| FormalDeclList ',' FormalDecl
;
FormalDecl :
  id ':' Type
;
OptReturnType :
  /* empty */
| ':' Type
;

Type :
  int
| id
;

/* ---- Statements ---- */

StmtList :	/* 0 or more semicolon terminated statements */
  /* empty */
| StmtList Stmt ';'
;
Stmt :
  CallStmt
| AssignStmt
| OutStmt
| IfStmt
| WhileStmt
| ReturnStmt
| ForStmt
| SwitchStmt
| EmptyStmt
;
CallStmt :
  id '(' OptExprList ')'
;
OptExprList :
  /* empty */
| ExprList
;
ExprList :	/* comma separated list of Exprs */
  Expr
| ExprList ',' Expr
;
AssignStmt :
  Lvalue gets Expr
;
Lvalue :
  id
;
OutStmt :
  output gets Expr
;
IfStmt :
  if Test then StmtList end
  if Test then StmtList else StmtList end
;
WhileStmt :
  while Test do StmtList end
;
ReturnStmt :
  return OptExpr
;
EmptyStmt :
  /* empty */
;
ForStmt :
  for id in Expr do StmtList end
;
SwitchStmt :
  switch Expr of OptSwitchLabels end
;
OptSwitchLabels :	/* 0 or more SwitchArm */
  /* empty */
| OptSwitchLabels SwitchArm
;
SwitchArm :
  case CaseLabel ':' StmtList end OptSemi
;
OptSemi :
  /* empty */
| ';'
;
CaseLabel :
  default
| ConstExpr
;

OptExpr :
  /* empty */
| Expr
;

/* ---- Expressions ---- */
Test :
  TestSum
;
TestSum :
  TestFactor
| TestSum or TestFactor
;
TestFactor :
  TestPrimary
| TestFactor and TestPrimary
;
TestPrimary:
  odd Sum
| Sum Relop Sum
| Sum in Sum		/* infix binary set membership test */
;
Relop :
  '<'
| lessthan
| '='
| gtrthan
| '>'
| neq
;

Expr :
  Sum
;
Sum :
  Term
| Sum '+' Term
| Sum '-' Term
;
Term :
  Factor
| Term '*' Factor
| Term '/' Factor
;
Factor :
  '-' Factor
| card Factor	/* unary prefix set cardinality operator */
| integer
| input
| '(' Expr ')'
/* note that the grammar is not left factored from here down */
| LValue			/* identifier */
| id '(' OptExprList ')'	/* function call */
| id '{' OptExprList '}'	/* set constructor */
;





401admin@cs.washington.edu
(Last modified: 27Oct97)