Sign in to follow this  
ScopeDynamo

Reduce or Shift on And/Or/Not in operator precedence parsing?

Recommended Posts

Hi, I'm following http://epaperpress.com/oper/ to create an expression evaluator and although it works, the table doesn't include And/Or/Not/Xor etc and what i need to do when combined with other code. Does anyone know of a table that includes them or know off by heart what I should do? Here's the code. [BlitzMax] Table definition. Copied from the def in the above link.
Const Scope_Entry=1,Scope_Exit=2
Const Assign = 3,Minus=4,Plus=5,Times=7,Devide=8
Const classentry=9,numeric=10,value=11,tend=12
Const reduce=1,shift=2

Global act:Int[,] = New Int[20,20]
act[Plus,plus] = reduce
act[plus,minus] = reduce
act[plus,times] = shift
act[plus,devide] = shift
act[plus,scope_entry] = shift
act[plus,scope_Exit] = reduce
act[plus,tend] = reduce
act[minus,plus] = reduce
act[minus,minus] = reduce
act[minus,times] = shift
act[minus,devide] = shift
act[minus,scope_entry] = shift
act[minus,scope_exit] = reduce
act[minus,tend] = reduce
act[times,plus] = reduce
act[times,minus] = reduce
act[times,times] = reduce
act[times,devide] = reduce
act[times,scope_entry] = shift
act[times,scope_Exit] = reduce
act[times,tend] = reduce
act[devide,plus] = reduce
act[devide,minus] = reduce
act[devide,Times] = reduce
act[devide,devide] = reduce
act[devide,scope_entry] = shift
act[devide,scope_exit] = reduce
act[devide,tend ] = reduce
act[scope_entry,plus] = shift
act[scope_entry,minus] = shift
act[scope_entry,times] = shift
act[scope_entry,devide] = shift
act[scope_entry,scope_Entry] = shift
act[scope_Entry,scope_exit] = shift
act[scope_Exit,plus] = reduce
act[scope_exit,minus] = reduce
act[scope_exit,devide] = reduce
act[scope_exit,times] = reduce
act[scope_Exit,scope_entry] = reduce
act[scope_exit,scope_exit] = reduce
act[scope_exit,tend] = reduce
act[tend,plus] = shift
act[tend,minus] = shift
act[tend,times] = shift
act[tend,devide] = shift
act[tend,scope_entry] = shift
act[tend,tend] = tend
Evaluator

Type ExpressionParser
	Field Val:Double[2000],valTop
	Field Opr:String[2000],oprTop
	
	Field tokes:Tokens
	Method New()
	
	End Method
	
	Method Parse!( Expr:String )
		
		Local tk:Tokenizer = New Tokenizer
		tokes:Tokens = tk.tokenize( expr+";" )
		valtop=-1
		oprtop=0
		opr[oprtop]=tend
		If nxttok() Return 1
		Repeat
		
			
			If tok = value
				If shiftstack() Return 1
				 Continue
			End If
		
			Select act[Int(opr[oprtop]),tok]
				Case reduce
					If reducestack() Return 1
					
				Case shift
					If shiftstack() Return 1
				Case tend
					If valtop<>0
						Print "Syntax error"
					End If
					Return val[valtop]
				Default
					Print "Unknown combo:"
					Print opr[oprtop]+":"+tok
					End
			End Select
			
			
		Forever					
	End Method
	Field debug1:String,debug2:String
	Method nxtTok()
		Local tokey:Token = tokes.nextToken()
		If tokey=Null Return 1
		debug1 = tokey.id
		getTok( tokey.id )
		
	End Method
	
	Field tokval!,tok
	Method GetTok(Toke:String)
		
		Select toke
			Case "+"
				tok=plus
			Case "-"
				tok=minus
				
			Case "*"
				tok=times
			Case "/"
				tok=devide
			Case "("
				tok=scope_entry
			Case ")"
				tok=scope_exit
			Case ";"
				tok=tend
			Default 
				tok=value
				tokval=Double(toke)
		End Select
			
	End Method
		
	Method shiftstack()
		If tok = value
			valTop:+1
			val[valTop]=tokval
		Else
			oprTop:+1
			opr[oprtop]=String(tok)
		EndIf
		If nxtTok() Return 1
	End Method
	
	Method Reducestack()
		Select Int(opr[oprtop])
			Case plus
				val[valtop-1]:+val[valtop]
				valtop:-1
			Case minus
				val[valtop-1]:-val[valtop]
				valtop:-1
			Case times
				val[valtop-1]:*val[valtop]
				valtop:-1
			Case devide
				val[valtop-1]:/val[valtop]
				valtop:-1
			Case scope_exit
				oprtop:-1
		End Select
		oprtop:-1
	End Method

	
End Type


Share this post


Link to post
Share on other sites
Thanks but I see nothing that helps with my problem. I need all the combinations of Not, and,or and greater than etc. Just wondering if there's a table or something somewhere.

Share this post


Link to post
Share on other sites
erissian,

what you linked has nothing to do with what he is asking.

to the OP:

so I skimmed this operator precedence parsing. Basically, the website skims over all the theory so you don't know how to create the extra stuff. I think you are actually doing predictive parsing with one token lookahead: basically, the table really is combining the production and the follow set together.

So basically, what you wanna do is figure out what can follow an and/or/not/xor and then figure out what production, you wanna have, for each token that can follow it.

so like &&
say for number, you can have an number after &&, so you wanna have a shift, to shift it into &&.
but you can't have another &&, because that's an error, so stick an error there.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this