Re: [9fans] non greedy regular expressions - Plan9

This is a discussion on Re: [9fans] non greedy regular expressions - Plan9 ; First of all, thanks for the explanation. It's above my head, but thanks anyway. > This guy seems to blur the distinctions here. His discussion He doesn't. If one reads the whole section part of which was quoted one will ...

+ Reply to Thread
Results 1 to 3 of 3

Thread: Re: [9fans] non greedy regular expressions

  1. Re: [9fans] non greedy regular expressions

    First of all, thanks for the explanation. It's above my head, but thanks
    anyway.

    > This guy seems to blur the distinctions here. His discussion


    He doesn't. If one reads the whole section part of which was quoted one
    will see that he clearly states DFA and NFA are theoretically equivalent,
    but then goes on to explain that DFA and NFA _implementations_ are not
    identical.

    > The true mathematical and computational meaning of "NFA" is different
    > from what is commonly called an "NFA regex engine." In theory, NFA and
    > DFA engines should match exactly the same text and have exactly the same
    > features. In practice, the desire for richer, more expressive regular
    > expressions has caused their semantics to diverge. An example is the
    > support for backreferences.
    >
    > The design of a DFA engine precludes backreferences, but it's a
    > relatively small task to add backreference support to a true
    > (mathematically speaking) NFA engine. In doing so, you create a more
    > powerful tool, but you also make it decidedly nonregular (mathematically
    > speaking). What does this mean? At most, that you should probably stop
    > calling it an NFA, and start using the phrase "nonregular expressions,"
    > since that describes (mathematically speaking) the new situation. No one
    > has actually done this, so the name "NFA" has lingered, even though the
    > implementation is no longer (mathematically speaking) an NFA.


    -- from the same book

    > And a good book on automata theory can give you far more
    > than any "big book of...", "... in 21 days" or "... for
    > dummies" book can. Besides, why would you think that
    > anyone is denying you knowledge or the opportunity
    > to write code that demonstrates your ideas?


    Because lowlifes don't write code. No need for somebody to stop them from
    doing so. They learn slowly, hardly, painfully--they aren't smart. If
    possible they'll learn less rather than learn more. What the "hacker"
    denies the lowlife is the opportunity to exist free of "GNU-is-wrong" or
    "X-is-wrong" blemish. GNU may be wrong, or right, but GNU is learnt fast
    and easy. And it does the job.

    By the way, Friedl's book has the advantage of giving a lowlife a glimpse
    of a subject otherwise arcane from that same lowlife's point of view. It's
    good--for the lowlife, of course--to know the wonders they see didn't
    spring into existence out of the blue. I benefitted from that learning.

    --On Monday, October 27, 2008 4:13 PM +0000 "Brian L. Stuart"
    wrote:

    >> The set of "big books on regular expressions" includes Jeffrey Friedl's
    >> "Mastering Regular Expressions" that happens to contain a chapter by the
    >> title "NFA, DFA, and POSIX" wherein he says:
    >>
    >> > DFA Speed with NFA Capabilities: Regex Nirvana?

    >
    > This guy seems to blur the distinctions here. His discussion
    > makes it sound like he's saying that NFAs have more expressive
    > power than DFAs. This is incorrect. Both NFAs and DFAs have
    > exactly the same expressive power as the class of grammars
    > called regular. For the arbitrary case of nesting (e.g. parens),
    > these machines are insufficient. However, for any prescribed
    > maximum nesting level, you can write a regular expression to
    > account for it, though it becomes clumsy.
    >
    > To get more expressiveness, you need to go to a machine
    > with more functionality. Classically, the next step
    > up the hierarchy is the pushdown automaton. The expressive
    > power of this machine corresponds directly to the context-
    > free grammars. Because the full generality of the CFG
    > require nondeterminism, automated translations from CFG
    > to code/machine are usually done with restricted classes
    > of CFGs, such as LR(k) and LALR. You can also increase
    > the power of a FA by adding a counter or by making the
    > transitions probablistic. If you truly want to build
    > expression matching mechanisms that go beyond regular,
    > building on the FA with counter(s) would be a far more
    > sound foundation than a lot of the ad hoc stuff that's
    > been done. But the truth is that whipping up a CFG
    > and feeding it to yacc is far more expedient than torturing
    > regular expressions all day.
    >
    >> Again, turns out the "big books on regular expressions" can give the
    >> lowlife--that's me--things "hackers" deny them.

    >
    > And a good book on automata theory can give you far more
    > than any "big book of...", "... in 21 days" or "... for
    > dummies" book can. Besides, why would you think that
    > anyone is denying you knowledge or the opportunity
    > to write code that demonstrates your ideas?
    >
    > BLS
    >
    >



  2. Re: [9fans] non greedy regular expressions

    > > This guy seems to blur the distinctions here. His discussion
    >
    > He doesn't. If one reads the whole section part of which was quoted one
    > will see that he clearly states DFA and NFA are theoretically equivalent,
    > but then goes on to explain that DFA and NFA _implementations_ are not
    > identical.


    Actually, that's why I said "seems to." Basically, what he
    should be saying is that some people have found it easier
    to add elements to the NFA model that augment the grammar.
    But then he goes on to use the initials NFA when he really
    means the extensions thereof. This creates in the reader's
    mind the misimpression that there's something magically
    different between an NFA and a DFA, theoretically or
    implementationally. They have exactly the same expressive
    power in both realms. Besides, nondeterminism can only
    be simulated when running on a deterministic computer.
    That's actually the insight behind the NFA to DFA construction.
    So talking about an "NFA implementation" is rather artificial.

    > They learn slowly, hardly, painfully--they aren't smart. If
    > possible they'll learn less rather than learn more. What the "hacker"
    > denies the lowlife is the opportunity to exist free of "GNU-is-wrong" or
    > "X-is-wrong" blemish.


    Look at it this way. The people here aren't trying to
    create blemishes on anything. Rather we are trying to
    help your learning process. We're trying to head off
    the tendency for people to jump from "it was easy to
    learn how to do X in this tool" to "how this tool does
    things is better." Instead, before asserting something
    is better or asking for others to write software according
    to a personal preference, it is important to broaden
    your understanding so that you know what the options
    really are and what the design decisions really imply.
    Implementing a laundry list of features without that
    perspective simply produces bad software.

    > It's
    > good--for the lowlife, of course--to know the wonders they see didn't
    > spring into existence out of the blue.


    That's why we teach the theory that everyone seems to
    want to complain about. Building on Newton, if we want
    to see farther than those before us, we need to know
    those before us well enough to climb onto their shoulders.
    No software is based on Hogwarts' technology, and no
    good software comes from the "random walk method of
    programming." It is the product of intellectual reasoning.
    Criticism of the result won't be taken too seriously
    if the critic shows they have not understood the reasoning
    behind it.

    BLS



  3. Re: [9fans] non greedy regular expressions

    Thanks for the explanations. The lowlife learns a bit or two :-)

    --On Tuesday, October 28, 2008 2:51 PM +0000 "Brian L. Stuart"
    wrote:

    >> > This guy seems to blur the distinctions here. His discussion

    >>
    >> He doesn't. If one reads the whole section part of which was quoted one
    >> will see that he clearly states DFA and NFA are theoretically
    >> equivalent, but then goes on to explain that DFA and NFA
    >> _implementations_ are not identical.

    >
    > Actually, that's why I said "seems to." Basically, what he
    > should be saying is that some people have found it easier
    > to add elements to the NFA model that augment the grammar.
    > But then he goes on to use the initials NFA when he really
    > means the extensions thereof. This creates in the reader's
    > mind the misimpression that there's something magically
    > different between an NFA and a DFA, theoretically or
    > implementationally. They have exactly the same expressive
    > power in both realms. Besides, nondeterminism can only
    > be simulated when running on a deterministic computer.
    > That's actually the insight behind the NFA to DFA construction.
    > So talking about an "NFA implementation" is rather artificial.
    >
    >> They learn slowly, hardly, painfully--they aren't smart. If
    >> possible they'll learn less rather than learn more. What the "hacker"
    >> denies the lowlife is the opportunity to exist free of "GNU-is-wrong" or
    >> "X-is-wrong" blemish.

    >
    > Look at it this way. The people here aren't trying to
    > create blemishes on anything. Rather we are trying to
    > help your learning process. We're trying to head off
    > the tendency for people to jump from "it was easy to
    > learn how to do X in this tool" to "how this tool does
    > things is better." Instead, before asserting something
    > is better or asking for others to write software according
    > to a personal preference, it is important to broaden
    > your understanding so that you know what the options
    > really are and what the design decisions really imply.
    > Implementing a laundry list of features without that
    > perspective simply produces bad software.
    >
    >> It's
    >> good--for the lowlife, of course--to know the wonders they see didn't
    >> spring into existence out of the blue.

    >
    > That's why we teach the theory that everyone seems to
    > want to complain about. Building on Newton, if we want
    > to see farther than those before us, we need to know
    > those before us well enough to climb onto their shoulders.
    > No software is based on Hogwarts' technology, and no
    > good software comes from the "random walk method of
    > programming." It is the product of intellectual reasoning.
    > Criticism of the result won't be taken too seriously
    > if the critic shows they have not understood the reasoning
    > behind it.
    >
    > BLS
    >
    >



+ Reply to Thread