Search code examples
nullantlr4grammarfinite-automata

The grammar of a language of a NFA state diagram - Antlr v4

I am trying to write the grammer of the following NFA diagram Coffee machine state diagram

My code is

grammar LTFA;

rS: 'Start' rA | EOF;

rA: 'Select_coffe' rB;

rB: 'Enter_money' rC | 'Cancel' rS;

rC:  'More_money_needed' rC | 'Refund' rE | 'Right_amount_of_money' rD;

rD: 'Change' rC | 'Done' | 'Done' rS;

rE: 'End' | 'End' rS;

WS: ( ' ' | '\t' | '\n')->skip;

The problem is the language does not accept a null string(empty), how can I make is accept null??

here is the error I got

The error

Solution

  • This task is probably not possible to accomplish. While you can generate a state machine (ATN, NFA, DFA) from a grammar, it's not possible to do the reverse, because states are not rules and you cannot create rules from only states and transitions. However, you are trying here to use grammar rules in place of states.

    Let's take a look at an example, your rule rB:

    rB: 'Enter_money' rC | 'Cancel' rS;

    What your state diagram says you want is:

    1. We have to be in state Q2.
    2. We enter the input "Enter_money".
    3. We end up in state Q3.

    or

    1. We enter the input "cancel".
    2. We end up in state Q0.

    The rule however says:

    1. Match the input "Enter_money".
    2. Then match rule rC (which requires more input)

    or

    1. Match the input "Cancel".
    2. Then match rule ' rS' (which requires the whole chain to match again).

    While you can certainly take a set of nodes and put them in a rule to execute for certain input, you will not be able to direct the parser interpreter (or state walker) to end up in a specific state (like the start state once a purchase was finished or cancelled).