On 3/22/2023 1:37 PM, George Neuner wrote:
I build FSMs similarly. But, you can't commit graphs to
ASCII text whereas tables are a natural consequence.
The difference seems largely to be that DFA are geared towards
expressing "languages" (sequences of symbols) whereas FSMs
are geared towards expressing sequences of events/actions.
By contrast, an FSM will often have a variety of very different
symbols recognized in a given state and acted upon differently
(POWER_FAIL, POWER_RESTORED, LOW_BATTERY, CLEAR, ENTER, BARCODE_DETECTED, >etc.). These tend to have more "work" associated with their
recognition than a set of equivalent symbols (e.g., digits).
And, while each may be handled differently from the others,
they tend to be handled the same way when encountered in
different states. I.e., a POWER_FAIL is processed the same
each place it is considered significant.
I build "state subroutines" to handle sets of symbols that
are handled the same way but "invoked" from different states
(see Exceptions). But, the individual symbols can invoke
different actions *and* different next states -- as long as
they are consistent in each "application".
If instead you did something like:
integer: [:digit:] return 'i'
hex: [:digit:]|['a'-'f'] return 'h';
This would blow up in your face because 0..9 would never be recognized
a hex digit, but more importantly the 2 uses of the class lead
/immediately/ to different actions so the class subroutine (subgraph)
would have to be repeated in the FA with different exit actions.
Yes. If the tool places an implicit priority on the rules
based on the order in which they are encountered. I intentionally
don't specify this in the design of the tables, leaving the
"post processor" some latitude in how it implements them
and the runtime some potential efficiencies.
The difference seems largely to be that DFA are geared towards
expressing "languages" (sequences of symbols) whereas FSMs
are geared towards expressing sequences of events/actions.
The terms "FA" (finite automaton) and "FSM" (finite state machine)
are, in fact, synonymous.
What is confusing is that we got to this point through discussion of
parsing and lexing tools - which ARE geared toward languages.
Moreover, yacc and bison do NOT implement a general FA, but rather a particular variety of FA that useful for language parsing and which
involves an auxiliary stack.
Purely as a techical matter, (f)lex can create general FA assuming
that transition conditions can be represented as character input to
the reader. The "reader" function is completely redefineable: the
default is to read from STDIN, but, in fact, a custom reader can do absolutely anything under the hood so long as it returns a character
(or EOF) when called.
In practice you would not want to do this. A decent UML tool would be
a much better choice.
By contrast, an FSM will often have a variety of very different
symbols recognized in a given state and acted upon differently
(POWER_FAIL, POWER_RESTORED, LOW_BATTERY, CLEAR, ENTER, BARCODE_DETECTED,
etc.). These tend to have more "work" associated with their
recognition than a set of equivalent symbols (e.g., digits).
And, while each may be handled differently from the others,
they tend to be handled the same way when encountered in
different states. I.e., a POWER_FAIL is processed the same
each place it is considered significant.
Yes. And you could (at least theoretically) represent this in flex by encoding POWER_FAIL, etc. as characters or strings and sending those characters or strings as input to the reader when those events occur. Internal state transitions can be handled the same way: send
characters to the reader.
Again, this is an abuse of the tool. Just because you can do it does
not mean you should do it.
I build "state subroutines" to handle sets of symbols that
are handled the same way but "invoked" from different states
(see Exceptions). But, the individual symbols can invoke
different actions *and* different next states -- as long as
they are consistent in each "application".
flex (not lex) permits defining contextual "start" states, which the
code can arbitrarily switch among. The same input can be treated
differently in different start states. These really are coroutines -
not subroutines - and the user code decides which state to switch to
next, but flex does provides a stack so you can use them as
subroutines (without having to track the nesting yourself).
If instead you did something like:
integer: [:digit:] return 'i'
hex: [:digit:]|['a'-'f'] return 'h';
This would blow up in your face because 0..9 would never be recognized
a hex digit, but more importantly the 2 uses of the class lead
/immediately/ to different actions so the class subroutine (subgraph)
would have to be repeated in the FA with different exit actions.
Yes. If the tool places an implicit priority on the rules
based on the order in which they are encountered. I intentionally
don't specify this in the design of the tables, leaving the
"post processor" some latitude in how it implements them
and the runtime some potential efficiencies.
The tool places priority on the longest, most precise match. It falls
back on definition order when the input - as given - matches multiple patterns.
But again, start states can (sometimes) be used to get around this
behavior.
On Wed, 22 Mar 2023 18:15:43 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
The terms "FA" (finite automaton) and "FSM" (finite state machine)
are, in fact, synonymous.
What is confusing is that we got to this point through discussion of
parsing and lexing tools - which ARE geared toward languages.
Moreover, yacc and bison do NOT implement a general FA, but rather a particular variety of FA that useful for language parsing and which
involves an auxiliary stack.
On 3/25/2023 9:45 PM, George Neuner wrote:
My hardware classes talked about FSMs, Meely/Moore, "state diagrams"
and optimization techniques.
My software classes talked about DFAs, EBNFs, *railroad* diagrams
but never a mention of optimization tools or techniques.
They also seem to be applied differently. E.g., in a (hardware) FSM,
it is not uncommon to list a logical expression as the stimulus
for a transition (e.g., "LineFeed & /Last_Line" vs. "LineFeed & LastLine" >directing the machine to two different states with two different outputs
or actions). In DFAs, it was always just sequences of symbols -- the
sorts of things that would specify a grammar (inherently serial, one-at-a-time >"conditions").
Purely as a techical matter, (f)lex can create general FA assuming
that transition conditions can be represented as character input to
the reader. The "reader" function is completely redefineable: the
default is to read from STDIN, but, in fact, a custom reader can do
absolutely anything under the hood so long as it returns a character
(or EOF) when called.
Therein lies a notable limitation. In a (hardware) FSM, there are no limits >to the number of inputs that can CONCURRENTLY be examined by the machine. >E.g., I could label a transition with:
A*/B*/C*D*E*F*/G*H*I*J*/K*/L*/M + N*O*P*Q + /R*/S*/T*U*V + W + X*Y*Z
To represent this to lex/yacc, I would have to reduce it to a "narrow"
symbol -- possible if there are only a limited number of such combinations
in the grammar (as sourced by the lexer).
In practice you would not want to do this. A decent UML tool would be
a much better choice.
In a (hardware) FSM, one would see all of the "possible exits" from a >particular state and could notice ambiguities:
X*Y*/Z
X*Y
clearly overlap.
Furthermore, one could detect these conflicts with a simple tool;
it need not understand the entire machine, just look at a single state
and the transitions leaving it.
What's interesting (being a hardware-software person) is that, despite
the obvious duality, the approaches taken to these technologies is so >disjointed. DFA tend to use a parser-generator of preference while FSMs
(in software) have a variety of different implementations with dramatic >design and runtime differences in efficiencies.
Similarly, that hardware FSMs tend to be designed with total disregard
to the possible applicability of parser generators, regex compilers, etc.
Its as if each domain has its own notion of how the technology should
be applied and implemented.
On Sun, 26 Mar 2023 03:35:27 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
On 3/25/2023 9:45 PM, George Neuner wrote:
My hardware classes talked about FSMs, Meely/Moore, "state diagrams"
and optimization techniques.
My software classes talked about DFAs, EBNFs, *railroad* diagrams
but never a mention of optimization tools or techniques.
This I think is a teaching failure.
Before we go on here we have to clarify a possible terminology trap: "deterministic" vs "non-deterministic".
In the context of FA, "deterministic" means that the machine can be
only in one state at any given time. "non-deterministic" means that
the machine (at least logically) can simultaneously be in a set of
multiple states.
To explain this better, I'm falling back on lexing because it is
simple minded. You will need to generalize the concepts to consider
other possible uses.
Ignoring the behavior of any real-world tools and just thinking about
an *ideal* recognizer, consider
integer: [:digit:]+
hex : [:digit:]+|[a-fA-F]+
Lacking further input, the sequence "1234" is ambiguous - the
recognizer doesn't know yet whether it has an integer value or a hex
value. Logically it must consider both patterns simultaneously, and
so logically the recognizer must be an NDFA.
For every NDFA there is a corresponding DFA which contains an equal or greater number of states. Where the NDFA logically would be in a set
of states simultaneously, the corresponding DFA will contain not only
those explicit NDFA states but also additional states which represent possible combinations of those states which the NDFA could find itself
in. The additional states are required because a DFA can be in only
one state at any given time, so it needs a way to (logically)
represent being in multiple states simultaneously. The additional
"set" states serve to disambiguate ambiguous state transitions ...
eventually the DFA must arrive in one of the explicit states of the
original NDFA.
The typical notion of FSM as taught to hardware oriented students
corresponds to non-deterministic FA. Hardware can directly implement
an NDFA, but software can only *emulate* it - with all the caveats
implied by emulation.
Algorithms to transform graph based NDFA to DFA and back again have
been known at least since the 1950s, as have ways of generating table
driven vs switch based machines from a graph. But, typically, none of
this ever is taught to hardware oriented students (or even most
software oriented students) - if they learn anything at all, they
learn some practical methods to manually achieve the same results.
From the software viewpoint, you rarely, if ever, would try to design
a DFA directly. Instead you would design an NDFA that does what you
want, and then (for performance) you have it algorithmically
transformed into its corresponding DFA form. The transformation
[assuming it's done right ;-)] produces an optimal DFA state machine.
(f)lex is a tool that can - at least technically - create general
state machines. However, because it was designed for string
recognition, its machine description language is specialized for that
use.
yacc and bison don't even try to create general state machines - they
create a very specific type of FA which is optimized for parsing. And
again, because they were designed for parsing, their machine
description languages are specialized for that task.
UML tools are what you need to consider for more general FA / FSM.
They also seem to be applied differently. E.g., in a (hardware) FSM,
it is not uncommon to list a logical expression as the stimulus
for a transition (e.g., "LineFeed & /Last_Line" vs. "LineFeed & LastLine"
directing the machine to two different states with two different outputs
or actions). In DFAs, it was always just sequences of symbols -- the
sorts of things that would specify a grammar (inherently serial, one-at-a-time
"conditions").
FSM *are* FA are just alternate terms for the same concept.
There is nothing whatsoever which limits one or the other to any
particular uses. Any apparent difference is an artifact of how they
are taught to students in different disciplines: hardware students
learn practice but rarely, if ever, learn the theory.
And, in truth, only CS students taking language / compiler courses
ever will learn how to build NDFA and DFA state graphs, convert one
graph form into the other, or how to generate table driven or switch
code from a state graph.
Purely as a techical matter, (f)lex can create general FA assuming
that transition conditions can be represented as character input to
the reader. The "reader" function is completely redefineable: the
default is to read from STDIN, but, in fact, a custom reader can do
absolutely anything under the hood so long as it returns a character
(or EOF) when called.
Therein lies a notable limitation. In a (hardware) FSM, there are no limits >> to the number of inputs that can CONCURRENTLY be examined by the machine.
E.g., I could label a transition with:
A*/B*/C*D*E*F*/G*H*I*J*/K*/L*/M + N*O*P*Q + /R*/S*/T*U*V + W + X*Y*Z
To represent this to lex/yacc, I would have to reduce it to a "narrow"
symbol -- possible if there are only a limited number of such combinations >> in the grammar (as sourced by the lexer).
You could just use the string above to represent the condition.
But this is where (f)lex falls down hard: you would have to define
strings that represent all possible combinations of your simultaneous conditions, and to drive the resulting DFA the code that monitors your hardware must be able to send those condition strings into the
recognizer.
If you can do that, (f)lex will happily generate a working state
machine for you.
In practice you would not want to do this. A decent UML tool would be
a much better choice.
In a (hardware) FSM, one would see all of the "possible exits" from a
particular state and could notice ambiguities:
X*Y*/Z
X*Y
clearly overlap.
Furthermore, one could detect these conflicts with a simple tool;
it need not understand the entire machine, just look at a single state
and the transitions leaving it.
That's why you need a tool designed for the purpose. All of our
discussion here about what is possible with (f)lex is academic ...
nobody in their right mind should be doing it.
What's interesting (being a hardware-software person) is that, despite
the obvious duality, the approaches taken to these technologies is so
disjointed. DFA tend to use a parser-generator of preference while FSMs
(in software) have a variety of different implementations with dramatic
design and runtime differences in efficiencies.
Similarly, that hardware FSMs tend to be designed with total disregard
to the possible applicability of parser generators, regex compilers, etc.
Its as if each domain has its own notion of how the technology should
be applied and implemented.
Unfortunately yes. I think very few people ever think about it enough
to recognize that.
On 26/03/23 15:45, George Neuner wrote:
On Wed, 22 Mar 2023 18:15:43 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
The terms "FA" (finite automaton) and "FSM" (finite state machine)
are, in fact, synonymous.
What is confusing is that we got to this point through discussion of
parsing and lexing tools - which ARE geared toward languages.
Moreover, yacc and bison do NOT implement a general FA, but rather a
particular variety of FA that useful for language parsing and which
involves an auxiliary stack.
The stack means it's not a FA.
Yacc and bison exist for the sole purpose
of processing LALR2 grammars that cannot be processed with an FA.
Also
because the grammars are LALR, the stack is a bottom-up stack, so it
doesn't resemble anything you'll see in a top-down parser, ...
... and you'll
get parse errors that probably don't really tell you what is wrong with
the input :P.
Lex/Flex on the other hand exists to process only finite
states. The FSM algorithms they use are more efficient than any
algorithm that can handle LALR2, which is why these tools still exist as >independent tools.
Notably, the combination of yacc&lex (or flex&bison) still isn't
powerful enough even to parse C without extra help - goto labels blow
thing up and there is a hand-coded hack in the C language lexers for it.
ANTLR also implements some version of an LR/LALR parser ...
... but instead of
a finite 2 tokens lookahead, it transforms arbitrary lookahead
expressions into something finite (an FSM), and if it can't do that, it >fails. Terence Parr got his PhD for figuring out how to do that >transformation... and lived to tell the tale. :)
Anyone interested in the overlap between regular languages and finite
state machines should refer to the excellent ><https://github.com/katef/libfsm>. You can give it an assortment of
regular expressions and it will unify them and construct a DFA to
process them. The README at the top of that page has a simple example,
and there's a tutorial if you want to look further. This library is >perfectly at home processing arbitrary binary file formats and
protocols, not just programming language text files. But only the parts
that are reducible to a FA... Nevertheless there is absolutely nothing
wrong with using this kind of library to write arbitrary FSMs.
I'm currently building a generalised parsing engine that also has the >capability of processing arbitrary binary file and network stream
formats, using a VM approach that interprets something very like a BNF,
but in prefix notation (+a means one-or-more "a"s, not a+). It's tiny, >efficient, embeddable, but can take a protocol description in a very few >bytes of VM code to handle almost any new protocol or format. I don't
think that has been done before, and I've wanted to do it for 25 years.
Clifford Heath.--- Synchronet 3.20a-Linux NewsLink 1.114
On 3/26/2023 11:32 PM, George Neuner wrote:
The hardware machine *is* only in a single ACTUAL state at any given
time (because there is just one set of state variables and that tuple
defines THE state). Until an [a..f] is encountered, it is content
being in that single state.
However, once one is encountered, it has to recognize that it
actually is in one *particular* variant of that state (assuming
that "hex" and "integer" can have different contexts, elsewhere
in the grammar)
UML tools are what you need to consider for more general FA / FSM.
Which brings us full circle to the top of the thread.
I contend that to be expressive enough (i.e., to acts AS
equivalents for) to generate code, such a notation would
be just as complex as writing that code.
And, given that one *must* write code -- but needn't always
reduce a design to an FSM -- you end up developing a second tool
that the developer is reliant upon but with less "practice"
than that of writing code.
In hardware designs, you can directly see the costs of an
implementation: how many FFs to represent the state,
how much combinatorial logic to determine next_state and
outputs, etc. So, optimization (can) results in a savings
of circuitry. And, can speed up the machine by eliminating
a serial "step".
And, in truth, only CS students taking language / compiler courses
ever will learn how to build NDFA and DFA state graphs, convert one
graph form into the other, or how to generate table driven or switch
code from a state graph.
My education is dated in that *all* CS students learned how to design >grammars, build compilers, etc. when I was taught. Now, I suspect
"CS" means "programmer".
What's interesting (being a hardware-software person) is that, despite
the obvious duality, the approaches taken to these technologies is so
disjointed. DFA tend to use a parser-generator of preference while FSMs >>> (in software) have a variety of different implementations with dramatic
design and runtime differences in efficiencies.
Similarly, that hardware FSMs tend to be designed with total disregard
to the possible applicability of parser generators, regex compilers, etc. >>>
Its as if each domain has its own notion of how the technology should
be applied and implemented.
Unfortunately yes. I think very few people ever think about it enough
to recognize that.
Because they likely don't work in both domains.
Think about it; as a hardware person, I see nothing different between:
ready * /buffer_full
and
/(/ready + buffer_full)
I could draw either representation schematically and recognize that
the same gates were involved. I would choose the "expression"
(rendition) that best "fit into" what *followed* that "signal".
For software people, this seems to require a conscious effort
("What are the equivalent ways of expressing this and which
makes most sense to someone reading my code, later?") so you
often see expressions that you have to THINK about instead of
being more intuitively expressed.
Likewise, a hardware person KNOWS that changing multiple
signals "concurrently" can lead to races and hazards.
But, a software person has to be lectured in atomic operators
(because time is serial to him -- ASSUMING he thinks about it!).
Folks taught in (just) one domain often are poor practitioners
in the other.
On Mon, 27 Mar 2023 16:18:51 +1100, Clifford Heath
<no.spam@please.net> wrote:
On 26/03/23 15:45, George Neuner wrote:
On Wed, 22 Mar 2023 18:15:43 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
The terms "FA" (finite automaton) and "FSM" (finite state machine)
are, in fact, synonymous.
What is confusing is that we got to this point through discussion of
parsing and lexing tools - which ARE geared toward languages.
Moreover, yacc and bison do NOT implement a general FA, but rather a
particular variety of FA that useful for language parsing and which
involves an auxiliary stack.
The stack means it's not a FA.
No, it still is an FA ... it just is a specialized form.
Stackless FA, in fact, can process LR(1) grammars ... they just need (typically many) more states in the machine to do so
... and you'll
get parse errors that probably don't really tell you what is wrong with
the input :P.
You can't rely on the tool for error handling (or even just messages)
... you really need to add deliberate error handling.
Lex/Flex on the other hand exists to process only finite
states. The FSM algorithms they use are more efficient than any
algorithm that can handle LALR2, which is why these tools still exist as
independent tools.
They exist separately because they were intended for different tasks
In fact, regex tools existed already for a number of years before
either lex or yacc came about. The difference was most previous tools directly /interpreted/ regex patterns,
whereas lex
compiled multiple patterns into a single recognizer that (effectively)
tried all patterns simultaneously.
ANTLR implements LL(*) which is LL with unbounded lookahead.
There
are other LL(k) tools which require the programmer to choose a fixed
amount of lookahead (and fail to process the grammar if the k value is
too small). ANTLR analyzes the grammar and computes what lookahead is required pattern by pattern.
Anyone interested in the overlap between regular languages and finite
state machines should refer to the excellent
<https://github.com/katef/libfsm>.
I'm currently building a generalised parsing engine that also has the
capability of processing arbitrary binary file and network stream
formats, using a VM approach that interprets something very like a BNF,
but in prefix notation (+a means one-or-more "a"s, not a+). It's tiny,
efficient, embeddable, but can take a protocol description in a very few
bytes of VM code to handle almost any new protocol or format. I don't
think that has been done before, and I've wanted to do it for 25 years.
I would be interested to see that (when it's finished, of course).
Good luck!
UML tools are what you need to consider for more general FA / FSM.
Which brings us full circle to the top of the thread.
I contend that to be expressive enough (i.e., to acts AS
equivalents for) to generate code, such a notation would
be just as complex as writing that code.
And, given that one *must* write code -- but needn't always
reduce a design to an FSM -- you end up developing a second tool
that the developer is reliant upon but with less "practice"
than that of writing code.
Agree and disagree.
YMMV, but a lot of hand written state machines I have seen over the
years included a lot of duplicated condition / transition decision
code that could have been simplified or eliminated by the introdution
of additional explicit states.
Reminded of the proverb: "programmers are great at figuring out what
CAN be in parallel, but not what SHOULD be done in parallel".
A tool can aid in figuring out what states are necessary, given the conditions, to create an optimal (software) machine.
And, in truth, only CS students taking language / compiler courses
ever will learn how to build NDFA and DFA state graphs, convert one
graph form into the other, or how to generate table driven or switch
code from a state graph.
My education is dated in that *all* CS students learned how to design
grammars, build compilers, etc. when I was taught. Now, I suspect
"CS" means "programmer".
No. CS students learn theory. CSE and maybe also IS students learn
about development toolchains.
This dichotemy between theory and practice has existed at least since
the 80's (when I was in college) and probably started even earlier.
Prior to ~ late 90s, explicit CSE degrees didn't exist - there were
just certificate programming courses (if applicable), and the project management aspects had to be learned on the job.
For software people, this seems to require a conscious effort
("What are the equivalent ways of expressing this and which
makes most sense to someone reading my code, later?") so you
often see expressions that you have to THINK about instead of
being more intuitively expressed.
I'm primarily a software person, though I have done simple (mostly
TTL) interface hardware, and some not so simple FPGA programming [but
that I think still counts as "software"]. I have done a lot of
bit-banging and bare hardware programming.
I think the problem really is that too many programmers now do NOT
ever learn assembler. I had learned a few different assembler
languages before I learned C, and I think it helped immensely because
I never had any trouble with pointers or indirections, etc., or
manually managing memory ... the very things that tend to confound C
newbies.
Likewise, a hardware person KNOWS that changing multiple
signals "concurrently" can lead to races and hazards.
But, a software person has to be lectured in atomic operators
(because time is serial to him -- ASSUMING he thinks about it!).
Too much specialization in education.
Concurrency, parallelism and atomic operations tend to be addressed
(not "taught" per se) only in OS classes. Many CS students do not
take OS classes. Atomics and threading are covered in CSE, but only
the practical uses of them and not the theory (or how they evolved
which I think is almost as important).
Folks taught in (just) one domain often are poor practitioners
in the other.
The software industry, in particular, now tends to frown upon
generalists for developer positions, and for management any prior
developer experience no longer much matters.
If you can't demonstrate significant expertise in ___ of the week, in
most places you won't even make it past HR to be interviewed by the
people who can recognize that your prior experience has relevance and
that you could quickly learn whatever is needed to do the job.
On 29/03/23 02:17, George Neuner wrote:
On Mon, 27 Mar 2023 16:18:51 +1100, Clifford Heath
<no.spam@please.net> wrote:
On 26/03/23 15:45, George Neuner wrote:
On Wed, 22 Mar 2023 18:15:43 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
The terms "FA" (finite automaton) and "FSM" (finite state machine)
are, in fact, synonymous.
What is confusing is that we got to this point through discussion of
parsing and lexing tools - which ARE geared toward languages.
Moreover, yacc and bison do NOT implement a general FA, but rather a
particular variety of FA that useful for language parsing and which
involves an auxiliary stack.
The stack means it's not a FA.
No, it still is an FA ... it just is a specialized form.
Ok, it's an FA operating on a stack. The stack makes the whole thing >non-regular, aka infinite, so it's only an FA if you exclude the stack
from the machine.
Stackless FA, in fact, can process LR(1) grammars ... they just need
(typically many) more states in the machine to do so
No. A stack is not finite.
Every FA is finite, that's why they're called
FA. If you want to process a regular language, you can use an FA. If you >want to process an irregular language, you cannot - you need somewhere
to store unbounded staes and an FA *cannot* do that. It's in the
definition of such things!
... and you'll
get parse errors that probably don't really tell you what is wrong with
the input :P.
You can't rely on the tool for error handling (or even just messages)
... you really need to add deliberate error handling.
I wasn't talking about error recovery, just about reporting. Both are
hugely easier in an LL grammar. In the PEG parsers that I favour, you
can almost always just report the rules on the stack at the furthest
point reached, and (in all the grammars I've implemented) that gives a >better error report than anything you'd bother to create manually.
It amuses me that the folk who understand grammar well enough to be able
to produce powerful parser generators seem to be universally incapable
of generating code that can report parse failures in plain language. >Something about their brain's language centres has become so esoteric
that normal language escapes them.
Lex/Flex on the other hand exists to process only finite
states. The FSM algorithms they use are more efficient than any
algorithm that can handle LALR2, which is why these tools still exist as >>> independent tools.
They exist separately because they were intended for different tasks
The articles published at the time I first used them (in 1980) clearly >stated that the two tools were needed "because we don't have a single >algorithm that is equally efficient at both tokenisation and parsing".
Ken Thompson's implementation in the mid 1960s (documented in a 1968
CACM paper) translated the regexp into machine code. The list of
possible states was just a sequence of function call instructions.
The technique of converting multiple NFAs into a single DFA has also
been in use since the early 70s.
ANTLR implements LL(*) which is LL with unbounded lookahead.
It's unbounded, but must be regular. Many languages (including my >Constellation Query Language) require unbounded non-regular look-ahead, >which PEG provides, at some extra cost in memory. But the pathological
cases which *require* memoization only occur rarely, so a global packrat >strategy is sub-optimal.
There
are other LL(k) tools which require the programmer to choose a fixed
amount of lookahead (and fail to process the grammar if the k value is
too small). ANTLR analyzes the grammar and computes what lookahead is
required pattern by pattern.
That's a poor description of how it works. It looks ahead using an FA,
so lookahead must be regular ("Finite State").
Anyone interested in the overlap between regular languages and finite
state machines should refer to the excellent
<https://github.com/katef/libfsm>.
Did you look at the FSM on the main README page of that site?
It shows two RE's being combined into one DFA. Very neat stuff.
I'm currently building a generalised parsing engine that also has the
capability of processing arbitrary binary file and network stream
formats, using a VM approach that interprets something very like a BNF,
but in prefix notation (+a means one-or-more "a"s, not a+). It's tiny,
efficient, embeddable, but can take a protocol description in a very few >>> bytes of VM code to handle almost any new protocol or format. I don't
think that has been done before, and I've wanted to do it for 25 years.
I would be interested to see that (when it's finished, of course).
Good luck!
The putative grammar for Px is here (but this doesn't describe captures >fully):
<https://github.com/cjheath/strpp/blob/main/grammars/px.px>
and the Pegexp engine is here (a template that I'm specialising to add >non-regular aka full LL grammar capability): ><https://github.com/cjheath/strpp/blob/main/include/pegexp.h>
The Px grammar rewritten as a named-map of Pegexp expressions is here: ><https://github.com/cjheath/strpp/blob/main/test/peg_test.cpp#L55-L91>
but I'll use a better structure for a compiled Px grammar, so that names >don't need to be looked up at runtime.
I've almost finished dicking with the structure of input streams that
will make it feasible for this to process data directly arriving on a >socket, and only caching as much as is needed for back-up and retry.
It's also possible to compile with/without UTF-8 support, but I can make >that more convenient. It's possible to specify binary matching even in a >Unicode parser though.
I want captures to do things like turn the ASCII digits on an HTTP >Content-Length header into a binary integer, save that integer as a
capture variable, and use that variable to count bytes in a later >repetition. This will enable a simple grammar describe all of HTTP/2.
By nesting parsers (incrementally feeding capture sections to a nested >parser) it should be possible to for example, run a protocol engine that >generates an HTTP/2 request (generating from an HTTP request grammar), >parses the response chunks, feeds base64-encoded chunks into a
conversion function (not specified in Px), and the output of that
conversion into e.g. a JPEG parser that actually verifies the JPEG
format, and can e.g. extract (as a parse capture) the GPS location from >inside the Exif data attached... and all without having to extend or >recompile the engine. Just load the target grammar, and if it succeeds,
you get the GPS location... and all file formats have been validated.
I envisage a world where the file-system is type-safe; almost no file is
a pure byte-stream, and it's not possible to save a JPEG file that
doesn't match the JPEG syntax. The file system must be pre-loaded with a >grammar for every new file type before writing such a file.
Clifford Heath.
On Mon, 27 Mar 2023 16:18:51 +1100, Clifford Heath
<no.spam@please.net> wrote:
On 26/03/23 15:45, George Neuner wrote:
On Wed, 22 Mar 2023 18:15:43 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
The terms "FA" (finite automaton) and "FSM" (finite state machine)
are, in fact, synonymous.
What is confusing is that we got to this point through discussion of
parsing and lexing tools - which ARE geared toward languages.
Moreover, yacc and bison do NOT implement a general FA, but rather a
particular variety of FA that useful for language parsing and which
involves an auxiliary stack.
The stack means it's not a FA.
No, it still is an FA ... it just is a specialized form.
Clifford Heath.
On Wed, 29 Mar 2023 09:00:34 +1100, Clifford Heath
<no.spam@please.net> wrote:
On 29/03/23 02:17, George Neuner wrote:
On Mon, 27 Mar 2023 16:18:51 +1100, Clifford Heath
<no.spam@please.net> wrote:
On 26/03/23 15:45, George Neuner wrote:
On Wed, 22 Mar 2023 18:15:43 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
The terms "FA" (finite automaton) and "FSM" (finite state machine)
are, in fact, synonymous.
What is confusing is that we got to this point through discussion of >>>>> parsing and lexing tools - which ARE geared toward languages.
Moreover, yacc and bison do NOT implement a general FA, but rather a >>>>> particular variety of FA that useful for language parsing and which
involves an auxiliary stack.
The stack means it's not a FA.
No, it still is an FA ... it just is a specialized form.
Ok, it's an FA operating on a stack. The stack makes the whole thing
non-regular, aka infinite, so it's only an FA if you exclude the stack >>from the machine.
Stackless FA, in fact, can process LR(1) grammars ... they just need
(typically many) more states in the machine to do so
No. A stack is not finite.
Nor is the input stream. So what? The stack is NOT part of the
machine, it is a memory used BY the state machine.
Every FA is finite, that's why they're called
FA. If you want to process a regular language, you can use an FA. If you
want to process an irregular language, you cannot - you need somewhere
to store unbounded staes and an FA *cannot* do that. It's in the
definition of such things!
Nowhere in the definition of finite automaton does it say the
automaton is limited to what can be encoded by its states. In
particular there is no prohibition against using an external memory.
Recall that Turing machines used tapes of infinite length.
In any event, I'm still not following why you think this somehow is important.
... and you'll
get parse errors that probably don't really tell you what is wrong with >>>> the input :P.
You can't rely on the tool for error handling (or even just messages)
... you really need to add deliberate error handling.
I wasn't talking about error recovery, just about reporting. Both are
hugely easier in an LL grammar. In the PEG parsers that I favour, you
can almost always just report the rules on the stack at the furthest
point reached, and (in all the grammars I've implemented) that gives a
better error report than anything you'd bother to create manually.
I wasn't talking about recovery either. When using an LR parser the
grammar designer/implementer has to augment BOTH error reporting and
error handling - which may or may not involve "recovery". See next.
It amuses me that the folk who understand grammar well enough to be able
to produce powerful parser generators seem to be universally incapable
of generating code that can report parse failures in plain language.
Something about their brain's language centres has become so esoteric
that normal language escapes them.
LR works by incrementally assembling a sequence of tokens and looking
for a pattern that matches it.
LL works by selecting a pattern and incrementally looking to match
that pattern with the sequence of tokens beginning at the current
position in the input. Of course the pattern may be an alternation
having multiple possibilities, but the principle of operation remains.
Very, very different.
Neither method innately knows the context when a pattern match fails,
but in LL the context is readily apparent from the driver code which
directs the parse, so it is easy to provide a (somewhat) meaningful
error message just by maintaining a stack of the non-terminals already matched and dumping the last N entries.
In contrast, in LR the context of the current match is given by the
machine state and the stack of unreduced (as-yet unmatched) tokens.
There is nothing readily available that could be used to provide a
user meaningful message ... you'd have to examine the machine state to
figure out even what you /might/ be looking for. Your position in the
input is about as close as you can get to a meaningful message without
the user code manually tracking context.
Lex/Flex on the other hand exists to process only finite
states. The FSM algorithms they use are more efficient than any
algorithm that can handle LALR2, which is why these tools still exist as >>>> independent tools.
They exist separately because they were intended for different tasks
The articles published at the time I first used them (in 1980) clearly
stated that the two tools were needed "because we don't have a single
algorithm that is equally efficient at both tokenisation and parsing".
That was true, but wasn't the reason AT THE TIME they were written.
They were separate first and foremost because they were written at
different times. They never were combined because most machines of
that time did not have enough memory to handle the analysis and
recognizer generation for even moderately complex grammars ... making
the tool larger by including lexing was out of the question.
After a while, it was simply inertia that kept them from being
combined. Everyone was used to the status quo and so even when memory
sizes grew to the point where having a combination tool could be
useful, very few people cared.
Inertia is the reason why a lot of potentially interesting things
never happened. Diversion is the other reason - the people who could
have done it were doing other things.
Ken Thompson's implementation in the mid 1960s (documented in a 1968
CACM paper) translated the regexp into machine code. The list of
possible states was just a sequence of function call instructions.
Yes, but Thompson's method was not widely used - again because of
memory sizes. Most uses of regex used many patterns, and it was more efficient (memory-wise) to simply interpret the pattern directly: one
driver function to handle N patterns.
The technique of converting multiple NFAs into a single DFA has also
been in use since the early 70s.
Yes, and lex is from ~1973, IIRC. It was the first /publically/
available tool able to combine multiple NDFAs into single DFA.
ANTLR implements LL(*) which is LL with unbounded lookahead.
It's unbounded, but must be regular. Many languages (including my
Constellation Query Language) require unbounded non-regular look-ahead,
which PEG provides, at some extra cost in memory. But the pathological
cases which *require* memoization only occur rarely, so a global packrat
strategy is sub-optimal.
There
are other LL(k) tools which require the programmer to choose a fixed
amount of lookahead (and fail to process the grammar if the k value is
too small). ANTLR analyzes the grammar and computes what lookahead is
required pattern by pattern.
That's a poor description of how it works. It looks ahead using an FA,
so lookahead must be regular ("Finite State").
No. Lookahead (and backtracking both) simply requires maintaining a
queue of as-yet unmatched tokens. It certainly could be done by a
state machine, but it does NOT require a state machine.
Anyone interested in the overlap between regular languages and finite
state machines should refer to the excellent
<https://github.com/katef/libfsm>.
Did you look at the FSM on the main README page of that site?
It shows two RE's being combined into one DFA. Very neat stuff.
I haven't examined their method. It may be that they have found some particularly efficient way to do it. That would be great. But
algorithms for merging FAs in graph representation have been around at
least since the 60s.
I'm currently building a generalised parsing engine that also has theI would be interested to see that (when it's finished, of course).
capability of processing arbitrary binary file and network stream
formats, using a VM approach that interprets something very like a BNF, >>>> but in prefix notation (+a means one-or-more "a"s, not a+). It's tiny, >>>> efficient, embeddable, but can take a protocol description in a very few >>>> bytes of VM code to handle almost any new protocol or format. I don't
think that has been done before, and I've wanted to do it for 25 years. >>>
Good luck!
The putative grammar for Px is here (but this doesn't describe captures
fully):
<https://github.com/cjheath/strpp/blob/main/grammars/px.px>
and the Pegexp engine is here (a template that I'm specialising to add
non-regular aka full LL grammar capability):
<https://github.com/cjheath/strpp/blob/main/include/pegexp.h>
The Px grammar rewritten as a named-map of Pegexp expressions is here:
<https://github.com/cjheath/strpp/blob/main/test/peg_test.cpp#L55-L91>
but I'll use a better structure for a compiled Px grammar, so that names
don't need to be looked up at runtime.
I've almost finished dicking with the structure of input streams that
will make it feasible for this to process data directly arriving on a
socket, and only caching as much as is needed for back-up and retry.
It's also possible to compile with/without UTF-8 support, but I can make
that more convenient. It's possible to specify binary matching even in a
Unicode parser though.
I want captures to do things like turn the ASCII digits on an HTTP
Content-Length header into a binary integer, save that integer as a
capture variable, and use that variable to count bytes in a later
repetition. This will enable a simple grammar describe all of HTTP/2.
By nesting parsers (incrementally feeding capture sections to a nested
parser) it should be possible to for example, run a protocol engine that
generates an HTTP/2 request (generating from an HTTP request grammar),
parses the response chunks, feeds base64-encoded chunks into a
conversion function (not specified in Px), and the output of that
conversion into e.g. a JPEG parser that actually verifies the JPEG
format, and can e.g. extract (as a parse capture) the GPS location from
inside the Exif data attached... and all without having to extend or
recompile the engine. Just load the target grammar, and if it succeeds,
you get the GPS location... and all file formats have been validated.
I envisage a world where the file-system is type-safe; almost no file is
a pure byte-stream, and it's not possible to save a JPEG file that
doesn't match the JPEG syntax. The file system must be pre-loaded with a
grammar for every new file type before writing such a file.
Clifford Heath.
George
| Sysop: | DaiTengu |
|---|---|
| Location: | Appleton, WI |
| Users: | 918 |
| Nodes: | 10 (1 / 9) |
| Uptime: | 29:20:04 |
| Calls: | 12,179 |
| Calls today: | 2 |
| Files: | 186,523 |
| Messages: | 2,235,645 |