context free grammars

From Lojban
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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.
  • 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.
  • 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.