Apertium-recursive/Parser - Revision history

Trondtr at 06:12, 1 June 2023

2023-06-01T06:12:41Z

Popcorndude: link to example.

2019-07-31T20:14:03Z

link to example.

Popcorndude: Popcorndude moved page User:Popcorndude/Recursive Transfer/Parser to Apertium-recursive/Parser: transfer documentation to main namespace

2019-07-31T20:12:59Z

Popcorndude moved page User:Popcorndude/Recursive Transfer/Parser to Apertium-recursive/Parser: transfer documentation to main namespace

Popcorndude at 14:05, 25 July 2019

2019-07-25T14:05:06Z

Popcorndude: Describe the algorithm

2019-06-26T20:01:38Z

Describe the algorithm

New page

=== Pseudocode ===
def checkForReduce(branch):
result = []
if it would be possible to shift another token to this branch:
result.append(copy(branch))
rule = get best rule from current transducer state (longest pattern, highest weight)
while rule != -1:
take the appropriate number of chunks off branch and pass them to the virtual machine
if the rule is rejected:
get the next best rule
else:
add the output to the output to the branch
update the transducer state
call checkForReduce()
append updated branch(es) to result
break
if result is empty:
result.append(branch)
return result

parseGraph = the parse stack (actually a directed graph in this case)
next = readToken()
while true:
add next to each branch of parseGraph, calling checkForReduce()
for each branch in parseGraph:
if the number of transducer states is 0:
discard branch
if parseGraph is empty:
output everything in the branch that had the fewest nodes
if there is a tie, choose the branch with the highest weight
if there is still a tie, choose the one that happens to be listed first
next = readToken()
if the input stream is now empty:
output next (it's a blank)
end

=== Notes ===
The premise of this algorithm is that the information contained in an LR parse table is also contained in the transducers generated by <code>apertium-preprocess-transfer</code>.

Since we allow incomplete parses, <code>ACCEPT</code> and <code>ERROR</code> are equivalent and both are represented by the transducer having no live states.

<code>SHIFT</code> is represented by an outgoing connection from the current state, and <code>REDUCE</code> is represented by the current node being final.

Since there are rules which generate different output in different situations as well as rules which generate multiple outputs, the simplest way do deal with them is to take the output of a reduction and act as if it were normal input. The result is that pattern matching is linear in the number of nodes in the tree, rather than being linear in just the leaves, but this increase appears to be cancelled out by the decrease in the amount of checking and rejecting that would have to be done in the virtual machine otherwise.

This algorithm currently branches on shift-reduce conflicts but not reduce-reduce conflicts. The reason for this is that it seemed to me like we had enough information to decide reduce-reduce conflicts by applying LRLM and it also limits the number of times we need to fork the stack, which helps with speed. If it is desired, I can change this, however.

The nice thing about checking for shift-reduce conflicts, is that if there is a possible reduction, the token on the top of the stack is definitely an LU or a chunk and if there is a conflicting shift, then the token to be shifted is definitely a blank, so we can check whether any shifts are possible by stepping the transducer forward by a space and checking whether there are any live states.

← Older revision		Revision as of 06:12, 1 June 2023
Line 53:		Line 53:

	Since reductions treat rule outputs as if they were inputs, I have allowed for the possibility of rules which output multiple nodes. The effect of such rules will probably in generally be to reorder the input without reducing, which will be useful for handling some clitics.		Since reductions treat rule outputs as if they were inputs, I have allowed for the possibility of rules which output multiple nodes. The effect of such rules will probably in generally be to reorder the input without reducing, which will be useful for handling some clitics.



			[[Category:Recursive transfer]]

@@ Line 1: / Line 1: @@
+A full walkthrough of parsing an output sentence can be found at [[Apertium-recursive/Example]].
 === Pseudocode ===
  def checkForReduce(branch):

← Older revision	Revision as of 20:12, 31 July 2019
(No difference)

@@ Line 16: / Line 16: @@
        break
    if result is empty:
+     result.append(branch)
+   else if the next non-blank in the input stream matches a lookahead path from the current transducer state:
      result.append(branch)
    return result
@@ Line 24: / Line 26: @@
    add next to each branch of parseGraph, calling checkForReduce()
    for each branch in parseGraph:
-     if the number of transducer states is 0:
+     if the number of live transducer states is 0:
+       discard branch
+     if another branch ends with a parse tree covering the same span of input and has a higher weight:
        discard branch
    if parseGraph is empty:
@@ Line 46: / Line 50: @@
 This algorithm currently branches on shift-reduce conflicts but not reduce-reduce conflicts. The reason for this is that it seemed to me like we had enough information to decide reduce-reduce conflicts by applying LRLM and it also limits the number of times we need to fork the stack, which helps with speed. If it is desired, I can change this, however.
+Since reductions treat rule outputs as if they were inputs, I have allowed for the possibility of rules which output multiple nodes. The effect of such rules will probably in generally be to reorder the input without reducing, which will be useful for handling some clitics.
-The nice thing about checking for shift-reduce conflicts, is that if there is a possible reduction, the token on the top of the stack is definitely an LU or a chunk and if there is a conflicting shift, then the token to be shifted is definitely a blank, so we can check whether any shifts are possible by stepping the transducer forward by a space and checking whether there are any live states.