<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Storing tokens with flex & bison -->
<!--X-From-R13: "Xba O. Znzoreg" <wyflfvapNvk.argpbz.pbz> -->
<!--X-Date: Sun, 02 Jan 2000 21:23:55 -0800 -->
<!--X-Message-Id: 00a701bf55a9$2fcf1e00$020101df@JonLambert -->
<!--X-Content-Type: text/plain -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Storing tokens with flex & bison</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:jlsysinc#ix,netcom.com">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00029.html">Previous</a>
| <a href="msg00031.html">Next</a>
]
Thread:
[ <a href="msg00120.html">Previous</a>
| <a href="msg00032.html">Next</a>
]
Index:
[ <A HREF="author.html#00030">Author</A>
| <A HREF="#00030">Date</A>
| <A HREF="thread.html#00030">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Storing tokens with flex & bison</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <<A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A>></LI>
<LI><em>Subject</em>: Re: [MUD-Dev] Storing tokens with flex & bison</LI>
<LI><em>From</em>: "Jon A. Lambert" <<A HREF="mailto:jlsysinc#ix,netcom.com">jlsysinc#ix,netcom.com</A>></LI>
<LI><em>Date</em>: Mon, 3 Jan 2000 00:11:14 -0500</LI>
<LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
<LI><em>Sender</em>: <A HREF="mailto:mud-dev-admin#kanga,nu">mud-dev-admin#kanga,nu</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
Chris Gray wrote:
>
>JCL: why do you say recursive descent makes it hard to put a VM under a
>language? Lexing/parsing is pretty independent of execution. My AmigaMUD
>system uses recursive descent for its programming language, and that had
>no effect on being able to put a byte-code machine into the system. It
>had never occurred to me to even think about any effect. Hmm. Perhaps
>I'm misparsing the conjunction in your sentence?
I've noticed that you can obtain lots of little optimization tweaks by just using
"lazy evaluation". That is instead of emitting an opcode as soon as it is
identified, pass that opcode along as an integer to the next routine in the
parse tree as you begin to evaluate the next token. Based on the next
token you may be able to output code that handles that special case
rather than the general case.
For instance in the general case, you might evaluate and generate:
x+y --> pushvar(x) pushvar(y) addop()
x+1 --> pushvar(x) pushint(1) addop()
The second case can be optimized as a special case if instead of
immediately emiting pushvar(x), you wait until the next expression is
identified. Thus it could become:
x+1 --> pushvar(x) increment()
or
x+1 --> pushvar(x+1)
I imagine something similar goes on in C compilers which recognize
that forms like 'x++' and 'x=x+1' as equivalent.
Another possible optimization is for the parser to generate code for
a virtual machine that uses a combination of register and stack instructions.
The parser can be made smart enough to know to use registers.
For instance, instead of:
x+y --> pushvar(x) pushvar(y) addop()
would become...
x+y--> lda(x) adda(y) pusha()
and the special case...
x+1--> lda(x) inca() pusha()
The first example does 3 stack push operations and 2 stack pops,
while the latter does only 1 stack push. (Assuming addop() pops the
top 2 arguments on the stack and pushes the result.)
A VM that uses an array of possible registers to make assignments
could execute bytecode faster, no?
Class VM
{
int register[8];
Stack* stack;
int* code;
}
And finally, there are optimizations that you just can't do with a RD parser.
You can pass the generated byte-code into a post processor that rescans
it for patterns that can be simplified. Call it a byte-code optimizer, or
peephole optimizer. The only problem with this last bit is that pretty printing
or reverse disassembly to source becomes rather difficult. I've noticed a
lot of mud servers do not do this and seek to support reverse code generation
instead of storing the source code somewhere. Perhaps they are missing
out on some major optimization possibilities.
>Byte-code execution really only makes sense, I believe, for a strongly
>typed language. If run-time checks and conversions are needed, they will
>likely cost far more time than the basic interpretation of the code, and
>so going to byte-code instead of staying with something more direct, could
>be a waste of time, in that byte-code won't speed execution up much.
I don't know about whether it makes sense or not. You are paying for
something in the subjective area of "ease of user programming" that is
difficult to quantify. I agree that evaluations at runtime is definitely going to be
slower, than compile time evaluation. I don't agree that it will be slower than
interpreted execution though. Certainly some of the optimizations I talked about
above are operative with strong type checking.
--
--* Jon A. Lambert - TychoMUD Email: jlsysinc#nospam,ix.netcom.com *--
--* Mud Server Developer's Page <<A HREF="http://jlsysinc.home.netcom.com">http://jlsysinc.home.netcom.com</A>> *--
--* "No Free man shall ever be debarred the use of arms." Thomas Jefferson *--
_______________________________________________
MUD-Dev maillist - MUD-Dev#kanga,nu
<A HREF="http://www.kanga.nu/lists/listinfo/mud-dev">http://www.kanga.nu/lists/listinfo/mud-dev</A>
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<!--X-Follow-Ups-End-->
<!--X-References-->
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00029.html">[MUD-Dev] concerning tokenization, compilation, performance, and other fun stuff.</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00031.html">Re: [MUD-Dev] concerning tokenization, compilation, performance, and other fun stuff.</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00120.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00032.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00030"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00030"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><STRONG>Re: [MUD-Dev] Storing tokens with flex & bison</STRONG>, <EM>(continued)</EM>
<ul compact>
<LI><strong><A NAME="00027" HREF="msg00027.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></strong>,
cg <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Mon 03 Jan 2000, 03:25 GMT
<UL>
<LI><strong><A NAME="00066" HREF="msg00066.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></strong>,
Phillip Lenhardt <a href="mailto:philen#funky,monkey.org">philen#funky,monkey.org</a>, Fri 07 Jan 2000, 21:56 GMT
<UL>
<LI><strong><A NAME="00067" HREF="msg00067.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></strong>,
Dominic J. Eidson <a href="mailto:sauron#the-infinite,org">sauron#the-infinite,org</a>, Fri 07 Jan 2000, 22:35 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00120" HREF="msg00120.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></strong>,
J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Tue 18 Jan 2000, 08:47 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00030" HREF="msg00030.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></strong>,
Jon A. Lambert <a href="mailto:jlsysinc#ix,netcom.com">jlsysinc#ix,netcom.com</a>, Mon 03 Jan 2000, 05:23 GMT
</LI>
<LI><strong><A NAME="00032" HREF="msg00032.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></strong>,
cg <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Mon 03 Jan 2000, 06:20 GMT
</LI>
<LI><strong><A NAME="00045" HREF="msg00045.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></strong>,
Jon A. Lambert <a href="mailto:jlsysinc#ix,netcom.com">jlsysinc#ix,netcom.com</a>, Mon 03 Jan 2000, 23:01 GMT
</LI>
<LI><strong><A NAME="00048" HREF="msg00048.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></strong>,
cg <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Tue 04 Jan 2000, 07:07 GMT
</LI>
<LI><strong><A NAME="00068" HREF="msg00068.html">Re: [MUD-Dev] Storing tokens with flex & bison</A></strong>,
cg <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Sat 08 Jan 2000, 04:27 GMT
</LI>
</ul>
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>