Re: Fragments

On 2019-12-21, Andy <borucki.andrzej@gmail.com> wrote:
> In examples is usually used very small alphabet: 3 to 5 letters but in
> lexical analysing is not only Ascii but many thousands of Unicode.
> Many chars are grouped by the same action: for example digits->a
> letter->b whitepsaces->c
> We can use "fragments" [A-Za-z], [0-9] instead of alone letters.
> Problem that fragments not always are disjoint: digits and all chars, letters and letter 'a', etc.
>
> How to handle with not disjoint fragments? on input we get regular
> expression in Posix standard and we want make DFA with a few
> transitions.


In the TXR language, I wrote a regex engine to handle the full Unicode
range of characters.


To represent character ranges, I wrote a polymorphic "char set" data
type in C. See:


http://www.kylheku.com/cgit/txr/tree/regex.c


The main declaration looks like:


    typedef union char_set {
        struct any_char_set any;
        struct small_char_set s;
        struct displaced_char_set d;
        struct large_char_set l;
    #ifdef FULL_UNICODE
        struct xlarge_char_set xl;
    #endif
    } char_set_t;


Each of the types included in the union has a type field in the same
place which indicates which type of set it is.


The different set types are geared toward different situations.


The small_char_set is a 256 entry bitmask; it handles the ASCII/ISO
Latin 8 bit range.


The large_char_set has a two-level tree structure: basically a sparsely
populated array of bitmasks.


The xlarge_char_set has a three-level structure.


the displaced_char_set is also a small bitmask, but with an offset,
so it can represent characters anywhere in the map, if they fall into
the same 256-wide window.

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