Article

OMeta: an object-oriented language for pattern matching

Authors:

Alessandro Warth,

Ian PiumartaAuthors Info & Claims

DLS '07: Proceedings of the 2007 symposium on Dynamic languages

Pages 11 - 19

https://doi.org/10.1145/1297081.1297086

Published: 22 October 2007 Publication History

Abstract

This paper introduces OMeta, a new object-oriented language 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 natural 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 languages.

References

[1]

H. Abelson, R. K. Dybvig, C. T. Haynes, G. J. Rozas, I. N. I. Adams, D. P. Friedman, E. Kohlbecker, G. L. Steele, D. H. Bartley, R. Halstead, D. Oxley, G. J. Sussman, G. Brooks, C. Hanson, K. M. Pitman, and M. Wand. Revised report on the algorithmic language Scheme. SIGPLAN Lisp Pointers, IV(3):1--55, 1991.

Digital Library

[2]

ECMA. ECMAScript language specification.

[3]

B. Ford. Pappy: a parser generator for Haskell. http://pdos.csail.mit.edu/<baford/packrat/thesis/.

[4]

B. Ford. Packrat parsing: simple, powerful, lazy, linear time, functional pearl. In ICFP '02: Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, pages 36--47, New York, NY, USA, 2002. ACM Press.

Digital Library

[5]

B. Ford. Parsing Expression Grammars: a recognition-based syntactic foundation. In POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 111--122, New York, NY, USA, 2004. ACM Press.

Digital Library

[6]

E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns. Addison-Wesley Professional, January 1995.

[7]

R. Grimm. Better extensibility through modular syntax. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 38--51, New York, NY, USA, 2006. ACM Press.

Digital Library

[8]

G. Hutton and E. Meijer. Monadic parsing in Haskell. J. Funct. Program., 8(4):437--444, 1998.

Digital Library

[9]

D. Leijen and E. Meijer. Parsec: Direct style monadic parser combinators for the real world. Technical Report Technical Report UU-CS-2001-35, Universiteit Utrecht, 2001.

[10]

T. J. Parr and R. W. Quong. Adding semantic and syntactic predicates to LL(k): pred-LL(k). In Computational Complexity, pages 263--277, 1994.

Digital Library

[11]

I. Piumarta. Open, extensible programming systems. Keynote talk, Dynamic Languages Symposium, 2006.

[12]

G. Rossum. Python reference manual. Technical report, Centre for Mathematics and Computer Science, Amsterdam, The Netherlands, 1995.

Digital Library

[13]

D. J. Salomon and G. V. Cormack. Scannerless NSLR(1) parsing of programming languages. In PLDI '89: Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, pages 170--178, New York, NY, USA, 1989. ACM Press.

Digital Library

[14]

D. V. Schorre. META-II: a syntax-oriented compiler writing language. In Proceedings of the 1964 19th ACM national conference, pages 41.301--41.3011, New York, NY, USA, 1964. ACM Press.

Digital Library

[15]

G. L. Steele. An overview of Common Lisp. In LFP '82: Proceedings of the 1982 ACM symposium on LISP and functional programming, pages 98--107, New York, NY, USA, 1982. ACM Press.

Digital Library

[16]

L. G. Tesler, H. J. Enea, and D. C. Smith. The LISP70 pattern matching system. In Proc. of the 3rd IJCAI, pages 671--676, Stanford, MA, 1973.

Cited By

Schröder MCito JPasquale LTreude C(2022)Grammars for freeProceedings of the ACM/IEEE 44th International Conference on Software Engineering: New Ideas and Emerging Results10.1145/3510455.3512787(41-45)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510455.3512787
Schroder MCito J(2022)Grammars for Free: Toward Grammar Inference for Ad Hoc Parsers2022 IEEE/ACM 44th International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER)10.1109/ICSE-NIER55298.2022.9793523(41-45)Online publication date: May-2022
https://doi.org/10.1109/ICSE-NIER55298.2022.9793523
Chida NKawakoya YIkarashi DTakahashi KSen KPouchet LJimborean A(2020)Is stateful packrat parsing really linear in practice? a counter-example, an improved grammar, and its parsing algorithmsProceedings of the 29th International Conference on Compiler Construction10.1145/3377555.3377898(155-166)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3377555.3377898
Show More Cited By

