Here is a simple but very common grammar rule case in EBNF format, the
Statements is a none terminal symbol and
Statement is none terminal symbol:
Statements ::= (Statement ';')*
After converting this rule to NFA, and then do the subset contruction for converting the NFA to DFA, and at last get the dfa:
State0 -> Statement -> State1 -> ';' ->State0 State0 -> ε -> State0
State0 is the DFA's start state representing the none terminal symbol
Statements, also it is the finish state.
Statement and traslate to
State1 and input ';' at
State1, translate to
State0 could translate to self with the
And after converting the above dfa to regular grammar following the algorithm in dragon book, i get the following grammar rules:
Statements -> ε Statements -> Statement Extend_NT Extend_NT -> ';' Statements
It added the new none terminal symbol
Extend_NT, but i want to get the following the regular grammars which does not contain the extend symbol
Statements -> ε Statements -> Statement ';' Statements
So the question is that is there any algorithm could get the above result that does not contain the new none terminal symbol
Or it is just a engineering problem?
Solved: I have solved this by removing the extend symbol in parsing stage. For example, in LALR parsing stage, when to reduce a symbol, i can remove the extend symbol at same time.