Aarhus University Seal / Aarhus Universitets segl

Niels Damgaard Hansen

YakYak: Parsing with Logical Side Constraints

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Niels Damgaard Hansen
  • Nils Klarlund, Research scientist at Google, United States
  • Michael Ignatieff Schwartzbach, Denmark
  • Department of Computer Science
  • The Faculty Secretariat, Faculty of Science

Programming language syntax is often described by means of a context-free grammar, which is restricted by constraints programmed into the action code associated with productions. Without such code, the grammar would explode in size if it were to describe the same language.

We present the tool YakYak, which extends Yacc with first-order logic for specifying consteaints that are regular tree languages. Concise formulas about the parse tree replace explicit programming, and they are turned into canonical attribute grammars through tree automata calculations. YakYak is implemented as a proprocessor for Yacc, in which the transitions of the calculated tree automata are merged into the action code. We provide both practical experience and theoretical evidence that the YakYak approach results in fast and consisely specified parsers.

Original languageEnglish
Title of host publicationProceedings of the 4th International Conference on Development in Language Theory
EditorsGrzegorz Rozenberg, Wolfgang Thomas
Number of pages15
PublisherWorld Scientific
Publication year2000
ISBN (print)981-02-4380-4
Publication statusPublished - 2000
EventInternational Conference on Development in Language Theory - Archen, Germany
Duration: 13 Oct 199915 Oct 1999
Conference number: 4th


ConferenceInternational Conference on Development in Language Theory

See relations at Aarhus University Citationformats

ID: 17619872