Index Terms

OMeta: an object-oriented language for pattern matching
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
      2. Language types
        Object oriented languages

Recommendations

A fast general parser for automatic code generation
MTPP'10: Proceedings of the Second Russia-Taiwan conference on Methods and tools of parallel programming multicomputers

The code generator in a compiler attempts to match a subject tree against a collection of tree-shaped patterns for generating instructions. Tree-pattern matching may be considered as a generalization of string parsing. We propose a new generalized LR (...
Left recursion in Parsing Expression Grammars

Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PEG ...
Generating parsers for affix grammars

Affix grammars are two-level grammars which are similar to van Wijngaarden's two-level grammars used in the definition of Algol 68. Affix grammars are shown by Koster to be equal in power to van Wijngaarden grammars. They are much more suited to parsing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DLS '07: Proceedings of the 2007 symposium on Dynamic languages

October 2007

108 pages

ISBN:9781595938688

DOI:10.1145/1297081

Program Chairs:
Pascal Costanza
Vrije Universiteit Brussel, Belgium
,
Robert Hirschfeld
Hasso-Plattner-Institut Potsdam, Germany

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

OOPSLA07

Sponsor:

OOPSLA07: ACM SIGPLAN Object Oriented Programming Systems and Applications Conference

October 22, 2007

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 32 of 77 submissions, 42%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
507
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schröder MCito JPasquale LTreude C(2022)Grammars for freeProceedings of the ACM/IEEE 44th International Conference on Software Engineering: New Ideas and Emerging Results10.1145/3510455.3512787(41-45)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510455.3512787
Schroder MCito J(2022)Grammars for Free: Toward Grammar Inference for Ad Hoc Parsers2022 IEEE/ACM 44th International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER)10.1109/ICSE-NIER55298.2022.9793523(41-45)Online publication date: May-2022
https://doi.org/10.1109/ICSE-NIER55298.2022.9793523
Chida NKawakoya YIkarashi DTakahashi KSen KPouchet LJimborean A(2020)Is stateful packrat parsing really linear in practice? a counter-example, an improved grammar, and its parsing algorithmsProceedings of the 29th International Conference on Compiler Construction10.1145/3377555.3377898(155-166)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3377555.3377898
Zaytsev VSalvaneschi GDe Meuter WEugster PSant’Anna FZiarek LKamina TMasuhara H(2019)Event-based parsingProceedings of the 6th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems10.1145/3358503.3361275(31-40)Online publication date: 21-Oct-2019
https://dl.acm.org/doi/10.1145/3358503.3361275
Stucki NGiarrusso POdersky MErdweg SOliveira B(2018)Truly abstract interfaces for algebraic data types: the extractor typing problemProceedings of the 9th ACM SIGPLAN International Symposium on Scala10.1145/3241653.3241658(56-60)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3241653.3241658
Kuramitsu KCombemale BMernik MRumpe B(2017)A symbol-based extension of parsing expression grammars and context-sensitive packrat parsingProceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3136014.3136025(26-37)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3136014.3136025
Schuster CDisney TFlanagan C(2016)MacroficationProceedings of the 25th European Symposium on Programming Languages and Systems - Volume 963210.5555/3089528.3089553(644-671)Online publication date: 2-Apr-2016
https://dl.acm.org/doi/10.5555/3089528.3089553
Warth ADubroy PGarnock-Jones T(2016)Modular semantic actionsACM SIGPLAN Notices10.1145/3093334.298923152:2(108-119)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1145/3093334.2989231
Lviv MDucasse SSantos GTeruel CLaval JEtien A(2016)PhormsProceedings of the 11th edition of the International Workshop on Smalltalk Technologies10.1145/2991041.2991057(1-6)Online publication date: 23-Aug-2016
https://dl.acm.org/doi/10.1145/2991041.2991057
Warth ADubroy PGarnock-Jones TIerusalimschy R(2016)Modular semantic actionsProceedings of the 12th Symposium on Dynamic Languages10.1145/2989225.2989231(108-119)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1145/2989225.2989231
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten