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


Groups > comp.theory > #40835

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-26 02:09 +0100
Organization A noiseless patient Spider
Message-ID <87a6iw1tjm.fsf@bsb.me.uk> (permalink)
References (1 earlier) <GLWdnSs1lLhuOuj8nZ2dnUU7-UnNnZ2d@giganews.com> <87bl3d3o80.fsf@bsb.me.uk> <xYSdnUeGwL7Okev8nZ2dnUU7-dPNnZ2d@giganews.com> <87wnm01y9s.fsf@bsb.me.uk> <nPqdnbNMHNB72-r8nZ2dnUU7-S3NnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> On 10/25/2021 6:26 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> On 10/24/2021 8:08 PM, Ben Bacarisse wrote:
>>>> 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?
>>>
>>> I do use them.
>> I meant why not use them in the code you posted.
>
> They are used in the DFA shown below.

No they are not.

>>> I can refer to either the name or the definition of the character class.
>>> ASCII and CONTROL may be used in the future.
>>>
>>>>>       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".
>>>
>>> It recognizes everything that I will ever write.
>>
>> Ah.  That simplifies things, and alerts the reader not to check the DFA
>> since you can just say "I'd never write that!".  However...
>> 
> If I wanted a more robust function header recognizer I would adapt the
> lex/yacc spec for C.

Your DFA does not even recognise the one example you gave!

>>>>> // 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?
>>>
>>> int* M(int* N);
>>
>> This does not recognise the {fh} pattern.  Putting the named
>> patterns into the string at the point the action would be triggered I
>> get
>
> The above string would be rejected by the C compiler this never reach
> the DFA reogonizer.

Don't be silly, of course it won't be rejected.  I thought you knew a
bit about C.  But given that you thought it would be rejected, why give
it as an example or the need to handle *s.

Anyway, even "int f(int x)" does not get recognised as a function
header.  I thought you knew a bit about DFAs.

>>    int* {ft}M({fn}int* {vt}N){vn}
>> (The ; does not help -- there is no specified transition for ';' is
>> state 0.)
>> Furthermore, this example does not explain why you permit digits. 
>
> It recognizes all valid C identifiers.

Do you really not understand the DFA you wrote?  I am asking why you
single out digits to be accepted in state 0.  They form part of
identifiers, but that's not what state 0 is doing.  You skip digits,
spaces and *s in a position where digits are meaning less.

>>  You
>> say you won't ever write them, 
>
> I did not say that I will not write digits.

You said you would not write

  *1*x x(*x x()

and I am asking why you accept digits in state 0.  Why single them out?
They are never valid in that position, but then there are lots of other
characters you could pointlessly accept in state 0 as well.

> I said that I don't need a full parser.
>
>> but it's odd to permit them where they
>> are invalid.  That "NUMERIC(00)" part looks like "cargo cult"
>> programming.
>
> It was easiest to write this DFA from scratch when I explicitly
> accounted for all of the character classes on every line.

Except you don't do that.  You account for some of them in most of the
lines.

> This line skips white-space
> matches the first char of a valid C identifier
> ignores asterisk
> matches the first char of a C comment
> matches the first char of a C #define statement
>
>>>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)

and "ignores" digits for some unexplained reason.

>> Kept for reference:
>>>>> <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)
>> 
>>>>> // 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