Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Removing epsilon productions from context free grammars (thegreenplace.net)
5 points by mnemonik on Feb 8, 2010 | hide | past | favorite | 3 comments



This is not a new or innovative algorithm. This person is performing one step of the conversion of a CFG to Chomsky Normal Form. Please see Sipser’s “Theory of Computation,” page 107.


See also, "preliminary step a of part 2 of my senior compiler project."

Aren't compilers classes common in undergraduate CS programs? Don't they all do this?

E: In case you were curious, "part 2" of the project was implementing a LL(1) recursive descent parser, so you had to juggle the grammar to work with that kind of parser.


I think you'll find this algorithm in just about any book on formal languages and automata, won't you? In any case, it doesn't seem terribly useful in practice, as tools like yacc seem to deal well enough with \epsilon productions.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: