Self-Descriptive Grammars
posted on Jun 19, 2009 at 2:57am with three comments
and tagged with Computer Science, Parsing Theory
- Languages have structure.
- We can make a new language, X, to describe the structure of languages.
- Language X itself has a structure and as a result the structure of language X can be described.
- We made language X to describe the structure of languages.
- Therefore, language X can describe its own structure.
Comments
-
I don't think it naturally follows that language X will be able to describe itself. By the way, sounds like set theory to me.posted by countzero on Jun 20, 2009 at 9:46am
-
You are correct in that it doesn't necessarily follow that language X can describe itself. For example, if language X is inherently ambiguous and the language or the method used to parse languages according to its rules do not allow for ambiguity then language X simply won't suffice.posted by Peter Goodman on Jun 20, 2009 at 7:47pm
Another problem relating to the aforementioned ambiguity problem would be if language X's description were to require context-sensitive things, where a word in language X means one thing in one context and another in a different context. If language X is a context-free language then my conclusion does not follow.
The main motivation of the post was to elicit excitement about parsing. I like the description I gave because it is high level enough (it ignores all thoughts about ambiguity, context, recursion, etc) to expose an interesting idea and because the idea itself is closed box (insofar as we don't get stuck in an infinite regress of one thing describing itself describing itself describing ...).
I don't think that I follow your thought in saying this sounds like set theory; could you please elaborate? It's more precise to say that language X can describe a subset of all languages, and if language X itself is within that subset then language X can describe itself; however, I don't feel like this is what you were alluding to. -
posted by Peter Goodman on Sep 11, 2010 at 6:20pm
For those interested, a good example of a language meant to describe the structure of another language but that cannot describe itself would be regular expressions.
A language describing all regular languages contains all regular expressions; however, the language of all regular expressions is not regular (it is context-free, to see this, consider that regular expressions cannot be used to determine whether or not a string has a balanced number of parentheses).
Comment