path: root/Source/Dafny/Parser.ssc

using System.Collections.Generic;
using System.Numerics;
using Microsoft.Boogie;
using Microsoft.Contracts;

namespace Microsoft.Dafny {

public class Parser {
	const int maxT = 100;

	const bool T = true;
	const bool x = false;
	const int minErrDist = 2;
	
	static Token/*!*/ token;			// last recognized token
	static Token/*!*/ t;				// lookahead token
	static int errDist = minErrDist;

	static List<ModuleDecl!>! theModules = new List<ModuleDecl!>();


static Expression! dummyExpr = new LiteralExpr(Token.NoToken);
static FrameExpression! dummyFrameExpr = new FrameExpression(dummyExpr, null);
static Statement! dummyStmt = new ReturnStmt(Token.NoToken);
static Attributes.Argument! dummyAttrArg = new Attributes.Argument("dummyAttrArg");
static Scope<string>! parseVarScope = new Scope<string>();
static int anonymousIds = 0;

struct MemberModifiers {
  public bool IsGhost;
  public bool IsStatic;
  public bool IsUnlimited;
}

// helper routine for parsing call statements
private static void RecordCallLhs(IdentifierExpr! e,
                                  List<IdentifierExpr!>! lhs,
                                  List<AutoVarDecl!>! newVars) {
  int index = lhs.Count;
  lhs.Add(e);
  if (parseVarScope.Find(e.Name) == null) {
    AutoVarDecl d = new AutoVarDecl(e.tok, e.Name, new InferredTypeProxy(), index);
    newVars.Add(d);
    parseVarScope.Push(e.Name, e.Name);
  }
}

// helper routine for parsing call statements
private static Expression! ConvertToLocal(Expression! e)
{
  FieldSelectExpr fse = e as FieldSelectExpr;
  if (fse != null && fse.Obj is ImplicitThisExpr) {
    return new IdentifierExpr(fse.tok, fse.FieldName);
  }
  return e;  // cannot convert to IdentifierExpr (or is already an IdentifierExpr)
}

///<summary>
/// Parses top-level things (modules, classes, datatypes, class members) from "filename"
/// and appends them in appropriate form to "modules".
/// Returns the number of parsing errors encountered.
/// Note: first initialize the Scanner.
///</summary>
public static int Parse (string! filename, List<ModuleDecl!>! modules) /* throws System.IO.IOException */ {
  if (filename == "stdin.dfy") {
    BoogiePL.Buffer.Fill(System.Console.In);
    Scanner.Init(filename);
    return Parse(modules);
  } else {
    using (System.IO.StreamReader reader = new System.IO.StreamReader(filename)) {
      BoogiePL.Buffer.Fill(reader);
      Scanner.Init(filename);
      return Parse(modules);
    }
  }
}

///<summary>
/// Parses top-level things (modules, classes, datatypes, class members)
/// and appends them in appropriate form to "modules".
/// Returns the number of parsing errors encountered.
/// Note: first initialize the Scanner.
///</summary>
public static int Parse (List<ModuleDecl!>! modules) {
  List<ModuleDecl!> oldModules = theModules;
  theModules = modules;
  Parse();
  theModules = oldModules;
  return Errors.count;
}

/*--------------------------------------------------------------------------*/


	static void Error(int n) {
		if (errDist >= minErrDist) Errors.SynErr(n, t.filename, t.line, t.col);
		errDist = 0;
	}
	
	public static void SemErr(string! msg) {
		if (errDist >= minErrDist) Errors.SemErr(token.filename, token.line, token.col, msg);
		errDist = 0;
	}

	public static void SemErr(Token! tok, string! msg) {
		if (errDist >= minErrDist) Errors.SemErr(tok.filename, tok.line, tok.col, msg);
		errDist = 0;
	}

	static void Get() {
		for (;;) {
			token = t;
			t = Scanner.Scan();
			if (t.kind<=maxT) {errDist++; return;}

			t = token;
		}
	}
	
	static void Expect(int n) {
		if (t.kind==n) Get(); else Error(n);
	}
	
	static bool StartOf(int s) {
		return set[s, t.kind];
	}
	
	static void ExpectWeak(int n, int follow) {
		if (t.kind == n) Get();
		else {
			Error(n);
			while (!StartOf(follow)) Get();
		}
	}
	
	static bool WeakSeparator(int n, int syFol, int repFol) {
		bool[] s = new bool[maxT+1];
		if (t.kind == n) {Get(); return true;}
		else if (StartOf(repFol)) return false;
		else {
			for (int i=0; i <= maxT; i++) {
				s[i] = set[syFol, i] || set[repFol, i] || set[0, i];
			}
			Error(n);
			while (!s[t.kind]) Get();
			return StartOf(syFol);
		}
	}
	
	static void Dafny() {
		ClassDecl! c; DatatypeDecl! dt;
		Attributes attrs;  Token! id;  List<string!> theImports;
		  List<MemberDecl!> membersDefaultClass = new List<MemberDecl!>();
		ModuleDecl module;
		DefaultModuleDecl defaultModule = new DefaultModuleDecl();
		
		while (StartOf(1)) {
			if (t.kind == 4) {
				Get();
				attrs = null;  theImports = new List<string!>(); 
				while (t.kind == 6) {
					Attribute(ref attrs);
				}
				Ident(out id);
				if (t.kind == 5) {
					Get();
					Idents(theImports);
				}
				module = new ModuleDecl(id, id.val, theImports, attrs); 
				Expect(6);
				while (t.kind == 8 || t.kind == 12) {
					if (t.kind == 8) {
						ClassDecl(module, out c);
						module.TopLevelDecls.Add(c); 
					} else {
						DatatypeDecl(module, out dt);
						module.TopLevelDecls.Add(dt); 
					}
				}
				theModules.Add(module); 
				Expect(7);
			} else if (t.kind == 8) {
				ClassDecl(defaultModule, out c);
				defaultModule.TopLevelDecls.Add(c); 
			} else if (t.kind == 12) {
				DatatypeDecl(defaultModule, out dt);
				defaultModule.TopLevelDecls.Add(dt); 
			} else {
				ClassMemberDecl(membersDefaultClass);
			}
		}
		defaultModule.TopLevelDecls.Add(new DefaultClassDecl(defaultModule, membersDefaultClass));
		theModules.Add(defaultModule);
		
		Expect(0);
	}

	static void Attribute(ref Attributes attrs) {
		Expect(6);
		AttributeBody(ref attrs);
		Expect(7);
	}

	static void Ident(out Token! x) {
		Expect(1);
		x = token; 
	}

	static void Idents(List<string!>! ids) {
		Token! id; 
		Ident(out id);
		ids.Add(id.val); 
		while (t.kind == 15) {
			Get();
			Ident(out id);
			ids.Add(id.val); 
		}
	}

	static void ClassDecl(ModuleDecl! module, out ClassDecl! c) {
		Token! id;
		Attributes attrs = null;
		List<TypeParameter!> typeArgs = new List<TypeParameter!>();
		List<MemberDecl!> members = new List<MemberDecl!>();
		
		Expect(8);
		while (t.kind == 6) {
			Attribute(ref attrs);
		}
		Ident(out id);
		if (t.kind == 17) {
			GenericParameters(typeArgs);
		}
		Expect(6);
		while (StartOf(2)) {
			ClassMemberDecl(members);
		}
		Expect(7);
		c = new ClassDecl(id, id.val, module, typeArgs, members, attrs); 
	}

	static void DatatypeDecl(ModuleDecl! module, out DatatypeDecl! dt) {
		Token! id;
		Attributes attrs = null;
		List<TypeParameter!> typeArgs = new List<TypeParameter!>();
		List<DatatypeCtor!> ctors = new List<DatatypeCtor!>();
		
		Expect(12);
		while (t.kind == 6) {
			Attribute(ref attrs);
		}
		Ident(out id);
		if (t.kind == 17) {
			GenericParameters(typeArgs);
		}
		Expect(6);
		while (t.kind == 1 || t.kind == 6) {
			DatatypeMemberDecl(ctors);
		}
		Expect(7);
		dt = new DatatypeDecl(id, id.val, module, typeArgs, ctors, attrs); 
	}

