context free grammars: Difference between revisions
Jump to navigation
Jump to search
m (Text replace - "{BOX()} " to "") |
mNo edit summary |
||
Line 1: | Line 1: | ||
A grammar which rules do not depend on the context during parsing. I know, this is a circular definition. | |||
Here are some examples : | |||
* Lojban's grammar, and more generally any [[jbocre: LR|LR]] or [[jbocre: LL|LL]] grammar, are context-free. | |||
* The C language is supposed to be context-free, except on the topic of type definition (if "typedef" preceeds a definition, the symbol defined becomes a type rather than a variable : semantics change depending on the context, given the same lexical grammar). | |||
** C is fairly good about it, compared to many other languages. | |||
* English is not context-free. The way we parse/understand sentences depends on the context, either past or future. Consider this text : | |||
you if sense makes sentence this, please read the first six words backwards. | |||
*''mi'e cein. Doesn't Lojban have si/sa/su, which must be "understood" by the parser in the same sense as the English example above in order to be correctly parsed?'' | |||
** maybe this doesn't address what you mean -- but si/sa/su can be implemented below actual language parsing, simsa things such as \ line continuations in C. | |||
* | ** they are trivially handled by the lexer. | ||
* | *But this sentence isn't legitimate English... | ||
** arguable; but the point still stands -- english isn't context free. A phrase structure grammar for english would be hideously large and type 0-1, if a complete one were ever made, which is unlikely. --mi'e .djorden. | |||
---- | |||
I thought a CFG was one where the left side of the rewrite rule is unconditional. E.g. "A -> B C" is context free, but "A -> B C, when A is preceded by D" ("D A -> B C") is not context free. --[[User:And Rosta|And Rosta]] | |||
Fairly sure that is the case. It would certainly be context. --[[jbocre: Jay Kominek|Jay]] | |||
the above is correct -- a context free grammar may only have one non terminal on the left hand side of its rules. --mi'e .djorden. | |||
Revision as of 16:46, 4 November 2013
A grammar which rules do not depend on the context during parsing. I know, this is a circular definition.
Here are some examples :
- The C language is supposed to be context-free, except on the topic of type definition (if "typedef" preceeds a definition, the symbol defined becomes a type rather than a variable : semantics change depending on the context, given the same lexical grammar).
- C is fairly good about it, compared to many other languages.
- English is not context-free. The way we parse/understand sentences depends on the context, either past or future. Consider this text :
you if sense makes sentence this, please read the first six words backwards.
- mi'e cein. Doesn't Lojban have si/sa/su, which must be "understood" by the parser in the same sense as the English example above in order to be correctly parsed?
- maybe this doesn't address what you mean -- but si/sa/su can be implemented below actual language parsing, simsa things such as \ line continuations in C.
- they are trivially handled by the lexer.
- But this sentence isn't legitimate English...
- arguable; but the point still stands -- english isn't context free. A phrase structure grammar for english would be hideously large and type 0-1, if a complete one were ever made, which is unlikely. --mi'e .djorden.
I thought a CFG was one where the left side of the rewrite rule is unconditional. E.g. "A -> B C" is context free, but "A -> B C, when A is preceded by D" ("D A -> B C") is not context free. --And Rosta
Fairly sure that is the case. It would certainly be context. --Jay
the above is correct -- a context free grammar may only have one non terminal on the left hand side of its rules. --mi'e .djorden.