OMeta: an Object-Oriented Language for Pattern Matching

OMeta: an Object-Oriented Language for Pattern Matching

A new paper by Alessandro Warth and Ian Piumarta, related to the Reinvention of Programming project:

This paper introduces OMeta, a new object-oriented lan-
guage for pattern matching. OMeta is based on a variant of
Parsing Expression Grammars (PEGs) [5]—a recognition-
based foundation for describing syntax—which we have
extended to handle arbitrary kinds of data. We show that
OMeta’s general-purpose pattern matching provides a nat-
ural and convenient way for programmers to implement
tokenizers, parsers, visitors, and tree transformers, all of
which can be extended in interesting ways using familiar
object-oriented mechanisms. This makes OMeta particularly
well-suited as a medium for experimenting with new designs
for programming languages and extensions to existing lan-

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

That's not how you post to

That's not how you post to the home page... Reminder to editors: use the link at the bottom of the FAQ (and oh, keep in mind that you have a couple of accounts. The C-E account is "Manuel Simoni").

old email

Could you make the msimoni account C-E? I no longer have access to the other account's mailbox. Thanks!



A very interesting article

Many thanks to msimoni for this article. I found it to be excellent!

It seems like PEGs are increasing in popularity. Another fairly new language in which they are used is the Cat programming language. I'm still more used to BNF grammars (rather than PEGs) but it is good to see the increasing usage of PEGs, and OMeta looks to have had a lot of thought put into its design.

I agree this is a very

I agree this is a very interesting paper. The unification of various forms of lexers, parsers, and interpreters into a single parser is promising. The ability for OMeta to consume more than just text, meaning it can tokenize/parse numbers and and other data types, is also sophisticated at such a low level.

Building on top of COLA, OMeta borrows syntax and ideas from Scheme and Smalltalk.

Difference between BNF and PEG grammars?

In PEGs, non terminals have only one definition, right? so how are altenative cases for a rule may be expressed?

In the wikipedia article, it mentions that PEGs can be expressed using EBNF. But using operators like * is like introducing alternative cases for a rule, isn't it?

So what is really the difference?

PEGs have a "left-biased

PEGs have a "left-biased choice" operator.

So how does that make PEGs different from right-recursive BNFs?

So what is the difference between PEGs and right-recursive BNFs?

According to the example, the following:

product = value ((* | /) value)*

is PEG, but it's also a right-recursive BNF grammar.

There are no ambiguous PEGs

There are no ambiguous PEGs - if the left-hand choice is valid, it's the only valid parse. BNF doesn't support anything akin to semantic predicates.

Can we get this in R6RS?

1/2 ;)

(define puts
  (lambda (s)
    (let ((idx 0))
      { cola ::= :a ’[’ :i ’]’ => ‘(char@ ,a ,i)
               | ; }

      (while (!= s[idx] 0)
        (putchar s[idx])
        (set idx (+ idx 1)))
      (putchar 10))))

(puts "this is a test") ;; works
(printf "%d\n" "abcd"[0]) ;; parse error!

Figure 6. A lexically-scoped syntax extension for C-style array accesses.


I've written a port of OMeta in JavaScript, which means you can try it out in your web browser without having to download Squeak or COLA. Here's the URL, if you're interested:

(There's also a Smalltalk in there, and you can use both languages in a Squeak-style workspace user interface.)