YakYak: Parsing with Logical Side Constraints

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

  • Niels Damgaard Hansen
  • Nils Klarlund, Research scientist at Google, USA
  • Michael Ignatieff Schwartzbach, Danmark
  • Datalogisk Institut
  • Det Naturvidenskabelige Fakultetssekretariat

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.

OriginalsprogEngelsk
TitelProceedings of the 4th International Conference on Development in Language Theory
RedaktørerGrzegorz Rozenberg, Wolfgang Thomas
Antal sider15
ForlagWorld Scientific
Udgivelsesår2000
Sider286-301
ISBN (trykt)981-02-4380-4
StatusUdgivet - 2000
BegivenhedInternational Conference on Development in Language Theory - Archen, Tyskland
Varighed: 13 okt. 199915 okt. 1999
Konferencens nummer: 4th

Konference

KonferenceInternational Conference on Development in Language Theory
Nummer4th
LandTyskland
ByArchen
Periode13/10/199915/10/1999

Se relationer på Aarhus Universitet Citationsformater

ID: 17619872