Beefy Boxes and Bandwidth Generously Provided by pair Networks RobOMonk
Welcome to the Monastery
 
PerlMonks  

[Marpa::R2] More Help With Grammar

by three18ti (Scribe)
on Nov 16, 2013 at 23:47 UTC ( #1062951=perlquestion: print w/ replies, xml ) Need Help??
three18ti has asked for the wisdom of the Perl Monks concerning the following question:

Hello Monks,

Recently, I asked for the wisdom of the Monks in formatting my EBNF grammar for Marpa to parse the Sudoers file. [Marpa::R2] Help with EBNF Grammar Formatting
We've got quite an unruly Sudoers file (on the order of hundreds of MB), so I need to be able to break it down into understandable pieces.

We learned there that it's not actually EBNF grammar, it's more like E+BNF... ish. Which is "easier" (parsing isn't exactly easy as it turns out). An Anonymous Monk was kind enough to point out some of my incorrect assumptions and help point me in the right direction.

I think I understand basically what is going on and why in the modified version my Anonymous friend helped me out with. Re: [Marpa::R2] Help with EBNF Grammar Formatting (SLIF is more BNF than EBNF). Please find the code below. (I'm not sure if the "repeatUser_Alias ::=" is actually required but that's perhaps a discussion for another topic).

#!/usr/bin/env perl use strict; use warnings; use warnings; use Marpa::R2; my $grammar_spec = get_grammar(); my $test_input = test_input(); my $grammar = Marpa::R2::Scanless::G->new({ bless_package => 'Ast', so +urce => \$grammar_spec, }); my $recce = Marpa::R2::Scanless::R->new({ grammar => $grammar }); $recce->read(\$test_input); my $val = $recce->value; use Data::Dump; dd $val; sub get_grammar { return q{ :default ::= action => [values] :start ::= Definitions :discard ~ ws Definitions ::= Alias <new line> Alias ::= 'User_Alias' User_Alias repeatUser_Alias + bless => User_Alias1 || 'User_Alias' User_Alias + bless => User_ALias1a repeatUser_Alias ::= manyColonUser_Alias + bless => User_Alias2 ### repeated OPTIONALLY repeatUser_Alias ::= ### repeated many times manyColonUser_Alias ::= colonUser_Alias* + bless => User_Alias_Colon colonUser_Alias ::= ':' User_Alias + bless => User_Alias User_Alias ::= NAME '=' User_List + bless => Alias_Name User_List ::= User | User ',' User_List User ::= <user name> + bless => User_Name ws ~ [\s]+ NAME ~ <name_firstchar><name_restchars> name_firstchar ~ [A-Z] name_restchars ~ [A-Z0-9_]* <user name> ~ <username_firstchar><username_restchars> username_firstchar ~ [a-z] username_restchars ~ [a-z0-9_]* <new line> ~ [\n] }; } sub test_input { return <<'END_INPUT'; User_Alias FOO = abc, def END_INPUT }

So I tried a few different versions of the input, and for most versions of input, this works awesome. Where it breaks down, is where there is more than one line...

When I introduce multiple lines, I get an error:

* String before error: f : BAR = lmnd, adfs : BAZ = fda, reqw\nUser_Al +ias * The error was at line 2, column 11, and at character 0x0020 (non-gra +phic character), ... * here: ZAB = gfd, aed\n Marpa::R2 exception at test1.pl line 13.

Here's a couple of different versions of test_input, the last one is the one that gives me an error (I think this would could be a good use case for tests, again, a good topic for another thread)

sub test_input { return <<'END_INPUT'; User_Alias FOO = abc, def END_INPUT } sub test_input { return <<'END_INPUT'; User_Alias FOO = abc, def : BAR = lmnd, adfs : BAZ = fda, reqw END_INPUT } sub test_input { return <<'END_INPUT'; User_Alias FOO = abc, def : BAR = lmnd, adfs : BAZ = fda, reqw User_Alias ZAB = gfd, aed END_INPUT }

At first, I thought I would have to parse each line individually, e.g. wrap the calls to Marpa::R2::Scanless::R->new for each line. I'm pretty sure that's not the case as there is a cool "extended stackexchange answer" which delves into the some of the finer points of parsing. There is a Fully Functional Example which is able to handle multiple lines of input. For the $data variable, I used the following value:

my $data = <<'END'; If ((Myvalue.xyz == 1) Or (Frmae_1.signal_1 == 1)) Then a = 1 Else a = 0; If ((Myvalue.xyz == 1) Or (Frmae_1.signal_1 == 1)) Then a = 1 Else a = 0; END

This results in the following output (when using dd from Data::Dump) which is successfully parsing multiple lines.

bless([ [ bless([ bless([ bless([ bless(["Myvalue.xyz"], "Ast::Var"), "==", bless([1], "Ast::Literal"), ], "Ast::Binop"), "Or", bless([ bless(["Frmae_1.signal_1"], "Ast::Var"), "==", bless([1], "Ast::Literal"), ], "Ast::Binop"), ], "Ast::Binop"), bless([bless(["a"], "Ast::Var"), "=", bless([1], "Ast::Literal") +], "Ast::Binop"), bless([bless(["a"], "Ast::Var"), "=", bless([0], "Ast::Literal") +], "Ast::Binop"), ], "Ast::Cond"), ], [ bless([ bless([ bless([ bless(["Myvalue.xyz"], "Ast::Var"), "==", bless([1], "Ast::Literal"), ], "Ast::Binop"), "Or", bless([ bless(["Frmae_1.signal_1"], "Ast::Var"), "==", bless([1], "Ast::Literal"), ], "Ast::Binop"), ], "Ast::Binop"), bless([bless(["a"], "Ast::Var"), "=", bless([1], "Ast::Literal") +], "Ast::Binop"), bless([bless(["a"], "Ast::Var"), "=", bless([0], "Ast::Literal") +], "Ast::Binop"), ], "Ast::Cond"), ], ], "Ast::Block")

I'm clearly missing something in my rules, can someone help me out please? This also raises the question of how to tell Marpa that lines ending with a "\" continue onto the next line. Basically, I need to figure out how to say "if the line ends in "\n" stop processing this line, if it ends in "\\n" then the next line is part of the expression. I'm fairly certain the example provided in the extended stackexchange question above is doing SOMETHING to this effect, I'm just not seeing it.

Thanks for your input. I'm not married to Marpa, but it seems to be the best option, if someone has a better idea I'm certainly open to it.

Thank you for the assist!

Comment on [Marpa::R2] More Help With Grammar
Select or Download Code
Re: [Marpa::R2] More Help With Grammar (:discard whitespace fa fa fa)
by Anonymous Monk on Nov 17, 2013 at 02:25 UTC

    One problem is that you discard whitespace, but whitespace include \n, so \n is discarded before you can recognize it -- this might be a bug in marpa (or maybe some kind of configurable option ... blah blah blah ask on list :)

    One workaround is to redefine what you mean by whitespace, like

    ws ~ [ \f\r\t]+

    Basically, I need to figure out how to say "if the line ends in "\n" stop processing this line, if it ends in "\\n" then the next line is part of the expression.

    I kinda thought you figured this out, something like

    blahblah ::= stuff continuationcharacter blahblah ## recurse to self | stuff endoflinestop

    unicharproptoregexrange.pl - program to expand PosixPunct  '[:punct:]' => ['punctuation characters',, '\p{PosixPunct}', ],

    Example output of which includes "\\\n" as part of a line ... gee, i should probably just discard it

    discardedededit

Re: [Marpa::R2] More Help With Grammar
by Jeffrey Kegler (Friar) on Nov 17, 2013 at 02:57 UTC

    The problem you are having with multiple lines was caused by defining your file as only containing a single line. Here's what you need:

    :default ::= action => [values] :start ::= Definitions :discard ~ ws Definitions ::= Definition + Definition ::= Alias <new line>

    As for the backslash'd newlines, to treat them as horizontal space, you want something like:

    ws ~ <ws element> + <ws element> ~ [\s] <ws element> ~ backslash [\n] <backslash> ~ '\'

    I did test both of these with your multi-line example and they seem to work. The Sudoer's format is newline-sensitive -- it treats horizontal and vertical whitespace differently. You'll probably need to nail down exactly where newlines are OK according to the spec, before you're 100% compliant. Marpa has a mailing list, btw, where expert users hang out. Several of the people on the group have more experience with parsers for this kind of file than I have. You might consider joining up.

    I hope this helps.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1062951]
Approved by ww
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (13)
As of 2014-04-16 23:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (436 votes), past polls