User:Mlforcada/Robust LR for Transfer - Revision history

Mlforcada at 17:25, 4 January 2015

2015-01-04T17:25:24Z

Mlforcada at 21:29, 1 January 2015

2015-01-01T21:29:14Z

Mlforcada at 17:50, 1 January 2015

2015-01-01T17:50:55Z

Mlforcada at 17:42, 1 January 2015

2015-01-01T17:42:49Z

Mlforcada at 17:37, 1 January 2015

2015-01-01T17:37:33Z

Mlforcada at 17:29, 1 January 2015

2015-01-01T17:29:25Z

Mlforcada at 16:44, 1 January 2015

2015-01-01T16:44:28Z

Mlforcada: q

2015-01-01T16:42:32Z

Mlforcada: Created page with "We need a way to implement Apertium4 Bison grammars that are robust. Here, '''Bison GRAMMAR''' is a LALR(1) grammar with actions between braces. There should be a way (or a ..."

2015-01-01T16:25:58Z

Created page with "We need a way to implement Apertium4 Bison grammars that are robust. Here, '''Bison GRAMMAR''' is a LALR(1) grammar with actions between braces. There should be a way (or a ..."

New page

We need a way to implement Apertium4 Bison grammars that are robust.

Here, '''Bison GRAMMAR''' is a LALR(1) grammar with actions between braces.

There should be a way (or a procedure) to complete handwritten rules, if possible automatically, to generate a robust parser (and translator).
The idea is to take the handwritten Bison grammar <math>G</math> and complement it with automatically-generated glue rules in such a way that conflicts are not produced (or are harmless) to produce a new grammar <math>G'</math>.

One possible way to do so is to model left-to-right '''restarts''' as follows:

* by accepting the longest possible constituent that cannot be merged with the remaining output and generating some kind of translation for it
* and treating the remaining output as a complete sentence again

@@ Line 18: / Line 18: @@
    | v NP  { write(acc($2),$1) };
 </pre>
-the sequence <math>v n n</math> could not be parsed and would lead to an error. However, it could be seen as a NP followed by a VP, and a translation could be generated for both. One could augment the grammar by systematically adding some rules:
+the sequence <math>v n n</math> could not be parsed and would lead to an error. However, it could be seen as a VP followed by a NP, and a translation could be generated for both separately. One could augment the grammar by systematically adding some rules:
 <pre>
 S : NP VP  { write(agree(nom($1),$2)) }

@@ Line 39: / Line 39: @@
 S : terminal S
 </pre>
-for all terminals, which would (probably) skip one token and try again, but we have to make sure that this does not shadow other rules (although this would be detected by conflicts the grammar, I assume). This could be like a specialized error token. Not all (terminal S) rules could be added, but the ones added would add a lot of coverage, as they would in principle accept any sequence of words through S → terminal S  → terminal terminal S  ... etc. However, the problem of conflicts remains.
+for all terminals, which would (probably) skip one token and try again, but we have to make sure that this does not shadow other rules (although this would be detected by conflicts in the grammar, I assume). This could work a bit like a specialized error token. Not all (terminal S) rules could be added, but the ones added would add a lot of coverage, as they would in principle accept any sequence of words through S → terminal S  → terminal terminal S  ... etc. However, the problem of conflicts remains. Perhaps just adding rules for those terminals not producing a conflict would work.
+Then there is the problem of words which are not recognized by the lexer. We need some kind of default terminal for them, with a default action.

@@ Line 39: / Line 39: @@
 S : terminal S
 </pre>
-for all terminals, which would (probably) skip one token and try again, but we have to make sure that the (terminal S) sequence is not an S of its own. Also, it should not shadow other rules (although this would be detected by the grammar, I assume). This could be like a specialized error token.`
+for all terminals, which would (probably) skip one token and try again, but we have to make sure that this does not shadow other rules (although this would be detected by conflicts the grammar, I assume). This could be like a specialized error token. Not all (terminal S) rules could be added, but the ones added would add a lot of coverage, as they would in principle accept any sequence of words through S → terminal S  → terminal terminal S  ... etc. However, the problem of conflicts remains.

@@ Line 39: / Line 39: @@
 S : terminal S
 </pre>
-which would skip one token and try again, but we have to make sure that the (terminal S) sequence is not an S of its own.
+for all terminals, which would (probably) skip one token and try again, but we have to make sure that the (terminal S) sequence is not an S of its own. Also, it should not shadow other rules (although this would be detected by the grammar, I assume). This could be like a specialized error token.`

@@ Line 33: / Line 33: @@
 One can generate TryS rules for all left-hand-sides incrementally, but maybe order is important, so some ordering of constituents may be useful.
-Unary productions should be avoided.
+Unary productions should be avoided. There is no easy way to avoid that.
+'''Another strategy''' would just add rules of the form
+<pre>
+S : terminal S
+</pre>
+which would skip one token and try again, but we have to make sure that the (terminal S) sequence is not an S of its own.

@@ Line 15: / Line 15: @@
 S : NP VP  { write(agree(nom($1),$2)) };
 NP : n   { write($1) } ;
-VP : v  { write($1) } ;
+VP : v  { write($1) }
    | v NP  { write(acc($2),$1) };
 </pre>
-the sequence <math>v n n</math> could not be parsed and would lead to an error. However, it could be seen as a NP followed by a VP, and a translation could be generated for both. One could augment the grammar by adding some rules:
+the sequence <math>v n n</math> could not be parsed and would lead to an error. However, it could be seen as a NP followed by a VP, and a translation could be generated for both. One could augment the grammar by systematically adding some rules:
 <pre>
 S : NP VP  { write(agree(nom($1),$2)) }
@@ Line 27: / Line 27: @@
      | ;                                  # the remaining part may be empty
 NP : n   { write($1) } ;
-VP : v  { write($1) } ;
+VP : v  { write($1) }
    | v NP  { write(acc($2),$1) };
 </pre>