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


Groups > comp.theory > #40851

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 14:56 +0100
Organization A noiseless patient Spider
Message-ID <87pmrrzy74.fsf@bsb.me.uk> (permalink)
References (3 earlier) <xYSdnUeGwL7Okev8nZ2dnUU7-dPNnZ2d@giganews.com> <87wnm01y9s.fsf@bsb.me.uk> <nPqdnbNMHNB72-r8nZ2dnUU7-S3NnZ2d@giganews.com> <87a6iw1tjm.fsf@bsb.me.uk> <GMydnZtvI8x8wur8nZ2dnUU7-avNnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> On 10/25/2021 8:09 PM, Ben Bacarisse wrote:
>> 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.
>
> Here is LPAREN: [(]{fn}(06)
>>>>>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)

No.  That state uses the definitions ALPHA and NUMERIC but it does not
use the definition LPAREN.  The point, since I seem t have to spell it
out, is why name the class is you are not going to use the named
versions?  It makes the read think you don't know how the notation
works.

>>>>> 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! 
>
> Why did you delete it?

I didn't.  It is still quoted in the post you are replying to here and
you have kept in your reply and it is still there in this post.

> Here is is being correctly recognized:
> int* M(int* N);
>
>  [i]  State(00)        NextState(01)  LineNumber(0006)
>  [n]  State(01)        NextState(01)  LineNumber(0006)
>  [t]  State(01)        NextState(01)  LineNumber(0006)
>  [*]  State(01)        NextState(02)  LineNumber(0006)
>  [ ]  State(02)  {ft}  NextState(03)  LineNumber(0006)
>  [M]  State(03)        NextState(04)  LineNumber(0006)
>  [(]  State(04)  {fn}  NextState(06)  LineNumber(0006)
>  [i]  State(06)        NextState(07)  LineNumber(0006)
>  [n]  State(07)        NextState(07)  LineNumber(0006)
>  [t]  State(07)        NextState(07)  LineNumber(0006)
>  [*]  State(07)        NextState(08)  LineNumber(0006)
>  [ ]  State(08)  {vt}  NextState(09)  LineNumber(0006)
>  [N]  State(09)        NextState(10)  LineNumber(0006)
>  [)]  State(10)  {vn}  NextState(00)  LineNumber(0006)
>   insert("M", 1);

It is not recognised as matching the {fh} pattern.  That's (apparently)
the pattern for a function header.  Some things do match the {fh}
pattern.  For example "int M(void)".

Now you may have fudged things by making the action associated with the
{vn} action trigger whatever it is you want to with a function header,
but that's a hack.  Or maybe you've hacked it to work in some other way,
but some function headers do match the correct named pattern, but most
don't.

>>>>>>> // 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

This is where you should have show that example not being recognised and
then you would not accused me of deleting the example!

> Your:
> *1*x x(*x x()
> was rejected by the C compiler.

Yes.  But right after I complained about your "int* M(int* N);" example
not matching as a header you said

  "The above string would be rejected by the C compiler"

which is obviously not the case.

-- 
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