org.eclipse.xtext.util.formallang
Class PdaUtil

java.lang.Object
  org.eclipse.xtext.util.formallang.PdaUtil

public class PdaUtil
extends java.lang.Object

Author:

Moritz Eysholdt - Initial contribution and API

Nested Class Summary

protected static class	PdaUtil.IsPop<S,P>
protected class	PdaUtil.StackItem<T>
protected class	PdaUtil.TraceItem<S,P>

Field Summary

protected NfaUtil	nfaUtil
long	UNREACHABLE

Constructor Summary

PdaUtil()

Method Summary

<S,P> boolean	canReach(Pda<S,P> pda, S state, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
protected <T> PdaUtil.StackItem<T>	createStack(java.util.Iterator<T> stack)
<S,P> long	distanceTo(Pda<S,P> pda, java.lang.Iterable<S> starts, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
<S,P> Nfa<S>	filterUnambiguousPaths(Pda<S,P> pda)
protected <S,P> void	filterUnambiguousPaths(Pda<S,P> pda, S state, java.util.Map<S,java.lang.Integer> dist, java.util.Map<S,java.util.List<S>> followers)
<S,P> java.util.List<S>	shortestPathTo(Pda<S,P> pda, java.lang.Iterable<S> starts, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
<S,P> java.util.List<S>	shortestPathTo(Pda<S,P> pda, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches)
<S,P> java.util.List<S>	shortestPathTo(Pda<S,P> pda, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
<S,P> java.util.List<S>	shortestPathTo(Pda<S,P> pda, java.util.Iterator<P> stack, S match)
<S,P> java.util.List<S>	shortestPathTo(Pda<S,P> pda, S start, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
<S,P> java.util.List<S>	shortestPathToFinalState(Pda<S,P> pda, java.util.Iterator<P> stack)
<S,P> java.util.List<S>	shortestStackpruningPathTo(Pda<S,P> pda, java.lang.Iterable<S> starts, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
<S,P> java.util.List<S>	shortestStackpruningPathTo(Pda<S,P> pda, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches)
<S,P> java.util.List<S>	shortestStackpruningPathTo(Pda<S,P> pda, java.util.Iterator<P> stack, S matches)
<S,P> java.util.List<S>	shortestStackpruningPathTo(Pda<S,P> pda, S start, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
protected <S,P> PdaUtil.TraceItem<S,P>	trace(Pda<S,P> pda, java.lang.Iterable<S> starts, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
protected <S,P> PdaUtil.TraceItem<S,P>	traceToWithPruningStack(Pda<S,P> pda, java.lang.Iterable<S> starts, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

nfaUtil

@Inject
protected NfaUtil nfaUtil

UNREACHABLE

public final long UNREACHABLE

See Also:

Constant Field Values

Constructor Detail

PdaUtil

public PdaUtil()

Method Detail

canReach

public <S,P> boolean canReach(Pda<S,P> pda,
                              S state,
                              java.util.Iterator<P> stack,
                              com.google.common.base.Predicate<S> matches,
                              com.google.common.base.Predicate<S> canPass)

createStack

protected <T> PdaUtil.StackItem<T> createStack(java.util.Iterator<T> stack)

distanceTo

public <S,P> long distanceTo(Pda<S,P> pda,
                             java.lang.Iterable<S> starts,
                             java.util.Iterator<P> stack,
                             com.google.common.base.Predicate<S> matches,
                             com.google.common.base.Predicate<S> canPass)

filterUnambiguousPaths

public <S,P> Nfa<S> filterUnambiguousPaths(Pda<S,P> pda)

filterUnambiguousPaths

protected <S,P> void filterUnambiguousPaths(Pda<S,P> pda,
                                            S state,
                                            java.util.Map<S,java.lang.Integer> dist,
                                            java.util.Map<S,java.util.List<S>> followers)

shortestPathTo

public <S,P> java.util.List<S> shortestPathTo(Pda<S,P> pda,
                                              java.lang.Iterable<S> starts,
                                              java.util.Iterator<P> stack,
                                              com.google.common.base.Predicate<S> matches,
                                              com.google.common.base.Predicate<S> canPass)

shortestPathTo

public <S,P> java.util.List<S> shortestPathTo(Pda<S,P> pda,
                                              java.util.Iterator<P> stack,
                                              com.google.common.base.Predicate<S> matches)

shortestPathTo

public <S,P> java.util.List<S> shortestPathTo(Pda<S,P> pda,
                                              java.util.Iterator<P> stack,
                                              com.google.common.base.Predicate<S> matches,
                                              com.google.common.base.Predicate<S> canPass)

shortestPathTo

public <S,P> java.util.List<S> shortestPathTo(Pda<S,P> pda,
                                              java.util.Iterator<P> stack,
                                              S match)

shortestPathTo

public <S,P> java.util.List<S> shortestPathTo(Pda<S,P> pda,
                                              S start,
                                              java.util.Iterator<P> stack,
                                              com.google.common.base.Predicate<S> matches,
                                              com.google.common.base.Predicate<S> canPass)

shortestPathToFinalState

public <S,P> java.util.List<S> shortestPathToFinalState(Pda<S,P> pda,
                                                        java.util.Iterator<P> stack)

shortestStackpruningPathTo

public <S,P> java.util.List<S> shortestStackpruningPathTo(Pda<S,P> pda,
                                                          java.lang.Iterable<S> starts,
                                                          java.util.Iterator<P> stack,
                                                          com.google.common.base.Predicate<S> matches,
                                                          com.google.common.base.Predicate<S> canPass)

shortestStackpruningPathTo

public <S,P> java.util.List<S> shortestStackpruningPathTo(Pda<S,P> pda,
                                                          java.util.Iterator<P> stack,
                                                          com.google.common.base.Predicate<S> matches)

shortestStackpruningPathTo

public <S,P> java.util.List<S> shortestStackpruningPathTo(Pda<S,P> pda,
                                                          java.util.Iterator<P> stack,
                                                          S matches)

shortestStackpruningPathTo

public <S,P> java.util.List<S> shortestStackpruningPathTo(Pda<S,P> pda,
                                                          S start,
                                                          java.util.Iterator<P> stack,
                                                          com.google.common.base.Predicate<S> matches,
                                                          com.google.common.base.Predicate<S> canPass)

trace

protected <S,P> PdaUtil.TraceItem<S,P> trace(Pda<S,P> pda,
                                             java.lang.Iterable<S> starts,
                                             java.util.Iterator<P> stack,
                                             com.google.common.base.Predicate<S> matches,
                                             com.google.common.base.Predicate<S> canPass)

traceToWithPruningStack

protected <S,P> PdaUtil.TraceItem<S,P> traceToWithPruningStack(Pda<S,P> pda,
                                                               java.lang.Iterable<S> starts,
                                                               java.util.Iterator<P> stack,
                                                               com.google.common.base.Predicate<S> matches,
                                                               com.google.common.base.Predicate<S> canPass)