Text on FSM

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

George

Il 13/03/2023 16:55, StateMachineCOM ha scritto:

Yes, I know this tool and I like its philosopy. However I understood I can't use the generated code in closed source projects without a commercial license.

I read your book ;-)

*Hierarchical* state-machine is fundamental here to reduce complexity.

A good diagram is always much more expressive than a good code, for developers and for non-developers.

Hierarchical state-machines (UML state-machines) are fully qualified monsters.

This is the reason why a fsm generation tool could help. You don't need to build with /ad hoc/ approach.

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.

In my experience, diagrams that describe all the details of the code, as would be required for generating the code from the diagram, are usually much too complex to comprehend easily ("visually"). They tend to be mazes where one can perhaps trace out some significant paths with a careful finger, unless too many lines cross at one point.

To get a good, visually graspable diagram, IME one must almost always simplify and elide details. And then such diagrams are very good entry points into the code, if one has to read the code to get a complete understanding.

I remember one case where the SW for the central computer of a satellite was generated from state-and-message diagrams by an automatic "model-based design" tool. In graphical form, the diagrams covered numerous A4 pages and each page had several cryptically labelled inter-page links for messages coming from other pages and going to other pages. It was very difficult to get any kind of overall understanding of the SW.

I admit that there are some domains -- for example, servo-control systems -- where it is possible to generate significant amounts of code from readable diagrams, eg. SIMULINK diagrams. But I don't think it works well for most code in embedded systems.

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.

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.

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.

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.

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.

George

Hi Don,

Sorry for the delay here ... you know what's going on.

You merge multiple DFA by constructing an equivalent NDFA where all the transitions that lead to the same action are coalesced into a single node (effectively eliminating the redundancies). Some of the impossible halt states may also be eliminated as redundancies.

Once the minimum state NDFA is built, you turn /that/ back into a DFA to increase performance.

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

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.

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.

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

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.

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.

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.