M2compiler-V3/compiler/src/M2.atg

COMPILER M2
(* Step 1 — minimal integer pipeline (m2compiler-V3).
   Subset: program MODULE + CONST (literal) + VAR INTEGER +
   assignment + integer expressions (+ - * DIV MOD, leading sign,
   parens). Fresh QBE backend (QbeGen) to gen_ssa/<Module>.ssa;
   assemble with qbe, link with cc.

   Test convention: a global VAR ExitCode : INTEGER makes generated
   $main return its value as the process exit code, else return 0.

   Semantic errors reuse the V1/V2/Test2 family: 200 duplicate,
   201 undeclared, 202 module name mismatch, 210 bad assignment,
   211 bad arithmetic, 221 not a type, 230 construct not supported
   in step 1 (REAL/STRING literals, non-INTEGER VAR types,
   non-literal CONST expressions, imported names as values).
   Full language arrives in later steps; the 230s mark its edge. *)

IMPORT SymTab, QbeGen;

CHARACTERS
  eol      = CHR(13) .
  lf       = CHR(10) .
  letter   = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
  digit    = "0123456789" .
  hexDigit = digit + "ABCDEFabcdef" .
  noQuote1 = ANY - "'" - eol .
  noQuote2 = ANY - '"' - eol .

IGNORE CHR(9) .. CHR(13)

COMMENTS FROM "(*" TO "*)" NESTED
COMMENTS FROM "//" TO lf

TOKENS
  ident   = letter { letter | digit } .
  integer = digit { digit }
          | "0x" hexDigit { hexDigit }
          | "0X" hexDigit { hexDigit } .
  real    = digit { digit } "." { digit }
            [ ( "E" | "e" ) [ "+" | "-" ] digit { digit } ] .
  string  = "'" { noQuote1 } "'"
          | '"' { noQuote2 } '"' .

