search

coli-saar / alto

Alto, the Algebraic Language Toolkit
Other
16 stars 2 forks source link

Condensed intersection for recursive decomposition grammars #2

Open akoehn opened 9 years ago

akoehn commented 9 years ago

Original report by Alexander Koller (Bitbucket: akoller, GitHub: alexanderkoller).

Now works for direct loops (q -> {...}(q)) , as far as I can tell. I need to come back to this later for general recursion.

The GenericCondensedIntersectionAlgorithm only works if the right (condensed) automaton has no recursion. It will e.g. undergenerate if this automaton has rules of the form "q -> {f}(q)" and this rule is processed before the other rules that can expand q.

Condensed automata arise, for example, in parsing where the IRTG has rules like

A -> r(B) [i] ?1

where i is an input interpretation. This is not a rare case, so we should figure out how to deal with this correctly.

One situation in which this happens in particular is if we introduce a "super-startsymbol" in order to model a probability distribution over different "real" start symbols. The rules for the super-start-symbol map to ?1 on all interpretations.

akoehn commented 9 years ago

Original comment by Christoph Teichmann (Bitbucket: cteichmann, GitHub: CTNLP).

first attempt at fixing issue #2 for direct loops, i.e. rules of the form q -> {...}(q).

→ <<cset 41a151dae24a (bb)>>

akoehn commented 9 years ago

Original changes by Alexander Koller (Bitbucket: akoller, GitHub: alexanderkoller).

changed priority from "major" to "critical"

akoehn commented 9 years ago

Original changes by Alexander Koller (Bitbucket: akoller, GitHub: alexanderkoller).

set assignee_account_id to "557058:bb4f9100-7c0a-40a8-9758-25ab89d7e1c4"; set assignee to "cteichmann"

akoehn commented 9 years ago

Original changes by Christoph Teichmann (Bitbucket: cteichmann, GitHub: CTNLP).

changed state from "new" to "resolved"

akoehn commented 9 years ago

Original changes by Christoph Teichmann (Bitbucket: cteichmann, GitHub: CTNLP).

changed state from "resolved" to "open"

akoehn commented 9 years ago

Original changes by Christoph Teichmann (Bitbucket: cteichmann, GitHub: CTNLP).

changed priority from "critical" to "major"; changed content from "The GenericCondensedIntersectionAlgorithm only works if the right (condensed) automaton has no recursion. It will e.g. undergenerate if this automaton has rules of the form "q -> {f}(q)" and this rule is processed before the other rules that can expand q" to "Now works for direct loops (q -> {...}(q)) , as far as I can tell. I need to come back to this later for general recursion.

The GenericCondensedIntersectionAlgorithm only works if the right (condensed) automaton has no recursion. It wil"

akoehn commented 9 years ago

Original changes by Christoph Teichmann (Bitbucket: cteichmann, GitHub: CTNLP).

changed state from "open" to "on hold"