context free grammars: Difference between revisions

From Lojban
Jump to navigation Jump to search
m (Text replace - "jbocre: ([A-K])" to "$1")
No edit summary
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 [[LR|LR]] or [[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:
{{mu|you if sense makes sentence this, please read the first six words backwards.}}
==Discussion==


* English is not context-free. The way we parse/understand sentences depends on the context, either past or future. Consider this text :
*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?
you if sense makes sentence this, please read the first six words backwards.
** 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.
 
*''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.
** 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. --[[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.

Revision as of 06:55, 22 July 2014

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.