Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #40785

Re: I finally completed my lexical analyzer generator (needed by my halt decider) update

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: I finally completed my lexical analyzer generator (needed by my halt decider) update
Date 2021-10-25 02:08 +0100
Organization A noiseless patient Spider
Message-ID <87bl3d3o80.fsf@bsb.me.uk> (permalink)
References <TpydnRmO3dkGK-n8nZ2dnUU7-c3NnZ2d@giganews.com> <GLWdnSs1lLhuOuj8nZ2dnUU7-UnNnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> Enhancements: (Assumes that the C source code compiles)
> (a) Ignores /* */ comments
> (b) Ignores #define lines
> (c) Correctly handles trailing space in: int Function_Name(void   )
>
> //
> //  Deterministic Finite Automaton (DFA) recognizer
> //  of C function headers.
>
> // Character Classes
> //
>     EMPTY [0]
>     ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>   NUMERIC [0123456789]
>        WS [0x09,0x0A,0x0D,0x20]
>    LPAREN [(]
>    RPAREN [)]
>     POUND [#]
>  ASTERISK [*]     // 0x2a
>     COMMA [,]
>     SLASH [0x2f]  // "/"
>   NEWLINE [0x0A]

Why don't you use these last seven?

>     ASCII [0x20-0x7e]
>      ASCII_MINUS_NEWLINE [0x00-0x09,0x0b-0x7f]
>     ASCII_MINUS_ASTERISK [0x00-0x29,0x2b-0x7f]
>        ASCII_MINUS_SLASH [0x00-0x2e,0x30-0x7f]
>   CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>
> // Recognized Patterns
> //
> {et} Empty
> {ft} Function_Type
> {fn} Function_Name
> {vt} Variable_Type
> {vn} Variable_Name
> {fh} Function_Header
>
> // DFA Definition to recognize C function headers

No DFA can do that in general.  You mean "recognise a very restricted
subset of C function headers".

> // begin of function type
> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)

What does that [*] mean?  Judging by the other uses of []s, you seem to
be accepting *s and digits at the start of a C function header even
though they won't be taken to be one of your named matches.  Why single
out *s and digits?

> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>
> // begin of function name
> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>
> // begin of variable type
> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)

And all these uses of [*] are very odd.  It seems that after seeing this
string:

  *1*x x(*x x()

your DFA returns to state 0 having seen an {fh}.  Is that right?  Maybe
I've misunderstood the notation.

> // begin of variable name
> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00) [)]{fh}(00)
> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>
> // ignores all "//" comments
> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](14) [/](13)
> <13> ASCII_MINUS_NEWLINE(13)  [0x0A] (00)
>
> // look for comment terminator "*/"
> <14> ASCII_MINUS_ASTERISK(14) [*](15)
> <15>    ASCII_MINUS_SLASH(14) [/](00)

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

I finally completed my lexical analyzer generator (needed by my halt decider) olcott <NoOne@NoWhere.com> - 2021-10-23 20:27 -0500
  Re: I finally completed my lexical analyzer generator (needed by my halt decider) Richard Damon <Richard@Damon-Family.org> - 2021-10-23 21:49 -0400
    Re: I finally completed my lexical analyzer generator (needed by my halt decider) olcott <NoOne@NoWhere.com> - 2021-10-23 21:16 -0500
      Re: I finally completed my lexical analyzer generator (needed by my halt decider) Richard Damon <Richard@Damon-Family.org> - 2021-10-23 23:19 -0400
        Re: I finally completed my lexical analyzer generator ( axiomatic basis ) olcott <NoOne@NoWhere.com> - 2021-10-23 22:29 -0500
          Re: I finally completed my lexical analyzer generator ( axiomatic basis ) Richard Damon <Richard@Damon-Family.org> - 2021-10-24 06:40 -0400
            Re: I finally completed my lexical analyzer generator ( axiomatic basis ) olcott <NoOne@NoWhere.com> - 2021-10-24 09:04 -0500
              Re: I finally completed my lexical analyzer generator ( axiomatic basis ) Richard Damon <Richard@Damon-Family.org> - 2021-10-24 13:37 -0400
                Re: I finally completed my lexical analyzer generator ( semantic tautology ) olcott <NoOne@NoWhere.com> - 2021-10-25 10:02 -0500
                Re: I finally completed my lexical analyzer generator ( semantic tautology ) Richard Damon <Richard@Damon-Family.org> - 2021-10-25 19:40 -0400
  Re: I finally completed my lexical analyzer generator (needed by my halt decider) Richard Damon <Richard@Damon-Family.org> - 2021-10-24 07:59 -0400
    Re: I finally completed my lexical analyzer generator (needed by my halt decider) olcott <NoOne@NoWhere.com> - 2021-10-24 09:07 -0500
      Re: I finally completed my lexical analyzer generator (needed by my halt decider) Richard Damon <Richard@Damon-Family.org> - 2021-10-24 13:41 -0400
  Re: I finally completed my lexical analyzer generator (needed by my halt decider) update olcott <NoOne@NoWhere.com> - 2021-10-24 13:37 -0500
    Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Richard Damon <Richard@Damon-Family.org> - 2021-10-24 15:55 -0400
    Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-10-25 02:08 +0100
      Re: I finally completed my lexical analyzer generator (needed by my halt decider) update olcott <NoOne@NoWhere.com> - 2021-10-24 20:45 -0500
        Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-10-26 00:26 +0100
          Re: I finally completed my lexical analyzer generator (needed by my halt decider) update olcott <NoOne@NoWhere.com> - 2021-10-25 19:08 -0500
            Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-10-26 02:09 +0100
              Re: I finally completed my lexical analyzer generator (needed by my halt decider) update olcott <NoOne@NoWhere.com> - 2021-10-25 20:54 -0500
                Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Richard Damon <news.x.richarddamon@xoxy.net> - 2021-10-26 07:00 -0400
                Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-10-26 14:56 +0100
                Re: I finally completed my lexical analyzer generator (needed by my halt decider) update olcott <NoOne@NoWhere.com> - 2021-10-26 09:43 -0500
                Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-10-26 23:47 +0100

csiph-web