Author: kn
Date: Thu Feb 14 22:12:23 2008
New Revision: 7377
Log:
- Added more detailed note about RST not being representable by context free
grammars (BNF)
Modified:
experimental/Document/src/document/rst/parser.php
Modified: experimental/Document/src/document/rst/parser.php
==============================================================================
--- experimental/Document/src/document/rst/parser.php [iso-8859-1] (original)
+++ experimental/Document/src/document/rst/parser.php [iso-8859-1] Thu Feb 14
22:12:23 2008
@@ -24,9 +24,13 @@
/**
* Array containing simplified shift ruleset
*
- * We cannot express the RST syntax as a usual grammar using a BNF. This
- * structure contains an array with callbacks implementing the shift rules
- * for all tokens. There may be multiple rules for one single token.
+ * We cannot express the RST syntax as a usual grammar using a BNF. With
+ * the pumping lemma for context free grammars [1] you can easily prove,
+ * that the word a^n b c^n d e^n is not a context free grammar, and this is
+ * what the title definitions are.
+ *
+ * This structure contains an array with callbacks implementing the shift
+ * rules for all tokens. There may be multiple rules for one single token.
*
* The callbacks itself create syntax elements and push them to the
* document stack. After each push the reduction callbacks will be called
@@ -43,6 +47,8 @@
* )
* </code>
*
+ * [1]
http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages
+ *
* @var array
*/
protected $shifts = array(
--
svn-components mailing list
svn-components@lists.ez.no
http://lists.ez.no/mailman/listinfo/svn-components
