Are grammars programs? That is, are languages for grammar specification programming languages?
Motivation for the question is follows:
- To know whether languages for grammars are programming languages.
- Desire to know what words I use mean. Since no precise definition of term "programming language" exists we may bring it close to being by figuring out answers for such a tricky questions.
- Which programs can and which can't be written as grammars? (idea by Rehno Lindeque)
Observation that caused a question was:
- Language of grammars has executable semantics like a programming language: every grammar relates input to output (sequence of characters of given alphabet to boolean or AST, depends on implementation), deterministically or not. For example, grammars written in PEG are deterministic "programs" while in BNF are not. CFGs are not Turing complete while unrestricted grammars are.
- Grammar can be designed to carry out a computation on a computer -- actually a parser.