Re: Language Design n Compiler

On 2009-12-14, honey sran <sran.harshdeep@gmail.com> wrote:
> hi i'm new to compilers and language design. i want to write a simple
> language and its grammer- with elementary operations say addition ,
> subtraction,printing etc. and corresponding compiler for that
> language- how and from where should i to start( what all know how is
> required to design a language.). plz point out the steps involved in
> the whole process.


Start by learning Lisp.


Here is my one-Usenet-article, 15-minute compiler in one Lisp
function to get you started.


It supports an expression language with forms like:


    <IDENT> ;; denotes a named storage location
    <NUMBER> ;; denotes a constant
    (+ <EXPR> <EXPR>) ;; add two expressions
    (< <EXP1> <EXP2>) ;; determine whether EXP1 is less than EXP2,
                                            ;; yielding zero and nonzero


    (= <IDENT> <EXPR>) ;; assignment




    (if <E1> <E2> <E3>) ;; ternary if


    (while <E1> ;; loop
        <EXPR> ...)




Code:


;; compile expression, returning
;; register holding the value computed by
;; the expression.


(defun compile-expr (out-stream expr)
    (let ((t0 (gentemp "T")))
        (cond
          ;; NIL expression: let's compile that to a NOOP just for fun
          ((null expr)
            (format out-stream " NOOP~%")
            (values 'zero)) ;; let's understand noop to ``yield'' the zero reg.
          ;; variable reference: compile to LOAD instruction
          ((symbolp expr)
            (format out-stream " LOAD ~a, ~a~%" t0 expr)
            (values t0))
          ;; number: compile to load-immediate
          ((numberp expr)
            (format out-stream " LI ~a, ~a~%" t0 expr)
            (values t0))
          ;; otherwise compound expression
          (t
              ;; plus, minus, multiply, divide, relative ops
              (ecase (first expr)
                  ((+ - * / < > <= >= == !=)
                    (let ((insn (ecase (first expr)
                                                (+ 'ADD) (- 'SUB)
                                                (* 'MUL) (/ 'DIV)
                                                (< 'LT) (> 'GT)
                                                (<= 'LE) (>= 'GE)
                                                (== 'EQ) (!= 'NEQ)))
                                (t1 (compile-expr out-stream (second expr)))
                                (t2 (compile-expr out-stream (third expr))))
                        (format out-stream " ~a ~a, ~a, ~a~%" insn t0 t1 t2)
                        (values t0)))
                  ;; (= sym val) assignment
                  (= (destructuring-bind (oper sym val) expr
                            (check-type sym symbol)
                            (let ((t1 (compile-expr out-stream val)))
                                (format out-stream " STORE ~a, ~a~%" sym t1))))
                  ;; (if antecedent-condition consequent alternative)
                  (if (destructuring-bind (oper ante conseq alter) expr
                              (let ((l0 (gentemp "L"))
                                          (l1 (gentemp "L"))
                                          (t1 (compile-expr out-stream ante))
                                          t2 t3)
                                  (format out-stream " BEQ ~a, ~a~%" t1 l0);
                                  (setf t2 (compile-expr out-stream conseq))
                                  (format out-stream " MOV ~a, ~a~%" t0 t2)
                                  (format out-stream " BRA ~a~%" l1)
                                  (format out-stream "~a:~%" l0)
                                  (setf t3 (compile-expr out-stream ante))
                                  (format out-stream " MOV ~a, ~a~%" t0 t3)
                                  (format out-stream "~a:~%" l1)
                                  (values t0))))
                    ;; (while guard-condition forms ...)
                  (while (destructuring-bind (oper guard &rest forms) expr
                                    (let ((l0 (gentemp "L"))
                                                (l1 (gentemp "L"))
                                                t1)
                                        (format out-stream "~a:~%" l0)
                                        (setf t1 (compile-expr out-stream guard))
                                        (format out-stream " BEQ ~a, ~a~%" t1 l1)
                                        (dolist (form forms)
                                            (compile-expr out-stream form))
                                        (format out-stream " BRA ~a~%" l0)
                                        (format out-stream "~a:~%" l1)
                                        (values 'zero)))))))))




Test run, interactive session with CLISP:


kaz@localhost~ $ clisp -q -i compiler.lisp
;; Loading file compiler.lisp ...
;; Loaded file compiler.lisp
[1]> (compile-expr *standard-output* 1)
        LI T4, 1
T4
[2]> (compile-expr *standard-output* 'a)
        LOAD T5, A
T5
[3]> (compile-expr *standard-output* '(= a 3))
        LI T7, 3
        STORE A, T7
T7
[4]> (compile-expr *standard-output* '(+ a b))
        LOAD T9, A
        LOAD T10, B
        ADD T8, T9, T10
T8
[5]> (compile-expr *standard-output* '(while (< a 10) (if (> a 5) (= a (+ a 2)) (= a (+ a 1)))))
L12:
        LOAD T15, A
        LI T16, 10
        LT T14, T15, T16
        BEQ T14, L13
        LOAD T21, A
        LI T22, 5
        GT T20, T21, T22
        BEQ T20, L18
        LOAD T25, A
        LI T26, 2
        ADD T24, T25, T26
        STORE A, T24
        MOV T17, T24
        BRA L19
L18:
        LOAD T29, A
        LI T30, 1
        ADD T28, T29, T30
        STORE A, T28
        MOV T17, T28
L19:
        BRA L12
L13:
ZERO




Exercises.


1. Replace the textual output (stream and format calls) with
      logic which outputs instructions as data, returning a list of
      instructions and labels. Choose a Lispy representation for the
      instructions and labels, like for instance (mov t10 t11) or l13.


2. Write code to break an instruction sequence into basic blocks,
      returning a graph structure.


3. Implement a jump threading optimization. If a branch
      a target label which denotes an unconditional
      branch, rewrite the original branch so that it goes
      directly to the target of that unconditional branch.
      Modify the code so that it repeatedly applies the
      strategy until no more jumps can be threaded.
      For instance in the last example above, there is
      a branch to L19, which just branches back to L12.
      These branches could go to L12 directly.


4. Write code to identify dead temporaries (i.e. which
      have no next use) and remove them. For instance
      the MOV T17, ... instructions in the last example
      above are useless.

Return to the comp.compilers page.
Search the comp.compilers archives again.