	static void ClassMemberDecl(List<MemberDecl!>! mm) {
		Method! m;
		Function! f;
		MemberModifiers mmod = new MemberModifiers();
		
		while (t.kind == 9 || t.kind == 10 || t.kind == 11) {
			if (t.kind == 9) {
				Get();
				mmod.IsGhost = true; 
			} else if (t.kind == 10) {
				Get();
				mmod.IsStatic = true; 
			} else {
				Get();
				mmod.IsUnlimited = true; 
			}
		}
		if (t.kind == 14) {
			FieldDecl(mmod, mm);
		} else if (t.kind == 34) {
			FunctionDecl(mmod, out f);
			mm.Add(f); 
		} else if (t.kind == 19) {
			MethodDecl(mmod, out m);
			mm.Add(m); 
		} else Error(101);
	}

	static void GenericParameters(List<TypeParameter!>! typeArgs) {
		Token! id; 
		Expect(17);
		Ident(out id);
		typeArgs.Add(new TypeParameter(id, id.val)); 
		while (t.kind == 15) {
			Get();
			Ident(out id);
			typeArgs.Add(new TypeParameter(id, id.val)); 
		}
		Expect(18);
	}

	static void FieldDecl(MemberModifiers mmod, List<MemberDecl!>! mm) {
		Attributes attrs = null;
		Token! id;  Type! ty;
		
		Expect(14);
		if (mmod.IsUnlimited) { SemErr(token, "fields cannot be declared 'unlimited'"); }
		if (mmod.IsStatic) { SemErr(token, "fields cannot be declared 'static'"); }
		
		while (t.kind == 6) {
			Attribute(ref attrs);
		}
		IdentType(out id, out ty);
		mm.Add(new Field(id, id.val, mmod.IsGhost, ty, attrs)); 
		while (t.kind == 15) {
			Get();
			IdentType(out id, out ty);
			mm.Add(new Field(id, id.val, mmod.IsGhost, ty, attrs)); 
		}
		Expect(13);
	}

	static void FunctionDecl(MemberModifiers mmod, out Function! f) {
		Attributes attrs = null;
		Token! id;
		List<TypeParameter!> typeArgs = new List<TypeParameter!>();
		List<Formal!> formals = new List<Formal!>();
		Type! returnType;
		List<Expression!> reqs = new List<Expression!>();
		List<FrameExpression!> reads = new List<FrameExpression!>();
		List<Expression!> decreases = new List<Expression!>();
		Expression! bb;  Expression body = null;
		bool isFunctionMethod = false;
		
		Expect(34);
		if (t.kind == 19) {
			Get();
			isFunctionMethod = true; 
		}
		if (mmod.IsGhost) { SemErr(token, "functions cannot be declared 'ghost' (they are ghost by default)"); }
		
		while (t.kind == 6) {
			Attribute(ref attrs);
		}
		Ident(out id);
		if (t.kind == 17) {
			GenericParameters(typeArgs);
		}
		parseVarScope.PushMarker(); 
		Formals(true, false, formals);
		Expect(16);
		Type(out returnType);
		if (t.kind == 13) {
			Get();
			while (t.kind == 23 || t.kind == 25 || t.kind == 35) {
				FunctionSpec(reqs, reads, decreases);
			}
		} else if (StartOf(3)) {
			while (t.kind == 23 || t.kind == 25 || t.kind == 35) {
				FunctionSpec(reqs, reads, decreases);
			}
			FunctionBody(out bb);
			body = bb; 
		} else Error(102);
		parseVarScope.PopMarker();
		f = new Function(id, id.val, mmod.IsStatic, !isFunctionMethod, mmod.IsUnlimited, typeArgs, formals, returnType, reqs, reads, decreases, body, attrs);
		
	}

	static void MethodDecl(MemberModifiers mmod, out Method! m) {
		Token! id;
		Attributes attrs = null;
		List<TypeParameter!>! typeArgs = new List<TypeParameter!>();
		List<Formal!> ins = new List<Formal!>();
		List<Formal!> outs = new List<Formal!>();
		List<MaybeFreeExpression!> req = new List<MaybeFreeExpression!>();
		List<FrameExpression!> mod = new List<FrameExpression!>();
		List<MaybeFreeExpression!> ens = new List<MaybeFreeExpression!>();
		List<Expression!> dec = new List<Expression!>();
		Statement! bb;  BlockStmt body = null;
		
		Expect(19);
		if (mmod.IsUnlimited) { SemErr(token, "methods cannot be declared 'unlimited'"); }
		
		while (t.kind == 6) {
			Attribute(ref attrs);
		}
		Ident(out id);
		if (t.kind == 17) {
			GenericParameters(typeArgs);
		}
		parseVarScope.PushMarker(); 
		Formals(true, true, ins);
		if (t.kind == 20) {
			Get();
			Formals(false, true, outs);
		}
		if (t.kind == 13) {
			Get();
			while (StartOf(4)) {
				MethodSpec(req, mod, ens, dec);
			}
		} else if (StartOf(5)) {
			while (StartOf(4)) {
				MethodSpec(req, mod, ens, dec);
			}
			BlockStmt(out bb);
			body = (BlockStmt)bb; 
		} else Error(103);
		parseVarScope.PopMarker();
		m = new Method(id, id.val, mmod.IsStatic, mmod.IsGhost, typeArgs, ins, outs, req, mod, ens, dec, body, attrs);
		
	}

	static void DatatypeMemberDecl(List<DatatypeCtor!>! ctors) {
		Attributes attrs = null;
		Token! id;
		List<TypeParameter!> typeArgs = new List<TypeParameter!>();
		List<Formal!> formals = new List<Formal!>();
		
		while (t.kind == 6) {
			Attribute(ref attrs);
		}
		Ident(out id);
		if (t.kind == 17) {
			GenericParameters(typeArgs);
		}
		parseVarScope.PushMarker(); 
		if (t.kind == 26) {
			FormalsOptionalIds(formals);
		}
		parseVarScope.PopMarker();
		ctors.Add(new DatatypeCtor(id, id.val, typeArgs, formals, attrs));
		
		Expect(13);
	}

	static void FormalsOptionalIds(List<Formal!>! formals) {
		Token! id;  Type! ty;  string! name;  bool isGhost; 
		Expect(26);
		if (StartOf(6)) {
			TypeIdentOptional(out id, out name, out ty, out isGhost);
			formals.Add(new Formal(id, name, ty, true, isGhost));  parseVarScope.Push(name, name); 
			while (t.kind == 15) {
				Get();
				TypeIdentOptional(out id, out name, out ty, out isGhost);
				formals.Add(new Formal(id, name, ty, true, isGhost));  parseVarScope.Push(name, name); 
			}
		}
		Expect(27);
	}

	static void IdentType(out Token! id, out Type! ty) {
		Ident(out id);
		Expect(16);
		Type(out ty);
	}

	static void GIdentType(bool allowGhost, out Token! id, out Type! ty, out bool isGhost) {
		isGhost = false; 
		if (t.kind == 9) {
			Get();
			if (allowGhost) { isGhost = true; } else { SemErr(token, "formal cannot be declared 'ghost' in this context"); } 
		}
		IdentType(out id, out ty);
	}

	static void Type(out Type! ty) {
		Token! tok; 
		TypeAndToken(out tok, out ty);
	}

	static void IdentTypeOptional(out BoundVar! var) {
		Token! id;  Type! ty;  Type optType = null;
		
		Ident(out id);
		if (t.kind == 16) {
			Get();
			Type(out ty);
			optType = ty; 
		}
		var = new BoundVar(id, id.val, optType == null ? new InferredTypeProxy() : optType); 
	}

