Re: State-of-the-art algorithms for lexical analysis?

On 6/6/22 1:05 AM, gah4 wrote:


> It has a completely different PSL, Pattern Specification Language,
> much more powerful than the usual regular expression.


I wonder about the need for powerful patterns in programming languages.
Most items (operators, punctuators, keywords) are fixed literals with a
fixed ID for use by the parser and code generator. If source code is
written by humans then the remaining types (identifiers, literals,
comments) should not have a too complicated syntax. For machine
generated source code a lexer is not required, the generator can
immediately produce the tokens for the parser. And if humans should
understand the code produced by the generator then again the syntax has
to be as simple and easy understandable as possible to humans.




> Among others, PSL has the ability to define approximate matches,
> such as a word with one or more misspellings, that is insertions,
> deletions, or substitutions. Usual RE don't have that ability.


That's fine for keywords but does not help with user defined
identifiers. Still a nice to have feature :-)


> There are also PSL expressions for ranges of numbers.
> You can often do that with very complicated RE, considering
> all of the possibilities. PSL automatically processes those
> possibilities. (Some can expand to complicated code.)


If this feature is really helpful to the user?




> I suspect that in many cases the usual RE is not optimal for
> lexical analysis, other than being well known.
>
> But as noted, DFA are likely the best way to do them.


ACK


> Though that could change with changes in computer hardware.


Or with the style of writing. APL already tried to simplify typing, in
the near future a Chinese programming language with a glyph for each
token (except literals) would eliminate the need for a lexer. Then a
demand may arise for speech-to-text and reverse tools instead of a
lexer, for each natural language.


DoDi
[Regular expressions have the advantage that once you've paid the one-time cost
of making a DFA, the matching is extremely fast. Since the lexer is usually
one of the slowest parts of a compiler since it is the only part that has to
look at each character of the source program, this is a place where speed
matters. Anyone know how fast PSLs are? I've seen fuzzy matchers but they
haven't been very fast. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.