Hello
Does anyone know of a nice text on finite state machines and their software implementation on embedded systems?
I'm looking for some theoretical background and design methodology. A few examples of "C" implementation would be a nice but not really needed. I'm not looking for a recipe or code but for a more formal explanation on the workings of FSM.
Hello Does anyone know of a nice text on finite state machines and their software implementation on embedded systems?
I'm looking for some theoretical background and design methodology. A few examples of "C" implementation would be a nice but not really needed. I'm
not looking for a recipe or code but for a more formal explanation on the workings of FSM. Thanks jmariano
On 3/9/2023 3:17 PM, jmariano wrote:
Hello Does anyone know of a nice text on finite state machines and their
software implementation on embedded systems?
Implementations can vary widely. Do you want to present (current state, inputs) to a machine and have (next_state, outputs) emitted "immediately"? Or, is the processing time not critical (e.g., UI's tend to be this type)
Do you want to limit the machine to the "classic" design? Or, add extensions (e.g., support the notion of "previous_state", "subroutines", etc.)?
I'm looking for some theoretical background and design methodology. A few
examples of "C" implementation would be a nice but not really needed. I'm
not looking for a recipe or code but for a more formal explanation on the
workings of FSM. Thanks jmariano
In the degenerate case, you build a matrix that is accessed by [state][inputs]
and delivers (next_state, outputs). But, it's obvious that the size of
this structure grows quickly with number of states and inputs. In
practice,
often a state may have only a few significant inputs that govern the choice of next state so the matrix contains lots of redundant entries.
You can unfold the matrix into a series of switch/case statements -- but, I've found that makes it hard to sort out what's really happening (the
beauty of a state machine is that it is concise).
I prefer representations like:
Case IDLE
On <digit> GoTo ACCEPTING Executing GobbleDigit()
On <clear> GoTo ISSUE_PROMPT Executing ClearValue()
On <enter> GoTo TEST_VALUE Executing CheckLimits()
..
Note that there are only 3 items encoded on each line:
- the input being examined
- the name of the intended next_state
- the action to be performed *in* the transition
As such, this can be encoded in as few as 3 bytes (depending on how
many states, inputs, and actions you need to support)
But, the big advantage is it's concise -- no extra syntactic sugar
to clutter up the page (cuz you want to express the machine in
as little space as possible as it gets harder to chase layers of
case/switch statements with interspersed *actions*)
[There are also UML techniques for their representation and tools that will parse such descriptions and build the code for you]
In school, Hill & Peterson was our reference (_Intro to Switching Theory
and
Logical Design_) but you don't need much "text" to understand the concepts (assuming you already understand logic).
OTOH, it's worth learning about minimization techniques -- esp if your approach to the machine's design is /ad hoc/ (ripe for hidden
optimizations).
Hello
Does anyone know of a nice text on finite state machines and their software implementation on embedded systems?
I'm looking for some theoretical background and design methodology. A few examples of "C" implementation would be a nice but not really needed. I'm not looking for a recipe or code but for a more formal explanation on the workings of FSM.
Thanks
jmariano
I went to a course of lectures on (and by) Harel state-charts.
Here is one for text: https://github.com/cepsdev/machines4ceps
There is also https://www.codeproject.com/Articles/11398/A-Lightweight-Implementation-of-UML-Statecharts-in
Hierarchical state-machines are a very interesting argument for a system that can be modeled as an event-driven system. An embedded systems can be usually described as an event-driver system.
There will be a time when the programmer would simply draw one or more state-machines and click a button to generate the full working code in whatever
language.
There will be a time when the programmer would simply draw one or more >state-machines and click a button to generate the full working code in >whatever language.
On Fri, 10 Mar 2023 09:54:23 +0100, pozz <pozz...@gmail.com> wrote:
There will be a time when the programmer would simply draw one or more >state-machines and click a button to generate the full working code in >whatever language.When I went to school, 30 or so years ago, we did have such a program.
I am not able to remember its name, though.
On Fri, 10 Mar 2023 09:54:23 +0100, pozz <pozzugno@gmail.com> wrote:
There will be a time when the programmer would simply draw one or more
state-machines and click a button to generate the full working code in
whatever language.
When I went to school, 30 or so years ago, we did have such a program.
I am not able to remember its name, though.
The problem with all of these approaches is they add another "tool" to
the development process -- and another opportunity for the developer
(who only uses the tool for a *portion* of a project) to make mistakes
in its application. The more capable and expressive the tool, the
more knowledge is required of the developer to exploit its capabilities.
[E.g., if you had to construct an arbitrary regex, could you do so
with the knowledge you have committed to memory? Would a reference
answer all of the questions you *might* have about your particular
pattern?]
On 3/10/2023 4:48 AM, Robert Roland wrote:
On Fri, 10 Mar 2023 09:54:23 +0100, pozz <pozz...@gmail.com> wrote:
There will be a time when the programmer would simply draw one or more
state-machines and click a button to generate the full working code in
whatever language.
When I went to school, 30 or so years ago, we did have such a program.You can use regex "compilers" to deal with DFAs.
I am not able to remember its name, though.
The problem with all of these approaches is they add another "tool" to
the development process -- and another opportunity for the developer
(who only uses the tool for a *portion* of a project) to make mistakes
in its application. The more capable and expressive the tool, the
more knowledge is required of the developer to exploit its capabilities.
[E.g., if you had to construct an arbitrary regex, could you do so
with the knowledge you have committed to memory? Would a reference
answer all of the questions you *might* have about your particular
pattern?]
Instead (IMO), you want something that lets a developer use a technology without reliance on a particular tool (that may not be well-supported
or may have latent bugs that haven't yet been tickled).
As such, understanding the technique is more important than finding a tool that may )or may not) address your needs. ("I want to write in Eiffel.
Does your tool output Eiffel source?" Next week it may be some other
/langue du jour/)
The problem with all of these approaches is they add another "tool" to
the development process -- and another opportunity for the developer
(who only uses the tool for a *portion* of a project) to make mistakes
in its application. The more capable and expressive the tool, the
more knowledge is required of the developer to exploit its capabilities.
While you're last statement is true, I do not think it is a valid argument against
adding another tool to the development process. In a work (not hobby) environment, I expect good management and teams to make considered
choices about what tools to apply. If a tool is feature rich and well documented,
then the knowledge should be available (either in you head or in the manual) to make the job easier.
[E.g., if you had to construct an arbitrary regex, could you do so
with the knowledge you have committed to memory? Would a reference
answer all of the questions you *might* have about your particular
pattern?]
Yes.
When I have done a lot of regex work I kept a quick reference card handy.
Instead (IMO), you want something that lets a developer use a technology
without reliance on a particular tool (that may not be well-supported
or may have latent bugs that haven't yet been tickled).
Being tool agnostic is an ideal goal. In a practice, you must pick some specific tools to get the work done within schedule, budget, and quality constraints.
If you want portability of design then that should be an explicit fourth constraint.
Most projects select tools with the additional LONG TERM constraint of support throughout the life of the product or product line.
As such, understanding the technique is more important than finding a tool >> that may )or may not) address your needs. ("I want to write in Eiffel.
Does your tool output Eiffel source?" Next week it may be some other
/langue du jour/)
Exactly why an abstracting tool that is more focused on the design is better than
a specific tool.
State machine design tools are a good example. With a graphic design tool,
it is much easier to spot missing states or incorrect transitions. It can be clear enough that even end users can understand and point out flaws or enhancements. I don't think the particular output language is the point here.
BTW, lots of your earlier comments match closely to what I would have posted. This one just struck me are being a little too idealistic.
My first contact with FSM was many years ago when I was finishing my PhD. I had to implement a FSM on a FPGA and, of course, I was late, so I pick an example somewhere and just implemented, without really knowing what I was doing....
Now I would like to finally understand a little better how these things
work.
Also, the sort of things that I build, usually have some type of
"controller" in it, and usually talk to a PC via serial interface. This, it seems to me, could to be well modeled by a FSM. I understand that this representation might bring additional issues, as it was mentioned by Don Y, but my main goal here is to go one step further from the clumsy programming that I've been doing for the past few years into a bit more formal representation of the problems.
I also have some questions about synchronization of several FSM, but this is a subject for a feature post.
Because we all KNOW that we have more than adequate time to
devote to "doing it right", right? :>
[This is why I push the "idealistic" because in practice is far from it]
Hello again!electronics courses in college. I took courses on embedded systems, usually called "microprocessor in physics" and the like, but the emphasis of these courses tended to be on the digital part and not so much on the computational aspects of the thing.
Thank you all very much for your valuable inputs! I have A LOT of reading to do!
I'm not a professional developer, like most of you (I guess). I'm just a "gizmo" builder, serving mainly my own research and my colleagues. I don't have access to professional development tools. My background is in physics, although I took a few
My first contact with FSM was many years ago when I was finishing my PhD. I had to implement a FSM on a FPGA and, of course, I was late, so I pick an example somewhere and just implemented, without really knowing what I was doing....issues, as it was mentioned by Don Y, but my main goal here is to go one step further from the clumsy programming that I've been doing for the past few years into a bit more formal representation of the problems.
Now I would like to finally understand a little better how these things work.
Also, the sort of things that I build, usually have some type of "controller" in it, and usually talk to a PC via serial interface. This, it seems to me, could to be well modeled by a FSM. I understand that this representation might bring additional
I also have some questions about synchronization of several FSM, but this is a subject for a feature post.
Hello again!electronics courses in college. I took courses on embedded systems, usually called "microprocessor in physics" and the like, but the emphasis of these courses tended to be on the digital part and not so much on the computational aspects of the thing.
Thank you all very much for your valuable inputs! I have A LOT of reading to do!
I'm not a professional developer, like most of you (I guess). I'm just a "gizmo" builder, serving mainly my own research and my colleagues. I don't have access to professional development tools. My background is in physics, although I took a few
My first contact with FSM was many years ago when I was finishing my PhD. I had to implement a FSM on a FPGA and, of course, I was late, so I pick an example somewhere and just implemented, without really knowing what I was doing....issues, as it was mentioned by Don Y, but my main goal here is to go one step further from the clumsy programming that I've been doing for the past few years into a bit more formal representation of the problems.
Now I would like to finally understand a little better how these things work.
Also, the sort of things that I build, usually have some type of "controller" in it, and usually talk to a PC via serial interface. This, it seems to me, could to be well modeled by a FSM. I understand that this representation might bring additional
I also have some questions about synchronization of several FSM, but this is a subject for a feature post.
Cheers,
jmariano
On 3/10/2023 11:10 AM, Ed Prochak wrote:To your 1st sentence: AMEN. We don't really disagree here.
The problem with all of these approaches is they add another "tool" to
the development process -- and another opportunity for the developer
(who only uses the tool for a *portion* of a project) to make mistakes
in its application. The more capable and expressive the tool, the
more knowledge is required of the developer to exploit its capabilities.
While you're last statement is true, I do not think it is a valid argument againstYou have to decide if the effort to learn (and remain "current")
adding another tool to the development process. In a work (not hobby) environment, I expect good management and teams to make considered
choices about what tools to apply. If a tool is feature rich and well documented,
then the knowledge should be available (either in you head or in the manual)
to make the job easier.
the tool offsets the advantages gained by using it. I see lots
of developers who "almost" know how to use something. IMO, this
is worse than *not* knowing hot to use it (or, not *having* the
tool) because it breeds a false sense of confidence in their
efforts.
[E.g., if you had to construct an arbitrary regex, could you do so
with the knowledge you have committed to memory? Would a reference
answer all of the questions you *might* have about your particular
pattern?]
Yes.The qualifier on that last statement is the issue. What about
When I have done a lot of regex work I kept a quick reference card handy.
when you HAVEN'T done work with a tool for some period of time?
Will you admit to yourself that you likely need a "refresher"?
Or, will you stumble along and *hope* it "comes back to you"?
Error-free?
E.g., are multidimensional arrays stored in row or column major order?
There are too many "little details" like this that only stay fresh
in your mind with "frequent refreshing".
[I write a lot of formal documentation. Yet, I'll be damned if I can remember the shortcut for "non-breaking hyphenation" -- despite using
it dozens of times on any given document! (tomorrow, I'll look it up, again!)]
Instead (IMO), you want something that lets a developer use a technology >> without reliance on a particular tool (that may not be well-supported
or may have latent bugs that haven't yet been tickled).
Being tool agnostic is an ideal goal. In a practice, you must pick some specific tools to get the work done within schedule, budget, and quality constraints.
If you want portability of design then that should be an explicit fourth constraint.I've made a lot of money addressing the needs of clients who banked on
Most projects select tools with the additional LONG TERM constraint of support throughout the life of the product or product line.
a set of tools, only to discover that they were "no longer supported"
(e.g., doesn't run unde new version of OS, requires hardware that PCs no longer include, etc.)
You don't realize this is a legitimate design issue until you get
bitten by it. And, at that time, the time and $$$ available are
seldom what you'd need.
As such, understanding the technique is more important than finding a tool
that may )or may not) address your needs. ("I want to write in Eiffel.
Does your tool output Eiffel source?" Next week it may be some other
/langue du jour/)
Exactly why an abstracting tool that is more focused on the design is better thanWhat better than a human brain?
a specific tool.
State machine design tools are a good example. With a graphic design tool, it is much easier to spot missing states or incorrect transitions. It can beBut you can use a pencil and paper (or drawing program) to make
clear enough that even end users can understand and point out flaws or enhancements. I don't think the particular output language is the point here.
such a diagram and "see" the same missing states/incorrect transitions.
The tool just automates binding the design to a particular implementaion.
BTW, lots of your earlier comments match closely to what I would have posted.
This one just struck me are being a little too idealistic.
Have you looked at Harel charts? For *complex*/layered machines?
I suspect revisiting one that you managed to *coax* together at
the start of a project a year or two later (maintenance) would
leave you wondering what all of the cryptic notation means.
Would you admit ignorance and "play it safe" -- and expect to have
time to refamiliarize yourself with it BEFORE trying to make
changes? Or, would you proceed with a false set of confidence
and *hope* you don't break anything along the way?
Because we all KNOW that we have more than adequate time to
devote to "doing it right", right? :>
[This is why I push the "idealistic" because in practice is far from it]
Does anyone know of a nice text on finite state machines and their
software implementation on embedded systems?
I'm looking for some theoretical background and design methodology. A
few examples of "C" implementation would be a nice but not really
needed. I'm not looking for a recipe or code but for a more formal >explanation on the workings of FSM.
Thanks
jmariano
We think a lot alike because we've both have done this a long time.
when you HAVEN'T done work with a tool for some period of time?[E.g., if you had to construct an arbitrary regex, could you do so
with the knowledge you have committed to memory? Would a reference
answer all of the questions you *might* have about your particular
pattern?]
Yes.
When I have done a lot of regex work I kept a quick reference card handy. >> The qualifier on that last statement is the issue. What about
Will you admit to yourself that you likely need a "refresher"?
Or, will you stumble along and *hope* it "comes back to you"?
Error-free?
Personally, Yes, I admit to my own limitations.
E.g., are multidimensional arrays stored in row or column major order?
There are too many "little details" like this that only stay fresh
in your mind with "frequent refreshing".
True, but that is a different issue that the selection of the tool in the first place.
I've made a lot of money addressing the needs of clients who banked onInstead (IMO), you want something that lets a developer use a technology >>>> without reliance on a particular tool (that may not be well-supported
or may have latent bugs that haven't yet been tickled).
Being tool agnostic is an ideal goal. In a practice, you must pick some
specific tools to get the work done within schedule, budget, and quality constraints.
If you want portability of design then that should be an explicit fourth constraint.
Most projects select tools with the additional LONG TERM constraint of
support throughout the life of the product or product line.
a set of tools, only to discover that they were "no longer supported"
(e.g., doesn't run unde new version of OS, requires hardware that PCs no
longer include, etc.)
Yes a lot of projects don't follow due diligence. Hence my phrase
earlier about "good management and teams" was used deliberately.
What better than a human brain?As such, understanding the technique is more important than finding a tool >>>> that may )or may not) address your needs. ("I want to write in Eiffel. >>>> Does your tool output Eiffel source?" Next week it may be some other
/langue du jour/)
Exactly why an abstracting tool that is more focused on the design is better than
a specific tool.
I was focusing on documenting the design. I've tried to leave projects
with enough clear design so that I can be replaced.
The tool just automates binding the design to a particular implementaion.
Ideally it should do both, act as a design recording medium and
output the implementation.
BTW, lots of your earlier comments match closely to what I would have posted.
This one just struck me are being a little too idealistic.
Have you looked at Harel charts? For *complex*/layered machines?
I suspect revisiting one that you managed to *coax* together at
the start of a project a year or two later (maintenance) would
leave you wondering what all of the cryptic notation means.
Haven't used Harel charts. That's part of UML and no place that
I worked at has needed a tool set that complex. KISS
Taking a quick look, [again!] I can see why it may not be a good choice.
Would you admit ignorance and "play it safe" -- and expect to have
time to refamiliarize yourself with it BEFORE trying to make
changes? Or, would you proceed with a false set of confidence
and *hope* you don't break anything along the way?
If it is the design, then it better be clear enough to just read through
and be understandable and complete.
If it is the implementation, then I never assume I am familiar with
the code (even it I wrote it).
If you think about *applications*, in detail, you quickly discover that there are lots of states that need to be visible -- IF YOU WANT TO MODEL THE ENTIRE APPLICATION as a FSM).
Instead, use state diagrams to explain portions of the design in
more intuitive/visual ways -- without requiring them to be "complete
enough" to generate code (via some other tool). Let the developer look elsewhere for more detail -- expressed in a medium that is better
suited to THAT task.
On Friday, March 10, 2023 at 6:48:13 AM UTC-5, Robert Roland wrote:processor drawing package. Typically, FSM can be decomposed into multiple distinct FSM that are easier to understand, and typically relate to the problem better.
On Fri, 10 Mar 2023 09:54:23 +0100, pozz <pozz...@gmail.com> wrote:
There will be a time when the programmer would simply draw one or moreWhen I went to school, 30 or so years ago, we did have such a program.
state-machines and click a button to generate the full working code in
whatever language.
I am not able to remember its name, though.
The problem these have, like many graphic oriented approaches, is continuing support and version control of the source. I've never worked with a state machine that was so complex it required anything other than a diagram drawn up in your favorite word
A FSM with 10 states is easy to code. A FSM with 100 states is probably several FSMs, mistakenly combined into one.
Now imagine a tool that takes as input the diagram
and spits out a fsm.c
For example, a simple calculator can be modeled as a FSM: the
transitions are keystrokes. However it isn't a simple FSM...
I think the complexity of a FSM is not only related to the number if states, but also to the transitions/inputs.
It's much simpler to detect errors on a diagram instead on a cryptic list of switch/case instructions.
The great advantage of a diagram is that it can be
read by non-developers: customers, sales man, project managers and so on.
UML diagrams are there exactly for these reasons.
Now imagine a tool that takes as input the diagram and spits out a fsm.c without errors.
I know most of FSMs are simple, but most of the time you refuse to solve a problem with a FSM just because it could be too complex to convert in code. However, if you had this type of tool, you would consider FSMs for much more problems.
For example, a simple calculator can be modeled as a FSM: the transitions are keystrokes. However it isn't a simple FSM, because there are many subtle details that must be addressed. It is somewhat simple to make a diagram and solve some problems with arcs, arrows and rectangles, but it's much more complex to make the same things on a C code.
My first contact with FSM was many years ago when I was finishing my PhD. I had to implement a FSM on a FPGA and, of course, I was late, so I pick an example somewhere and just implemented, without really knowing what I was doing....issues, as it was mentioned by Don Y, but my main goal here is to go one step further from the clumsy programming that I've been doing for the past few years into a bit more formal representation of the problems.
Now I would like to finally understand a little better how these things work.
Also, the sort of things that I build, usually have some type of "controller" in it, and usually talk to a PC via serial interface. This, it seems to me, could to be well modeled by a FSM. I understand that this representation might bring additional
I learned state machines using the PLD compiler "CUPL" on
a VAX11/750. That had a nice syntax for Mealy and Moore
state machines and once I had understood that, I could also
do it in PALASM or VHDL.
Another useful tool is yacc from Unix or bison on Linux.
It reads a grammar and builds a state machine from it.
The state machine is later a blob of C. It reads a series of
symbols from its input much like your serial device and hopps
through the state machine if the string of symbols is legal
given the grammar. If a legal grammar rule is recognized,
you can trigger the execution of some C code.
Grammar:
expression = number: { $$ = $1; )
| expression = sym_variable: { $$ = $1; )
| expression = Number '+' number : { $$ = $1 + $3; }
| expression = epression '*' expression: { $$ = $1 * $3; }
| expression = epression '/' expression: { $$ = $1 / $3; }
| expression = '(' expression and so on
assignment = sym_variable ":=" expression: { $$ = $3; )
My syntax is wrong, but you get the principle. The stuff
in curly braces is the executed C code when a rule is
discovered, the $$ thingies are replaced by the relevant variables. Yacc tries
to find the most general rules possible.
That makes sure that y = a + b + c * sin(333); is recognized.
Usually you will insert a lexical scanner in the input, like
lex, so that the state machine does not grow beyond a reasonable
size. That would filter out things like "begin", "end",
"integer", ":=" and so on. lex() would return integer constants
like SY_BEGIN, VARIABLE_NAME, '(' and so on.
Yacc stands for "Yet Another Compiler Compiler", but it's
original job was to create Weinberger arrays, a LSI structure
not unlike a PAL.
Cheers,
Gerhard
lex/yacc are more applicable to parsing strings of characters
as you'd encounter in a (programming) language.
AFAICT, none of these tools knows how to optimize states by
noting equivalences (?) [George would know for sure]
OTOH, when dealing with hardware machines, it's a common step
to reduce via implication tables, etc.
On Mon, 13 Mar 2023 15:41:32 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
lex/yacc are more applicable to parsing strings of characters
as you'd encounter in a (programming) language.
AFAICT, none of these tools knows how to optimize states by
noting equivalences (?) [George would know for sure]
OTOH, when dealing with hardware machines, it's a common step
to reduce via implication tables, etc.
yacc and bison will remove unreachable PDA states. Unreachable states
in the parser typically are not deliberate but rather result from
ambiguities in the grammar. lex, being LALR(1), does not tolerate
much ambiguity - however bison can generate more powerful LR(1) and
GLR(1) parsers, and these are far more likely to have unreachable
states accidentally generated.
Similarly, lex will remove unreachable DFA states. Again, these
typically are not deliberate, but rather result from lex combining the various input regex into a single DFA having multiple entry points and multiple accepting states.
Then there is flex.
flex has some DFA optimizations available. First, flex can compress
the data tables which encode its DFA states. Second, flex can
discover "equivalence" classes: groups of characters which result in
the same action. And finally, flex can [sometimes] discover "meta-equivalence" classes: commonly expected sequences of characters
and/or other equivalence classes.
All of these can result in a smaller and/or more efficient recognizer
than is possible with lex.
yacc and lex are ancient and haven't been maintained for decades. They
have limitations that will never be addressed, and bugs that will
never be fixed. If you really need backward compatibility with them,
it is available using bison and flex ... and if you don't need bacward compatibility, bison and flex are much more powerful and modern tools
for use with new projects.
[There are other modern alternatives to yacc and lex also, but
discussion of them is beyond the scope of this missive.]
Now imagine a tool that takes as input the diagram
and spits out a fsm.c
Indeed. Please check out the freeware QM modeling tool:
- https://www.state-machine.com/qm
Automatic Code Generation video:
- https://youtu.be/FHV5vZyECOA
QM is an example of a modern, *lightweight* modeling tool. Older, "high-ceremony" tools have been available since the '90, but they couldn't pull their own weight and didn't catch on. However, things changed since the '90s...
For example, a simple calculator can be modeled as a FSM: the
transitions are keystrokes. However it isn't a simple FSM...
Interesting that you mention the calculator problem. (I've used it in my "Practical Statecharts" book published back in 2022.) I've also used it in my recent video "State machines as "spaghetti" reducers:
- https://youtu.be/fLXxNe4YeJ4
It turns out that even the "simple" 4-operation calculator is complex enough to be almost impossible to get right with traditional "improvised" state management. A state machine, on the other hand, is quite manageable.
On 3/13/2023 8:35 AM, pozz wrote:
I think the complexity of a FSM is not only related to the number if
states, but also to the transitions/inputs.
Of course. A 0..99 counter can have oodles of states... but the interactions
between them are trivial to the point of being boring.
Interconnectedness is the source of *all* complexity. E.g., the more modules your code interacts with, the more complex the code is likely to
be!
It's much simpler to detect errors on a diagram instead on a cryptic
list of switch/case instructions.
That depends on the problem and how expressive (and intuitive!) the
drawing.
The great advantage of a diagram is that it can be read by
non-developers: customers, sales man, project managers and so on.
See above.
UML diagrams are there exactly for these reasons.
Now imagine a tool that takes as input the diagram and spits out a
fsm.c without errors.
For what *classes* of state machines?
I know most of FSMs are simple, but most of the time you refuse to
solve a problem with a FSM just because it could be too complex to
convert in code. However, if you had this type of tool, you would
consider FSMs for much more problems.
You're already building an FSM when you solve such a problem. Th eissue is HOW you build it. If /ad hoc/ then it's more likely to contain errors
and be harder for folks to understand -- without digging deep.
For example, a simple calculator can be modeled as a FSM: the
transitions are keystrokes. However it isn't a simple FSM, because
there are many subtle details that must be addressed. It is somewhat
simple to make a diagram and solve some problems with arcs, arrows and
rectangles, but it's much more complex to make the same things on a C
code.
A calculator is a toy example.
Imagine, instead, if that calculator (keys + display) also had to
indicate when a key was *stuck*, when the batteries were low
(without a dedicated "low battery" indicator), the current time
of day (and date), implement an "egg timer" functionality as well
as a traditional "alarm", etc.
A calculator is *just* a calculator. Few embedded systems have such
limited -- and "regular" -- functionality.
Imagine being in the middle of a calculation and the display is
commandeered by the alarm function signalling the programmed time
has been reached. The value you had been typing is overwritten
AND your next keystroke is expected (but not guaranteed) to be
an interaction with the "alarm clock" -- acknowledge the alarm,
request an additional 10 minutes, leave it active (but not
monopolizing the display) for later attention, etc.
This condition can persist indefinitely (unless the design
times it out). So, what happens when the battery fails
some time later? Does that message overlay the alarm
message? How do you interact with THAT? And, when you've
"cleared" it, does the alarm display reappear? Do you
even *remember* the calculation that you were making when
this started?
[And let's not get into the possibilities for races because
you hadn't considered how one "process/interaction" could be interrupted/preempted by another!]
Il 13/03/2023 17:29, Don Y ha scritto:
On 3/13/2023 8:35 AM, pozz wrote:
I think the complexity of a FSM is not only related to the number if states,
but also to the transitions/inputs.
Of course. A 0..99 counter can have oodles of states... but the interactions
between them are trivial to the point of being boring.
Interconnectedness is the source of *all* complexity. E.g., the more
modules your code interacts with, the more complex the code is likely to be! >>
It's much simpler to detect errors on a diagram instead on a cryptic list of
switch/case instructions.
That depends on the problem and how expressive (and intuitive!) the
drawing.
A good diagram is always much more expressive than a good code, for developers
and for non-developers.
The great advantage of a diagram is that it can be read by non-developers: >>> customers, sales man, project managers and so on.
See above.
UML diagrams are there exactly for these reasons.
Now imagine a tool that takes as input the diagram and spits out a fsm.c >>> without errors.
For what *classes* of state machines?
Hierarchical state-machines (UML state-machines) are fully qualified monsters.
I know most of FSMs are simple, but most of the time you refuse to solve a >>> problem with a FSM just because it could be too complex to convert in code. >>> However, if you had this type of tool, you would consider FSMs for much more
problems.
You're already building an FSM when you solve such a problem. Th eissue is >> HOW you build it. If /ad hoc/ then it's more likely to contain errors
and be harder for folks to understand -- without digging deep.
This is the reason why a fsm generation tool could help. You don't need to build with /ad hoc/ approach.
For example, a simple calculator can be modeled as a FSM: the transitions >>> are keystrokes. However it isn't a simple FSM, because there are many subtle
details that must be addressed. It is somewhat simple to make a diagram and >>> solve some problems with arcs, arrows and rectangles, but it's much more >>> complex to make the same things on a C code.
A calculator is a toy example.
Imagine, instead, if that calculator (keys + display) also had to
indicate when a key was *stuck*, when the batteries were low
(without a dedicated "low battery" indicator), the current time
of day (and date), implement an "egg timer" functionality as well
as a traditional "alarm", etc.
A calculator is *just* a calculator. Few embedded systems have such
limited -- and "regular" -- functionality.
Imagine being in the middle of a calculation and the display is
commandeered by the alarm function signalling the programmed time
has been reached. The value you had been typing is overwritten
AND your next keystroke is expected (but not guaranteed) to be
an interaction with the "alarm clock" -- acknowledge the alarm,
request an additional 10 minutes, leave it active (but not
monopolizing the display) for later attention, etc.
This condition can persist indefinitely (unless the design
times it out). So, what happens when the battery fails
some time later? Does that message overlay the alarm
message? How do you interact with THAT? And, when you've
"cleared" it, does the alarm display reappear? Do you
even *remember* the calculation that you were making when
this started?
[And let's not get into the possibilities for races because
you hadn't considered how one "process/interaction" could be
interrupted/preempted by another!]
I didn't get your point of these all. There are simple applications and complex
applications, I don't think you need to convince me.
Anyway even a simple application such as a standard calculator can be complex enough to be implemented as a flat state-machine without any tool.
However the complexity can be managed and reduced on a diagram of a UML/hierarchical state-machine. After that, click on a build button and you error-free code is done.
Il 13/03/2023 17:29, Don Y ha scritto:
On 3/13/2023 8:35 AM, pozz wrote:
I think the complexity of a FSM is not only related to the number if
states, but also to the transitions/inputs.
Of course. A 0..99 counter can have oodles of states... but the
interactions
between them are trivial to the point of being boring.
Interconnectedness is the source of *all* complexity. E.g., the more
modules your code interacts with, the more complex the code is likely
to be!
It's much simpler to detect errors on a diagram instead on a cryptic
list of switch/case instructions.
That depends on the problem and how expressive (and intuitive!) the
drawing.
A good diagram is always much more expressive than a good code, for developers and for non-developers.
On 3/13/2023 8:07 PM, George Neuner wrote:
On Mon, 13 Mar 2023 15:41:32 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
lex/yacc are more applicable to parsing strings of characters
as you'd encounter in a (programming) language.
AFAICT, none of these tools knows how to optimize states by
noting equivalences (?) [George would know for sure]
OTOH, when dealing with hardware machines, it's a common step
to reduce via implication tables, etc.
yacc and bison will remove unreachable PDA states. Unreachable states
in the parser typically are not deliberate but rather result from
ambiguities in the grammar. lex, being LALR(1), does not tolerate
much ambiguity - however bison can generate more powerful LR(1) and
GLR(1) parsers, and these are far more likely to have unreachable
states accidentally generated.
Similarly, lex will remove unreachable DFA states. Again, these
typically are not deliberate, but rather result from lex combining the
various input regex into a single DFA having multiple entry points and
multiple accepting states.
But, the FSM parallel would be an "orphan" state that would (*likely*)
be readily apparent in a state diagram. "You can't get there from here".
In hardware designs, it is not uncommon to have multiple equivalent
states that aren't easily recognized as such (because you tend to
ignore "don't cares" -- which are ripe for collapsing equivalents).
Then there is flex.
flex has some DFA optimizations available. First, flex can compress
the data tables which encode its DFA states. Second, flex can
discover "equivalence" classes: groups of characters which result in
the same action. And finally, flex can [sometimes] discover
"meta-equivalence" classes: commonly expected sequences of characters
and/or other equivalence classes.
But, those are mapping equivalent *inputs* together, not equivalent
*states*. I.e., treating "BEGIN" and "begin" as equivalent.
Would it recognize a common sequence of state transitions
that occurs in two different places in the grammar? E.g.,
specifying the syntax for a numeric quantity in two different
places only to realize that it's actually the same part of
the grammar expressed as two different instances?
<number> ::= <digit><digits>
<value> ::= <digit><digits>
<expr> ::= <number> <op> <number> | <value> <op> <value>
(silly example; but the inputs in each case are the same)
yacc and lex are ancient and haven't been maintained for decades. They
have limitations that will never be addressed, and bugs that will
never be fixed. If you really need backward compatibility with them,
it is available using bison and flex ... and if you don't need bacward
compatibility, bison and flex are much more powerful and modern tools
for use with new projects.
[There are other modern alternatives to yacc and lex also, but
discussion of them is beyond the scope of this missive.]
Now, to the question at hand (or, a version thereof).
It's relatively common to design an algorithm or a hardware machine
as a "state transition diagram" and then reduce to an implementation.
(The question, posed here, is how much this can be automated and
the benefits that might acrue).
On Mon, 13 Mar 2023 22:59:25 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
On 3/13/2023 8:07 PM, George Neuner wrote:
On Mon, 13 Mar 2023 15:41:32 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
lex/yacc are more applicable to parsing strings of characters
as you'd encounter in a (programming) language.
AFAICT, none of these tools knows how to optimize states by
noting equivalences (?) [George would know for sure]
OTOH, when dealing with hardware machines, it's a common step
to reduce via implication tables, etc.
yacc and bison will remove unreachable PDA states. Unreachable states
in the parser typically are not deliberate but rather result from
ambiguities in the grammar. lex, being LALR(1), does not tolerate
much ambiguity - however bison can generate more powerful LR(1) and
GLR(1) parsers, and these are far more likely to have unreachable
states accidentally generated.
Similarly, lex will remove unreachable DFA states. Again, these
typically are not deliberate, but rather result from lex combining the
various input regex into a single DFA having multiple entry points and
multiple accepting states.
But, the FSM parallel would be an "orphan" state that would (*likely*)
be readily apparent in a state diagram. "You can't get there from here".
In hardware designs, it is not uncommon to have multiple equivalent
states that aren't easily recognized as such (because you tend to
ignore "don't cares" -- which are ripe for collapsing equivalents).
When you merge two FSM you often get redundant "don't care" nodes, but
you also can get nodes which either are impossible to enter [dead
code], or impossible to leave [halt], because there are no legal
transitions that will permit it. Joining FSM involves identifying and
pruning both types of nodes.
Then there is flex.
flex has some DFA optimizations available. First, flex can compress
the data tables which encode its DFA states. Second, flex can
discover "equivalence" classes: groups of characters which result in
the same action. And finally, flex can [sometimes] discover
"meta-equivalence" classes: commonly expected sequences of characters
and/or other equivalence classes.
But, those are mapping equivalent *inputs* together, not equivalent
*states*. I.e., treating "BEGIN" and "begin" as equivalent.
No. Consider the case of just recognizing a decimal digit: compare
the graph using the alternation: (0|1|2|3|4|5|6|7|8|9), vs the graph
using the class [:digit:].
Using the OR alternation, including start you have 11 nodes. Start has
10 transitions exiting, and each digit node has a single transition
entering.
Using the digit class, you have 2 nodes, with 10 transitions that all
get you from start to the digit class node.
Obviously this is simplistic, because the members of the character
class form a subgraph which itself has to be recognized. The
important point here is that the subgraph as a whole can represent a
/single/ node in a much more complex graph - its constituent
characters need not be repeated in the complex graph. More on this
below.
A complex DFA that combines many different regex may present other opportunities to recognize given (possibly arbitrary) sets of
characters - opportunites that may not be apparent from looking at the constituent regex.
Would it recognize a common sequence of state transitions
that occurs in two different places in the grammar? E.g.,
specifying the syntax for a numeric quantity in two different
places only to realize that it's actually the same part of
the grammar expressed as two different instances?
When given the option to find equivalence classes, flex can identify
sets of characters that are used repeatedly. Those characters are
gathered into an "equivalence" that then can be a node in the DFA
instead of redundantly repeating individual characters.
Remember DFA are deterministic - a node can't take different actions depending on which of multiple transitions entered (or left) it ... so
if you want the same character to be recognized in a different context (leading to a different action), you must repeat it in a different
node.
This is where being able to identify, essentially arbitrary, sets of character and coalesce them into a recognizer "class" is useful. If a
given set of N(>1) characters is used M times in the graph, then by coalescing them you remove M(N-1) nodes from your graph. The number
of /transitions/ in the graph remains the same, but recall that it is
the /nodes/ that consume space in the lexer tables.
<number> ::= <digit><digits>
<value> ::= <digit><digits>
<expr> ::= <number> <op> <number> | <value> <op> <value>
(silly example; but the inputs in each case are the same)
You're mixing abstraction levels here: <digit>, <digits>, <number>,
and <value> are lexical tokens, whereas <expr> is syntax.
However ...
Knowing that yacc and bison CAN handle characters as tokens, and
assuming you have defined <digit> and <digits> elsewhere in your
grammar, neither yacc nor bison can find this kind of equivalence. In
yacc it will result in a reduce/reduce error. In bison what happens
depends on the kind of parser you asked for (LALR,SLR,LR,GLR), but in
any case the result won't be pretty.
Assuming instead that you meant for <number> and <value> to be
recognized by the lexer rather than the parser ... flex (not lex)
could discover that <number> and <value> are equivalent, but since
they would lead to different actions: returning a different token -
both would included in the DFA. However, whichever one happened to be
tried first would be the only one that ever was recognized, and your
parser would only ever get one of the expected tokens.
yacc and lex are ancient and haven't been maintained for decades. They
have limitations that will never be addressed, and bugs that will
never be fixed. If you really need backward compatibility with them,
it is available using bison and flex ... and if you don't need bacward
compatibility, bison and flex are much more powerful and modern tools
for use with new projects.
[There are other modern alternatives to yacc and lex also, but
discussion of them is beyond the scope of this missive.]
Now, to the question at hand (or, a version thereof).
It's relatively common to design an algorithm or a hardware machine
as a "state transition diagram" and then reduce to an implementation.
(The question, posed here, is how much this can be automated and
the benefits that might acrue).
Algorithms for turning graphs into table driven FSM, or equivalently a
switch / case statement, are well known.
Assuming an appropriate graphical IDE, a designer certainly could
specify a state graph and code for actions, and have a program
generated from it. Given the right input from the designer, a great
deal of checking could be done against the graph to verify that it
covers enumerated inputs and transitions, that specified inputs lead
to specified actions, that action code exists, etc.
But what is NOT possible is to verify that all /possible/ inputs and
state transitions have been enumerated. Nor is it possible to verify
that required actions have been specified, or necessarily that the
actions are being taken in proper context ... those are things for
which the tool simply MUST trust the graph designer.
On 3/14/2023 6:29 PM, George Neuner wrote:
On Mon, 13 Mar 2023 22:59:25 -0700, Don Y
<blockedofcourse@foo.invalid> wrote:
On 3/13/2023 8:07 PM, George Neuner wrote:
When you merge two FSM you often get redundant "don't care" nodes, but
you also can get nodes which either are impossible to enter [dead
code], or impossible to leave [halt], because there are no legal
transitions that will permit it. Joining FSM involves identifying and
pruning both types of nodes.
Then how did you decide they were equivalent? Clearly, (at least)
one had a different set of options/transitions that is not supported
in the "merged" implementation.
Then there is flex.
flex has some DFA optimizations available. First, flex can compress
the data tables which encode its DFA states. Second, flex can
discover "equivalence" classes: groups of characters which result in
the same action. And finally, flex can [sometimes] discover
"meta-equivalence" classes: commonly expected sequences of characters
and/or other equivalence classes.
But, those are mapping equivalent *inputs* together, not equivalent
*states*. I.e., treating "BEGIN" and "begin" as equivalent.
No. Consider the case of just recognizing a decimal digit: compare
the graph using the alternation: (0|1|2|3|4|5|6|7|8|9), vs the graph
using the class [:digit:].
Using the OR alternation, including start you have 11 nodes. Start has
10 transitions exiting, and each digit node has a single transition
entering.
Are you using "node" as a synonym for "state"?
E.g.,
State Powered_Up
On '1' Goto Entry Executing Accept_Digit()
On '2' Goto Entry Executing Accept_Digit()
On '3' Goto Entry Executing Accept_Digit()
On '4' Goto Entry Executing Accept_Digit()
On '5' Goto Entry Executing Accept_Digit()
On '6' Goto Entry Executing Accept_Digit()
On '7' Goto Entry Executing Accept_Digit()
On '8' Goto Entry Executing Accept_Digit()
On '9' Goto Entry Executing Accept_Digit()
..
State Operation_Complete
On '1' Goto Entry Executing Accept_Digit()
On '2' Goto Entry Executing Accept_Digit()
On '3' Goto Entry Executing Accept_Digit()
On '4' Goto Entry Executing Accept_Digit()
On '5' Goto Entry Executing Accept_Digit()
On '6' Goto Entry Executing Accept_Digit()
On '7' Goto Entry Executing Accept_Digit()
On '8' Goto Entry Executing Accept_Digit()
On '9' Goto Entry Executing Accept_Digit()
..
In each of these, I would have a single transition exiting the
state labeled "0+1+2+3+4+5+6+7+8+9" invoking Accept_Digit()
and destined for "Entry"
Operation_Complete (i.e., the *end* of some undisclosed sequence
of actions, preparing to restart on another iteration) is equivalent
to Powered_Up -- presumably the state just before that sequence of
actions is first started (assuming "..." are equivalent)
I can detect this with an implication table. Even if a series of
states are involved (step1, step2, step3) An algorithm can
similarly detect it. And, remove one of these two states (or
series of states) from the machine (for example, "Operation_Complete"), >replacing all references to it in the machine with "Powered_Up".
Using the digit class, you have 2 nodes, with 10 transitions that all
get you from start to the digit class node.
I don't see where the extra nodes (states) come from.
Obviously this is simplistic, because the members of the character
class form a subgraph which itself has to be recognized. The
important point here is that the subgraph as a whole can represent a
/single/ node in a much more complex graph - its constituent
characters need not be repeated in the complex graph. More on this
below.
A complex DFA that combines many different regex may present other
opportunities to recognize given (possibly arbitrary) sets of
characters - opportunites that may not be apparent from looking at the
constituent regex.
Would it recognize a common sequence of state transitions
that occurs in two different places in the grammar? E.g.,
specifying the syntax for a numeric quantity in two different
places only to realize that it's actually the same part of
the grammar expressed as two different instances?
When given the option to find equivalence classes, flex can identify
sets of characters that are used repeatedly. Those characters are
gathered into an "equivalence" that then can be a node in the DFA
instead of redundantly repeating individual characters.
OK, but that just replaces N *identical*, "parallel" transitions
with a single one labeled with a class instead of a discrete value.
Just like "0+1+2+3+4+5+6+7+8+9". It hasn't reduced the number of states.
Remember DFA are deterministic - a node can't take different actions
depending on which of multiple transitions entered (or left) it ... so
if you want the same character to be recognized in a different context
(leading to a different action), you must repeat it in a different
node.
<number> ::= <digit><digits>
<value> ::= <digit><digits>
<expr> ::= <number> <op> <number> | <value> <op> <value>
(silly example; but the inputs in each case are the same)
You're mixing abstraction levels here: <digit>, <digits>, <number>,
and <value> are lexical tokens, whereas <expr> is syntax.
I'm making the point that <number> and <value> are equivalent
results. A machine that determines if an input satisfied
one would similarly satisfy the other.
So, the two machines would be duplicates of each other and
subject to being optimized into one (because <expr> treats
<number> and <value> as equivalent in *its* machine.
Knowing that yacc and bison CAN handle characters as tokens, and
assuming you have defined <digit> and <digits> elsewhere in your
grammar, neither yacc nor bison can find this kind of equivalence. In
yacc it will result in a reduce/reduce error. In bison what happens
depends on the kind of parser you asked for (LALR,SLR,LR,GLR), but in
any case the result won't be pretty.
Assuming instead that you meant for <number> and <value> to be
recognized by the lexer rather than the parser ... flex (not lex)
Then the question would be whether or not the lexer could
recognize these "little machines" were equivalent and rewite
the grammar so only one was present.
could discover that <number> and <value> are equivalent, but since
they would lead to different actions: returning a different token -
both would included in the DFA. However, whichever one happened to be
tried first would be the only one that ever was recognized, and your
parser would only ever get one of the expected tokens.
Now, to the question at hand (or, a version thereof).
It's relatively common to design an algorithm or a hardware machine
as a "state transition diagram" and then reduce to an implementation.
(The question, posed here, is how much this can be automated and
the benefits that might acrue).
Algorithms for turning graphs into table driven FSM, or equivalently a
switch / case statement, are well known.
Of course. But, they can't *create* information. Anything that
they synthesize has to be present in the input.
E.g., I can convert an ebnf to a railroad diagram. But, I can't
add information on the actions to be performed when each rule
in the grammar is applied (because the ebnf doesn't include that!)
Working backwards, you can't extract information from that railroad
diagram -- to include in the generated code -- that isn't there!
Assuming an appropriate graphical IDE, a designer certainly could
specify a state graph and code for actions, and have a program
generated from it. Given the right input from the designer, a great
deal of checking could be done against the graph to verify that it
covers enumerated inputs and transitions, that specified inputs lead
to specified actions, that action code exists, etc.
But what is NOT possible is to verify that all /possible/ inputs and
state transitions have been enumerated. Nor is it possible to verify
that required actions have been specified, or necessarily that the
actions are being taken in proper context ... those are things for
which the tool simply MUST trust the graph designer.
And, as above, if you want the code to do X, then, somehow, you must
put "X" into the graph. In the examples, here, we've lumped everything
that needs to be "done" into single function calls associated with each
of the transitions. As a single verb-noun is unlikely to be capable of >describing much detail, you're still stuck with code -- that the developer >had to explicitly write.
The dream that you can convert a drawing into an arbitrary *application* >exists as a pipe.
Then there is flex.
flex has some DFA optimizations available. First, flex can compress
the data tables which encode its DFA states. Second, flex can
discover "equivalence" classes: groups of characters which result in >>>>> the same action. And finally, flex can [sometimes] discover
"meta-equivalence" classes: commonly expected sequences of characters >>>>> and/or other equivalence classes.
But, those are mapping equivalent *inputs* together, not equivalent
*states*. I.e., treating "BEGIN" and "begin" as equivalent.
No. Consider the case of just recognizing a decimal digit: compare
the graph using the alternation: (0|1|2|3|4|5|6|7|8|9), vs the graph
using the class [:digit:].
Using the OR alternation, including start you have 11 nodes. Start has
10 transitions exiting, and each digit node has a single transition
entering.
Are you using "node" as a synonym for "state"?
I am using graph terminology - mostly because all FA builders start by constructing a state /graph/. After the graph is complete, it may be implemented using tables, or Duff's device, etc. ... but it doesn't
start that way. 8-)
Check ExceptionsE.g.,
State Powered_Up
On '1' Goto Entry Executing Accept_Digit()
On '2' Goto Entry Executing Accept_Digit()
On '3' Goto Entry Executing Accept_Digit()
On '4' Goto Entry Executing Accept_Digit()
On '5' Goto Entry Executing Accept_Digit()
On '6' Goto Entry Executing Accept_Digit()
On '7' Goto Entry Executing Accept_Digit()
On '8' Goto Entry Executing Accept_Digit()
On '9' Goto Entry Executing Accept_Digit()
Check Exceptions..
State Operation_Complete
On '1' Goto Entry Executing Accept_Digit()
On '2' Goto Entry Executing Accept_Digit()
On '3' Goto Entry Executing Accept_Digit()
On '4' Goto Entry Executing Accept_Digit()
On '5' Goto Entry Executing Accept_Digit()
On '6' Goto Entry Executing Accept_Digit()
On '7' Goto Entry Executing Accept_Digit()
On '8' Goto Entry Executing Accept_Digit()
On '9' Goto Entry Executing Accept_Digit()
..
In each of these, I would have a single transition exiting the
state labeled "0+1+2+3+4+5+6+7+8+9" invoking Accept_Digit()
and destined for "Entry"
Operation_Complete (i.e., the *end* of some undisclosed sequence
of actions, preparing to restart on another iteration) is equivalent
to Powered_Up -- presumably the state just before that sequence of
actions is first started (assuming "..." are equivalent)
I can detect this with an implication table. Even if a series of
states are involved (step1, step2, step3) An algorithm can
similarly detect it. And, remove one of these two states (or
series of states) from the machine (for example, "Operation_Complete"),
replacing all references to it in the machine with "Powered_Up".
Absolutely it /could/ be done with table based algorithms, but I've
never seen it done that way in any real (non toy) implementation ...
graph based solutions scale better to large problems.
Using the digit class, you have 2 nodes, with 10 transitions that all
get you from start to the digit class node.
I don't see where the extra nodes (states) come from.
Think about the "class" as a state in an /NDFA/ ... there are multiple transitions that can get you in - one transition (action) that gets
you out.
When the "class" is implemented it becomes (for lack of better term) a subroutine (subgraph) in the resulting DFA. The more the subgraph can
be reused, the more savings in the DFA.
Obviously this is simplistic, because the members of the character
class form a subgraph which itself has to be recognized. The
important point here is that the subgraph as a whole can represent a
/single/ node in a much more complex graph - its constituent
characters need not be repeated in the complex graph. More on this
below.
A complex DFA that combines many different regex may present other
opportunities to recognize given (possibly arbitrary) sets of
characters - opportunites that may not be apparent from looking at the
constituent regex.
Would it recognize a common sequence of state transitions
that occurs in two different places in the grammar? E.g.,
specifying the syntax for a numeric quantity in two different
places only to realize that it's actually the same part of
the grammar expressed as two different instances?
When given the option to find equivalence classes, flex can identify
sets of characters that are used repeatedly. Those characters are
gathered into an "equivalence" that then can be a node in the DFA
instead of redundantly repeating individual characters.
OK, but that just replaces N *identical*, "parallel" transitions
with a single one labeled with a class instead of a discrete value.
Just like "0+1+2+3+4+5+6+7+8+9". It hasn't reduced the number of states.
It will reduce the number of states IF the class is reused with the
same action. Consider
integer: [+-]?[:digit:]+
float: (((integer)\.)|((integer)?\.(integer)))(\e(integer))?
The [:digit:] class is resused 5 times. The definition of "integer"
also forms a (5x) reused meta-class that flex could recognize if told
to look for them.
Since, in this example, the [:digit:] class is always used with the
same action, it will be implemented in the DFA state graph just once.
Since the class itself consists of ~13 states: START that waits for
input, 0..9 that accept input, common EXIT, and common ERROR out if
something else is input ... treating it AS a class saves 52 states (13
x 4) in the state graph.
The common exit and error states out may be eliminated from the final
FA (assuming no conflicting uses of [:digit:], but they will be
included in initial construction of the state graph (think of them
like subroutine preamble/postamble).
Remember DFA are deterministic - a node can't take different actions
depending on which of multiple transitions entered (or left) it ... so
if you want the same character to be recognized in a different context
(leading to a different action), you must repeat it in a different
node.
<number> ::= <digit><digits>
<value> ::= <digit><digits>
<expr> ::= <number> <op> <number> | <value> <op> <value>
(silly example; but the inputs in each case are the same)
You're mixing abstraction levels here: <digit>, <digits>, <number>,
and <value> are lexical tokens, whereas <expr> is syntax.
I'm making the point that <number> and <value> are equivalent
results. A machine that determines if an input satisfied
one would similarly satisfy the other.
So, the two machines would be duplicates of each other and
subject to being optimized into one (because <expr> treats
<number> and <value> as equivalent in *its* machine.
Yes they are duplicates at some level of abstraction, but that level
is above what the tool can recognize and deal with.
The programmer
labeled them differently and so the tool has to assume both are
required, even if in use there is no practical way to distinguish them
in the input.
Knowing that yacc and bison CAN handle characters as tokens, and
assuming you have defined <digit> and <digits> elsewhere in your
grammar, neither yacc nor bison can find this kind of equivalence. In
yacc it will result in a reduce/reduce error. In bison what happens
depends on the kind of parser you asked for (LALR,SLR,LR,GLR), but in
any case the result won't be pretty.
Assuming instead that you meant for <number> and <value> to be
recognized by the lexer rather than the parser ... flex (not lex)
Then the question would be whether or not the lexer could
recognize these "little machines" were equivalent and rewite
the grammar so only one was present.
You'd need a combination tool that produced parser and lexer from a
unfied spec. There are such tools: e.g., ANTLR ... but I'm not aware
of any tools that do /that/ kind of optimization.
It's all about the context: there's no practical way to merge
identical recognizers if they directly lead to different actions. In
the examples above, [:digit:] could be reused only because every use
of it simply accumulated another input character ... the differences
occurred when a non-digit character was entered.
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.
Assuming an appropriate graphical IDE, a designer certainly could
specify a state graph and code for actions, and have a program
generated from it. Given the right input from the designer, a great
deal of checking could be done against the graph to verify that it
covers enumerated inputs and transitions, that specified inputs lead
to specified actions, that action code exists, etc.
But what is NOT possible is to verify that all /possible/ inputs and
state transitions have been enumerated. Nor is it possible to verify
that required actions have been specified, or necessarily that the
actions are being taken in proper context ... those are things for
which the tool simply MUST trust the graph designer.
And, as above, if you want the code to do X, then, somehow, you must
put "X" into the graph. In the examples, here, we've lumped everything
that needs to be "done" into single function calls associated with each
of the transitions. As a single verb-noun is unlikely to be capable of
describing much detail, you're still stuck with code -- that the developer >> had to explicitly write.
The dream that you can convert a drawing into an arbitrary *application*
exists as a pipe.
Absolutely: somehow actions have to be specified, whether as arbitrary
user entered code attached to graph nodes, or as predefined "action"
nodes linked into the graph.
But as I said above, there are things that simply can't be checked
without embedding significant domain knowledge into the tool itself.
That essentially precludes any notion of a generic tool ... even if
the tool included an expert system, it's likely that no generic
interface to the expert system could be designed that would
satisfactorily deal with the needs of many different domains.
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.
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 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 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 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: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 308 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 91:23:04 |
| Calls: | 6,923 |
| Calls today: | 1 |
| Files: | 12,382 |
| Messages: | 5,434,024 |