Home | History | Annotate | Download | only in analysis 
      1 /*
      2  * [The "BSD license"]
      3  *  Copyright (c) 2010 Terence Parr
      4  *  All rights reserved.
      5  *
      6  *  Redistribution and use in source and binary forms, with or without
      7  *  modification, are permitted provided that the following conditions
      8  *  are met:
      9  *  1. Redistributions of source code must retain the above copyright
     10  *      notice, this list of conditions and the following disclaimer.
     11  *  2. Redistributions in binary form must reproduce the above copyright
     12  *      notice, this list of conditions and the following disclaimer in the
     13  *      documentation and/or other materials provided with the distribution.
     14  *  3. The name of the author may not be used to endorse or promote products
     15  *      derived from this software without specific prior written permission.
     16  *
     17  *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     18  *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     19  *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     20  *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     21  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     22  *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     26  *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27  */
     28 package org.antlr.analysis;
     29 
     30 import org.antlr.grammar.v3.ANTLRParser;
     31 import org.antlr.misc.IntervalSet;
     32 import org.antlr.misc.MultiMap;
     33 
     34 import java.util.Collections;
     35 import java.util.Iterator;
     36 import java.util.List;
     37 
     38 /** A special DFA that is exactly LL(1) or LL(1) with backtracking mode
     39  *  predicates to resolve edge set collisions.
     40  */
     41 public class LL1DFA extends DFA {
     42 	/** From list of lookahead sets (one per alt in decision), create
     43 	 *  an LL(1) DFA.  One edge per set.
     44 	 *
     45 	 *  s0-{alt1}->:o=>1
     46 	 *  | \
     47 	 *  |  -{alt2}->:o=>2
     48 	 *  |
     49 	 *  ...
     50 	 */
     51 	public LL1DFA(int decisionNumber, NFAState decisionStartState, LookaheadSet[] altLook) {
     52 		DFAState s0 = newState();
     53 		startState = s0;
     54 		nfa = decisionStartState.nfa;
     55 		nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(decisionStartState);
     56 		this.decisionNumber = decisionNumber;
     57 		this.decisionNFAStartState = decisionStartState;
     58 		initAltRelatedInfo();
     59 		unreachableAlts = null;
     60 		for (int alt=1; alt<altLook.length; alt++) {
     61 			DFAState acceptAltState = newState();
     62 			acceptAltState.acceptState = true;
     63 			setAcceptState(alt, acceptAltState);
     64 			acceptAltState.k = 1;
     65 			acceptAltState.cachedUniquelyPredicatedAlt = alt;
     66 			Label e = getLabelForSet(altLook[alt].tokenTypeSet);
     67 			s0.addTransition(acceptAltState, e);
     68 		}
     69 	}
     70 
     71 	/** From a set of edgeset->list-of-alts mappings, create a DFA
     72 	 *  that uses syn preds for all |list-of-alts|>1.
     73 	 */
     74 	public LL1DFA(int decisionNumber,
     75 				  NFAState decisionStartState,
     76 				  MultiMap<IntervalSet, Integer> edgeMap)
     77 	{
     78 		DFAState s0 = newState();
     79 		startState = s0;
     80 		nfa = decisionStartState.nfa;
     81 		nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(decisionStartState);
     82 		this.decisionNumber = decisionNumber;
     83 		this.decisionNFAStartState = decisionStartState;
     84 		initAltRelatedInfo();
     85 		unreachableAlts = null;
     86 		for (Iterator it = edgeMap.keySet().iterator(); it.hasNext();) {
     87 			IntervalSet edge = (IntervalSet)it.next();
     88 			List<Integer> alts = edgeMap.get(edge);
     89 			Collections.sort(alts); // make sure alts are attempted in order
     90 			//System.out.println(edge+" -> "+alts);
     91 			DFAState s = newState();
     92 			s.k = 1;
     93 			Label e = getLabelForSet(edge);
     94 			s0.addTransition(s, e);
     95 			if ( alts.size()==1 ) {
     96 				s.acceptState = true;
     97 				int alt = alts.get(0);
     98 				setAcceptState(alt, s);
     99 				s.cachedUniquelyPredicatedAlt = alt;
    100 			}
    101 			else {
    102 				// resolve with syntactic predicates.  Add edges from
    103 				// state s that test predicates.
    104 				s.resolvedWithPredicates = true;
    105 				for (int i = 0; i < alts.size(); i++) {
    106 					int alt = (int)alts.get(i);
    107 					s.cachedUniquelyPredicatedAlt =	NFA.INVALID_ALT_NUMBER;
    108 					DFAState predDFATarget = getAcceptState(alt);
    109 					if ( predDFATarget==null ) {
    110 						predDFATarget = newState(); // create if not there.
    111 						predDFATarget.acceptState = true;
    112 						predDFATarget.cachedUniquelyPredicatedAlt =	alt;
    113 						setAcceptState(alt, predDFATarget);
    114 					}
    115 					// add a transition to pred target from d
    116 					/*
    117 					int walkAlt =
    118 						decisionStartState.translateDisplayAltToWalkAlt(alt);
    119 					NFAState altLeftEdge = nfa.grammar.getNFAStateForAltOfDecision(decisionStartState, walkAlt);
    120 					NFAState altStartState = (NFAState)altLeftEdge.transition[0].target;
    121 					SemanticContext ctx = nfa.grammar.ll1Analyzer.getPredicates(altStartState);
    122 					System.out.println("sem ctx = "+ctx);
    123 					if ( ctx == null ) {
    124 						ctx = new SemanticContext.TruePredicate();
    125 					}
    126 					s.addTransition(predDFATarget, new Label(ctx));
    127 					*/
    128 					SemanticContext.Predicate synpred =
    129 						getSynPredForAlt(decisionStartState, alt);
    130 					if ( synpred == null ) {
    131 						synpred = new SemanticContext.TruePredicate();
    132 					}
    133 					s.addTransition(predDFATarget, new PredicateLabel(synpred));
    134 				}
    135 			}
    136 		}
    137 		//System.out.println("dfa for preds=\n"+this);
    138 	}
    139 
    140 	protected Label getLabelForSet(IntervalSet edgeSet) {
    141 		Label e = null;
    142 		int atom = edgeSet.getSingleElement();
    143 		if ( atom != Label.INVALID ) {
    144 			e = new Label(atom);
    145 		}
    146 		else {
    147 			e = new Label(edgeSet);
    148 		}
    149 		return e;
    150 	}
    151 
    152 	protected SemanticContext.Predicate getSynPredForAlt(NFAState decisionStartState,
    153 														 int alt)
    154 	{
    155 		int walkAlt =
    156 			decisionStartState.translateDisplayAltToWalkAlt(alt);
    157 		NFAState altLeftEdge =
    158 			nfa.grammar.getNFAStateForAltOfDecision(decisionStartState, walkAlt);
    159 		NFAState altStartState = (NFAState)altLeftEdge.transition[0].target;
    160 		//System.out.println("alt "+alt+" start state = "+altStartState.stateNumber);
    161 		if ( altStartState.transition[0].isSemanticPredicate() ) {
    162 			SemanticContext ctx = altStartState.transition[0].label.getSemanticContext();
    163 			if ( ctx.isSyntacticPredicate() ) {
    164 				SemanticContext.Predicate p = (SemanticContext.Predicate)ctx;
    165 				if ( p.predicateAST.getType() == ANTLRParser.BACKTRACK_SEMPRED ) {
    166 					/*
    167 					System.out.println("syn pred for alt "+walkAlt+" "+
    168 									   ((SemanticContext.Predicate)altStartState.transition[0].label.getSemanticContext()).predicateAST);
    169 					*/
    170 					if ( ctx.isSyntacticPredicate() ) {
    171 						nfa.grammar.synPredUsedInDFA(this, ctx);
    172 					}
    173 					return (SemanticContext.Predicate)altStartState.transition[0].label.getSemanticContext();
    174 				}
    175 			}
    176 		}
    177 		return null;
    178 	}
    179 }
    180