straightline/src/main/java/org/poormanscastle/studies/compilers/utils/grammartools/ll1/LL1Grammar.java
/**
     * creates the first sets and follow sets for all symbols and productions. As needed for LL grammars.
     */
creates the first sets and follow sets for all symbols and productions. As needed for LL grammars.
creates the first sets and follow sets for all symbols and productions . As needed for LL grammars .
public void calculateStartAndFollowSets() {
        for (Symbol symbol : terminalSymbols) {
            checkState(symbol.isTerminal());
            symbol.addToFirstSet(symbol);
        }
        boolean tablesWereUpdated = false;
        do {
            tablesWereUpdated = false;
            for (Production production : productions) {
                boolean visibleFirstX = true;
                for (int i = 0; i < production.getRhs().size(); i++) {
                    Symbol symbol = production.getRhs().get(i);
                    if (visibleFirstX 
                            && (!production.getLhs().getFirstSet().containsAll(symbol.getFirstSet())
                            || !production.getFirstSet().containsAll(symbol.getFirstSet()))) {
                        production.getLhs().getFirstSet().addAll(symbol.getFirstSet());
                        production.getFirstSet().addAll(symbol.getFirstSet());
                        tablesWereUpdated = true;
                    }
                    visibleFirstX &= symbol.isNullable();
                    boolean visibleFollowX = true;
                    for (int j = i + 1; j < production.getRhs().size(); j++) {
                        if (!symbol.getFollowSet().containsAll(production.getRhs().get(j).getFirstSet())) {
                            symbol.getFollowSet().addAll(production.getRhs().get(j).getFirstSet());
                            tablesWereUpdated = true;
                        }
                        if (!(visibleFollowX &= production.getRhs().get(j).isNullable())) {
                            break;
                        }
                    }
                    if (visibleFollowX && !symbol.getFollowSet().containsAll(production.getLhs().getFollowSet())) {
                        symbol.getFollowSet().addAll(production.getLhs().getFollowSet());
                        tablesWereUpdated = true;
                    }
                }
            }
        } while (tablesWereUpdated);
    }
public void calculateStartAndFollowSets ( ) { for ( Symbol symbol : terminalSymbols ) { checkState ( symbol . isTerminal ( ) ) ; symbol . addToFirstSet ( symbol ) ; } boolean tablesWereUpdated = false ; do { tablesWereUpdated = false ; for ( Production production : productions ) { boolean visibleFirstX = true ; for ( int i = 0 ; i < production . getRhs ( ) . size ( ) ; i ++ ) { Symbol symbol = production . getRhs ( ) . get ( i ) ; if ( visibleFirstX && ( ! production . getLhs ( ) . getFirstSet ( ) . containsAll ( symbol . getFirstSet ( ) ) || ! production . getFirstSet ( ) . containsAll ( symbol . getFirstSet ( ) ) ) ) { production . getLhs ( ) . getFirstSet ( ) . addAll ( symbol . getFirstSet ( ) ) ; production . getFirstSet ( ) . addAll ( symbol . getFirstSet ( ) ) ; tablesWereUpdated = true ; } visibleFirstX &= symbol . isNullable ( ) ; boolean visibleFollowX = true ; for ( int j = i + 1 ; j < production . getRhs ( ) . size ( ) ; j ++ ) { if ( ! symbol . getFollowSet ( ) . containsAll ( production . getRhs ( ) . get ( j ) . getFirstSet ( ) ) ) { symbol . getFollowSet ( ) . addAll ( production . getRhs ( ) . get ( j ) . getFirstSet ( ) ) ; tablesWereUpdated = true ; } if ( ! ( visibleFollowX &= production . getRhs ( ) . get ( j ) . isNullable ( ) ) ) { break ; } } if ( visibleFollowX && ! symbol . getFollowSet ( ) . containsAll ( production . getLhs ( ) . getFollowSet ( ) ) ) { symbol . getFollowSet ( ) . addAll ( production . getLhs ( ) . getFollowSet ( ) ) ; tablesWereUpdated = true ; } } } } while ( tablesWereUpdated ) ; }
creates the first sets and follow sets for all symbols and productions.
creates the first sets and follow sets for all symbols and productions .
// take care of the terminal symbols: // for all terminal symbols s: first(s) <- {s} // the algorithm is repeated until the tables do not change for a whole iteration. // go through rhs and do some set algebra // visible says if all rhs symbols up to now where nullable and the // current symbol is relevant for first(X) in X -> c1 ... ci ... ck // impact of symbol.firstSet on X.firstSet. // also, production.firstSet gets updated // the next two checks are to avoid tablesWereUpdated=true when all is aleady set. // impact of X.followSet on symbol.FollowSet // if all symbols between si and the end of the production's rhs are nullable, // add follow(X) to follow(si).