GSoC/GCI Archive
Google Code-in 2014 Apertium

Write code to generate an AST representing the bison parse tree

completed by: Stan K.

mentors: Kevin Brubeck Unhammer, Francis Tyers

1) Write a bison grammar for a language fragment. For example to cover 5 lines of the Apertium "story".[1]

   - The grammar should use the bison error token allow it to return a tree / parse things outside the grammar.

   - The grammar should construct an internal AST and print it out in bracketed format.



S -> NP VP

VP -> V NP

DP -> Det NP

NP -> N | AP N | DP

AP -> A | A AP

A -> adjec

N -> noun

Det -> det

V -> verb


Would produce a tree for the following sentence:


The bear eats a small tree .

The<det> bear<n> eats<vblex> a<det> small<adj> tree<n> .<sent>


[S [DP [Det the<det>] [NP [N bear<n>]]] [VP [V eats<vblex>] [DP [Det a<det>] [NP [AP [A small<adj>]] [N tree<n>]]]]]


The node representation could be something like:


node {

  int id;

  int lin;

  string info;

  bool term;

  node *children;