context free grammars: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
Line 6: | Line 6: | ||
** C is fairly good about it, compared to many other languages. | ** 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: | * English is not context-free. The way we parse/understand sentences depends on the context, either past or future. Consider this text: | ||
{{mu|you if sense makes sentence this, please read the first six words backwards.}} | {{mu||you if sense makes sentence this, please read the first six words backwards.}} | ||
==Discussion== | ==Discussion== | ||
*cein: | *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, similar to \ line continuations in C. | *** maybe this doesn't address what you mean - but '''si/sa/su''' can be implemented below actual language parsing, similar to \ line continuations in C. | ||
** they are trivially handled by the lexer. | *** they are trivially handled by the lexer. | ||
*But this sentence isn't legitimate English... | *But this sentence isn't legitimate English... | ||
**.djorden.: | **.djorden.: | ||
** | ***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. | ||
*[[User:And Rosta|And Rosta]]: | *[[User:And Rosta|And Rosta]]: | ||
* | **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. | ||
*[[Jay Kominek|Jay]]: | *[[Jay Kominek|Jay]]: | ||
* | **Fairly sure that is the case. It would certainly be context. | ||
*.djorden.: | *.djorden.: | ||
* | **The above is correct - a context free grammar may only have one non terminal on the left hand side of its rules. |
Latest revision as of 14:40, 1 July 2015
aka CFG, a grammar which rules do not depend on the context during parsing. I know, this is a circular definition.
Here are some examples :
- Lojban grammar, and more generally any LR or 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. |
Discussion
- 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, similar to \ line continuations in C.
- they are trivially handled by the lexer.
- 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?
- But this sentence isn't legitimate English...
- .djorden.:
- 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.
- .djorden.:
- And Rosta:
- 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.
- Jay:
- Fairly sure that is the case. It would certainly be context.
- .djorden.:
- The above is correct - a context free grammar may only have one non terminal on the left hand side of its rules.