chomsky hierarchy and programming languages

Posted by dader51 on Stack Overflow See other posts from Stack Overflow or by dader51
Published on 2010-05-28T13:47:37Z Indexed on 2010/05/30 23:22 UTC
Read the original article Hit count: 481

Hi, I'm trying to learn some aspects of the CH ( chomsky hierarchy ) which are related to PL ( programming languages ), and i still have to read the Dragon Book.

I've read that most of the PL can be parsed as CFG ( context free grammar ). In term of computational power, it equals the one of a pushdown non deterministic automaton. Am I right ?

If it's true, then how could a CFG holds a UG ( unrestricted grammar, which is turing complete ) ? I'm asking because, even if PL are CFG they are actually used to describe TM (turing machines ) and through UG.

I think that's because of at least two different levels of computing, the first, which is the parsing of a CFG focuses on the syntax related to the structure ( representation ? ) of the language, while the other focuses on the semantic ( sense, interpretation of the data itself ? ) related to the capabilities of the pl which is turing complete. Again, are these assumptions rights ?

thanx a lot.

© Stack Overflow or respective owner

Related posts about programming-languages

Related posts about formal-languages