	static void TypeIdentOptional(out Token! id, out string! identName, out Type! ty, out bool isGhost) {
		string name = null;  isGhost = false; 
		if (t.kind == 9) {
			Get();
			isGhost = true; 
		}
		TypeAndToken(out id, out ty);
		if (t.kind == 16) {
			Get();
			UserDefinedType udt = ty as UserDefinedType;
			if (udt != null && udt.TypeArgs.Count == 0) {
			  name = udt.Name;
			} else {
			  SemErr(id, "invalid formal-parameter name in datatype constructor");
			}
			
			Type(out ty);
		}
		if (name != null) {
		 identName = name;
		} else {
		  identName = "#" + anonymousIds++;
		}
		
	}

	static void TypeAndToken(out Token! tok, out Type! ty) {
		tok = Token.NoToken;  ty = new BoolType();  /*keep compiler happy*/
		List<Type!>! gt;
		
		if (t.kind == 28) {
			Get();
			tok = token; 
		} else if (t.kind == 29) {
			Get();
			tok = token;  ty = new IntType(); 
		} else if (t.kind == 30) {
			Get();
			tok = token;  gt = new List<Type!>(); 
			GenericInstantiation(gt);
			if (gt.Count != 1) {
			 SemErr("set type expects exactly one type argument");
			}
			ty = new SetType(gt[0]);
			
		} else if (t.kind == 31) {
			Get();
			tok = token;  gt = new List<Type!>(); 
			GenericInstantiation(gt);
			if (gt.Count != 1) {
			 SemErr("seq type expects exactly one type argument");
			}
			ty = new SeqType(gt[0]);
			
		} else if (t.kind == 1 || t.kind == 32 || t.kind == 33) {
			ReferenceType(out tok, out ty);
		} else Error(104);
	}

	static void Formals(bool incoming, bool allowGhosts, List<Formal!>! formals) {
		Token! id;  Type! ty;  bool isGhost; 
		Expect(26);
		if (t.kind == 1 || t.kind == 9) {
			GIdentType(allowGhosts, out id, out ty, out isGhost);
			formals.Add(new Formal(id, id.val, ty, incoming, isGhost));  parseVarScope.Push(id.val, id.val); 
			while (t.kind == 15) {
				Get();
				GIdentType(allowGhosts, out id, out ty, out isGhost);
				formals.Add(new Formal(id, id.val, ty, incoming, isGhost));  parseVarScope.Push(id.val, id.val); 
			}
		}
		Expect(27);
	}

	static void MethodSpec(List<MaybeFreeExpression!>! req, List<FrameExpression!>! mod, List<MaybeFreeExpression!>! ens,
List<Expression!>! decreases) {
		Expression! e;  FrameExpression! fe;  bool isFree = false;
		
		if (t.kind == 21) {
			Get();
			if (StartOf(7)) {
				FrameExpression(out fe);
				mod.Add(fe); 
				while (t.kind == 15) {
					Get();
					FrameExpression(out fe);
					mod.Add(fe); 
				}
			}
			Expect(13);
		} else if (t.kind == 22 || t.kind == 23 || t.kind == 24) {
			if (t.kind == 22) {
				Get();
				isFree = true; 
			}
			if (t.kind == 23) {
				Get();
				Expression(out e);
				Expect(13);
				req.Add(new MaybeFreeExpression(e, isFree)); 
			} else if (t.kind == 24) {
				Get();
				Expression(out e);
				Expect(13);
				ens.Add(new MaybeFreeExpression(e, isFree)); 
			} else Error(105);
		} else if (t.kind == 25) {
			Get();
			Expressions(decreases);
			Expect(13);
		} else Error(106);
	}

	static void BlockStmt(out Statement! block) {
		Token! x;
		List<Statement!> body = new List<Statement!>();
		Statement! s;
		
		parseVarScope.PushMarker(); 
		Expect(6);
		x = token; 
		while (StartOf(8)) {
			Stmt(body);
		}
		Expect(7);
		block = new BlockStmt(x, body); 
		parseVarScope.PopMarker(); 
	}

	static void FrameExpression(out FrameExpression! fe) {
		Expression! e;  Token! id;  string fieldName = null; 
		Expression(out e);
		if (t.kind == 37) {
			Get();
			Ident(out id);
			fieldName = id.val; 
		}
		fe = new FrameExpression(e, fieldName); 
	}

	static void Expression(out Expression! e) {
		Token! x;  Expression! e0;  Expression! e1 = dummyExpr;
		e = dummyExpr;
		
		if (t.kind == 49) {
			Get();
			x = token; 
			Expression(out e);
			Expect(61);
			Expression(out e0);
			Expect(50);
			Expression(out e1);
			e = new ITEExpr(x, e, e0, e1); 
		} else if (StartOf(9)) {
			EquivExpression(out e);
		} else Error(107);
	}

	static void Expressions(List<Expression!>! args) {
		Expression! e; 
		Expression(out e);
		args.Add(e); 
		while (t.kind == 15) {
			Get();
			Expression(out e);
			args.Add(e); 
		}
	}

	static void GenericInstantiation(List<Type!>! gt) {
		Type! ty; 
		Expect(17);
		Type(out ty);
		gt.Add(ty); 
		while (t.kind == 15) {
			Get();
			Type(out ty);
			gt.Add(ty); 
		}
		Expect(18);
	}

	static void ReferenceType(out Token! tok, out Type! ty) {
		tok = Token.NoToken;  ty = new BoolType();  /*keep compiler happy*/
		List<Type!>! gt;
		
		if (t.kind == 32) {
			Get();
			tok = token;  ty = new ObjectType(); 
		} else if (t.kind == 33) {
			Get();
			tok = token;  gt = new List<Type!>(); 
			GenericInstantiation(gt);
			if (gt.Count != 1) {
			 SemErr("array type expects exactly one type argument");
			}
			ty = UserDefinedType.ArrayType(tok, gt[0]);
			
		} else if (t.kind == 1) {
			Ident(out tok);
			gt = new List<Type!>(); 
			if (t.kind == 17) {
				GenericInstantiation(gt);
			}
			ty = new UserDefinedType(tok, tok.val, gt); 
		} else Error(108);
	}

	static void FunctionSpec(List<Expression!>! reqs, List<FrameExpression!>! reads, List<Expression!>! decreases) {
		Expression! e;  FrameExpression! fe; 
		if (t.kind == 23) {
			Get();
			Expression(out e);
			Expect(13);
			reqs.Add(e); 
		} else if (t.kind == 35) {
			Get();
			if (StartOf(10)) {
				PossiblyWildFrameExpression(out fe);
				reads.Add(fe); 
				while (t.kind == 15) {
					Get();
					PossiblyWildFrameExpression(out fe);
					reads.Add(fe); 
				}
			}
			Expect(13);
		} else if (t.kind == 25) {
			Get();
			Expressions(decreases);
			Expect(13);
		} else Error(109);
	}

	static void FunctionBody(out Expression! e) {
		e = dummyExpr; 
		Expect(6);
		if (t.kind == 38) {
			MatchExpression(out e);
		} else if (StartOf(7)) {
			Expression(out e);
		} else Error(110);
		Expect(7);
	}

	static void PossiblyWildFrameExpression(out FrameExpression! fe) {
		fe = dummyFrameExpr; 
		if (t.kind == 36) {
			Get();
			fe = new FrameExpression(new WildcardExpr(token), null); 
		} else if (StartOf(7)) {
			FrameExpression(out fe);
		} else Error(111);
	}

	static void PossiblyWildExpression(out Expression! e) {
		e = dummyExpr; 
		if (t.kind == 36) {
			Get();
			e = new WildcardExpr(token); 
		} else if (StartOf(7)) {
			Expression(out e);
		} else Error(112);
	}

	static void MatchExpression(out Expression! e) {
		Token! x;  MatchCaseExpr! c;
		List<MatchCaseExpr!> cases = new List<MatchCaseExpr!>();
		
		Expect(38);
		x = token; 
		Expression(out e);
		while (t.kind == 39) {
			CaseExpression(out c);
			cases.Add(c); 
		}
		e = new MatchExpr(x, e, cases); 
	}