PRODUCTIONS
  M2
    = Unit "." .
  (* Units: program modules compile fully; DEFINITION and
     IMPLEMENTATION modules parse + check now but lower in step 4
     (each ends with one 230); same for nested local modules. *)
  Unit
    = DefUnit
    | ImplUnit
    | ProgModule .
  DefUnit                               (. VAR m1, m2: SymTab.Name; .)
    = "DEFINITION" "MODULE"
      GetIdent<m1>                      (. SymTab.Init; QbeGen.OpenModule(m1);
                                           IF ~SymTab.Enter(m1,
                                              SymTab.KindModule) THEN
                                             SemError(200) END; .)
      ";"
      { Import }
      { ConstBlock | OpaqueBlock | VarBlock }
      "END"
      GetIdent<m2>                      (. IF ~SymTab.Equal(m1, m2) THEN
                                             SemError(202) END; .)
                                        (. QbeGen.CloseModule;
                                           SemError(230);
                                           SymTab.PrintTable; .) .
  ImplUnit                              (. VAR m1, m2: SymTab.Name; .)
    = "IMPLEMENTATION" "MODULE"
      GetIdent<m1>                      (. SymTab.Init; QbeGen.OpenModule(m1);
                                           IF ~SymTab.Enter(m1,
                                              SymTab.KindModule) THEN
                                             SemError(200) END; .)
      ";"
      { Import }
      DeclSeq
      [ "BEGIN"                         (. QbeGen.BeginBody; .)
        [ StatSeq ] ]
      "END"
      GetIdent<m2>                      (. IF ~SymTab.Equal(m1, m2) THEN
                                             SemError(202) END; .)
                                        (. QbeGen.CloseModule;
                                           SemError(230);
                                           SymTab.PrintTable; .) .
  ProgModule                            (. VAR m1, m2: SymTab.Name; .)
    = "MODULE"
      GetIdent<m1>                      (. SymTab.Init; QbeGen.OpenModule(m1);
                                           IF ~SymTab.Enter(m1,
                                              SymTab.KindModule) THEN
                                             SemError(200) END; .)
      [ Priority ]
      ";"
      { Import }
      DeclSeq
      [ "BEGIN"                         (. QbeGen.BeginBody; .)
        [ StatSeq ] ]
      "END"
      GetIdent<m2>                      (. IF ~SymTab.Equal(m1, m2) THEN
                                             SemError(202) END; .)
                                        (. QbeGen.EndModule;
                                           SymTab.PrintTable; .) .
  DeclSeq
    = { ConstBlock | VarBlock | NestedModule ";" } .
  (* Local module, Wirth form. Parses + checks fully (own scope);
     lowering waits for step 4, marked by one 230 at END. *)
  NestedModule                          (. VAR m1, m2: SymTab.Name; .)
    = "MODULE"
      GetIdent<m1>                      (. IF ~SymTab.Enter(m1,
                                             SymTab.KindModule) THEN
                                             SemError(200) END;
                                           SymTab.PushScope; .)
      [ Priority ]
      ";"
      { Import }
      [ Export ]
      DeclSeq
      [ "BEGIN"
        [ StatSeq ] ]
      "END"
      GetIdent<m2>                      (. IF ~SymTab.Equal(m1, m2) THEN
                                             SemError(202) END;
                                           SymTab.PopScope;
                                           SemError(230); .) .
  Priority
    = "[" integer "]"                   (. SemError(230); .) .
  Export                                (. VAR nm: SymTab.Name; .)
    = "EXPORT"                          (* names wire up in step 4 *)
      [ "QUALIFIED" ]
      GetIdent<nm>
      { "," GetIdent<nm> }
      ";" .
  Import                                (. VAR n: SymTab.Name; .)
    = "FROM"
      GetIdent<n>                       (. IF ~SymTab.Enter(n,
                                             SymTab.KindImport) THEN
                                             SemError(200) END; .)
      "IMPORT"
      ImpList ";"
    | "IMPORT"
      ImpList ";" .
  ImpList                               (. VAR n: SymTab.Name; .)
    = GetIdent<n>                       (. IF ~SymTab.Enter(n,
                                             SymTab.KindImport) THEN
                                             SemError(200) END; .)
      { ","
        GetIdent<n>                     (. IF ~SymTab.Enter(n,
                                             SymTab.KindImport) THEN
                                             SemError(200) END; .) } .
  (* Opaque TYPE declarations (definition modules). The targetless
     alias resolves to InvalidType until step 4 completes it. *)
  OpaqueBlock
    = "TYPE" { OpaqueDecl ";" } .
  OpaqueDecl                            (. VAR n: SymTab.Name; .)
    = GetIdent<n>                       (. IF ~SymTab.Enter(n,
                                             SymTab.KindType) THEN
                                             SemError(200) END;
                                           SymTab.SetSymType(n,
                                             SymTab.NewAlias()); .) .
  ConstBlock
    = "CONST" { ConstDecl ";" } .
  ConstDecl                             (. VAR n: SymTab.Name;
                                             t: SymTab.TypeIndex;
                                             qv: QbeGen.QVal;
                                             cls: INTEGER; .)
    = GetIdent<n>                       (. IF ~SymTab.Enter(n,
                                             SymTab.KindConst) THEN
                                             SemError(200) END; .)
      "="
      Expr<t, qv>                       (. SymTab.SetSymType(n, t);
                                           cls := SymTab.ClassOf(t);
                                           IF cls = SymTab.ClStr THEN
                                             SemError(230)
                                           ELSIF ~QbeGen.IsImm(qv) THEN
                                             SemError(230) END;
                                           QbeGen.DeclConst(n, qv, t); .) .
  VarBlock
    = "VAR" { VarDecl ";" } .
  VarDecl                               (. VAR n, nm: SymTab.Name;
                                             t: SymTab.TypeIndex;
                                             i: CARDINAL;
                                             cls: INTEGER; .)
    = VarIdents ":"
      GetIdent<n>                       (. IF ~SymTab.Lookup(n) THEN
                                             SemError(201);
                                             t := SymTab.InvalidType
                                           ELSIF (SymTab.SymKind(n) #
                                                  SymTab.KindType)
                                              & (SymTab.SymKind(n) #
                                                 SymTab.KindPredef) THEN
                                             SemError(221);
                                             t := SymTab.InvalidType
                                           ELSE t := SymTab.SymType(n)
                                           END;
                                           cls := SymTab.ClassOf(t);
                                           IF (t # SymTab.InvalidType)
                                              & (cls # SymTab.ClInt) THEN
                                             SemError(230) END;
                                           i := 0;
                                           WHILE i < SymTab.PendCount() DO
                                             SymTab.PendName(i, nm);
                                             QbeGen.DeclVar(nm, t);
                                             INC(i)
                                           END;
                                           SymTab.FixPending(t); .) .
  VarIdents                             (. VAR n: SymTab.Name; .)
    = GetIdent<n>                       (. IF ~SymTab.EnterPending(n,
                                             SymTab.KindVar) THEN
                                             SemError(200) END; .)
      { ","
        GetIdent<n>                     (. IF ~SymTab.EnterPending(n,
                                             SymTab.KindVar) THEN
                                             SemError(200) END; .) } .
  StatSeq
    = Statement { ";" Statement } .
  Statement
    = Assign .
  Assign                                (. VAR dt, et: SymTab.TypeIndex;
                                             dk: INTEGER;
                                             qd, qe: QbeGen.QVal;
                                             qn: SymTab.Name; .)
    = Design<dt, dk, qd, qn> ":="
      Expr<et, qe>                      (. IF (dt # SymTab.InvalidType)
                                           & (dk # SymTab.KindVar) THEN
                                           SemError(210)
                                         ELSIF ~SymTab.Assignable(et,
                                                  dt) THEN
                                           SemError(210) END;
                                         IF (dk = SymTab.KindVar)
                                            & (dt # SymTab.InvalidType)
                                            & (et # SymTab.InvalidType) THEN
                                           QbeGen.StoreVar(qn, qe, FALSE)
                                         END; .) .
  (* Designator, step-1 form: scalar variables and constants only.
     No suffixes (field/index/deref are syntax errors in step 1). *)
  Design<VAR t: SymTab.TypeIndex; VAR k: INTEGER;
         VAR q: QbeGen.QVal; VAR qn: SymTab.Name>
                                        (. VAR n: SymTab.Name;
                                             cls: INTEGER; .)
    = GetIdent<n>                       (. QbeGen.CopyOp(n, qn);
                                           IF ~SymTab.Lookup(n) THEN
                                             SemError(201);
                                             t := SymTab.InvalidType;
                                             k := -1;
                                             QbeGen.CopyOp("0", q)
                                           ELSE
                                             t := SymTab.SymType(n);
                                             k := SymTab.SymKind(n);
                                             IF k = SymTab.KindConst THEN
                                               IF SymTab.Equal(n,
                                                  "TRUE") THEN
                                                 t := SymTab.BoolType();
                                                 QbeGen.CopyOp("1", q)
                                               ELSIF SymTab.Equal(n,
                                                  "FALSE") THEN
                                                 t := SymTab.BoolType();
                                                 QbeGen.CopyOp("0", q)
                                               ELSE
                                                 cls :=
                                                   SymTab.ClassOf(t);
                                                 IF (t #
                                                     SymTab.InvalidType)
                                                    & (cls = SymTab.ClInt) THEN
                                                   QbeGen.LoadVar(n,
                                                     FALSE, q)
                                                 ELSE
                                                   QbeGen.CopyOp("0", q)
                                                 END
                                               END
                                             ELSIF k = SymTab.KindVar THEN
                                               cls :=
                                                 SymTab.ClassOf(t);
                                               IF cls = SymTab.ClInt THEN
                                                 QbeGen.LoadVar(n,
                                                   FALSE, q)
                                               ELSE SemError(230);
                                                 QbeGen.CopyOp("0", q)
                                               END
                                             ELSE QbeGen.CopyOp("0", q);
                                               IF k = SymTab.KindImport THEN
                                                 SemError(230)
                                               END
                                             END
                                           END; .) .
  Expr<VAR t: SymTab.TypeIndex; VAR q: QbeGen.QVal>
    = SimExpr<t, q> .
  SimExpr<VAR t: SymTab.TypeIndex; VAR q: QbeGen.QVal>
                                        (. VAR t2, res2: SymTab.TypeIndex;
                                             op: INTEGER;
                                             q2, qt: QbeGen.QVal;
                                             neg: BOOLEAN; .)
    =                                   (. neg := FALSE; .)
      [ "+" | "-"                       (. neg := TRUE; .) ]
      Term<t, q>                        (. IF neg THEN
                                           IF QbeGen.IsImm(q) THEN
                                             QbeGen.NegFold(q, q)
                                           ELSE QbeGen.NewTemp(qt);
                                             QbeGen.NegQ(q, qt, FALSE);
                                             QbeGen.CopyOp(qt, q)
                                           END
                                         END; .)
      { AddOp<op> Term<t2, q2>
        (. IF SymTab.ArithCheck(t, t2, FALSE, res2) THEN
             t := res2
           ELSE SemError(211); t := SymTab.InvalidType END;
           IF t # SymTab.InvalidType THEN
             QbeGen.NewTemp(qt);
             IF op = SymTab.OpAdd THEN
               QbeGen.Op3("add", qt, q, q2, FALSE)
             ELSE
               QbeGen.Op3("sub", qt, q, q2, FALSE)
             END;
             QbeGen.CopyOp(qt, q)
           ELSE QbeGen.CopyOp("0", q)
           END; .) } .
  AddOp<VAR op: INTEGER>
    = "+"                               (. op := SymTab.OpAdd; .)
    | "-"                               (. op := SymTab.OpSub; .) .
  Term<VAR t: SymTab.TypeIndex; VAR q: QbeGen.QVal>
                                        (. VAR t2, res2: SymTab.TypeIndex;
                                             op: INTEGER;
                                             q2, qt: QbeGen.QVal; .)
    = Fact<t, q> { MulOp<op> Fact<t2, q2>
      (. IF SymTab.ArithCheck(t, t2,
            (op = SymTab.OpDiv) OR (op = SymTab.OpMod),
            res2) THEN t := res2
         ELSE SemError(211); t := SymTab.InvalidType END;
         IF t # SymTab.InvalidType THEN
           QbeGen.NewTemp(qt);
           IF op = SymTab.OpTimes THEN
             QbeGen.Op3("mul", qt, q, q2, FALSE)
           ELSIF op = SymTab.OpDiv THEN
             QbeGen.Op3("div", qt, q, q2, FALSE)
           ELSE
             QbeGen.Op3("rem", qt, q, q2, FALSE)
           END;
           QbeGen.CopyOp(qt, q)
         ELSE QbeGen.CopyOp("0", q)
         END; .) } .
  MulOp<VAR op: INTEGER>
    = "*"                               (. op := SymTab.OpTimes; .)
    | "DIV"                             (. op := SymTab.OpDiv; .)
    | "MOD"                             (. op := SymTab.OpMod; .) .
  Fact<VAR t: SymTab.TypeIndex; VAR q: QbeGen.QVal>
                                        (. VAR s: ARRAY [0 .. 255] OF CHAR;
                                             et, dt: SymTab.TypeIndex;
                                             dk: INTEGER;
                                             qd: QbeGen.QVal;
                                             qn: SymTab.Name; .)
    = integer                           (. LexString(s);
                                           QbeGen.NormInt(s, q);
                                           t := SymTab.IntType(); .)
    | real                              (. LexString(s);
                                           t := SymTab.RealType();
                                           SemError(230);
                                           QbeGen.CopyOp("0", q); .)
    | string                            (. LexString(s);
                                           IF SymTab.StrLen(s) <= 3 THEN
                                             t := SymTab.CharType();
                                             QbeGen.IntStr(
                                               QbeGen.CharVal(s), q)
                                           ELSE t := SymTab.NewStr();
                                             SemError(230);
                                             QbeGen.CopyOp("0", q)
                                           END; .)
    | Design<dt, dk, qd, qn>            (. t := dt;
                                           QbeGen.CopyOp(qd, q); .)
    | "(" Expr<et, q> ")"               (. t := et; .) .
  GetIdent<VAR n: SymTab.Name>
    = ident                             (. LexName(n); .) .

END M2.