<commit_before>package grammar;

import java.io.IOException;
import java.util.*;

import helper.SyntaxHelper;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import token.*;

public class Grammar {

    // Logger
    private Logger l = LogManager.getFormatterLogger(getClass());

    // Variables
    private Map<String, List<List<AbstractSyntaxToken>>> productions;
    private Map<List<AbstractSyntaxToken>, Set<String>> ruleFirstSetMap;
    private Map<String, Set<String>> followSetMap;
    private String start;
    private Set<String> terminals;

    /**
     * Create grammar from file
     * @param file
     */
    public Grammar(String file) {

        try {

            // Init variables
            productions = new LinkedHashMap<>();
            ruleFirstSetMap = new HashMap<>();
            followSetMap = new HashMap<>();
            terminals = new HashSet<>();
            start = null;

            // Add EOS to terminal
            terminals.add(SyntaxHelper.END_OF_STACK);

            // Parse file
            parse(file);

            // Computer first
            computeFirst();
            l.info("First sets: %s", ruleFirstSetMap.toString());

            // Computer follow
            computeFollow();
            l.info("Follow sets: %s", followSetMap.toString());

        } catch (IOException e) {
            l.error(e.getMessage());
        }
    }

    /**
     * Get terminals
     * @return set of terminals
     */
    public Set<String> getTerminals() {
        return terminals;
    }

    /**
     * Get non terminals
     * @return set of non-terminals
     */
    public Set<String> getNonTerminals() {
        return productions.keySet();
    }

    /**
     * Get productions
     * @return productions map
     */
    public Map<String, List<List<AbstractSyntaxToken>>> getProductions() {
        return this.productions;
    }

    /**
     * Get first set map
     * @return first set map
     */
    public Map<List<AbstractSyntaxToken>, Set<String>> getRuleFirstSetMap() {
        return this.ruleFirstSetMap;
    }

    /**
     * Get follow set map
     * @return follow set map
     */
    public Map<String, Set<String>> getFollowSetMap() {
        return this.followSetMap;
    }

    /**
     * Compute the First set of all Non-Terminals
     */
    private void computeFirst() {

        // Rules iterator
        Iterator<Map.Entry<String, List<List<AbstractSyntaxToken>>>> it = productions.entrySet().iterator();

        // While more rules
        while (it.hasNext()) {
            computeFirst(SyntaxTokenFactory.createNonTerminalToken(it.next().getKey()));
        }
    }

    /**
     * Compute the first set of a non terminal recursively
     * @param token
     * @return first set of a non-terminal
     */
    private Set<String> computeFirst(AbstractSyntaxToken token) {

        // Optimize
        Set<String> tokenFirstSet = getFirstSetOf(token);
        if(token instanceof NonTerminalToken && !tokenFirstSet.isEmpty())
            return tokenFirstSet;

        // Get RHS
        List<List<AbstractSyntaxToken>> RHS = productions.get(token.getValue());

        // Loop on all productions
        for(List<AbstractSyntaxToken> production : RHS) {

            // Calculate first set for each rule
            Set<String> firstSet = new HashSet<>();

            // Loop on production tokens
            for(AbstractSyntaxToken syntaxToken : production) {

                // If terminal or epsilon
                if(syntaxToken instanceof TerminalToken || syntaxToken instanceof EpsilonToken) {
                    firstSet.add(syntaxToken.getValue());
                    break;

                } else if(syntaxToken instanceof NonTerminalToken) {

                    // Get first of token
                    Set<String> syntaxTokenFirstSet = computeFirst(syntaxToken);

                    // If doesn't have epsilon, or last token in the production
                    if(!syntaxTokenFirstSet.contains(SyntaxHelper.EPSILON) || syntaxToken == production.get(production.size()-1)) {

                        // Superset
                        firstSet.addAll(syntaxTokenFirstSet);

                        // Don't try next token
                        break;

                    } else {

                        // Superset minus epsilon
                        for(String str : syntaxTokenFirstSet) {
                            if (!str.equals(SyntaxHelper.EPSILON)) {
                                firstSet.add(str);
                            }
                        }
                    }
                }
            }

            // Add first set
            ruleFirstSetMap.put(production, firstSet);
        }

        // Get first set
        return getFirstSetOf(token);
    }