	static void CaseExpression(out MatchCaseExpr! c) {
		Token! x, id, arg;
		List<BoundVar!> arguments = new List<BoundVar!>();
		Expression! body;
		
		Expect(39);
		x = token;  parseVarScope.PushMarker(); 
		Ident(out id);
		if (t.kind == 26) {
			Get();
			Ident(out arg);
			arguments.Add(new BoundVar(arg, arg.val, new InferredTypeProxy()));
			parseVarScope.Push(arg.val, arg.val); 
			while (t.kind == 15) {
				Get();
				Ident(out arg);
				arguments.Add(new BoundVar(arg, arg.val, new InferredTypeProxy()));
				parseVarScope.Push(arg.val, arg.val); 
			}
			Expect(27);
		}
		Expect(40);
		Expression(out body);
		c = new MatchCaseExpr(x, id.val, arguments, body);
		parseVarScope.PopMarker(); 
	}

	static void Stmt(List<Statement!>! ss) {
		Statement! s; 
		while (t.kind == 6) {
			BlockStmt(out s);
			ss.Add(s); 
		}
		if (StartOf(11)) {
			OneStmt(out s);
			ss.Add(s); 
		} else if (t.kind == 9 || t.kind == 14) {
			VarDeclStmts(ss);
		} else Error(113);
	}

	static void OneStmt(out Statement! s) {
		Token! x;  Token! id;  string label = null;
		s = dummyStmt;  /* to please the compiler */
		
		switch (t.kind) {
		case 57: {
			AssertStmt(out s);
			break;
		}
		case 58: {
			AssumeStmt(out s);
			break;
		}
		case 59: {
			UseStmt(out s);
			break;
		}
		case 60: {
			PrintStmt(out s);
			break;
		}
		case 1: case 26: case 92: case 93: {
			AssignStmt(out s);
			break;
		}
		case 48: {
			HavocStmt(out s);
			break;
		}
		case 53: {
			CallStmt(out s);
			break;
		}
		case 49: {
			IfStmt(out s);
			break;
		}
		case 51: {
			WhileStmt(out s);
			break;
		}
		case 38: {
			MatchStmt(out s);
			break;
		}
		case 54: {
			ForeachStmt(out s);
			break;
		}
		case 41: {
			Get();
			x = token; 
			Ident(out id);
			Expect(16);
			s = new LabelStmt(x, id.val); 
			break;
		}
		case 42: {
			Get();
			x = token; 
			if (t.kind == 1) {
				Ident(out id);
				label = id.val; 
			}
			Expect(13);
			s = new BreakStmt(x, label); 
			break;
		}
		case 43: {
			Get();
			x = token; 
			Expect(13);
			s = new ReturnStmt(x); 
			break;
		}
		default: Error(114); break;
		}
	}

	static void VarDeclStmts(List<Statement!>! ss) {
		VarDecl! d;  bool isGhost = false; 
		if (t.kind == 9) {
			Get();
			isGhost = true; 
		}
		Expect(14);
		IdentTypeRhs(out d, isGhost);
		ss.Add(d);  parseVarScope.Push(d.Name, d.Name); 
		while (t.kind == 15) {
			Get();
			IdentTypeRhs(out d, isGhost);
			ss.Add(d);  parseVarScope.Push(d.Name, d.Name); 
		}
		Expect(13);
	}

	static void AssertStmt(out Statement! s) {
		Token! x;  Expression! e; 
		Expect(57);
		x = token; 
		Expression(out e);
		Expect(13);
		s = new AssertStmt(x, e); 
	}

	static void AssumeStmt(out Statement! s) {
		Token! x;  Expression! e; 
		Expect(58);
		x = token; 
		Expression(out e);
		Expect(13);
		s = new AssumeStmt(x, e); 
	}

	static void UseStmt(out Statement! s) {
		Token! x;  Expression! e; 
		Expect(59);
		x = token; 
		Expression(out e);
		Expect(13);
		s = new UseStmt(x, e); 
	}

	static void PrintStmt(out Statement! s) {
		Token! x;  Attributes.Argument! arg;
		List<Attributes.Argument!> args = new List<Attributes.Argument!>();
		
		Expect(60);
		x = token; 
		AttributeArg(out arg);
		args.Add(arg); 
		while (t.kind == 15) {
			Get();
			AttributeArg(out arg);
			args.Add(arg); 
		}
		Expect(13);
		s = new PrintStmt(x, args); 
	}

	static void AssignStmt(out Statement! s) {
		Token! x;
		Expression! lhs;
		Expression rhs;
		Type ty;
		s = dummyStmt;
		
		LhsExpr(out lhs);
		Expect(44);
		x = token; 
		AssignRhs(out rhs, out ty);
		if (ty == null) {
		 assert rhs != null;
		 s = new AssignStmt(x, lhs, rhs);
		} else if (rhs == null) {
		  s = new AssignStmt(x, lhs, ty);
		} else {
		  s = new AssignStmt(x, lhs, ty, rhs);
		}
		
		Expect(13);
	}

	static void HavocStmt(out Statement! s) {
		Token! x;  Expression! lhs; 
		Expect(48);
		x = token; 
		LhsExpr(out lhs);
		Expect(13);
		s = new AssignStmt(x, lhs); 
	}

	static void CallStmt(out Statement! s) {
		Token! x, id;
		Expression! e;
		List<IdentifierExpr!> lhs = new List<IdentifierExpr!>();
		List<AutoVarDecl!> newVars = new List<AutoVarDecl!>();
		
		Expect(53);
		x = token; 
		CallStmtSubExpr(out e);
		if (t.kind == 15 || t.kind == 44) {
			if (t.kind == 15) {
				Get();
				e = ConvertToLocal(e);
				if (e is IdentifierExpr) {
				  RecordCallLhs((IdentifierExpr)e, lhs, newVars);
				} else if (e is FieldSelectExpr) {
				  SemErr(e.tok, "each LHS of call statement must be a variable, not a field");
				} else {
				  SemErr(e.tok, "each LHS of call statement must be a variable");
				}
				
				Ident(out id);
				RecordCallLhs(new IdentifierExpr(id, id.val), lhs, newVars); 
				while (t.kind == 15) {
					Get();
					Ident(out id);
					RecordCallLhs(new IdentifierExpr(id, id.val), lhs, newVars); 
				}
				Expect(44);
				CallStmtSubExpr(out e);
			} else {
				Get();
				e = ConvertToLocal(e);
				if (e is IdentifierExpr) {
				  RecordCallLhs((IdentifierExpr)e, lhs, newVars);
				} else if (e is FieldSelectExpr) {
				  SemErr(e.tok, "each LHS of call statement must be a variable, not a field");
				} else {
				  SemErr(e.tok, "each LHS of call statement must be a variable");
				}
				
				CallStmtSubExpr(out e);
			}
		}
		Expect(13);
		if (e is FunctionCallExpr) {
		 FunctionCallExpr fce = (FunctionCallExpr)e;
		 s = new CallStmt(x, newVars, lhs, fce.Receiver, fce.Name, fce.Args);  // this actually does an ownership transfer of fce.Args
		} else {
		  SemErr("RHS of call statement must denote a method invocation");
		  s = new CallStmt(x, newVars, lhs, dummyExpr, "dummyMethodName", new List<Expression!>());
		}
		
	}

	static void IfStmt(out Statement! ifStmt) {
		Token! x;
		Expression guard;
		Statement! thn;
		Statement! s;
		Statement els = null;
		
		Expect(49);
		x = token; 
		Guard(out guard);
		BlockStmt(out thn);
		if (t.kind == 50) {
			Get();
			if (t.kind == 49) {
				IfStmt(out s);
				els = s; 
			} else if (t.kind == 6) {
				BlockStmt(out s);
				els = s; 
			} else Error(115);
		}
		ifStmt = new IfStmt(x, guard, thn, els); 
	}

