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


Groups > comp.theory > #40781

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

Subject Re: I finally completed my lexical analyzer generator (needed by my halt decider) update
Newsgroups comp.theory
References <TpydnRmO3dkGK-n8nZ2dnUU7-c3NnZ2d@giganews.com> <GLWdnSs1lLhuOuj8nZ2dnUU7-UnNnZ2d@giganews.com>
From Richard Damon <Richard@Damon-Family.org>
Message-ID <bTidJ.9898$D64.1912@fx41.iad> (permalink)
Organization Forte - www.forteinc.com
Date 2021-10-24 15:55 -0400

Show all headers | View raw


On 10/24/21 2:37 PM, olcott wrote:
> On 10/23/2021 8:27 PM, olcott wrote:
>> In order to make my halt decider a pure function it had to have a way 
>> to look at the inputs to function calls. In order to look at the 
>> inputs to function calls it had to know how many inputs that a 
>> function has.
>>
>> This is DFA analyzes C source code to provide the number of parameters 
>> of each function in the file. The number of parameters per function is 
>> the number of {vt} matches per {fn} match.
>>
>> The only thing that will change with this file is that the halt 
>> decider will use different halt deciding criteria so that the halt 
>> decider becomes a pure function.
>>
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>
>>
>> In computer programming, a pure function is a function that has the 
>> following properties:[1][2]
>>
>> (1) The function return values are identical for identical arguments 
>> (no variation with local static variables, non-local variables, 
>> mutable reference arguments or input streams).
>>
>> (2) The function application has no side effects (no mutation of local 
>> static variables, non-local variables, mutable reference arguments or 
>> input/output streams).
>>
>> https://en.wikipedia.org/wiki/Pure_function
>>
>>
> 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]
>      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
> 
> // begin of function type
> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)
> <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)
> 
> 
> 

And again my question, what good is this if the halt decider is getting 
the compiled version of the code as its input?

If H doesn't have the source code, it can't give what it doesn't have to 
the DFA to get the data it wants.

Or, does the Halt Decider now get the source code and is compiling it 
before running it?

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