context free grammars: Difference between revisions

From Lojban
Jump to navigation Jump to search
mNo edit summary
No edit summary
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
aka CFG, a grammar which rules do not depend on the context during parsing. I know, this is a circular definition.
A grammar which rules do not depend on the context during parsing. I know, this is a circular definition.


Here are some examples :
Here are some examples :
 
* Lojban grammar, and more generally any [[LR]] or [[LL]] grammar, are context-free.
* 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).
* 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.
** 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.}}
 
==Discussion==
you if sense makes sentence this, please read the first six words backwards.
*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?
*''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, 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, simsa things such as \ 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.:
** 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.
***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]]:
----
**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]]:
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.
 
*.djorden.:
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.
 
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.

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