2
$\begingroup$

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

The State0 is the DFA's start state representing the none terminal symbol Statements, also it is the finish state. From State0 input Statement and traslate to State1 and input ';' at State1, translate to State0. Also, 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 Extend_NT:

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 Extend_NT?

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Sorry for confusing you. I have detailed the problem. $\endgroup$
    – Swordow
    Nov 17, 2021 at 3:42
  • $\begingroup$ Thank you for the clarification. I'm a bit puzzled what is the motivation to translate EBNF -> NFA -> DFA -> regular grammar, but OK. $\endgroup$
    – D.W. ♦
    Nov 17, 2021 at 6:07
  • $\begingroup$ You can try to use some pattern-matching-based simplification rule which discovers this exact situation, and performs the required simplification. $\endgroup$
    – Yuval Filmus
    Nov 17, 2021 at 15:38
  • $\begingroup$ @D.W. I am making a parser generator and the input is grammar file in EBNF format. $\endgroup$
    – Swordow
    Nov 18, 2021 at 1:33

1 Answer 1

Reset to default
-1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.