Compiling Parenthesis Without Recursion

Discuss programming topics for the various GPL'd game engine sources.
Post Reply
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Compiling Parenthesis Without Recursion

Post by Baker »

Here is the short story.

I hate regex/posix search, it is cryptic. I am writing some code to search source code in real time.

1) I'm using what basically looks like natural language ...
2) Find: red -black +blue -"const blue"
3) I then compile the expression to bytes, the type of compare is an enum (compare_equals = 1, compare_equals_caseless = 2, compare_starts_with, compare_partial, ...)

Parenthesis?
4) john and (fred or bob)

How can I evaluate parenthesis without recursion? My goal is for the byte code to be reversible back into text.
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
ericw
Posts: 92
Joined: Sat Jan 18, 2014 2:11 am

Re: Compiling Parenthesis Without Recursion

Post by ericw »

Whenever you hit an opening paren, push something on to a stack that says "opening paren at character X".
When you hit a closing paren, you know it's closing the top paren on the stack, so pop that off.
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Compiling Parenthesis Without Recursion

Post by Baker »

Haha, I came to that conclusion and then read this! I'm a bit happy I worked through it myself.

This problem had been ticking me off. Truth is, there isn't an easy way to avoid the recursion (it can be done by reordering, but then I'm destroying the reversibility back to text) and using a stack is technically recursion (whether you dodge it with a stack and a for loop) but that is what is really going on so.

And it made me see that any time you have a () in an equation it is a virtual function, no wonder languages came up with the idea of throwing a name before the () and creating the idea of named functions.

Well, 2 weeks ago the idea of how to write my own pattern matching was a bit of a mystery and now I'm first and goal from the 5 yard line. :D

(I didn't expect I'd be writing byte code to solve this a couple of weeks ago, but the idea of reinterpreting a string over and over again is quite redundant.)
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
frag.machine
Posts: 2126
Joined: Sat Nov 25, 2006 1:49 pm

Re: Compiling Parenthesis Without Recursion

Post by frag.machine »

This reminds me about the venerable Sinclair BASIC interpreter.
IIRC there's a non-recursive expression evaluator there, may be worth to check it for ideas.
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Compiling Parenthesis Without Recursion

Post by Baker »

frag.machine wrote:This reminds me about the venerable Sinclair BASIC interpreter.
IIRC there's a non-recursive expression evaluator there, may be worth to check it for ideas.
Interesting stuff :D People think of basic as an interpreted language, but really very old BASIC (IF THEN GOTO 20) is a thin cover over assembly language. And some people scream when they see a "goto" because of the text representation, many whom are unaware that assembly is all gotos. And I think C's longjmp is called such because an assembly goto (JMP?) is a byte limited to 0-255.

(After messing with bytecode, and I've have it working --- I can see why verified working bytecode often gets signed via some method (I think Quake uses CRC-32 or is it CRC-16? Actually without looking I'm pretty sure it is CRC-16) so you know you don't have to error check it while it runs.)
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Re: Compiling Parenthesis Without Recursion

Post by revelator »

Aye old style basic ain't all that bad :) freebasic still works that way but can link to and use C or C++ libraries.
I actually started coding in basic way way back but i havent used it for much in the later years so i forgot most of the syntax :) i do remember the goto's though hehe.
Was a pretty hardcore language back then also cause there was no such thing as debuggers so if you screwed up you could pretty much start over ;).
took around 14 days to write a ping pong game hehe.

asm jmp ;) yep correct thats a goto.
Productivity is a state of mind.
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Compiling Parenthesis Without Recursion

Post by Baker »

I did some quick checking.

BASIC (1964) is older than C (1972).
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Re: Compiling Parenthesis Without Recursion

Post by revelator »

does not surprise me i first heard of C/C++ way later :) damn basic is older than me Oo im from 68.
I think even cobol is older than C i had one of the piccolo's (early PC) which used an OS built in cobol way back in the early 90's, newer learned the language and the OS was weird as hell to get around in.
Productivity is a state of mind.
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Re: Compiling Parenthesis Without Recursion

Post by revelator »

Ah no remembered wrong the piccolo used a language called comal80.
But cobol is also older than C 1969 :) it was an industrial language, and easy to learn but it had some drawbacks like not being able to construct advanced structures.
Comal80 (1973) was invented by some of my countrymen Benedict Løfstedt and Børge Christensen, same as C++ (early 80's) which was invented by bjarne stroustrup guess us danes are not so stupid after all ;).
Should have kept that old piece of junk, its worth a fortune today hehe.
Productivity is a state of mind.
Post Reply