I am trying to convert this grammar from context free grammar with kleene star productions into the Chomsky normal form equivalent. I am having a hard time trying to understand how to do this, I need this for use in recursive decent parsers primarily a table driven top down predictive parser.


expr ::= term {addop term}
term ::= factor {mulop factor}
factor ::= variable| unsigned-number| ( expr)
variable ::= identifier
addop ::= + | -
mulop ::= * | /

  • 1
    $\begingroup$ Why do you need CNF to produce a recursive descent parser? Once you know the grammar is LL(1), you can just turn each production directly into RD parsing code. (Use a while loop to translate the Kleene stars, which are not technically part of the CFG rules.) $\endgroup$ – rici Nov 17 '19 at 18:58
  • $\begingroup$ Okay, could you expand upon what you were saying? I do not really understand how you are supposed to do this and then get the same. The grammar from my knowledge is ll(1) but I just dont get how you would implement the kleene star with the while and be able to predict what production to use and how to use it with a table driven setup. $\endgroup$ – Fel Nov 17 '19 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.