	static void WhileStmt(out Statement! stmt) {
		Token! x;
		Expression guard;
		bool isFree;  Expression! e;
		List<MaybeFreeExpression!> invariants = new List<MaybeFreeExpression!>();
		List<Expression!> decreases = new List<Expression!>();
		Statement! body;
		
		Expect(51);
		x = token; 
		Guard(out guard);
		assume guard == null || Owner.None(guard); 
		while (t.kind == 22 || t.kind == 25 || t.kind == 52) {
			if (t.kind == 22 || t.kind == 52) {
				isFree = false; 
				if (t.kind == 22) {
					Get();
					isFree = true; 
				}
				Expect(52);
				Expression(out e);
				invariants.Add(new MaybeFreeExpression(e, isFree)); 
				Expect(13);
			} else {
				Get();
				PossiblyWildExpression(out e);
				decreases.Add(e); 
				while (t.kind == 15) {
					Get();
					PossiblyWildExpression(out e);
					decreases.Add(e); 
				}
				Expect(13);
			}
		}
		BlockStmt(out body);
		stmt = new WhileStmt(x, guard, invariants, decreases, body); 
	}

	static void MatchStmt(out Statement! s) {
		Token x;  Expression! e;  MatchCaseStmt! c;
		List<MatchCaseStmt!> cases = new List<MatchCaseStmt!>(); 
		Expect(38);
		x = token; 
		Expression(out e);
		Expect(6);
		while (t.kind == 39) {
			CaseStatement(out c);
			cases.Add(c); 
		}
		Expect(7);
		s = new MatchStmt(x, e, cases); 
	}

	static void ForeachStmt(out Statement! s) {
		Token! x, boundVar;
		Type! ty;
		Expression! collection;
		Expression! range;
		List<PredicateStmt!> bodyPrefix = new List<PredicateStmt!>();
		AssignStmt bodyAssign = null;
		
		parseVarScope.PushMarker(); 
		Expect(54);
		x = token;
		range = new LiteralExpr(x, true);
		ty = new InferredTypeProxy();
		
		Expect(26);
		Ident(out boundVar);
		if (t.kind == 16) {
			Get();
			Type(out ty);
		}
		Expect(55);
		Expression(out collection);
		parseVarScope.Push(boundVar.val, boundVar.val); 
		if (t.kind == 56) {
			Get();
			Expression(out range);
		}
		Expect(27);
		Expect(6);
		while (t.kind == 57 || t.kind == 58 || t.kind == 59) {
			if (t.kind == 57) {
				AssertStmt(out s);
				if (s is PredicateStmt) { bodyPrefix.Add((PredicateStmt)s); } 
			} else if (t.kind == 58) {
				AssumeStmt(out s);
				if (s is PredicateStmt) { bodyPrefix.Add((PredicateStmt)s); } 
			} else {
				UseStmt(out s);
				if (s is PredicateStmt) { bodyPrefix.Add((PredicateStmt)s); } 
			}
		}
		if (StartOf(12)) {
			AssignStmt(out s);
			if (s is AssignStmt) { bodyAssign = (AssignStmt)s; } 
		} else if (t.kind == 48) {
			HavocStmt(out s);
			if (s is AssignStmt) { bodyAssign = (AssignStmt)s; } 
		} else Error(116);
		Expect(7);
		if (bodyAssign != null) {
		 s = new ForeachStmt(x, new BoundVar(boundVar, boundVar.val, ty), collection, range, bodyPrefix, bodyAssign);
		} else {
		  s = dummyStmt;  // some error occurred in parsing the bodyAssign
		}
		
		parseVarScope.PopMarker(); 
	}

	static void LhsExpr(out Expression! e) {
		SelectExpression(out e);
	}

	static void AssignRhs(out Expression e, out Type ty) {
		Token! x;  Expression! ee;  Type! tt;
		e = null;  ty = null;
		
		if (t.kind == 45) {
			Get();
			TypeAndToken(out x, out tt);
			ty = tt; 
			if (t.kind == 46) {
				Get();
				Expression(out ee);
				Expect(47);
				e = ee; 
			}
		} else if (StartOf(7)) {
			Expression(out ee);
			e = ee; 
		} else Error(117);
		if (e == null && ty == null) { e = dummyExpr; } 
	}

	static void SelectExpression(out Expression! e) {
		Token! id;  e = dummyExpr; 
		if (t.kind == 1) {
			IdentOrFuncExpression(out e);
		} else if (t.kind == 26 || t.kind == 92 || t.kind == 93) {
			ObjectExpression(out e);
		} else Error(118);
		while (t.kind == 46 || t.kind == 89) {
			SelectOrCallSuffix(ref e);
		}
	}

	static void IdentTypeRhs(out VarDecl! d, bool isGhost) {
		Token! id;  Type! ty;  Expression! e;
		Expression rhs = null;  Type newType = null;
		Type optionalType = null;  DeterminedAssignmentRhs optionalRhs = null;
		
		Ident(out id);
		if (t.kind == 16) {
			Get();
			Type(out ty);
			optionalType = ty; 
		}
		if (t.kind == 44) {
			Get();
			AssignRhs(out rhs, out newType);
		}
		if (newType == null && rhs != null) {
		 optionalRhs = new ExprRhs(rhs);
		} else if (newType != null) {
		  if (rhs == null) {
		    optionalRhs = new TypeRhs(newType);
		  } else {
		    optionalRhs = new TypeRhs(newType, rhs);
		  }
		} else if (optionalType == null) {
		  optionalType = new InferredTypeProxy();
		}
		d = new VarDecl(id, id.val, optionalType, isGhost, optionalRhs);
		
	}

	static void Guard(out Expression e) {
		Expression! ee;  e = null; 
		Expect(26);
		if (t.kind == 36) {
			Get();
			e = null; 
		} else if (StartOf(7)) {
			Expression(out ee);
			e = ee; 
		} else Error(119);
		Expect(27);
	}

	static void CaseStatement(out MatchCaseStmt! c) {
		Token! x, id, arg;
		List<BoundVar!> arguments = new List<BoundVar!>();
		List<Statement!> body = new List<Statement!>();
		
		Expect(39);
		x = token;  parseVarScope.PushMarker(); 
		Ident(out id);
		if (t.kind == 26) {
			Get();
			Ident(out arg);
			arguments.Add(new BoundVar(arg, arg.val, new InferredTypeProxy()));
			parseVarScope.Push(arg.val, arg.val); 
			while (t.kind == 15) {
				Get();
				Ident(out arg);
				arguments.Add(new BoundVar(arg, arg.val, new InferredTypeProxy()));
				parseVarScope.Push(arg.val, arg.val); 
			}
			Expect(27);
		}
		Expect(40);
		parseVarScope.PushMarker(); 
		while (StartOf(8)) {
			Stmt(body);
		}
		parseVarScope.PopMarker(); 
		c = new MatchCaseStmt(x, id.val, arguments, body); 
		parseVarScope.PopMarker(); 
	}

	static void CallStmtSubExpr(out Expression! e) {
		e = dummyExpr; 
		if (t.kind == 1) {
			IdentOrFuncExpression(out e);
		} else if (t.kind == 26 || t.kind == 92 || t.kind == 93) {
			ObjectExpression(out e);
			SelectOrCallSuffix(ref e);
		} else Error(120);
		while (t.kind == 46 || t.kind == 89) {
			SelectOrCallSuffix(ref e);
		}
	}

	static void AttributeArg(out Attributes.Argument! arg) {
		Expression! e;  arg = dummyAttrArg; 
		if (t.kind == 3) {
			Get();
			arg = new Attributes.Argument(token.val.Substring(1, token.val.Length-2)); 
		} else if (StartOf(7)) {
			Expression(out e);
			arg = new Attributes.Argument(e); 
		} else Error(121);
	}

