"Fossies" - the Fresh Open Source Software Archive

Member "gentle-97/examples/virtual/virtual.g" (20 Aug 1998, 9958 Bytes) of package /linux/misc/old/gentle-97.tar.gz:


As a special service "Fossies" has tried to format the requested text file into HTML format (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    1 /*****************************************************************************/
    2 /*                                                                           */
    3 /*  A compiler for PL/0                                                      */
    4 /*                                                                           */
    5 /*  Source language and target machine of this compiler are described in     */
    6 /*                                                                           */
    7 /*  Niklaus Wirth                                                            */
    8 /*  Compilerbau                                                              */
    9 /*  B.G. Teubner, Stuttgart 1986                                             */
   10 /*                                                                           */
   11 /*****************************************************************************/
   12 
   13 -- Abstract syntax
   14 
   15 'type' Block
   16    block(ConstDecls, VarDecls, ProcDecls, Statement)
   17 
   18 'type' ConstDecls
   19    list(ConstDecl, ConstDecls), nil
   20 
   21 'type' ConstDecl
   22    const(IDENT, INT, POS)
   23 
   24 'type' VarDecls
   25    list(VarDecl, VarDecls), nil
   26 
   27 'type' VarDecl
   28    var(IDENT, POS)
   29 
   30 'type' ProcDecls
   31    list(ProcDecl, ProcDecls), nil
   32 
   33 'type' ProcDecl
   34    proc(IDENT, Block, POS)
   35 
   36 'type' Statement
   37    assign(IDENT, Expression, POS)
   38    call(IDENT, POS)
   39    seq(Statement, Statement)
   40    if(Condition, Statement)
   41    while(Condition, Statement)
   42    null
   43    put(Expression)
   44 
   45 'type' Condition
   46    odd(Expression)
   47    rel(Op, Expression, Expression)
   48 
   49 'type' Expression
   50    neg(Expression)
   51    binary(Op, Expression, Expression)
   52    id(IDENT, POS)
   53    int(INT)
   54 
   55 'type' Op
   56    plus, minus, times, div, eq, ne, lt, le, gt, ge
   57 
   58 'type' IDENT
   59 
   60 -- Concrete syntax
   61 
   62 'root'
   63    program(-> B)
   64    trafo(B)
   65 
   66 'nonterm' program(-> Block)
   67 'rule' program(-> B):
   68    block(-> B) "."
   69 
   70 'nonterm' block(-> Block)
   71 'rule' block(-> block(C, V, P, S)):
   72    constpart(-> C) varpart(-> V) procpart(-> P) statement(-> S)
   73 
   74 'nonterm' constpart(-> ConstDecls)
   75 'rule' constpart(-> C): "const" constdeflist(-> C) ";"
   76 'rule' constpart(-> nil):
   77 
   78 'nonterm' constdeflist(-> ConstDecls)
   79 'rule' constdeflist(-> list(D, L)): constdef(-> D) "," constdeflist(-> L)
   80 'rule' constdeflist(-> list(D, nil)): constdef(-> D)
   81 
   82 'nonterm'constdef(-> ConstDecl)
   83 'rule' constdef(-> const(I, N, Pos)): Ident(-> I) @(-> Pos) "=" Number(-> N)
   84 
   85 'nonterm' varpart(-> VarDecls)
   86 'rule' varpart(-> V): "var" vardecllist(-> V) ";"
   87 'rule' varpart(-> nil):
   88 
   89 'nonterm' vardecllist(-> VarDecls)
   90 'rule' vardecllist(-> list(D, L)): vardecl(-> D) "," vardecllist(-> L)
   91 'rule' vardecllist(-> list(D, nil)): vardecl(-> D)
   92 
   93 'nonterm' vardecl(-> VarDecl)
   94 'rule' vardecl(-> var(I, Pos)): Ident(-> I) @(-> Pos)
   95 
   96 'nonterm' procpart(-> ProcDecls)
   97 'rule' procpart(-> list(D, L)): procdef(-> D) procpart(-> L)
   98 'rule' procpart(-> nil):
   99 
  100 'nonterm' procdef(-> ProcDecl)
  101 'rule' procdef(-> proc(I, B, Pos)):
  102    "procedure" Ident(-> I) @(-> Pos) ";" block(-> B) ";"
  103 
  104 'nonterm' statement(-> Statement)
  105 'rule' statement(-> assign(I, E, P)): Ident(-> I) @(-> P) ":=" expression(-> E)
  106 'rule' statement(-> call(I, P)): "call" Ident(-> I) @(-> P)
  107 'rule' statement(-> S): "begin" statementlist(-> S) "end"
  108 'rule' statement(-> if(C, S)): "if" condition(-> C) "then" statement(-> S)
  109 'rule' statement(-> while(C, S)): "while" condition(-> C) "do" statement(-> S)
  110 'rule' statement(-> put(E)): "put" expression(-> E)
  111 'rule' statement(-> null):
  112 
  113 'nonterm' statementlist(-> Statement)
  114 'rule' statementlist(-> seq(S, L)): statement(-> S) ";" statementlist(-> L)
  115 'rule' statementlist(-> S): statement(-> S)
  116 
  117 'nonterm' condition(-> Condition)
  118 'rule' condition(-> odd(E)): "odd" expression(-> E)
  119 'rule' condition(-> rel(Op, E1, E2)):
  120    expression(-> E1) relop(-> Op) expression(-> E2)
  121 
  122 'nonterm' relop(-> Op)
  123 'rule' relop(-> eq): "="
  124 'rule' relop(-> ne): "#"
  125 'rule' relop(-> lt): "<"
  126 'rule' relop(-> le): "<="
  127 'rule' relop(-> gt): ">"
  128 'rule' relop(-> ge): ">="
  129 
  130 'nonterm' expression(-> Expression)
  131 'rule' expression(-> E): "+" term(-> E)
  132 'rule' expression(-> neg(E)): "-" term(-> E)
  133 'rule' expression(-> E): expr2(-> E)
  134 
  135 'nonterm' expr2(-> Expression)
  136 'rule' expr2(-> binary(Op, E1, E2)): expr2(-> E1) addop(-> Op) term(-> E2)
  137 'rule' expr2(-> E): term(-> E)
  138 
  139 'nonterm' addop(-> Op)
  140 'rule' addop(-> plus): "+"
  141 'rule' addop(-> minus): "-"
  142 
  143 'nonterm' term(-> Expression)
  144 'rule' term(-> binary(Op, E1, E2)): term(-> E1) mulop(-> Op) factor(-> E2)
  145 'rule' term(-> E): factor(-> E)
  146 
  147 'nonterm' mulop(-> Op)
  148 'rule' mulop(-> times): "*"
  149 'rule' mulop(-> div): "/"
  150 
  151 'nonterm' factor(-> Expression)
  152 'rule' factor(-> id(I, P)): Ident(-> I) @(-> P)
  153 'rule' factor(-> int(N)): Number(-> N)
  154 'rule' factor(-> E): "(" expression(-> E) ")"
  155 
  156 'token' Ident(-> IDENT)
  157 'token' Number(-> INT)
  158 -- Trafo
  159 'action' trafo(Block)
  160 'rule' trafo(B)
  161    InitEnv
  162    trBlock(B)
  163    execute
  164 
  165 'var' Offset: INT
  166 
  167 'action' trBlock(Block)
  168 'rule' trBlock(block(ConstDecls, VarDecls, ProcDecls, Statement)):
  169    EnterScope
  170    trConstDecls(ConstDecls)
  171    Offset <- 3
  172    trVarDecls(VarDecls)
  173    Offset -> N
  174    PC(-> X)
  175    JMP(0)
  176    trProcDecls(ProcDecls)
  177    PATCH(X)
  178    INT_(N)
  179    trStatement(Statement)
  180    OPR(0)
  181    LeaveScope
  182 
  183 'action' trConstDecls(ConstDecls)
  184 'rule' trConstDecls(list(ConstDecl, ConstDecls)):
  185    trConstDecl(ConstDecl)
  186    trConstDecls(ConstDecls)
  187 'rule' trConstDecls(nil):
  188 
  189 'action' trConstDecl(ConstDecl)
  190 'rule' trConstDecl(const(Id, N, Pos)):
  191    Define(Id, const(N), Pos)
  192 
  193 'action' trVarDecls(VarDecls)
  194 'rule' trVarDecls(list(VarDecl, VarDecls)):
  195    trVarDecl(VarDecl)
  196    trVarDecls(VarDecls)
  197 'rule' trVarDecls(nil):
  198 
  199 'action' trVarDecl(VarDecl)
  200 'rule' trVarDecl(var(Id, Pos)):
  201    CurrentLevel -> L
  202    Offset -> N
  203    Offset <- N+1
  204    Define(Id, var(L, N), Pos)
  205 
  206 'action' trProcDecls(ProcDecls)
  207 'rule' trProcDecls(list(ProcDecl, ProcDecls)):
  208    trProcDecl(ProcDecl)
  209    trProcDecls(ProcDecls)
  210 'rule' trProcDecls(nil):
  211 
  212 'action' trProcDecl(ProcDecl)
  213 'rule' trProcDecl(proc(Id, Block, Pos)):
  214    CurrentLevel -> Lev
  215    PC(-> X)
  216    Define(Id, proc(Lev, X), Pos)
  217    trBlock(Block)
  218 
  219 'action' trStatement(Statement)
  220 'rule' trStatement(assign(Id, Expression, Pos)):
  221    trExpression(Expression)
  222    (| Apply(Id -> var(L, A))
  223       CurrentLevel -> CurLev
  224       STO(CurLev-L,A)
  225    || ErrorI("[1] '", Id, "' not defined as variable", Pos)
  226    |)
  227 'rule' trStatement(call(Id, Pos)):
  228    (| Apply(Id -> proc(L, A))
  229       CurrentLevel -> CurLev
  230       CAL(CurLev-L,A)
  231    || ErrorI("[2] '", Id, "' not defined as procedure", Pos)
  232    |)
  233 'rule' trStatement(seq(Statement1, Statement2)):
  234    trStatement(Statement1)
  235    trStatement(Statement2)
  236 'rule' trStatement(if(Condition, Statement)):
  237    trCondition(Condition)
  238    PC(-> X)
  239    JPC(0)
  240    trStatement(Statement)
  241    PATCH(X)
  242 'rule' trStatement(while(Condition, Statement)):
  243    PC(-> X1)
  244    trCondition(Condition)
  245    PC(-> X2)
  246    JPC(0)
  247    trStatement(Statement)
  248    JMP(X1)
  249    PATCH(X2)
  250 'rule' trStatement(null):
  251 'rule' trStatement(put(Expression)):
  252    trExpression(Expression)
  253    OPR(14)
  254 
  255 'action' trCondition(Condition)
  256 'rule' trCondition(odd(Expression)):
  257    trExpression(Expression)
  258    OPR(6)
  259 'rule' trCondition(rel(Op, Expression1, Expression2)):
  260    trExpression(Expression1)
  261    trExpression(Expression2)
  262    OpCode(Op -> N)
  263    OPR(N)
  264 
  265 'action' trExpression(Expression)
  266 'rule' trExpression(neg(Expression)):
  267    trExpression(Expression)
  268    OPR(1)
  269 'rule' trExpression(binary(Op, Expression1, Expression2)):
  270    trExpression(Expression1)
  271    trExpression(Expression2)
  272    OpCode(Op -> N)
  273    OPR(N)
  274 'rule' trExpression(id(Id, Pos)):
  275    (| Apply(Id -> const(N))
  276       LIT(N)
  277    || Apply(Id -> var(L, A))
  278       CurrentLevel -> CurLev
  279       LOD(CurLev-L,A)
  280    || ErrorI("[3] '", Id, "' not defined as constant or variable", Pos)
  281    |)
  282 'rule' trExpression(int(N)):
  283    LIT(N) 
  284 
  285 'action' OpCode(Op -> INT)
  286 'rule' OpCode(plus -> 2)
  287 'rule' OpCode(minus -> 3)
  288 'rule' OpCode(times -> 4)
  289 'rule' OpCode(div -> 5)
  290 'rule' OpCode(eq -> 8)
  291 'rule' OpCode(ne -> 9)
  292 'rule' OpCode(lt -> 10)
  293 'rule' OpCode(ge -> 11)
  294 'rule' OpCode(gt -> 12)
  295 'rule' OpCode(le -> 13)
  296 
  297 -- Error messages
  298 
  299 'action' ErrorI (STRING, IDENT, STRING, POS)
  300 -- Instructions
  301 
  302 'action' LIT(INT)
  303 'action' OPR(INT)
  304 'action' LOD(L: INT, A: INT)
  305 'action' STO(L: INT, A: INT)
  306 'action' CAL(L: INT, A: INT)
  307 'action' INT_(INT)
  308 'action' JMP(INT)
  309 'action' JPC(INT)
  310 
  311 'action' PC(-> INT)
  312 'action' PATCH(INT)
  313 
  314 'action' execute
  315 
  316 -- Scopes
  317 
  318 'type' Object
  319    const(INT)
  320    var(Level: INT, Addr: INT)
  321    proc(Level: INT, Addr: INT)
  322 
  323 'action' DefMeaning (IDENT, ASSOC)
  324 'condition' HasMeaning (IDENT -> ASSOC)
  325 
  326 'type' ENV
  327    env (NEST, ENV), emptyenv 
  328 
  329 'type' NEST
  330    nest (IDENT, NEST), emptynest
  331 
  332 'type' ASSOC
  333    assoc(Obj: Object, Level: INT, Hidden: ASSOC), noassoc
  334 
  335 'var' CurrentEnv: ENV
  336 'var' CurrentNest: NEST
  337 'var' CurrentLevel: INT
  338 
  339 'action' InitEnv
  340 'rule' InitEnv :
  341    CurrentEnv <- emptyenv
  342    CurrentNest <- emptynest
  343    CurrentLevel <- 0
  344 
  345 'action' EnterScope
  346 'rule' EnterScope :
  347    CurrentEnv -> OldEnv
  348    CurrentNest -> OldNest
  349    CurrentEnv <- env(OldNest, OldEnv)
  350    CurrentNest <- emptynest
  351    CurrentLevel -> N
  352    CurrentLevel <- N+1
  353 
  354 'action' LeaveScope
  355 'rule' LeaveScope :
  356    CurrentEnv -> env (OldNest, OldEnv)
  357    CurrentNest -> Nest
  358    ForgetNest (Nest)
  359    CurrentEnv <- OldEnv
  360    CurrentNest <- OldNest
  361    CurrentLevel -> N
  362    CurrentLevel <- N-1
  363 
  364 'action' Define (IDENT, Object, POS)
  365 'rule' Define (Ident, Object, Pos) :
  366    CurrentLevel -> ThisLev
  367    (| HasMeaning(Ident -> Hidden)
  368       where(Hidden -> assoc(_,L,_))
  369       [| eq(L, ThisLev)
  370 	 ErrorI("[4] multiple declaration of '", Ident, "'", Pos)
  371       |]
  372    || let(noassoc -> Hidden)
  373    |)
  374    DefMeaning (Ident, assoc(Object, ThisLev, Hidden))
  375    CurrentNest -> Nest
  376    CurrentNest <- nest(Ident, Nest)
  377 
  378 'condition' Apply (IDENT -> Object)
  379 'rule' Apply (Ident -> Object) :
  380    HasMeaning (Ident -> assoc(Object,Lev,Hidden))
  381 
  382 'action' ForgetNest (NEST)
  383 'rule' ForgetNest (nest(Id, Nest)) :
  384    HasMeaning (Id -> assoc(Obj, Lev, Hidden))
  385    DefMeaning (Id, Hidden)
  386    ForgetNest (Nest)
  387 'rule' ForgetNest (emptynest) :