Hansen, Niels Damgaard6; Klarlund, Nils4; Schwartzbach, Michael Ignatieff7
Grzegorz Rozenberg, Wolfgang Thomas
1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 The Faculty Secretariat, Faculty of Science, Faculty of Science, Aarhus University, Aarhus University3 ST Administrative Centre, Science and Technology, Aarhus University4 Research scientist at Google5 Department of Computer Science, Science and Technology, Aarhus University6 ST Administrative Centre, Science and Technology, Aarhus University7 Department of Computer Science, Science and Technology, Aarhus University
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.
Proceedings of the 4th International Conference on Development in Language Theory, 2000, p. 286-301
Main Research Area:
International Conference on Development in Language Theory, 2000