	static void EquivExpression(out Expression! e0) {
		Token! x;  Expression! e1; 
		ImpliesExpression(out e0);
		while (t.kind == 62 || t.kind == 63) {
			EquivOp();
			x = token; 
			ImpliesExpression(out e1);
			e0 = new BinaryExpr(x, BinaryExpr.Opcode.Iff, e0, e1); 
		}
	}

	static void ImpliesExpression(out Expression! e0) {
		Token! x;  Expression! e1; 
		LogicalExpression(out e0);
		if (t.kind == 64 || t.kind == 65) {
			ImpliesOp();
			x = token; 
			ImpliesExpression(out e1);
			e0 = new BinaryExpr(x, BinaryExpr.Opcode.Imp, e0, e1); 
		}
	}

	static void EquivOp() {
		if (t.kind == 62) {
			Get();
		} else if (t.kind == 63) {
			Get();
		} else Error(122);
	}

	static void LogicalExpression(out Expression! e0) {
		Token! x;  Expression! e1; 
		RelationalExpression(out e0);
		if (StartOf(13)) {
			if (t.kind == 66 || t.kind == 67) {
				AndOp();
				x = token; 
				RelationalExpression(out e1);
				e0 = new BinaryExpr(x, BinaryExpr.Opcode.And, e0, e1); 
				while (t.kind == 66 || t.kind == 67) {
					AndOp();
					x = token; 
					RelationalExpression(out e1);
					e0 = new BinaryExpr(x, BinaryExpr.Opcode.And, e0, e1); 
				}
			} else {
				OrOp();
				x = token; 
				RelationalExpression(out e1);
				e0 = new BinaryExpr(x, BinaryExpr.Opcode.Or, e0, e1); 
				while (t.kind == 68 || t.kind == 69) {
					OrOp();
					x = token; 
					RelationalExpression(out e1);
					e0 = new BinaryExpr(x, BinaryExpr.Opcode.Or, e0, e1); 
				}
			}
		}
	}

	static void ImpliesOp() {
		if (t.kind == 64) {
			Get();
		} else if (t.kind == 65) {
			Get();
		} else Error(123);
	}

	static void RelationalExpression(out Expression! e0) {
		Token! x;  Expression! e1;  BinaryExpr.Opcode op; 
		Term(out e0);
		if (StartOf(14)) {
			RelOp(out x, out op);
			Term(out e1);
			e0 = new BinaryExpr(x, op, e0, e1); 
		}
	}

	static void AndOp() {
		if (t.kind == 66) {
			Get();
		} else if (t.kind == 67) {
			Get();
		} else Error(124);
	}

	static void OrOp() {
		if (t.kind == 68) {
			Get();
		} else if (t.kind == 69) {
			Get();
		} else Error(125);
	}

	static void Term(out Expression! e0) {
		Token! x;  Expression! e1;  BinaryExpr.Opcode op; 
		Factor(out e0);
		while (t.kind == 79 || t.kind == 80) {
			AddOp(out x, out op);
			Factor(out e1);
			e0 = new BinaryExpr(x, op, e0, e1); 
		}
	}

	static void RelOp(out Token! x, out BinaryExpr.Opcode op) {
		x = Token.NoToken;  op = BinaryExpr.Opcode.Add/*(dummy)*/; 
		switch (t.kind) {
		case 70: {
			Get();
			x = token;  op = BinaryExpr.Opcode.Eq; 
			break;
		}
		case 17: {
			Get();
			x = token;  op = BinaryExpr.Opcode.Lt; 
			break;
		}
		case 18: {
			Get();
			x = token;  op = BinaryExpr.Opcode.Gt; 
			break;
		}
		case 71: {
			Get();
			x = token;  op = BinaryExpr.Opcode.Le; 
			break;
		}
		case 72: {
			Get();
			x = token;  op = BinaryExpr.Opcode.Ge; 
			break;
		}
		case 73: {
			Get();
			x = token;  op = BinaryExpr.Opcode.Neq; 
			break;
		}
		case 74: {
			Get();
			x = token;  op = BinaryExpr.Opcode.Disjoint; 
			break;
		}
		case 55: {
			Get();
			x = token;  op = BinaryExpr.Opcode.In; 
			break;
		}
		case 75: {
			Get();
			x = token;  op = BinaryExpr.Opcode.NotIn; 
			break;
		}
		case 76: {
			Get();
			x = token;  op = BinaryExpr.Opcode.Neq; 
			break;
		}
		case 77: {
			Get();
			x = token;  op = BinaryExpr.Opcode.Le; 
			break;
		}
		case 78: {
			Get();
			x = token;  op = BinaryExpr.Opcode.Ge; 
			break;
		}
		default: Error(126); break;
		}
	}

	static void Factor(out Expression! e0) {
		Token! x;  Expression! e1;  BinaryExpr.Opcode op; 
		UnaryExpression(out e0);
		while (t.kind == 36 || t.kind == 81 || t.kind == 82) {
			MulOp(out x, out op);
			UnaryExpression(out e1);
			e0 = new BinaryExpr(x, op, e0, e1); 
		}
	}

	static void AddOp(out Token! x, out BinaryExpr.Opcode op) {
		x = Token.NoToken;  op=BinaryExpr.Opcode.Add/*(dummy)*/; 
		if (t.kind == 79) {
			Get();
			x = token;  op = BinaryExpr.Opcode.Add; 
		} else if (t.kind == 80) {
			Get();
			x = token;  op = BinaryExpr.Opcode.Sub; 
		} else Error(127);
	}

	static void UnaryExpression(out Expression! e) {
		Token! x;  e = dummyExpr; 
		if (t.kind == 80) {
			Get();
			x = token; 
			UnaryExpression(out e);
			e = new BinaryExpr(x, BinaryExpr.Opcode.Sub, new LiteralExpr(x, 0), e); 
		} else if (t.kind == 83 || t.kind == 84) {
			NegOp();
			x = token; 
			UnaryExpression(out e);
			e = new UnaryExpr(x, UnaryExpr.Opcode.Not, e); 
		} else if (StartOf(12)) {
			SelectExpression(out e);
		} else if (StartOf(15)) {
			ConstAtomExpression(out e);
		} else Error(128);
	}

	static void MulOp(out Token! x, out BinaryExpr.Opcode op) {
		x = Token.NoToken;  op = BinaryExpr.Opcode.Add/*(dummy)*/; 
		if (t.kind == 36) {
			Get();
			x = token;  op = BinaryExpr.Opcode.Mul; 
		} else if (t.kind == 81) {
			Get();
			x = token;  op = BinaryExpr.Opcode.Div; 
		} else if (t.kind == 82) {
			Get();
			x = token;  op = BinaryExpr.Opcode.Mod; 
		} else Error(129);
	}

	static void NegOp() {
		if (t.kind == 83) {
			Get();
		} else if (t.kind == 84) {
			Get();
		} else Error(130);
	}

	static void ConstAtomExpression(out Expression! e) {
		Token! x, dtName, id;  BigInteger n;  List<Expression!>! elements;
		e = dummyExpr;  
		
		switch (t.kind) {
		case 85: {
			Get();
			e = new LiteralExpr(token, false); 
			break;
		}
		case 86: {
			Get();
			e = new LiteralExpr(token, true); 
			break;
		}
		case 87: {
			Get();
			e = new LiteralExpr(token); 
			break;
		}
		case 2: {
			Nat(out n);
			e = new LiteralExpr(token, n); 
			break;
		}
		case 88: {
			Get();
			x = token; 
			Ident(out dtName);
			Expect(89);
			Ident(out id);
			elements = new List<Expression!>(); 
			if (t.kind == 26) {
				Get();
				if (StartOf(7)) {
					Expressions(elements);
				}
				Expect(27);
			}
			e = new DatatypeValue(token, dtName.val, id.val, elements); 
			break;
		}
		case 90: {
			Get();
			x = token; 
			Expect(26);
			Expression(out e);
			Expect(27);
			e = new FreshExpr(x, e); 
			break;
		}
		case 56: {
			Get();
			x = token; 
			Expression(out e);
			e = new UnaryExpr(x, UnaryExpr.Opcode.SeqLength, e); 
			Expect(56);
			break;
		}
		case 6: {
			Get();
			x = token;  elements = new List<Expression!>(); 
			if (StartOf(7)) {
				Expressions(elements);
			}
			e = new SetDisplayExpr(x, elements); 
			Expect(7);
			break;
		}
		case 46: {
			Get();
			x = token;  elements = new List<Expression!>(); 
			if (StartOf(7)) {
				Expressions(elements);
			}
			e = new SeqDisplayExpr(x, elements); 
			Expect(47);
			break;
		}
		default: Error(131); break;
		}
	}

