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