diff options
Diffstat (limited to 'boot/stage8.elna')
| -rw-r--r-- | boot/stage8.elna | 694 |
1 files changed, 585 insertions, 109 deletions
diff --git a/boot/stage8.elna b/boot/stage8.elna index c88e19d..6243634 100644 --- a/boot/stage8.elna +++ b/boot/stage8.elna @@ -4,7 +4,9 @@ # Stage 8 compiler. # - +# - Procedure calls in expressions. +# - Comments between (* and *) are supported. These are still single line +# comments and they should be on a separate line. const symbol_builtin_name_int := "Int"; symbol_builtin_name_word := "Word"; @@ -34,14 +36,13 @@ const symbol_type_info_char := S(1, @symbol_builtin_type_char); symbol_type_info_bool := S(1, @symbol_builtin_type_bool); -# When modifiying also change the read size in the entry point procedure. -.type source_code, @object -source_code: .zero 81920 - -.type compiler_strings, @object -compiler_strings: .zero 8192 - var + source_code: Array; + compiler_strings: Array; + symbol_table_global: Array; + symbol_table_local: Array; + classification: Array; + compiler_strings_position: Pointer := @compiler_strings; compiler_strings_length: Word := 0; source_code_position: Pointer := @source_code; @@ -130,7 +131,8 @@ begin mv a1, a0 # STDIN. li a0, 0 - li a7, 63 # SYS_READ. + # SYS_READ. + li a7, 63 ecall end; @@ -145,7 +147,8 @@ begin mv a1, a0 # STDOUT. li a0, 1 - li a7, 64 # SYS_WRITE. + # SYS_WRITE. + li a7, 64 ecall end; @@ -323,7 +326,8 @@ begin .read_token_loop: lw t0, 0(sp) - lb t0, (t0) # Current character. + # Current character. + lb t0, (t0) # First we try to read a derictive. # A derictive can contain a dot and characters. @@ -425,44 +429,6 @@ begin return v88 end; -proc _compile_section(); -begin - # Print and skip the ".section" (8 characters) directive and a space after it. - _write_token(9); - _advance_token(); - - # Read the section name. - _read_token(); - addi a0, a0, 1 - - _write_token(); - _advance_token(); -end; - -# Prints and skips a line. -proc _skip_comment(); -begin - la t0, source_code_position - lw t1, (t0) - -.skip_comment_loop: - # Check for newline character. - lb t2, (t1) - li t3, '\n' - beq t2, t3, .skip_comment_end - - # Advance the input string by one byte. - addi t1, t1, 1 - sw t1, (t0) - - goto .skip_comment_loop; - -.skip_comment_end: - # Skip the newline. - addi t1, t1, 1 - sw t1, (t0) -end; - # Prints and skips a line. proc _compile_line(); begin @@ -601,6 +567,9 @@ begin li t1, '"' beq a0, t1, .compile_term_string_literal + li t1, '_' + beq a0, t1, .compile_term_call + _is_digit(v0); bnez a0, .compile_term_integer_literal @@ -630,6 +599,11 @@ begin _compile_string_literal(); goto .compile_term_end; +.compile_term_call: + _compile_call(); + _write_z("\nmv t0, a0\n\0"); + goto .compile_term_end; + .compile_term_variable: _compile_variable_expression(); goto .compile_term_end; @@ -1038,6 +1012,8 @@ end; proc _compile_procedure_body(); begin .compile_procedure_body_loop: + _skip_empty_lines(); + # 3 is "end" length. _memcmp(source_code_position, "end", 3); @@ -1091,7 +1067,8 @@ begin _advance_token(5); _read_token(); - sw a0, 0(sp) # Save the procedure name length. + # Save the procedure name length. + sw a0, 0(sp) # Write .type _procedure_name, @function. _write_z(".type \0"); @@ -1136,13 +1113,41 @@ begin .skip_newlines_end: end; +# Prints and skips a line. +proc _skip_comment(); +begin + la t0, source_code_position + lw t1, (t0) + +.skip_comment_loop: + # Check for newline character. + lb t2, (t1) + li t3, '\n' + beq t2, t3, .skip_comment_end + + # Advance the input string by one byte. + addi t1, t1, 1 + sw t1, (t0) + + goto .skip_comment_loop; + +.skip_comment_end: + # Skip the newline. + addi t1, t1, 1 + sw t1, (t0) +end; + # Skip newlines and comments. proc _skip_empty_lines(); begin -.skip_empty_lines_loop: +.skip_empty_lines_rerun: la t0, source_code_position lw t0, (t0) - lb t0, (t0) + sw t0, 0(sp) + +.skip_empty_lines_loop: + lw t2, 0(sp) + lb t0, (t2) li t1, '#' beq t0, t1, .skip_empty_lines_comment @@ -1150,15 +1155,35 @@ begin li t1, '\n' beq t0, t1, .skip_empty_lines_newline + li t1, '\t' + beq t0, t1, .skip_empty_lines_tab + + li t1, '(' + bne t0, t1, .skip_empty_lines_end + addi t2, t2, 1 + lb t0, (t2) + li t1, '*' + beq t0, t1, .skip_empty_lines_comment + goto .skip_empty_lines_end; .skip_empty_lines_comment: + la t0, source_code_position + lw t1, 0(sp) + sw t1, (t0) _skip_comment(); - goto .skip_empty_lines_loop; + goto .skip_empty_lines_rerun; .skip_empty_lines_newline: - _advance_token(1); - goto .skip_empty_lines_loop; + la t0, source_code_position + lw t1, 0(sp) + addi t1, t1, 1 + sw t1, (t0) + goto .skip_empty_lines_rerun; + +.skip_empty_lines_tab: + v0 := v0 + 1; + goto .skip_empty_lines_loop .skip_empty_lines_end: end; @@ -1295,12 +1320,6 @@ begin _advance_token(1); - la t0, source_code_position - lw t0, (t0) - lb t0, (t0) - li t1, '#' - beq t0, t1, .compile_const_part_loop - _compile_constant_declaration(); goto .compile_const_part_loop; @@ -1358,18 +1377,16 @@ begin _write_z(".section .data\n\0"); .compile_var_part_loop: + _skip_empty_lines(); + la t0, source_code_position lw t0, (t0) lb t0, (t0) - li t1, 'p' - beq t0, t1, .compile_var_part_end - li t1, '\t' beq t0, t1, .compile_var_part_declaration - _compile_line(); - goto .compile_var_part_loop; + goto .compile_var_part_end; .compile_var_part_declaration: _advance_token(1); @@ -1383,64 +1400,25 @@ end; proc _compile_module(); begin _compile_const_part(); - _write_z(".section .bss\n\0"); - -.compile_module_bss: - la t0, source_code_position - lw t0, (t0) - lb t0, (t0) - li t1, 'v' - beq t0, t1, .compile_module_code - - li t1, 'p' - beq t0, t1, .compile_module_code - - _compile_line(); - goto .compile_module_bss; - -.compile_module_code: + _skip_empty_lines(); _compile_var_part(); + _write_z(".section .text\n\0"); .compile_module_loop: - _skip_newlines(); + _skip_empty_lines(); la t0, source_code_position lw t0, (t0) lb t0, (t0) beqz t0, .compile_module_end - li t1, '#' - beq t0, t1, .compile_module_comment - - # 8 is ".section" length. - _memcmp(source_code_position, ".section", 8); - beqz a0, .compile_module_section # 5 is "proc " length. Space is needed to distinguish from "procedure". _memcmp(source_code_position, "proc ", 5); beqz a0, .compile_module_procedure - # 6 is ".globl" length. - _memcmp(source_code_position, ".globl", 6); - beqz a0, .compile_module_global - # Not a known token, exit. goto .compile_module_end; -.compile_module_section: - _compile_section(); - - goto .compile_module_loop; - -.compile_module_global: - _compile_line(); - - goto .compile_module_loop; - -.compile_module_comment: - _skip_comment(); - - goto .compile_module_loop; - .compile_module_procedure: _compile_procedure(); @@ -1490,14 +1468,512 @@ begin ecall end; +# Inserts a symbol into the table. +# +# Parameters: +# a0 - Symbol pointer. +# a1 - Symbol name length. +# a2 - Symbol name pointer. +# a3 - Symbol table. +proc _symbol_table_enter(); +begin + # The first word in the symbol table is its length, get it. + lw a0, 76(sp) + lw a0, (a0) + sw a0, 0(sp) + + # Calculate the offset for the new symbol. + v4 := v0 * 4; + v4 := v4 + 4; + v4 := v76 + 4; + + _memcpy(v4, @v80, 12); + + # Increment the symbol table length. + v0 := v0 + 1; + lw t0, 0(sp) + lw t1, 76(sp) + sw t0, (t1) +end; + +proc _symbol_table_build(); +begin + _symbol_table_enter(@symbol_type_info_int, 3, symbol_builtin_name_int, @symbol_table_global); + _symbol_table_enter(@symbol_type_info_word, 4, symbol_builtin_name_word, @symbol_table_global); + _symbol_table_enter(@symbol_type_info_pointer, 7, symbol_builtin_name_pointer, @symbol_table_global); + _symbol_table_enter(@symbol_type_info_char, 4, symbol_builtin_name_char, @symbol_table_global); + _symbol_table_enter(@symbol_type_info_bool, 4, symbol_builtin_name_bool, @symbol_table_global); +end; + +# +# Classification table assigns each possible character to a group (class). All +# characters of the same group a handled equivalently. +# +# Classification: +# +# TransitionClass = ( +# transitionClassInvalid = 1, +# transitionClassDigit = 2, +# transitionClassAlpha = 3, +# transitionClassSpace = 4, +# transitionClassColon = 5, +# transitionClassEquals = 6, +# transitionClassLeftParen = 7, +# transitionClassRightParen = 8, +# transitionClassAsterisk = 9, +# transitionClassUnderscore = 10, +# transitionClassSingle = 11, +# transitionClassHex = 12, +# transitionClassZero = 13, +# transitionClassX = 14, +# transitionClassEof = 15, +# transitionClassDot = 16, +# transitionClassMinus = 17, +# transitionClassSingleQuote = 18, +# transitionClassDoubleQuote = 19, +# transitionClassGreater = 20, +# transitionClassLess = 21, +# transitionClassOther = 22 +# ); +# TransitionState = ( +# transitionStateStart = 1, +# transitionStateColon = 2, +# transitionStateIdentifier = 3, +# transitionStateDecimal = 4, +# transitionStateGreater = 5, +# transitionStateMinus = 6, +# transitionStateLeftParen = 7, +# transitionStateLess = 8, +# transitionStateDot = 9, +# transitionStateComment = 10, +# transitionStateClosingComment = 11, +# transitionStateCharacter = 12, +# transitionStateString = 13, +# transitionStateLeadingZero = 14, +# transitionStateDecimalSuffix = 15, +# transitionStateEnd = 16 +# ); +# Transition = record +# action: TransitionAction; +# next_state: TransitionState +# end; +# TransitionAction = ( +# none = 1, +# accumulate = 2, +# skip = 3, +# single = 4, +# eof = 5, +# finalize = 6, +# composite = 7, +# key_id = 8, +# integer = 9, +# delimited = 10 +# ); + +# Assigns some value to at array index. +# +# Parameters: +# a0 - Array pointer. +# a1 - Index (word offset into the array). +# a2 - Data to assign. +proc _assign_at(); +begin + v0 := v84 + -1; + v0 := v0 * 4; + v0 := v88 + v0; + + lw t0, 0(sp) + lw t1, 80(sp) + sw t1, (t0) +end; + +proc _initialize_classification(); +begin + _assign_at(@classification, 1, 15); + _assign_at(@classification, 2, 1); + _assign_at(@classification, 3, 1); + _assign_at(@classification, 4, 1); + _assign_at(@classification, 5, 1); + _assign_at(@classification, 6, 1); + _assign_at(@classification, 7, 1); + _assign_at(@classification, 8, 1); + _assign_at(@classification, 9, 1); + _assign_at(@classification, 10, 4); + _assign_at(@classification, 11, 4); + _assign_at(@classification, 12, 1); + _assign_at(@classification, 13, 1); + _assign_at(@classification, 14, 4); + _assign_at(@classification, 15, 1); + _assign_at(@classification, 16, 1); + _assign_at(@classification, 17, 1); + _assign_at(@classification, 18, 1); + _assign_at(@classification, 19, 1); + _assign_at(@classification, 20, 1); + _assign_at(@classification, 21, 1); + _assign_at(@classification, 22, 1); + _assign_at(@classification, 23, 1); + _assign_at(@classification, 24, 1); + _assign_at(@classification, 25, 1); + _assign_at(@classification, 26, 1); + _assign_at(@classification, 27, 1); + _assign_at(@classification, 28, 1); + _assign_at(@classification, 29, 1); + _assign_at(@classification, 30, 1); + _assign_at(@classification, 31, 1); + _assign_at(@classification, 32, 1); + _assign_at(@classification, 33, 4); + _assign_at(@classification, 34, 11); + _assign_at(@classification, 35, 19); + _assign_at(@classification, 36, 22); + _assign_at(@classification, 37, 22); + _assign_at(@classification, 38, 11); + _assign_at(@classification, 39, 11); + _assign_at(@classification, 40, 18); + _assign_at(@classification, 41, 7); + _assign_at(@classification, 42, 8); + _assign_at(@classification, 43, 9); + _assign_at(@classification, 44, 11); + _assign_at(@classification, 45, 11); + _assign_at(@classification, 46, 17); + _assign_at(@classification, 47, 16); + _assign_at(@classification, 48, 11); + _assign_at(@classification, 49, 13); + _assign_at(@classification, 50, 2); + _assign_at(@classification, 51, 2); + _assign_at(@classification, 52, 2); + _assign_at(@classification, 53, 2); + _assign_at(@classification, 54, 2); + _assign_at(@classification, 55, 2); + _assign_at(@classification, 56, 2); + _assign_at(@classification, 57, 2); + _assign_at(@classification, 58, 2); + _assign_at(@classification, 59, 5); + _assign_at(@classification, 60, 11); + _assign_at(@classification, 61, 21); + _assign_at(@classification, 62, 6); + _assign_at(@classification, 63, 20); + _assign_at(@classification, 64, 22); + _assign_at(@classification, 65, 11); + _assign_at(@classification, 66, 3); + _assign_at(@classification, 67, 3); + _assign_at(@classification, 68, 3); + _assign_at(@classification, 69, 3); + _assign_at(@classification, 70, 3); + _assign_at(@classification, 71, 3); + _assign_at(@classification, 72, 3); + _assign_at(@classification, 73, 3); + _assign_at(@classification, 74, 3); + _assign_at(@classification, 75, 3); + _assign_at(@classification, 76, 3); + _assign_at(@classification, 77, 3); + _assign_at(@classification, 78, 3); + _assign_at(@classification, 79, 3); + _assign_at(@classification, 80, 3); + _assign_at(@classification, 81, 3); + _assign_at(@classification, 82, 3); + _assign_at(@classification, 83, 3); + _assign_at(@classification, 84, 3); + _assign_at(@classification, 85, 3); + _assign_at(@classification, 86, 3); + _assign_at(@classification, 87, 3); + _assign_at(@classification, 88, 3); + _assign_at(@classification, 89, 3); + _assign_at(@classification, 90, 3); + _assign_at(@classification, 91, 3); + _assign_at(@classification, 92, 11); + _assign_at(@classification, 93, 22); + _assign_at(@classification, 94, 11); + _assign_at(@classification, 95, 11); + _assign_at(@classification, 96, 10); + _assign_at(@classification, 97, 22); + _assign_at(@classification, 98, 12); + _assign_at(@classification, 99, 12); + _assign_at(@classification, 100, 12); + _assign_at(@classification, 101, 12); + _assign_at(@classification, 102, 12); + _assign_at(@classification, 103, 12); + _assign_at(@classification, 104, 3); + _assign_at(@classification, 105, 3); + _assign_at(@classification, 106, 3); + _assign_at(@classification, 107, 3); + _assign_at(@classification, 108, 3); + _assign_at(@classification, 109, 3); + _assign_at(@classification, 110, 3); + _assign_at(@classification, 111, 3); + _assign_at(@classification, 112, 3); + _assign_at(@classification, 113, 3); + _assign_at(@classification, 114, 3); + _assign_at(@classification, 115, 3); + _assign_at(@classification, 116, 3); + _assign_at(@classification, 117, 3); + _assign_at(@classification, 118, 3); + _assign_at(@classification, 119, 3); + _assign_at(@classification, 120, 3); + _assign_at(@classification, 121, 14); + _assign_at(@classification, 122, 3); + _assign_at(@classification, 123, 3); + _assign_at(@classification, 124, 22); + _assign_at(@classification, 125, 11); + _assign_at(@classification, 126, 22); + _assign_at(@classification, 127, 11); + _assign_at(@classification, 128, 1); + + v0 := 129; + +# Set the remaining 129 - 256 bytes to transitionClassOther. +.initialize_classification_loop: + _assign_at(@classification, v0, 22); + v0 := v0 + 1; + + lw t0, 0(sp) + li t1, 257 + blt t0, t1, .initialize_classification_loop +end; + +# Parameters: +# a0 - Current state (first index into transitions table). +# a1 - Transition (second index into transitions table).. +# a2 - Action to assign. +# a3 - Next state to assign. +proc _set_transition(); +begin + # Transitions start at offset in classification array. Save the transitions start in v0. + la t0, classification + addi t0, t0, 256 + sw t0, 0(sp) + + # Each state is 8 bytes long (2 words: action and next state). + # There are 16 transition classes, so a transition 8 * 16 = 128 bytes long. + + v4 := v88 + -1; + v4 := v4 * 128; + + v8 := v84 + -1; + v8 := v8 * 8; + + v12 := v0 + v4; + v12 := v12 + v8; + + lw t0, 12(sp) + lw t1, 80(sp) + lw t2, 76(sp) + sw t1, (t0) + addi t0, t0, 4 + sw t2, (t0) +end; + +# Parameters: +# a0 - Current state (Transition state enumeration). +# a1 - Default action (Callback). +# a2 - Next state (Transition state enumeration). +proc _set_default_transition(); +begin + _set_transition(v88, 1, v84, v80); + _set_transition(v88, 2, v84, v80); + _set_transition(v88, 3, v84, v80); + _set_transition(v88, 4, v84, v80); + _set_transition(v88, 5, v84, v80); + _set_transition(v88, 6, v84, v80); + _set_transition(v88, 7, v84, v80); + _set_transition(v88, 8, v84, v80); + _set_transition(v88, 9, v84, v80); + _set_transition(v88, 10, v84, v80); + _set_transition(v88, 11, v84, v80); + _set_transition(v88, 12, v84, v80); + _set_transition(v88, 13, v84, v80); + _set_transition(v88, 14, v84, v80); + _set_transition(v88, 15, v84, v80); + _set_transition(v88, 16, v84, v80); + _set_transition(v88, 17, v84, v80); + _set_transition(v88, 18, v84, v80); + _set_transition(v88, 19, v84, v80); + _set_transition(v88, 20, v84, v80); + _set_transition(v88, 21, v84, v80); + _set_transition(v88, 22, v84, v80); +end; + + +# The transition table describes transitions from one state to another, given +# a symbol (character class). +# +# The table has m rows and n columns, where m is the amount of states and n is +# the amount of classes. So given the current state and a classified character +# the table can be used to look up the next state. +# +# Each cell is a word long. +# - The least significant byte of the word is a row number (beginning with 0). +# It specifies the target state. "ff" means that this is an end state and no +# transition is possible. +# - The next byte is the action that should be performed when transitioning. +# For the meaning of actions see labels in the lex_next function, which +# handles each action. +proc _initialize_transitions(); +begin + # Start state. + _set_transition(1, 1, 1, 16); + _set_transition(1, 2, 2, 4); + _set_transition(1, 3, 2, 3); + _set_transition(1, 4, 3, 1); + _set_transition(1, 5, 2, 5); + _set_transition(1, 6, 4, 16); + _set_transition(1, 7, 2, 7); + _set_transition(1, 8, 4, 16); + _set_transition(1, 9, 4, 16); + _set_transition(1, 10, 2, 3); + _set_transition(1, 11, 4, 16); + _set_transition(1, 12, 2, 3); + _set_transition(1, 13, 2, 14); + _set_transition(1, 14, 2, 3); + _set_transition(1, 15, 5, 16); + _set_transition(1, 16, 2, 9); + _set_transition(1, 17, 2, 6); + _set_transition(1, 18, 2, 12); + _set_transition(1, 19, 2, 13); + _set_transition(1, 20, 2, 5); + _set_transition(1, 21, 2, 8); + _set_transition(1, 22, 1, 16); + + # Colon state. + _set_default_transition(2, 6, 16); + _set_transition(2, 6, 7, 16); + + # Identifier state. + _set_default_transition(3, 8, 16); + _set_transition(3, 2, 2, 3); + _set_transition(3, 3, 2, 3); + _set_transition(3, 10, 2, 3); + _set_transition(3, 12, 2, 3); + _set_transition(3, 13, 2, 3); + _set_transition(3, 14, 2, 3); + + # Decimal state. + _set_default_transition(4, 9, 16); + _set_transition(4, 2, 2, 4); + _set_transition(4, 3, 2, 15); + _set_transition(4, 10, 1, 16); + _set_transition(4, 12, 2, 15); + _set_transition(4, 13, 2, 4); + _set_transition(4, 14, 2, 15); + + # Greater state. + _set_default_transition(5, 6, 16); + _set_transition(5, 6, 7, 16); + + # Minus state. + _set_default_transition(6, 6, 16); + _set_transition(6, 20, 7, 16); + + # Left paren state. + _set_default_transition(7, 6, 16); + _set_transition(7, 9, 2, 10); + + # Less state. + _set_default_transition(8, 6, 16); + _set_transition(8, 6, 7, 16); + _set_transition(8, 20, 7, 16); + + # Hexadecimal after 0x. + _set_default_transition(9, 6, 16); + _set_transition(9, 16, 7, 16); + + # Comment. + _set_default_transition(10, 2, 10); + _set_transition(10, 9, 2, 11); + _set_transition(10, 15, 1, 16); + + # Closing comment. + _set_default_transition(11, 2, 10); + _set_transition(11, 1, 1, 16); + _set_transition(11, 8, 10, 16); + _set_transition(11, 9, 2, 11); + _set_transition(11, 15, 1, 16); + + # Character. + _set_default_transition(12, 2, 12); + _set_transition(12, 1, 1, 16); + _set_transition(12, 15, 1, 16); + _set_transition(12, 18, 10, 16); + + # String. + _set_default_transition(13, 2, 13); + _set_transition(13, 1, 1, 16); + _set_transition(13, 15, 1, 16); + _set_transition(13, 19, 10, 16); + + # Leading zero. + _set_default_transition(14, 9, 16); + _set_transition(14, 2, 1, 16); + _set_transition(14, 3, 1, 16); + _set_transition(14, 10, 1, 16); + _set_transition(14, 12, 1, 16); + _set_transition(14, 13, 1, 16); + _set_transition(14, 14, 1, 16); + + # Digit with a character suffix. + _set_default_transition(15, 9, 16); + _set_transition(15, 3, 1, 16); + _set_transition(15, 2, 1, 16); + _set_transition(15, 12, 1, 16); + _set_transition(15, 13, 1, 16); + _set_transition(15, 14, 1, 16); +end; + +proc _lexer_get_state(); +begin + # Lexer state is saved after the transition tables. The offset is 256 + 16 * 22. + v0 := @classification; + v4 := 16 * 22; + v0 := v0 + 256; + + return v0 + v4 +end; + +# Gets pointer to the current source text. +proc _lexer_get_current(); +begin + _lexer_get_state(); + sw a0, 0(sp) + + return v0 + 4 +end; + +# Resets the lexer state for reading the next token. +proc _lexer_reset(); +begin + # Transition start state is 1. + _lexer_get_state(); + li t0, 1 + sw t0, (a0) + sw a0, 0(sp) + + # Text pointer to the beginning of the currently read token. + _lexer_get_current(); + la t0, source_code_position + lw t0, (t0) + sw t0, (a0) + + # Initial length of the token is 0. + addi t0, t0, 4 + sw zero, (t0) +end; + +# One time lexer initialization. +proc _lexer_initialize(); +begin + _initialize_classification(); + _initialize_transitions(); +end; + # Entry point. proc _start(); begin + _lexer_initialize(); + _symbol_table_build(); + # Read the source from the standard input. # Second argument is buffer size. Modifying update the source_code definition. _read_file(@source_code, 81920); _compile(); _exit(0); - end; |