Re: One possible future of parsing Graph::Easy input texts
Hi Folks I've been using the Perl module Marpa to design a parser for Graph::Easy style graph definitions, with great success. So far, I haven't written a lexer to turn the definitions into an intermediary language, but I've designed that intermediary language along with a Marpa-style grammar, which handles many cases of Graph::Easy syntax. In a day or two I'll release a set of modules under the Graph::Easy::Marpa namespace, which has currently 12 files containing examples of the intermediary language, and a number of tests, all documented. -- Ron Savage http://savage.net.au/ Ph: 0421 920 622
Re: One possible future of parsing Graph::Easy input texts
Hi all, On Tuesday 22 Mar 2011 00:10:49 David Nicol wrote: On Mon, Mar 21, 2011 at 4:04 PM, dhu...@hudes.org wrote: An interesting concept but describing the syntax as a grammar is not the same as an FSA. The FSA is part of the parser and lexer. I disagree. State Machine is a powerful abstraction that is useful in many places. The thing about parsing and Perl is that your lexer can be based on regular expressions which Perl of course understands itself. Regardless, the first step is to come up with a formal grammar. The RHS of the productions are calls to Graph::Easy. Regular expressions describe state machines, for instance. Regex is a descriptive (opposed to procedural) language. So is Graph::Easy. At this time, we have a working parser for Graph::Easy regardless of how it was created. While a formal grammar is wonderful for documenting that language, why are we looking at replacing the parser in the first place? what size /complexity input is causing such a performance problem? Or is that new features for the language are desired and it is difficult to implement them in the existing system? Yes, yes! Perhaps Shlomi will explain exactly what the itch is that he's scratching? I'm just guessing: does the existing Graph::Easy have issues with mixed-direction unicode? It's not me who suggested to reimplement the parser - it's something that Ron (Savage) wanted. I just blogged about the fact that I'd like someone to actively maintain Graph-Easy instead of me: http://community.livejournal.com/shlomif_tech/57021.html Regards, Shlomi Fish -- - Shlomi Fish http://www.shlomifish.org/ Interview with Ben Collins-Sussman - http://shlom.in/sussman No one knows all of Perl - not even Larry Wall. Except Chuck Norris, who knows all of Perl 5, Perl 6 and can answer questions about the design of Perl 7. Please reply to list if it's a mailing list post - http://shlom.in/reply .
Re: One possible future of parsing Graph::Easy input texts
Hi All On Tue, 2011-03-22 at 12:38 +0200, Shlomi Fish wrote: Hi all, On Tuesday 22 Mar 2011 00:10:49 David Nicol wrote: On Mon, Mar 21, 2011 at 4:04 PM, dhu...@hudes.org wrote: An interesting concept but describing the syntax as a grammar is not the same as an FSA. The FSA is part of the parser and lexer. I disagree. State Machine is a powerful abstraction that is useful in many places. The thing about parsing and Perl is that your lexer can be based on regular expressions which Perl of course understands itself. Regardless, the first step is to come up with a formal grammar. The RHS of the productions are calls to Graph::Easy. Regular expressions describe state machines, for instance. Regex is a descriptive (opposed to procedural) language. So is Graph::Easy. At this time, we have a working parser for Graph::Easy regardless of how it was created. While a formal grammar is wonderful for documenting that language, why are we looking at replacing the parser in the first place? what size /complexity input is causing such a performance problem? Or is that new features for the language are desired and it is difficult to implement them in the existing system? Yes, yes! Perhaps Shlomi will explain exactly what the itch is that he's scratching? I'm just guessing: does the existing Graph::Easy have issues with mixed-direction unicode? It's not me who suggested to reimplement the parser - it's something that Ron (Savage) wanted. I just blogged about the fact that I'd like someone to actively maintain Graph-Easy instead of me: http://community.livejournal.com/shlomif_tech/57021.html Yes, it's true. The idea of a re-implementation was definitely mine, but where the discussion will lead, I just don't know. -- Ron Savage http://savage.net.au/ Ph: 0421 920 622
One possible future of parsing Graph::Easy input texts
On Sun, Mar 20, 2011 at 6:42 PM, dhu...@hudes.org wrote: In terms of considering parser improvements or reimplementation, the first step is to come up with a formal grammar for the language. Preferably a Context Free Grammar (CFG) expressed in BNF or EBNF. Once we have that we have options - any of several Perl implementations including Parse::Yapp / Parse::Eyapp - using bison to generate a parser in C and then gluing that in with XS or even Inline::C One could describe the Graph::Easy format grammar as a state machine, draw the state machine with Graph::Easy, then implement a parser from your diagram, with Graph::Easy::StateMachinehttp://cpan.uwinnipeg.ca/htdocs/Graph-Easy-StateMachine/Graph/Easy/StateMachine.html , for a future Graph::Easy that is self-hosting. How cool would that be or what? -- This is not a 'bug'. Being documented, it is merely a 'restriction'. -- Intercal manual
Re: One possible future of parsing Graph::Easy input texts
On Mon, Mar 21, 2011 at 4:04 PM, dhu...@hudes.org wrote: An interesting concept but describing the syntax as a grammar is not the same as an FSA. The FSA is part of the parser and lexer. I disagree. State Machine is a powerful abstraction that is useful in many places. The thing about parsing and Perl is that your lexer can be based on regular expressions which Perl of course understands itself. Regardless, the first step is to come up with a formal grammar. The RHS of the productions are calls to Graph::Easy. Regular expressions describe state machines, for instance. Regex is a descriptive (opposed to procedural) language. So is Graph::Easy. At this time, we have a working parser for Graph::Easy regardless of how it was created. While a formal grammar is wonderful for documenting that language, why are we looking at replacing the parser in the first place? what size /complexity input is causing such a performance problem? Or is that new features for the language are desired and it is difficult to implement them in the existing system? Yes, yes! Perhaps Shlomi will explain exactly what the itch is that he's scratching? I'm just guessing: does the existing Graph::Easy have issues with mixed-direction unicode? -- simple interpolable credential obfuscator: perl -ple 's/(.)/sprintf \\%03o,ord $1/ge;'
Re: One possible future of parsing Graph::Easy input texts
Hi On Mon, 2011-03-21 at 14:04 -0700, dhu...@hudes.org wrote: One could describe the Graph::Easy format grammar as a state machine, draw the state machine with Graph::Easy, then implement a parser from your diagram, with Graph::Easy::StateMachinehttp://cpan.uwinnipeg.ca/htdocs/Graph-Easy-StateMachine/Graph/Easy/StateMachine.html , for a future Graph::Easy that is self-hosting. How cool would that be or what? An interesting concept but describing the syntax as a grammar is not the same as an FSA. The FSA is part of the parser and lexer. The thing about parsing and Perl is that your lexer can be based on regular expressions which Perl of course understands itself. Regardless, the first step is to come up with a formal grammar. The RHS of the productions are calls to Graph::Easy. At this time, we have a working parser for Graph::Easy regardless of how it was created. While a formal grammar is wonderful for documenting that language, why are we looking at replacing the parser in the first place? what size /complexity input is causing such a performance problem? Best to start reading here, about maintenance. Nothing was said (in this thread?) about performance. http://community.livejournal.com/shlomif_tech/57021.html Or is that new features for the language are desired and it is difficult to implement them in the existing system? It's not new 'features', it's new 'humans', to do the support/maintenance. -- Ron Savage http://savage.net.au/ Ph: 0421 920 622
Re: One possible future of parsing Graph::Easy input texts
On Mon, Mar 21, 2011 at 4:04 PM, dhu...@hudes.org wrote: An interesting concept but describing the syntax as a grammar is not the same as an FSA. The FSA is part of the parser and lexer. I disagree. State Machine is a powerful abstraction that is useful in many places. FSA/FSM are -very- useful. I've never used your module but I have implemented FSM though it has been quite some time since I tried to describe one mathematically. A parser has states it is certainly true but is not quite the same thing. Yes, yes! Perhaps Shlomi will explain exactly what the itch is that he's scratching? I'm just guessing: does the existing Graph::Easy have issues with mixed-direction unicode? That's a lexer issue not a parser issue. Parsers deal with symbols which are the output of the lexer. Switching from left-right to right-left word order is certainly an odd thing to do but in the end a parser deals with a sequence of symbols. -- simple interpolable credential obfuscator: perl -ple 's/(.)/sprintf \\%03o,ord $1/ge;'
Re: One possible future of parsing Graph::Easy input texts
I reviewed the list of bugs at https://rt.cpan.org/Public/Dist/Display.html?Name=Graph-Easy Very few seem related to parsing or the input language. The layouter hanging on a 749 edge graph would seem a problem even if you explicitly did it with calls from perl code. Indeed most of the bugs seem to concern one aspect or another of the layout engine not the parser.
