• Advertisement
Sign in to follow this  

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

This topic is 4484 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement