Algebra of Grammars?

As in "I can parse integers and F can parse floats so I + F must parse integers and floats".

Not sure what I *F must do though. :)

Akin to parser combinators, perhaps.

Executable notation with Marpa just as the relational algebra is executable with SQL.

Looks like an algebra of grammars be defined in terms of their parseable sets (Algebra of Sets). Then I *F must parse only integers (intersection).

And then, if a problem domain can be reduced to an algebra of parseable entities, it must be parsed by an algebra of grammars with all benefits of mixing, matching, and reusing grammars at will.

That's all probably looks too trivial or too vague, but it starts making much more sense (to me at least) when doing general practical BNF parsing with Marpa::R2 now that grammars like this see the light of day.

5 Comments

Grammar algebra is an interesting set of ideas, and its connection with Marpa is intriguing.

Note that: I ⊂ F

I <+> F can parse I or F but it is not commutative.

F <+> I = F

Since F can parse everything I can, so putting F first means I never gets a chance to parse anything.

I <*> F = F <*> I = I

"'putting F first means I never gets a chance to parse anything' has more to do with algebra of parser combinators that is defined in terms of parse results rather than parseable sets."

Yes but why build a parser if you don't care about parsing? Without parsing, this is just an exercise in set theory.

And there is a difference between I and F. I does integer division, resulting in the dropping of fractions. So the order is very important if, of course, you are actually parsing.

Leave a comment

About rns

user-pic I blog about Perl.