    /**
     * Compute the Follow set of all Non-Terminals
     */
    private void computeFollow() {

        // Loop on non terminals and init empty sets
        for(String nonTerminal : productions.keySet()) {
            followSetMap.put(nonTerminal, new HashSet<>());
        }

        // Add EOS to follow set of start token
        followSetMap.get(start).add(SyntaxHelper.END_OF_STACK);

        // Repeat the computation multiple times
        for (int repeatX = 0; repeatX < productions.size(); ++repeatX) {

            // Rules iterator
            Iterator<Map.Entry<String, List<List<AbstractSyntaxToken>>>> it = productions.entrySet().iterator();<commit_msg>Fixed left recursion problem in compute First Set<commit_after>package grammar;

import java.io.IOException;
import java.util.*;

import helper.SyntaxHelper;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import token.*;

public class Grammar {

    // Logger
    private Logger l = LogManager.getFormatterLogger(getClass());

    // Variables
    private Map<String, List<List<AbstractSyntaxToken>>> productions;
    private Map<List<AbstractSyntaxToken>, Set<String>> ruleFirstSetMap;
    private Map<String, Set<String>> followSetMap;
    private String start;
    private Set<String> terminals;

    /**
     * Create grammar from file
     * @param file
     */
    public Grammar(String file) {

        try {

            // Init variables
            productions = new LinkedHashMap<>();
            ruleFirstSetMap = new HashMap<>();
            followSetMap = new HashMap<>();
            terminals = new HashSet<>();
            start = null;

            // Add EOS to terminal
            terminals.add(SyntaxHelper.END_OF_STACK);

            // Parse file
            parse(file);

            // Computer first
            computeFirst();
            l.info("First sets: %s", ruleFirstSetMap.toString());

            // Computer follow
            computeFollow();
            l.info("Follow sets: %s", followSetMap.toString());

        } catch (IOException e) {
            l.error(e.getMessage());
        }
    }

    /**
     * Get terminals
     * @return set of terminals
     */
    public Set<String> getTerminals() {
        return terminals;
    }

    /**
     * Get non terminals
     * @return set of non-terminals
     */
    public Set<String> getNonTerminals() {
        return productions.keySet();
    }

    /**
     * Get productions
     * @return productions map
     */
    public Map<String, List<List<AbstractSyntaxToken>>> getProductions() {
        return this.productions;
    }

    /**
     * Get first set map
     * @return first set map
     */
    public Map<List<AbstractSyntaxToken>, Set<String>> getRuleFirstSetMap() {
        return this.ruleFirstSetMap;
    }

    /**
     * Get follow set map
     * @return follow set map
     */
    public Map<String, Set<String>> getFollowSetMap() {
        return this.followSetMap;
    }

    /**
     * Compute the First set of all Non-Terminals
     */
    private void computeFirst() {

        // Initialize an empty set for each production in the grammar
        for (List<List<AbstractSyntaxToken>> productionList : productions.values()) {
            for(List<AbstractSyntaxToken> production : productionList) {
                ruleFirstSetMap.put(production, new HashSet<>());
            }
        }

        // Repeat the computation multiple times
        for (int repeatX = 0; repeatX < productions.size(); ++repeatX) {

            // Loop on all productions LHS
            for (String LHS : productions.keySet()) {

                // Get RHS
                List<List<AbstractSyntaxToken>> RHS = productions.get(LHS);

                // Loop on all productions
                for(List<AbstractSyntaxToken> production : RHS) {

                    // Calculate first set for each rule
                    Set<String> firstSet = ruleFirstSetMap.get(production);

                    // Loop on production tokens
                    for(AbstractSyntaxToken syntaxToken : production) {

                        // If terminal or epsilon
                        if(syntaxToken instanceof TerminalToken || syntaxToken instanceof EpsilonToken) {
                            firstSet.add(syntaxToken.getValue());
                            break;

                        } else if(syntaxToken instanceof NonTerminalToken) {

                            // Get first of token
                            Set<String> syntaxTokenFirstSet = getFirstSetOf(syntaxToken);

                            // If doesn't have epsilon, or last token in the production
                            if(!syntaxTokenFirstSet.contains(SyntaxHelper.EPSILON) || syntaxToken == production.get(production.size()-1)) {

                                // Superset
                                firstSet.addAll(syntaxTokenFirstSet);

                                // Don't try next token
                                break;

                            } else {

                                // Superset minus epsilon
                                for(String str : syntaxTokenFirstSet) {
                                    if (!str.equals(SyntaxHelper.EPSILON)) {
                                        firstSet.add(str);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    /**
     * Compute the Follow set of all Non-Terminals
     */
    private void computeFollow() {

        // Loop on non terminals and init empty sets
        for(String nonTerminal : productions.keySet()) {
            followSetMap.put(nonTerminal, new HashSet<>());
        }

        // Add EOS to follow set of start token
        followSetMap.get(start).add(SyntaxHelper.END_OF_STACK);

        // Repeat the computation multiple times
        for (int repeatX = 0; repeatX < productions.size(); ++repeatX) {

            // Rules iterator
            Iterator<Map.Entry<String, List<List<AbstractSyntaxToken>>>> it = productions.entrySet().iterator();
{'fraction_non_alphanumeric': 0.09712262866479078, 'fraction_numerical': 0.0008169193065262776, 'mean_word_length': 1.6434740882917467, 'pattern_counts': {'":': 0, '<': 83, '<?xml version=': 0, '>': 80, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2489366', 'n_tokens_mistral': 2838, 'n_tokens_neox': 2636, 'n_words': 695}