News for hackers. Stuff that matters.

A comment on My Most Important Project Was a Bytecode Interpreter. Parent comment

Re:My Most Important Project Was a Bytecode Interpreter by adrianratnapala on Thursday September 22, 2016 @01:24AM (#12554575)
Presumably that means "this is not true for any more powerful class of grammars".

Any particular pair grammars from that class. I mean if you showed me a yacc grammar for Pascal and another one for Java, I am sure I could prove they were ineqivelent.

More tricky, if you gave someone clever a hand written Pascal parser and that same yacc grammar she could probably prove equivilency with some effort. But there is no guarantee that this is always possible.

[ Parent | on HN ]
Re:My Most Important Project Was a Bytecode Interpreter by wyager on Thursday September 22, 2016 @01:50AM (#12554697)
Yes, that is what I meant.

> I mean if you showed me a yacc grammar for Pascal and another one for Java,

This is why I said "any", and not "all". In most practical cases, you can tell if two grammars are different, but it's easy to construct cases where you can't.

[ Parent | on HN ]