	static void Nat(out BigInteger n) {
		Expect(2);
		try {
		 n = BigInteger.Parse(token.val);
		} catch (System.FormatException) {
		  SemErr("incorrectly formatted number");
		  n = BigInteger.Zero;
		}
		
	}

	static void IdentOrFuncExpression(out Expression! e) {
		Token! id;  e = dummyExpr;  List<Expression!>! args; 
		Ident(out id);
		if (t.kind == 26) {
			Get();
			args = new List<Expression!>(); 
			if (StartOf(7)) {
				Expressions(args);
			}
			Expect(27);
			e = new FunctionCallExpr(id, id.val, new ImplicitThisExpr(id), args); 
		}
		if (e == dummyExpr) {
		 if (parseVarScope.Find(id.val) != null) {
		   e = new IdentifierExpr(id, id.val);
		 } else {
		   e = new FieldSelectExpr(id, new ImplicitThisExpr(id), id.val);
		 }
		}
		
	}

	static void ObjectExpression(out Expression! e) {
		Token! x;  e = dummyExpr; 
		if (t.kind == 92) {
			Get();
			e = new ThisExpr(token); 
		} else if (t.kind == 93) {
			Get();
			x = token; 
			Expect(26);
			Expression(out e);
			Expect(27);
			e = new OldExpr(x, e); 
		} else if (t.kind == 26) {
			Get();
			if (StartOf(16)) {
				QuantifierGuts(out e);
			} else if (StartOf(7)) {
				Expression(out e);
			} else Error(132);
			Expect(27);
		} else Error(133);
	}

	static void SelectOrCallSuffix(ref Expression! e) {
		Token! id, x;  List<Expression!>! args;
		Expression e0 = null;  Expression e1 = null;  Expression! ee;  bool anyDots = false;
		bool func = false;
		
		if (t.kind == 89) {
			Get();
			Ident(out id);
			if (t.kind == 26) {
				Get();
				args = new List<Expression!>();  func = true; 
				if (StartOf(7)) {
					Expressions(args);
				}
				Expect(27);
				e = new FunctionCallExpr(id, id.val, e, args); 
			}
			if (!func) { e = new FieldSelectExpr(id, e, id.val); } 
		} else if (t.kind == 46) {
			Get();
			x = token; 
			if (StartOf(7)) {
				Expression(out ee);
				e0 = ee; 
				if (t.kind == 44 || t.kind == 91) {
					if (t.kind == 91) {
						Get();
						anyDots = true; 
						if (StartOf(7)) {
							Expression(out ee);
							e1 = ee; 
						}
					} else {
						Get();
						Expression(out ee);
						e1 = ee; 
					}
				}
			} else if (t.kind == 91) {
				Get();
				Expression(out ee);
				anyDots = true;  e1 = ee; 
			} else Error(134);
			if (!anyDots && e0 == null) {
			 /* a parsing error occurred */
			 e0 = dummyExpr;
			}
			assert !anyDots ==> e0 != null;
			if (anyDots) {
			  assert e0 != null || e1 != null;
			  e = new SeqSelectExpr(x, false, e, e0, e1);
			} else if (e1 == null) {
			  assert e0 != null;
			  e = new SeqSelectExpr(x, true, e, e0, null);
			} else {
			  assert e0 != null;
			  e = new SeqUpdateExpr(x, e, e0, e1);
			}
			
			Expect(47);
		} else Error(135);
	}

	static void QuantifierGuts(out Expression! q) {
		Token! x = Token.NoToken;
		bool univ = false;
		BoundVar! bv;
		List<BoundVar!> bvars = new List<BoundVar!>();
		Token! tok;  Expr! e;  ExprSeq! es;
		Attributes attrs = null;
		Triggers trigs = null;
		Expression! body;
		
		if (t.kind == 94 || t.kind == 95) {
			Forall();
			x = token;  univ = true; 
		} else if (t.kind == 96 || t.kind == 97) {
			Exists();
			x = token; 
		} else Error(136);
		parseVarScope.PushMarker(); 
		IdentTypeOptional(out bv);
		bvars.Add(bv);  parseVarScope.Push(bv.Name, bv.Name); 
		while (t.kind == 15) {
			Get();
			IdentTypeOptional(out bv);
			bvars.Add(bv);  parseVarScope.Push(bv.Name, bv.Name); 
		}
		while (t.kind == 6) {
			AttributeOrTrigger(ref attrs, ref trigs);
		}
		QSep();
		Expression(out body);
		if (univ) {
		 q = new ForallExpr(x, bvars, body, trigs, attrs);
		} else {
		  q = new ExistsExpr(x, bvars, body, trigs, attrs);
		}
		parseVarScope.PopMarker();
		
	}

	static void Forall() {
		if (t.kind == 94) {
			Get();
		} else if (t.kind == 95) {
			Get();
		} else Error(137);
	}

	static void Exists() {
		if (t.kind == 96) {
			Get();
		} else if (t.kind == 97) {
			Get();
		} else Error(138);
	}

	static void AttributeOrTrigger(ref Attributes attrs, ref Triggers trigs) {
		List<Expression!> es = new List<Expression!>();
		
		Expect(6);
		if (t.kind == 16) {
			AttributeBody(ref attrs);
		} else if (StartOf(7)) {
			es = new List<Expression!>(); 
			Expressions(es);
			trigs = new Triggers(es, trigs); 
		} else Error(139);
		Expect(7);
	}

	static void QSep() {
		if (t.kind == 98) {
			Get();
		} else if (t.kind == 99) {
			Get();
		} else Error(140);
	}

	static void AttributeBody(ref Attributes attrs) {
		string aName;
		List<Attributes.Argument!> aArgs = new List<Attributes.Argument!>();
		Attributes.Argument! aArg;
		
		Expect(16);
		Expect(1);
		aName = token.val; 
		if (StartOf(17)) {
			AttributeArg(out aArg);
			aArgs.Add(aArg); 
			while (t.kind == 15) {
				Get();
				AttributeArg(out aArg);
				aArgs.Add(aArg); 
			}
		}
		attrs = new Attributes(aName, aArgs, attrs); 
	}



	public static void Parse() {
		Errors.SynErr = new ErrorProc(SynErr);
		t = new Token();
		Get();
		Dafny();

	}

	[Microsoft.Contracts.Verify(false)]
	static void SynErr(int n, string filename, int line, int col) {
		Errors.count++;
		System.Console.Write("{0}({1},{2}): syntax error: ", filename, line, col);
		string s;
		switch (n) {
			case 0: s = "EOF expected"; break;
			case 1: s = "ident expected"; break;
			case 2: s = "digits expected"; break;
			case 3: s = "string expected"; break;
			case 4: s = "module expected"; break;
			case 5: s = "imports expected"; break;
			case 6: s = "{ expected"; break;
			case 7: s = "} expected"; break;
			case 8: s = "class expected"; break;
			case 9: s = "ghost expected"; break;
			case 10: s = "static expected"; break;
			case 11: s = "unlimited expected"; break;
			case 12: s = "datatype expected"; break;
			case 13: s = "; expected"; break;
			case 14: s = "var expected"; break;
			case 15: s = ", expected"; break;
			case 16: s = ": expected"; break;
			case 17: s = "< expected"; break;
			case 18: s = "> expected"; break;
			case 19: s = "method expected"; break;
			case 20: s = "returns expected"; break;
			case 21: s = "modifies expected"; break;
			case 22: s = "free expected"; break;
			case 23: s = "requires expected"; break;
			case 24: s = "ensures expected"; break;
			case 25: s = "decreases expected"; break;
			case 26: s = "( expected"; break;
			case 27: s = ") expected"; break;
			case 28: s = "bool expected"; break;
			case 29: s = "int expected"; break;
			case 30: s = "set expected"; break;
			case 31: s = "seq expected"; break;
			case 32: s = "object expected"; break;
			case 33: s = "array expected"; break;
			case 34: s = "function expected"; break;
			case 35: s = "reads expected"; break;
			case 36: s = "* expected"; break;
			case 37: s = "` expected"; break;
			case 38: s = "match expected"; break;
			case 39: s = "case expected"; break;
			case 40: s = "=> expected"; break;
			case 41: s = "label expected"; break;
			case 42: s = "break expected"; break;
			case 43: s = "return expected"; break;
			case 44: s = ":= expected"; break;
			case 45: s = "new expected"; break;
			case 46: s = "[ expected"; break;
			case 47: s = "] expected"; break;
			case 48: s = "havoc expected"; break;
			case 49: s = "if expected"; break;
			case 50: s = "else expected"; break;
			case 51: s = "while expected"; break;
			case 52: s = "invariant expected"; break;
			case 53: s = "call expected"; break;
			case 54: s = "foreach expected"; break;
			case 55: s = "in expected"; break;
			case 56: s = "| expected"; break;
			case 57: s = "assert expected"; break;
			case 58: s = "assume expected"; break;
			case 59: s = "use expected"; break;
			case 60: s = "print expected"; break;
			case 61: s = "then expected"; break;
			case 62: s = "<==> expected"; break;
			case 63: s = "\\u21d4 expected"; break;
			case 64: s = "==> expected"; break;
			case 65: s = "\\u21d2 expected"; break;
			case 66: s = "&& expected"; break;
			case 67: s = "\\u2227 expected"; break;
			case 68: s = "|| expected"; break;
			case 69: s = "\\u2228 expected"; break;
			case 70: s = "== expected"; break;
			case 71: s = "<= expected"; break;
			case 72: s = ">= expected"; break;
			case 73: s = "!= expected"; break;
			case 74: s = "!! expected"; break;
			case 75: s = "!in expected"; break;
			case 76: s = "\\u2260 expected"; break;
			case 77: s = "\\u2264 expected"; break;
			case 78: s = "\\u2265 expected"; break;
			case 79: s = "+ expected"; break;
			case 80: s = "- expected"; break;
			case 81: s = "/ expected"; break;
			case 82: s = "% expected"; break;
			case 83: s = "! expected"; break;
			case 84: s = "\\u00ac expected"; break;
			case 85: s = "false expected"; break;
			case 86: s = "true expected"; break;
			case 87: s = "null expected"; break;
			case 88: s = "# expected"; break;
			case 89: s = ". expected"; break;
			case 90: s = "fresh expected"; break;
			case 91: s = ".. expected"; break;
			case 92: s = "this expected"; break;
			case 93: s = "old expected"; break;
			case 94: s = "forall expected"; break;
			case 95: s = "\\u2200 expected"; break;
			case 96: s = "exists expected"; break;
			case 97: s = "\\u2203 expected"; break;
			case 98: s = ":: expected"; break;
			case 99: s = "\\u2022 expected"; break;
			case 100: s = "??? expected"; break;
			case 101: s = "invalid ClassMemberDecl"; break;
			case 102: s = "invalid FunctionDecl"; break;
			case 103: s = "invalid MethodDecl"; break;
			case 104: s = "invalid TypeAndToken"; break;
			case 105: s = "invalid MethodSpec"; break;
			case 106: s = "invalid MethodSpec"; break;
			case 107: s = "invalid Expression"; break;
			case 108: s = "invalid ReferenceType"; break;
			case 109: s = "invalid FunctionSpec"; break;
			case 110: s = "invalid FunctionBody"; break;
			case 111: s = "invalid PossiblyWildFrameExpression"; break;
			case 112: s = "invalid PossiblyWildExpression"; break;
			case 113: s = "invalid Stmt"; break;
			case 114: s = "invalid OneStmt"; break;
			case 115: s = "invalid IfStmt"; break;
			case 116: s = "invalid ForeachStmt"; break;
			case 117: s = "invalid AssignRhs"; break;
			case 118: s = "invalid SelectExpression"; break;
			case 119: s = "invalid Guard"; break;
			case 120: s = "invalid CallStmtSubExpr"; break;
			case 121: s = "invalid AttributeArg"; break;
			case 122: s = "invalid EquivOp"; break;
			case 123: s = "invalid ImpliesOp"; break;
			case 124: s = "invalid AndOp"; break;
			case 125: s = "invalid OrOp"; break;
			case 126: s = "invalid RelOp"; break;
			case 127: s = "invalid AddOp"; break;
			case 128: s = "invalid UnaryExpression"; break;
			case 129: s = "invalid MulOp"; break;
			case 130: s = "invalid NegOp"; break;
			case 131: s = "invalid ConstAtomExpression"; break;
			case 132: s = "invalid ObjectExpression"; break;
			case 133: s = "invalid ObjectExpression"; break;
			case 134: s = "invalid SelectOrCallSuffix"; break;
			case 135: s = "invalid SelectOrCallSuffix"; break;
			case 136: s = "invalid QuantifierGuts"; break;
			case 137: s = "invalid Forall"; break;
			case 138: s = "invalid Exists"; break;
			case 139: s = "invalid AttributeOrTrigger"; break;
			case 140: s = "invalid QSep"; break;

			default: s = "error " + n; break;
		}
		System.Console.WriteLine(s);
	}

	static bool[,]! set = {
	{T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x},
	{x,x,x,x, T,x,x,x, T,T,T,T, T,x,T,x, x,x,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x},
	{x,x,x,x, x,x,x,x, x,T,T,T, x,x,T,x, x,x,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x},
	{x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, x,T,x,x, x,x,x,x, x,x,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x},
	{x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,T,T,T, T,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x},
	{x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,T,T,T, T,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x},
	{x,T,x,x, x,x,x,x, x,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, T,T,T,T, T,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x},
	{x,T,T,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,T,x,x, x,x,x,x, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, T,x,x,T, T,T,T,T, T,x,T,x, T,T,x,x, x,x,x,x, x,x},
	{x,T,x,x, x,x,T,x, x,T,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,T,x, x,T,T,T, x,x,x,x, T,T,x,T, x,T,T,x, x,T,T,T, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, T,T,x,x, x,x,x,x, x,x},
	{x,T,T,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, T,x,x,T, T,T,T,T, T,x,T,x, T,T,x,x, x,x,x,x, x,x},
	{x,T,T,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, T,x,x,x, x,x,x,x, x,x,T,x, x,T,x,x, x,x,x,x, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, T,x,x,T, T,T,T,T, T,x,T,x, T,T,x,x, x,x,x,x, x,x},
	{x,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,T,x, x,T,T,T, x,x,x,x, T,T,x,T, x,T,T,x, x,T,T,T, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, T,T,x,x, x,x,x,x, x,x},
	{x,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, T,T,x,x, x,x,x,x, x,x},
	{x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,T, T,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x},
	{x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,T,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,T, T,T,T,T, T,T,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x},
	{x,x,T,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,T,T,T, T,x,T,x, x,x,x,x, x,x,x,x, x,x},
	{x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,T, T,T,x,x, x,x},
	{x,T,T,T, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,T,x,x, x,x,x,x, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, T,x,x,T, T,T,T,T, T,x,T,x, T,T,x,x, x,x,x,x, x,x}

	};

	[Microsoft.Contracts.Verify(false)]
	static Parser() {}
} // end Parser

} // end namespace