Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2016-01-19

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary

All times shown according to UTC.

Time Nick Message
00:28 Idiosyncrat joined #marpa
00:29 shadowpaste joined #marpa
05:43 Idiosyncrat Good night!
07:07 ronsavage joined #marpa
15:02 kaare_ joined #marpa
15:29 koo7 joined #marpa
15:30 koo8 joined #marpa
18:34 beaugunderson joined #marpa
18:39 iarna joined #marpa
19:20 VsyachePuz here is what i think about EBNF grammar - https://raw.githubusercontent.com/ArsenShnurkov/earley-sppf/master/src/test1/Resources/ebnf-grammar-2.ebnf
19:25 VsyachePuz there are 2 things which i don;t understood: 1) how to implement "-" operation; 2) how to use ?...? extensions
19:33 Idiosyncrat joined #marpa
19:34 Idiosyncrat VsyachePuz: there's no general way to implement a '-' operation.
19:34 Idiosyncrat CFG's are not closed under difference, intersection, and complement
19:35 VsyachePuz Idiosyncrat: may i ask you to recomment some full-length article on these properties of CFGs?
19:36 Idiosyncrat In the standards I've read the '-' operation is restricted to cases where regular expressions are involved.
19:37 VsyachePuz i don't see that restriction in the file http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf
19:37 Idiosyncrat I haven't surveyed them all, but I use Hopcroft & Ullman _Introduction to Automata Theory, Languages and Computation_
19:38 Idiosyncrat It *is* authoritative and I've owned a copy forever.  There may be better, though.
19:39 Idiosyncrat re http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf == it might be they just don't say,
19:40 Idiosyncrat Note that being "not closed" does not mean that it's not a language -- just that it's not a CFG, so you can't translate it into BNF.
19:40 Idiosyncrat If you want to give me a page reference, I can try to figure out their intent.
19:43 Idiosyncrat Re  ?...? extensions --  http://irclog.perlgeek.de/marpa/2016-01-19#i_11909848 ==
19:44 Idiosyncrat I am not sure what those are.
19:44 VsyachePuz in my grammar regular expressions are enough. So, now I am able to read some sort of EBNF parser and can start to write EBNF->BNF conversion
19:48 VsyachePuz 4.7 Syntactic exception says: "It may be shown that the difference between a
19:48 VsyachePuz context-free grammar and a regular grammar is always another
19:48 VsyachePuz context-free grammar"
19:49 VsyachePuz the term "regular grammar" is not described
19:50 VsyachePuz may be it is regular expressions
19:50 VsyachePuz http://stackoverflow.com/questions/559763/regular-vs-context-free-grammars
19:52 Idiosyncrat Regular grammars are those which describe only the regular expressions.
19:53 Idiosyncrat Other interesting stuff -- note the EBNF doc *does* describe EBNF in EBNF, *but* ...
19:53 Idiosyncrat the description is informal -- apparently EBNF is *not* capable of fully describing itself.
19:55 Idiosyncrat Also, re '-', the 'except' operator -- it's RHS can only be a "syntactic exception", not a full "syntactic factor"
19:56 VsyachePuz ok, i will rewrite my grammar to make it closer to pdf-s definitions
19:56 Idiosyncrat And a syntactic exception is "a syntactic-factor that could be replaced by a syntactic-factor containing no meta-identifiers"
19:57 Idiosyncrat Which I think means that a syntactic exception cannot be recursive and therefore must be the equivalent of a regular expression.
19:57 Idiosyncrat "pdf's definitions"?
19:58 VsyachePuz i used "rhs" in the right part - https://github.com/ArsenShnurkov/earley-sppf/blob/master/src/test1/Resources/ebnf-grammar-2.ebnf#L14
19:59 VsyachePuz will rewrite that
20:10 Idiosyncrat Jean-Damien: I notice that your EBNF to BNF project is empy on Github -- https://github.com/jddurand/MarpaX-Languages-EBNF
20:11 Idiosyncrat Did you delete it?
20:15 VsyachePuz I want not only translate from one to another, but also keep links between rule positions, and between linear positions and lines/columns
20:25 Idiosyncrat I describe a method for doing this in the new Marpa book.
20:26 Idiosyncrat https://drive.google.com/open?id=0B9_mR_M2zOc4UUJDUjc4ZFNaTVk
20:27 Idiosyncrat It's Chapter 4, pp 23-25
20:27 Idiosyncrat The Book is not complete, but that chapter should be stable.
20:28 Idiosyncrat I was also implementing it in Kollos.
20:28 Idiosyncrat ... before I interrupted that for the Marpa Book.
20:29 VsyachePuz I alwasy wondered - how something can be the first implementation, if original impelemntors already implemented it when developed an algorithm?
20:30 Idiosyncrat Some algorithms are not implemented by the inventor -- I don't think Knuth implemented his LR algorithm.
20:31 Idiosyncrat And that Valiant did not implement his algorithm.
20:31 Idiosyncrat Wrt Marpa, it is the first *practical* implementation of Joop Leo's algorithm.
20:33 Idiosyncrat And wrt Marpa itself, I am actually unusual in both discovering a parsing algorithm and doing a full practical implemention of it.
20:51 VsyachePuz "We assume that a Marpa grammar is cycle-free — that none of its rules are cyclic. We assume that every symbol is productive — that is,that it derives a sentence. We assume that every symbol is accessible — that is, that it is derivable from the start symbol." assume is a wrong word. You should check these conditions at early stages of grammar analysis
20:55 Idiosyncrat In describing a mathematical construct, you posit certain requirements necessary for your analysis to be correct.
20:55 Idiosyncrat These are correcty called "assumptions".
20:55 Idiosyncrat Whether or not an implementation guarantees them is another matter.
20:56 Idiosyncrat In the case of the SLIF, it does check to make sure the grammar is cycle-free.
21:00 ronsavage joined #marpa
22:46 VsyachePuz The Idea to order papers by time (as you did in yout "timeline" is actually very good. Why you didn't followed it in your book?
23:34 koo8 joined #marpa

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary