Re:How Google understands language like a 10-year-old
by nostrademons on Monday October 18, 2010 @01:01PM
(#1804229)
Don't you mean context-sensitive? A context-free grammar can be parsed pretty easily with a stack machine, and most programming languages are context-free. C and C++ are even context-sensitive, but the context-sensitivity is mostly limited to typedefs, and so doesn't tend to blow up parse times beyond reason. (Well, many would consider C++'s compile time to be unreasonable, but this is largely because of #include, which is another issue.)
[ Parent
| on HN ]
Re:How Google understands language like a 10-year-old
by nvoorhies on Monday October 18, 2010 @01:51PM
(#1804428)
Most sane programming language syntaxes are confined to a subset of CFGs, usually LALR, which is nice and easy to generate fast parsers for. To parse any CFG you have to fall back to strategies like CKY that have worst case behaviors that are way worse than linear, like CKY or GLR or what have you.
But yeah, context sensitive stuff can be way worse.
Unless new evidence has surfaced in the years since I finished a degree in linguistics, there's only a couple of pieces of evidence for language constructions in natural languages that can't be generated by a context free grammar, like a Adv1Adv2Adv3Adj1Adj2Adj3 construction in Zürich dialectical German (where Adv = adverb and Adj=adjective, and numbers represent which adverb modifies which adjective).