;
; UFRGS - INF - M Johann - 2023 - johann@inf.ufrgs.br
; Simple Bottom-Up parser for Ramses (SLR1, as it has few states)
; No free space left, but some instructions can still be saved
; To optimize also: combine last part of shift and reduce (PUSH RA)

; GRAMAR in this example is: {"P:T","T:F","T:T*F","F:i","F:(T)", "i*(i*(i))"}
; Productions: T->F T->T*F F->i F->(T)
; Terminals are: 0=$, 1=*, 2=i, 3=(, 4=)
; NT's are: T=7, F=8
; Test input sentence is "i*(i*(i))": 2132132440

; ----- INPUT is a 0 terminated sequence of symbols (from 1 to 6)

		org 	h50
input:		dab	2,1,3,2,1,3,2,4,4,0,0,0,0,0,0,0		; up to 16 symbols
output:		dab	[32]			; up to 32 actions recorded
		; ends with hFF on success or hFE on error


; ----- TABLE is 10 rows of 10 columns: EOF($)=0, 6 T's, and 3 NT's (7,8,9)
; states will be labeled as offsets from table base
; 0 means empty, FF is Success, and msb is shift=0/reduce=1

	org	h80
table:	
	dab	0,0,h1E,h28,0,0,0,h0A,h14,0	; offset 00h
	dab	hFF,h32,0,0,0,0,0,0,0,0		; offset 0Ah
	dab	h81,h81,0,0,h81,0,0,0,0,0	; offset 14h
	dab	h83,h83,0,0,h83,0,0,0,0,0	; offset 1Eh
	dab	0,0,h1E,h28,0,0,0,h3C,h14,0	; offset 28h
	dab	0,0,h1E,h28,0,0,0,0,h46,0	; offset 32h
	dab	0,h32,0,0,h50,0,0,0,0,0		; offset 3Ch
	dab	h82,h82,0,0,h82,0,0,0,0,0	; offset 46h
	dab	h84,h84,0,0,h84,0,0,0,0,0	; offset 50h
	dab	0,0,0,0,0,0,0,0,0,0		; offset 5Ah

; ----- Productions - up to 6 productions allowed, numbered from 1 to 6

prod_size:	dab	1,3,1,3,0,0	; number of symbols on right-hand side
prod_NT:	dab	7,7,8,8,0,0	; Non-Terminal on the left-hand side

; ----- STACK has 16 positions or states (actually offsets) including start 0

stack:		dab	[16]
		
; ----- BEGIN MAIN CODE 

		org	0
startup:		
loop:		LDR	X,stacktop,I	; take the stack top
		ADD	X,inputhead,I	; add current input symbol
		LDR	A,table,X	; read action from table entry
		; test error when empty action
		JZ	error
		; record action
		LDR	B,outputhead	; advance output head
		ADD	B,#1
		STR	B,outputhead	
		STR	A,outputhead,I	; store action (shift, reduce or end)
		; test terminating condition
		SUB	A,#hFF
		JZ	finish
		ADD	A,#hFF
		; test shift action
		AND	A,#h80
		JZ	makeshift
		; process reduce action
makereduce:	LDR	X,table,X	; read action again, now RX has the action
		AND	X,#h0F		; take production number
		SUB	X,#1		; adjust to 0-based vector
		LDR	B,stacktop	; RB gets pointer to stack top
		SUB	B,prod_size,X	; subtract production size (right-hand side)
		STR	B,stacktop	; complete the POPs
		LDR	X,prod_NT,X	; reads NT to acess goto part of the table
		ADD	X,stacktop,I	; recall state at new (lower) stack top
					; RX has now the address of GOTO's cell
		LDR	A,table,X	; read the GOTO (next state)
		LDR	B,stacktop	; advance stack pointer - ALREADY IN RB
		ADD	B,#1
		STR	B,stacktop
		STR	A,stacktop,I	; push the GOTO state there
		JMP	loop

makeshift:	LDR	A,table,X	; read action again
		LDR	B,stacktop	; advance stack pointer
		ADD	B,#1
		STR	B,stacktop
		STR	A,stacktop,I	; push new state there
		LDR	B,inputhead	; advance input head
		ADD	B,#1
		STR	B,inputhead
		JMP	loop

error:		; include here the error indication
		LDR	A,#hFE
		STR	A,outputhead,I

finish:		; on successful termination, last recorded action was hFF
		HLT

; ----- PROGRAM VARIABLES

stacktop:	db	stack
inputhead:	db	input
outputhead:	db	output

; ----- table template is
;	dab	0,0,0,0,0,0,0,0,0,0	; state 0 offset 00h
;	dab	0,0,0,0,0,0,0,0,0,0	; state 1 offset 0Ah
;	dab	0,0,0,0,0,0,0,0,0,0	; state 2 offset 14h	
;	dab	0,0,0,0,0,0,0,0,0,0	; state 3 offset 1Eh
;	dab	0,0,0,0,0,0,0,0,0,0	; state 4 offset 28h
;	dab	0,0,0,0,0,0,0,0,0,0	; state 5 offset 32h
;	dab	0,0,0,0,0,0,0,0,0,0	; state 6 offset 3Ch
;	dab	0,0,0,0,0,0,0,0,0,0	; state 7 offset 46h
;	dab	0,0,0,0,0,0,0,0,0,0	; state 8 offset 50h
;	dab	0,0,0,0,0,0,0,0,0,0	; state 9 offset 5Ah
		
; END OF FILE