diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/emit.lisp | 66 | ||||
| -rw-r--r-- | src/lex.lisp | 108 | ||||
| -rw-r--r-- | src/main.lisp | 19 | ||||
| -rw-r--r-- | src/package.lisp | 31 | ||||
| -rw-r--r-- | src/parse.lisp | 229 | ||||
| -rw-r--r-- | src/util.lisp | 64 |
6 files changed, 315 insertions, 202 deletions
diff --git a/src/emit.lisp b/src/emit.lisp new file mode 100644 index 0000000..acc2772 --- /dev/null +++ b/src/emit.lisp @@ -0,0 +1,66 @@ +(in-package #:emit) + +(defun fits-in-X-bits (n) + "Returns the number of bits required to represent N" + (ceiling (/ (log (ceiling n (log 2))) (log 2)))) + +(defmacro generate-type-map (ops) + "Generates an alist where the key corresponds to an element in +OPS, while the value is the index of that key (padded to the minimum +number of bits required to represent all +concatenated with TYPE." + `(let ((i 0) + (opsize (fits-in-X-bits (length ,ops)))) + (mapcar (lambda (x) + (incf i) + (cons x (util:format-as-binary i opsize))) + ,ops))) + +(defvar mnemonic-loc + `(,@(generate-type-map util:r-type) + ,@(generate-type-map util:i-type) + ,@(generate-type-map util:j-type)) + "An alist mapping known mnemonics to their binary representation.") + +(defun lookup-mnemonic (mnemonic) + (cdr (assoc mnemonic mnemonic-loc :test #'string=))) + +(defun p (d x) + (append x d)) + +(defun d (&rest lst) + (mapcar (lambda (x) (util:format-as-binary x 32)) lst)) + +(defun x (&rest lst) + lst) + +(defun r (mnemonic s1 s2 d) + (concatenate + 'string (format nil "~10,'0d" 0) d s2 s1 (lookup-mnemonic mnemonic) "00")) + +(defun i (mnemonic s d i) + (concatenate + 'string (util:format-as-binary i 16) d s (lookup-mnemonic mnemonic) "01")) + +(defun j (mnemonic b d) + (concatenate + 'string (util:format-as-binary d 21) b (lookup-mnemonic mnemonic) "10")) + +(defun rr (val) + (if (<= 0 val 23) + (util:format-as-binary val 5) + (error (format nil "~a is not a valid register id!~%" val)))) + +(defun imm (val) val) + +(defun l (l s) + (let ((d (util:get-label l))) + (- d s))) + +(defun var (s) + (let ((pos (util:get-variable s))) + (+ pos parse:line-number))) + +(defun emit (p) + (format t "~a~%" p) + (eval p)) diff --git a/src/lex.lisp b/src/lex.lisp deleted file mode 100644 index 5b1457d..0000000 --- a/src/lex.lisp +++ /dev/null @@ -1,108 +0,0 @@ -(in-package #:lex) - -(define-condition lexer-error (error) - ((message :initarg :message - :initform nil - :reader message)) - (:report (lambda (condition stream) - (format stream "~A" (message condition)))) - (:documentation "Dedicated error for an invalid lex.")) - -(defun file->tokens (file) - "Opens FILE and parses returns a list of tokens, or -NIL if the file could not be opened." - - (defun read-instr (lst tokens-so-far) - "Collects tokens in FILE into TOKENS-SO-FAR, splitting on a newline." - (let ((token (read-token))) - (cond ((null token) (reverse tokens-so-far)) - ((eq token 'nl) - (cons (reverse tokens-so-far) (read-instr nil nil))) - (t (read-instr lst (cons token tokens-so-far)))))) - - (and (probe-file file) - (with-open-file (*standard-input* file :direction :input) - (remove nil (read-instr '() '()))))) - -(defun read-token () - "Reads *STANDARD-INPUT* and returns a token, or nil if the end -of file has been reached. -Whitespace, commas, colons, and parentheses are token delimiters. -Comments start with a semi-colon ';' and all tokens after are ignored." - (let ((chr (read-char *standard-input* nil))) - (cond - ((null chr) chr) - - ((char= chr #\linefeed) 'nl) - - ((whitespace-char-p chr) - (read-token)) - - ((char= chr #\;) - (progn (read-line *standard-input* nil) - 'nl)) - - ((char= chr #\() 'left-paren) - ((char= chr #\)) 'right-paren) - - ((char= chr #\:) 'colon) - ((char= chr #\$) 'dollar) - - ((char= chr #\+) 'plus) - ((char= chr #\-) 'minus) - - ((digit-char-p chr) - (read-immediate chr)) - - ((alpha-char-p chr) - (read-keyword chr)) - - (t (error 'lexer-error - :message - (format nil "LEX failled--~a is not a valid lexical symbol.~%" chr)))))) - -(defun read-immediate (chr) - "Reads a sequence of digits, in base 2, 8, 10, or 16.. Throws -`invalid-immediate-or-keyword' error if an alphabetic character is encountered." - ;; may be combined with read-keyword-helper - (defun read-immediate-helper (chrs-so-far) - (let ((chr (peek-char nil *standard-input* nil))) - (cond ((and (not (null chr)) (digit-char-p chr)) - (read-immediate-helper (cons (read-char *standard-input* nil) chrs-so-far))) - ((and (not (null chr)) (alpha-char-p chr)) - (error 'lexer-error - :message - (format nil "LEX failed--encountered ~a while reading immediate.~%" chr))) - (t (reverse chrs-so-far))))) - - (let* ((next (peek-char nil *standard-input* nil)) - (radix (cond ((null next) 10) - ((char= next #\b) 2) - ((char= next #\o) 8) - ((char= next #\x) 16) - ((alpha-char-p next) nil) - (t 10))) - (arg (list chr))) - (when (and (char= chr #\0) radix (not (= radix 10))) - (read-char *standard-input* nil) - (setq arg '())) - (parse-integer (coerce (read-immediate-helper arg) 'string) :radix radix))) - -(defun read-keyword (chr) - "Reads a sequence of alphabetic characters. Throws `invalid-immediate-or-keyword' -error if a digit is encountered." - ;; may be combined with read-immediate-helper - (defun read-keyword-helper (chrs-so-far) - (let ((chr (peek-char nil *standard-input* nil))) - (cond ((and (not (null chr)) (alpha-char-p chr)) - (read-keyword-helper (cons (read-char *standard-input* nil) chrs-so-far))) - ((and (not (null chr)) (digit-char-p chr)) - (error 'lexer-error - :message - (format nil "LEX failed--encountered ~a while reading keyword.~%" chr))) - (t (reverse chrs-so-far))))) - (coerce (read-keyword-helper (list chr)) 'string)) - -(defun whitespace-char-p (x) - (or (char= #\space x) - (not (graphic-char-p x)))) diff --git a/src/main.lisp b/src/main.lisp index f6e5754..f20b022 100644 --- a/src/main.lisp +++ b/src/main.lisp @@ -1,6 +1,6 @@ (in-package #:rva) -(defparameter *banner* +(defvar *banner* " _/_/ _/_/ _/ _/ _/ _/ _/_/ _/ _/ _/_/_/ _/ @@ -19,13 +19,6 @@ _/_/ _/_/ " (list (clingon:make-option :flag - :description "run the lexer, but stop before parsing" - :long-name "lex" - :short-name #\l - :required nil - :key :lex) - (clingon:make-option - :flag :description "run the parser, but stop before emission" :long-name "parse" :short-name #\p @@ -37,17 +30,17 @@ _/_/ _/_/ " (print-splash) (let* ((args (clingon:command-arguments cmd)) (file (car args)) - (parse? (not (clingon:getopt cmd :lex))) (emit? (not (clingon:getopt cmd :parse)))) (cond ;; complain about num arguments ((/= (length args) 1) (error "Wrong number of arguments.~%")) ((not (util:asm-extension? file)) (error "The file is not an asm source code file.~%")) - (t (let ((tokens (lex:file->tokens file))) - (if tokens - (progn (pprint tokens) - (terpri)) + (t (let ((str (uiop:read-file-string file))) + (if str + (let ((ast (esrap:parse 'parse::str->ast (string-upcase str)))) + (when emit? + (format t "~a~%" (emit::emit ast)))) (error "The file does not exist, or it could not be opened.~%")) (format t "Nitimur in Vetitum~%")))))) diff --git a/src/package.lisp b/src/package.lisp index 3364856..bbb45a3 100644 --- a/src/package.lisp +++ b/src/package.lisp @@ -1,4 +1,4 @@ -helper(defpackage #:rva +(defpackage #:rva (:use #:cl) (:export #:main)) @@ -6,21 +6,22 @@ helper(defpackage #:rva (:use #:cl) (:export #:asm-extension? #:format-as-binary - #:type-r - #:type-i - #:type-j - #:label-loc)) + #:insert-in-middle + #:iota + #:riffle + #:add-variable + #:add-label + #:get-variable + #:get-label + #:r-type + #:i-type + #:j-type)) -(defpackage #:lex +(defpackage #:parse (:use #:cl) - (:export #:lexer-error - #:file->tokens - ;; exported for testing only - #:read-token)) + (:export #:str->ast + #:line-number)) -(defpackage #:parse +(defpackage #:emit (:use #:cl) - (:export #:parser-error - #:tokens->ast - ;; exported for testing only - #:extract-label)) + (:export #:emit)) diff --git a/src/parse.lisp b/src/parse.lisp index 3052583..d971444 100644 --- a/src/parse.lisp +++ b/src/parse.lisp @@ -1,55 +1,174 @@ -helper(in-package #:parse) - -(define-condition parser-error (error) - ((message :initarg :message - :initform nil - :reader message)) - (:report (lambda (condition stream) - (format stream "~A" (message condition)))) - (:documentation "Dedicated error for an invalid parse.")) - -(defun tokens->ast (program) - "Given PROGRAM, which is a list of lists of symbols, -filters out the labels and parses." - ;; TODO add directives - (let ((program (remove nil (mapcar #'extract-label program))) - (i 0)) - (mapcar (lambda (l) (extract-instruction l i)) program))) - -(let ((i 0)) - (defun extract-label (line) - "Given a series of tokens LINE, determines if LINE is -in the form STRING {colon}. If it is, then it is treated as a -label, and pushed onto the stack with the line index. - -Note that this function is intended to be called using mapcar, -so that labels can be added to a map and otherwise removed from -processing." - (trivia:match line - ((list (and id (type string)) - (satisfies (lambda (x) (equal x 'lex::colon)))) - (progn (push (cons (read-from-string id) i) util:label-loc) nil)) - (_ (progn (incf i) line))))) - -(defun extract-instruction (line i) - "Given instruction LINE, determines the expected type format and passes -LINE and the index I to the the respective function." - ;; TODO add pseudo-ops (i.e., nop, mov, ...) - (let* ((type-map '((r-type . extract-r-type) - (i-type . extract-i-type) - (j-type . extract-j-type))) - (keyword (car line)) - (type-fn (cdr (assoc keyword type-map)))) - (if type-fn - (funcall type-fn line i) - (error 'parser-error - (format nil "PARSE failed--~a is not a known keyword.~%" (keyword)))))) - -(defun extract-r-type (line i) - 'r) - -(defun extract-i-type (line i) - 'i) - -(defun extract-j-type (line i) - 'j) +(in-package #:parse) + +(defparameter line-number 0 + "The number of real instructions processed up until this point.") +(defparameter var-offset 0 + "The number of variables processed up until this point.") + +(esrap:defrule space + (+ (or #\space #\tab)) + (:constant nil)) + +(esrap:defrule nl (+ #\newline) + (:constant nil)) + +(esrap:defrule nl-inc (+ #\newline) + (:lambda (n) + (declare (ignore n)) + (incf line-number) + nil)) + +(esrap:defrule alpha (+ (alphanumericp character)) + (:text t)) + +;;; defines rules to parse an integer in various bases + +(defmacro define-number-rule ()) + +(esrap:defrule binary (and #\0 #\B (+ (or "0" "1"))) + (:lambda (e) (parse-integer (esrap:text (cddr e)) :radix 2))) + +(esrap:defrule octal (and #\0 #\O (+ (or (esrap:character-ranges (#\0 #\7))))) + (:lambda (e) (parse-integer (esrap:text (cddr e)) :radix 8))) + +(esrap:defrule decimal (+ (or (esrap:character-ranges (#\0 #\9)))) + (:lambda (e) (parse-integer (esrap:text e) :radix 10))) + +(esrap:defrule hex (and #\0 #\X (+ (or (esrap:character-ranges (#\0 #\9)) + "A" "B" "C" "D" "E" "F"))) + (:lambda (e) (parse-integer (esrap:text (cddr e)) :radix 16))) + +(esrap:defrule int (or binary octal hex decimal)) + +;;; defines rules to parse an operand + +(esrap:defrule register (and #\$ int) + (:function cadr) + (:lambda (e) (list 'emit::rr e))) + +(esrap:defrule var alpha + (:lambda (e) (list (list 'emit::rr 0) (list 'emit::var e)))) + +(esrap:defrule dereference (and (esrap:? (or #\+ #\-)) int #\( register #\)) + (:destructure (s i1 w1 r w2) + (declare (ignore w1 w2)) + (list r (list 'emit::imm (if (and s (string= s "-")) (- i1) i1))))) + +(esrap:defrule immediate int + (:lambda (e) (list 'emit::imm e))) + +;;; defines rules to parse labels + +(esrap:defrule label alpha + (:lambda (e) (list 'emit::l e line-number))) + +(esrap:defrule label-decl (and alpha #\:) + (:function car) + (:lambda (e) + (util:add-label e line-number) + nil)) + +;;; defines rules to parse instruction types + +(defun generate-mnemonic (name ops) + (let ((expr `(or ,@ops))) + (esrap:add-rule + name (make-instance 'esrap:rule :expression expr)))) + +;; define special cases first +(generate-mnemonic 'r-type-1-m '("NOT")) +(generate-mnemonic 'r-type-2-m '("CMP" "CEV")) +(generate-mnemonic 'i-type-1-m '("LOADV" "LOAD")) +(generate-mnemonic 'i-type-2-m '("STOREV" "STORE")) +(generate-mnemonic 'j-type-1-m '("JMP" "JAL")) +(generate-mnemonic 'j-type-2-m '("PUSH" "POP")) + +;; we need to reverse to ensure rules like "ADDV" are matched before "ADD" +(generate-mnemonic 'r-type-3-m (reverse util:r-type)) +(generate-mnemonic 'i-type-3-m (reverse util:i-type)) +(generate-mnemonic 'j-type-3-m (reverse util:j-type)) + +;; TODO this is pretty gross +(defmacro defrule-instr (name type-id order &rest destructure-pattern) + "Defines the boilerplate for a common esrap instruction rule. +NAME is the name of the non-terminal symbol. +TYPE-ID is the symbol which appears as the first element of a successful parse. +ORDER is the order to place the parsed tokens in the resulting list. +DESTRUCTURE-PATTERN is the list of non-terminals on the right side of the grammar rule." + (let* ((pattern-size (length destructure-pattern)) + (spaces (mapcar (lambda (x) (read-from-string (format nil "w~A" x))) (util:iota pattern-size))) + (vars (mapcar (lambda (x) (read-from-string (format nil "s~A" x))) (util:iota pattern-size)))) + `(esrap:defrule ,name + (and ,(read-from-string (format nil "~A-m" name)) ,@(util:riffle (make-list pattern-size :initial-element 'space) destructure-pattern)) + (:destructure (m ,@(util:riffle spaces vars)) + (declare (ignore ,@spaces)) + (list ,type-id m ,@(mapcar (lambda (x) (or (nth x vars) ''(emit::rr 0))) order)))))) + +(defrule-instr r-type-1 'emit::r (1 2 0) register register) +(defrule-instr r-type-2 'emit::r (0 1 2) register register) +(defrule-instr r-type-3 'emit::r (1 2 0) register register register) +(defrule-instr i-type-3 'emit::i (0 1 2) register register immediate) +(defrule-instr j-type-3 'emit::j (1 0) label) + +(esrap:defrule i-type-1 (and i-type-1-m space register space (or dereference var)) + (:destructure (m w1 s w2 di) + (declare (ignore w1 w2)) + `(emit::i ,m ,s ,@di))) + +(esrap:defrule i-type-2 (and i-type-2-m space register space (or dereference var)) + (:destructure (m w1 s w2 di) + (declare (ignore w1 w2)) + `(emit::i ,m ,@(util:insert-in-middle di s)))) + +(esrap:defrule j-type-1 (and j-type-1-m space dereference) + (:destructure (m w di) + (declare (ignore w)) + `(emit::j ,m ,@di))) + +(esrap:defrule j-type-2 (and j-type-2-m space register) + (:destructure (m w r) + (declare (ignore w)) + `(emit::j ,m ,r (emit::imm 0)))) + +(esrap:defrule instr (or r-type-1 r-type-2 r-type-3 i-type-1 i-type-2 + i-type-3 j-type-1 j-type-2 j-type-3)) + +;;; defines rules to parse the .text segment + +(esrap:defrule instr-clean (and (esrap:? space) instr (esrap:? space) nl-inc) + (:function cadr)) + +(esrap:defrule label-clean (and label-decl (esrap:? space) nl) + (:function car)) + +(esrap:defrule text-line (or instr-clean label-clean)) + +(esrap:defrule text (and ".TEXT" (esrap:? space) nl (* text-line)) + (:function cadddr) + (:lambda (e) `(emit::x ,@(remove nil e)))) + +;;; defines rules to parse the .data segment + +(esrap:defrule data-word (and (esrap:? space) int) + (:function cadr) + (:lambda (e) + (incf var-offset) + e)) + +(esrap:defrule var-decl alpha + (:lambda (e) + (util:add-variable e var-offset) + nil)) + +(esrap:defrule data-line (and (esrap:? space) var-decl (+ data-word) (esrap:? space) nl) + (:function caddr)) + +(esrap:defrule data (and ".DATA" (esrap:? space) nl (* data-line)) + (:function cadddr) + (:lambda (e) `(emit::d ,@(apply #'append e)))) + +;;; defines rules to parse a program + +(esrap:defrule str->ast (and (* (or space nl)) data text) + (:function cdr) + (:lambda (e) `(emit::p ,@e))) diff --git a/src/util.lisp b/src/util.lisp index 5edee4a..f3035fe 100644 --- a/src/util.lisp +++ b/src/util.lisp @@ -4,24 +4,66 @@ "Returns t if FILE is extended with .asm, nil otherwise." (string= (pathname-type file) "asm")) -;; TODO this won't work for negative numbers of odd sizes quite yet. + (defun format-as-binary (num len) "Formats NUM as a binary number, and pads to LEN with zeros." (declare (type number num)) (declare (type (integer 0 *) len)) - (format nil "~V,'0b" len num)) + (let ((max-val (1- (expt 2 len)))) + (format nil "~V,'0b" len (logand num max-val)))) + +(defun insert-in-middle (list element) + (append (list (car list)) (list element) (cdr list))) + +(defun iota (n) + "Generates a number sequence from 0 to N." + (when (> n 0) + (do ((i 0 (1+ i)) + (item 0 (1+ item)) + (result nil (push item result))) + ((= i n) (nreverse result))))) + +(defun riffle (lst1 lst2) + "Given LST1 and LST2, returns a new list which is the an alternating sequence +of the elements from both lists. Returns nil if the lists are not equal size." + (when (eq (length lst1) (length lst2)) + (loop for l1 in lst1 + for l2 in lst2 + append (list l1 l2)))) + +(defvar variable-table (make-hash-table :test #'equalp)) +(defvar label-table (make-hash-table :test #'equalp)) -(defparameter type-r - '(ADD SUB MUL QUOT REM SFTR SFTL AND OR NOT XOR ADDV SUBV MULV DIVV CMP CEV) +(defun add-variable (name value) + (if (gethash name variable-table) + (error "~@<Variable declared twice: ~S.~@:>" name) + (setf (gethash name variable-table) value))) + +(defun add-label (name value) + (if (gethash name label-table) + (error "~@<Label declared twice: ~S.~@:>" name) + (setf (gethash name label-table) value))) + +(defun get-variable (name) + (alexandria:if-let ((value (gethash name variable-table))) + value + (progn (maphash #'(lambda (k v) (format t "~A => ~A~%" k v)) variable-table) + (error "~@<Variable ~S not declared.~@:>" name)))) + +(defun get-label (name) + (alexandria:if-let ((value (gethash name label-table))) + value + (error "~@<Label ~S not found.~@:>" name))) + +(defvar r-type + '("ADD" "SUB" "MUL" "QUOT" "REM" "SFTR" "SFTL" "AND" "OR" + "NOT" "XOR" "ADDV" "SUBV" "MULV" "DIVV" "CMP" "CEV") "R-type instructions.") -(defparameter type-i - '(LOAD LOADV ADDI SUBI SFTRI SFTLI ANDI ORI XORI STORE STOREV) +(defvar i-type + '("LOAD" "LOADV" "ADDI" "SUBI" "SFTRI" "SFTLI" "ANDI" "ORI" "XORI" "STORE" "STOREV") "I-type instructions.") -(defparameter type-j - '(JMP JRL JAL BEQ BGT BUF BOF PUSH POP) +(defvar j-type + '("JMP" "JRL" "JAL" "BEQ" "BGT" "BUF" "BOF" "PUSH" "POP") "J-type instructions.") - -(defparameter label-loc '() - "A symbol table mapping label names to line indices.") |