scott <sco### [at] scottcom> wrote:
> I don't know a great deal about parsers (the most I've done is made one 
> to calculate very simple sums, like (5+4)/2) but AIUI things like POV 
> first convert the human readable text to binary symbols (removing any 
> unnecessary formatting) and then parse the binary symbols rather than 
> the raw text.

POV-Ray doesn't convert the SDL file into any internal binary format.
It just parses the text and creates objects as needed.

Fast parsing (regardless of whether you are interpreting as you parse or
whether you are byte-compiling it) is a difficult problem, one I have some
experience with.

The fastest possible way of parsing a text file with human-readable syntax
is to load it into an array in memory (if the file is exceedingly large
you'll have to do it in sections, but that shouldn't slow it down in any
significant way) and then parse it in-place (ie. without pulling out any
parts of it or creating new objects just to parse the thing) in a linear
fashion (ie. you traverse the array from beginning to end, without ever
going back.)

It is possible to do this kind of parsing without any kind of recursion,
but it becomes a bit complicated. Basically you need a state machine (which
has been generated at compile time into your program), and usually this
means generated code. (I suppose you could write a state machine by hand,
but it quickly becomes complicated, especially if the syntax of the thing
you are parsing is complex.)

The easiest way of writing an efficient parser by hand is to implement
a recursive descent parser (which, as said, parses the input in-place
from the array where it has been read to.) A RDP allows parsing any amount
of nested blocks in the input syntax (eg. parentheses or other types of
nested blocks) at any nesting depth, without ever having to go back in the
input (ie. just traversing the input from beginning to end once.)

What you do with the parsed information depends on what you want, but eg.
byte-compiling it into a stack-based bytecode (that can be later interpreted
in a very efficient manner) is very easy with a RDP. You could, of course,
just interpret the input directly.

-- 
                                                          - Warp

Post a reply to this message