Has anybody used flex or something similar to generate the (basic) code for a lexer?
Randy Kramer
markup lexer.
I guess a difficulty will be that most lexer generators can't deal with
significant whitespace, but I thought that might be something I could
fairly easily modify. (But, I've never used a lexer generator, so I
may have a big learning curve in front of me.)
Randy Kramer
Eric Promislow
I designed a separate language for ActiveState's Komodo IDE.
Rather than generating lexers, I wrote a general purpose lexer engine in C++,
and our language (called Luddite) is compiled down into bytecodes that
the lexer loads once, and uses to process buffers in that language.
We designed the system primarily to make it easier to quickly add support
for HTML-based multi-sub-language languages, but I recently wrote a
lexer for Markdown in it. One limitation is that UDL (the name of the
lexer engine) only looks at one line at a time, and has a very limited
concept of variables, so I can't easily support the underlining concept a
lot of the lightweight markup languages (like Markdown and ReST) have,
but it's easy enough to fake it.
Luddite does more than Lex/Flex. For one thing, it does allow arbitrary
nesting, in order to handle arbitrary language transitions (like "<%=...%>"
escapes in HTML attribute values for PHP and RHTML). It also can handle
here documents for PHP, Ruby, and Perl. But if you don't need that, you
could leave it out. However, it doesn't track whitespace -- the main limitation
here is that it can't generate folding information for Python-like languages.
During early development, I actually was generating C++ rather than bytecode,
to make it easier to debug, and that code is still in place, so it's certainly
a plausible alternative.
The Luddite compiler is written in Python, and ships as part of the
Komodo distribution, so you can see what I did there. The UDL lexer engine
is available via openkomodo.com -- we haven't pushed it back into
scintilla.
Regards,
Eric Promislow
,
Lex Trotman
I doubt that flex or other lexical analyser generators are suitable
for lexers in scintilla. They generate lexical analysers that are
optimised for reading the whole file from the beginning and returning
a string of tokens to the parser.
With a Scintilla lexer you are only going to be analysing the little
bit of text that scintilla tells you to, starting at the state of the
previous character, something that flex isn't optimised for since it
*mostly* assumes that the parser handles state (yes you can have start
conditions but it quickly gets very messy). Also you might have
issues with quoted text like the inline bold markup if it isn't closed
properly.
For something as simple as Twiki it is probably easier to just use
your own state machine.
Cheers
Lex
2009/9/12 Randy Kramer <rhkr...@gmail.com>:
Randy Kramer
Thanks for the suggestion! I downloaded Luddite and UDL (well actually,
I downloaded all of Komodo--wish I had looked first--something over 400
MB). Anyway, started looking, may try looking again--tentatively
headed in the direction of writing the lexer "manually"--you'll
probably see more questions on the list.
Randy Kramer
Randy Kramer
On Friday 11 September 2009 07:37:07 pm Lex Trotman wrote:
> I doubt that flex or other lexical analyser generators are suitable
> for lexers in scintilla. They generate lexical analysers that are
> optimised for reading the whole file from the beginning and returning
> a string of tokens to the parser.
Ahh, good point--I think I was starting to understand that, but you're
comment made it clear to me. I'm headed in the direction of writing
the lexer "manually" in C++, and you'll probably see more questions on
the list.
One thing that sort of bothers me--I know you can use labels and gotos
in C/C++ (at least I'm pretty sure of that), but it's pretty much
considered bad form. But, it looks to me like that is the best
approach for parts of my state machine--like the main loop and parts of
other sub-loops (I guess I should say main state machine and parts of
other sub- state machines).
One of the alternatives is a deeply nested structure that, for some of
the things to be recognized, may be deeply nested indeed--just the
indentation to handle the nesting would be ridiculous. I could create
sub-functions just to minimize nesting, but gotos seem so much easier.
Oh, I have come across the quex lexical analyser generator which has a
facility to (automatically, iiuc) create a state diagram based on the
input. I'm tempted to use it just to create a good state diagram for
documentation.
Thanks!
Randy Kramer
Randy Kramer
> One thing that sort of bothers me--I know you can use labels and
> gotos in C/C++ (at least I'm pretty sure of that), but it's pretty
> much considered bad form. But, it looks to me like that is the best
> approach for parts of my state machine--like the main loop and parts
> of other sub-loops (I guess I should say main state machine and parts
> of other sub- state machines).
Hmm, and I just re-read (re-skimmed?) Neil's coding style document
(Scintilla and SciTE: Code Style) and see this:
"The goto statement is not used because of bad memories from my first
job maintaining FORTRAN programs. The union feature is not used as it
can lead to non-type-safe value access."
If I'm still thinking the way I am now, I might write the first
version(s) with gotos, and try to revise it later.
Randy Kramer
Lex Trotman
> Hi again, Lex ;-)
>
> On Friday 11 September 2009 07:37:07 pm Lex Trotman wrote:
>> I doubt that flex or other lexical analyser generators are suitable
>> for lexers in scintilla. They generate lexical analysers that are
>> optimised for reading the whole file from the beginning and returning
>> a string of tokens to the parser.
>
> Ahh, good point--I think I was starting to understand that, but you're
> comment made it clear to me. I'm headed in the direction of writing
> the lexer "manually" in C++, and you'll probably see more questions on
> the list.
>
> One thing that sort of bothers me--I know you can use labels and gotos
> in C/C++ (at least I'm pretty sure of that), but it's pretty much
> considered bad form. But, it looks to me like that is the best
> approach for parts of my state machine--like the main loop and parts of
> other sub-loops (I guess I should say main state machine and parts of
> other sub- state machines).
>
> One of the alternatives is a deeply nested structure that, for some of
> the things to be recognized, may be deeply nested indeed--just the
> indentation to handle the nesting would be ridiculous. I could create
> sub-functions just to minimize nesting, but gotos seem so much easier.
>
especially so in state machines which just loop through the input.
Normally state machines don't nest, just the number of states
increases to accomodate the sub-states and the state machine is
allowed to loop through as many states as it needs to get the
complexity handled, without incrementing the character pointer (and of
course loop through as many characters in one state as it needs, such
as counting repeated characters).
The state machine is usually one big switch statement inside a loop,
roughly (very roughly)
enum states { STATE_NAME, .... }; // lots of states with really
understandable names :-S
while( not at end ){
switch( state ){
case STATE_NAME:
.
.
.
}
if( advance character flag )advance it
}
The crude but simple flag to advance the character (or whatever the
state machine is iterating over) is pretty common when there are lots
of substates that don't advance the input. Just set it at the start of
the loop to the most common condition (advance or not) and then set it
to the other state in the other cases (bad pun intended).
> Oh, I have come across the quex lexical analyser generator which has a
> facility to (automatically, iiuc) create a state diagram based on the
> input. I'm tempted to use it just to create a good state diagram for
> documentation.
>
performance so anything that helps you is worth a try and if it helps
you get it correct even better.
Although as Neil says about scintilla lexers, don't stress about
performance, its unlikely to exceed the code in the
Scintilla/GTK/X11/Graphics_Driver stack that is displaying your
styling :-)
Cheers
Lex
Neil Hodgson
> Hmm, and I just re-read (re-skimmed?) Neil's coding style document
> (Scintilla and SciTE: Code Style) and see this:
>
> "The goto statement is not used because of bad memories from my first
> job maintaining FORTRAN programs. The union feature is not used as it
> can lead to non-type-safe value access."
>
> If I'm still thinking the way I am now, I might write the first
> version(s) with gotos, and try to revise it later.
Lexers don't have to follow the style rules when they are written
by others so are their responsibility. Some currently use goto.
Neil
Philippe Lhoste
> One thing that sort of bothers me--I know you can use labels and gotos
> in C/C++ (at least I'm pretty sure of that), but it's pretty much
> considered bad form. But, it looks to me like that is the best
> approach for parts of my state machine--like the main loop and parts of
> other sub-loops (I guess I should say main state machine and parts of
> other sub- state machines).
Well, look (again?) at some mainstream lexers like LexCPP, LexLua or similar: most of them
if not all have a state machine made by using a test on the state (sc.state) -- could have
been a switch, I suppose, and some tests on the current char (and those around) which
result on a state change (sc.ChangeState, sc.ForwardSetState)... or not (sc.Forward).
The resulting code is still readable, not too deeply nested.
Actually, some lexers use a switch (like LexInno). But not all use StyleContext (even
though most of them include the header!). I think a new lexer should use StyleContext as
it really eases writing lexer code.
--
Philippe Lhoste
-- (near) Paris -- France
-- http://Phi.Lho.free.fr
-- -- -- -- -- -- -- -- -- -- -- -- -- --
KHMan
I second that, I think it is convenient to follow the LexCPP
structure and use StyleContext. The COBOL lexer, for example, is
structured a bit differently, and in some cases, a character can
be left sorta 'unlexed' or skipped over (in normal source code,
such glitches are often not noticeable, though.)
As for gotos, once I zapped a huge chunk of duplicated code in
LexPerl with gotos, and Neil accepted the patch. :-) But recently,
I have rewritten it to follow the LexCPP style, and no gotos are
needed there.
--
Cheers,
Kein-Hong Man (esq.)
Kuala Lumpur, Malaysia
Randy Kramer
Thanks! (Sorry for the late reply!)
I might still start with my goto approach (especially while working in
pseudocode), but then think about rewriting it to use switch
statements.
I have noticed that a fair number of the "lexer generators" generate
code using gotos, but I guess they (as opposed to a human) are diligent
enough to handle it without making mistakes. ;-)
Randy Kramer
Philippe Lhoste
> I have noticed that a fair number of the "lexer generators" generate
> code using gotos, but I guess they (as opposed to a human) are diligent
> enough to handle it without making mistakes. ;-)
Yes, and they don't care about readability and maintenability (at least by themselves!). :-D