SHARE
TWEET

Untitled

a guest Sep 11th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package br.ufpe.cin.if688.table;
  2.  
  3. import java.util.HashMap;
  4. import java.util.List;
  5. import java.util.Map;
  6. import java.util.Map.Entry;
  7. import java.util.Set;
  8.  
  9. import br.ufpe.cin.if688.parsing.analysis.GeneralSymbol;
  10. import br.ufpe.cin.if688.parsing.analysis.SetGenerator;
  11. import br.ufpe.cin.if688.parsing.analysis.SpecialSymbol;
  12. import br.ufpe.cin.if688.parsing.grammar.Grammar;
  13. import br.ufpe.cin.if688.parsing.grammar.Nonterminal;
  14. import br.ufpe.cin.if688.parsing.grammar.Production;
  15. import br.ufpe.cin.if688.parsing.grammar.Terminal;
  16.  
  17. public final class Table {
  18.  
  19.     private Table() {
  20.     }
  21.  
  22.     public static Map<LL1Key, List<GeneralSymbol>> createTable(Grammar g) throws NotLL1Exception {
  23.         if (g == null) {
  24.             throw new NullPointerException();
  25.         }
  26.  
  27.         // Conjuntos de FIRST e FOLLOW da gramática
  28.         Map<Nonterminal, Set<GeneralSymbol>> first = SetGenerator.getFirst(g);
  29.         Map<Nonterminal, Set<GeneralSymbol>> follow = SetGenerator.getFollow(g, first);
  30.  
  31.         Map<LL1Key, List<GeneralSymbol>> parsingTable = new HashMap<LL1Key, List<GeneralSymbol>>();
  32.  
  33.         // Mapeamento auxiliando na identificação de células da tabela
  34.         Map<Nonterminal, Map<GeneralSymbol, LL1Key>> mapping = new HashMap<Nonterminal, Map<GeneralSymbol, LL1Key>>();
  35.         for (Nonterminal nonterminal : g.getNonterminals()) {
  36.             mapping.put(nonterminal, new HashMap<GeneralSymbol, LL1Key>());
  37.  
  38.             for (Terminal terminal : g.getTerminals()) {
  39.                 LL1Key key = new LL1Key(nonterminal, terminal);
  40.  
  41.                 Map<GeneralSymbol, LL1Key> row = mapping.get(nonterminal);
  42.                 row.put(terminal, key);
  43.             }
  44.  
  45.             LL1Key key = new LL1Key(nonterminal, SpecialSymbol.EOF);
  46.  
  47.             Map<GeneralSymbol, LL1Key> row = mapping.get(nonterminal);
  48.             row.put(SpecialSymbol.EOF, key);
  49.         }
  50.  
  51.         // Verifica em quais células cada produção se encaixa
  52.         for (Production production : g.getProductions()) {
  53.             Nonterminal nonterminal = production.getNonterminal();
  54.  
  55.             Map<GeneralSymbol, LL1Key> row = mapping.get(nonterminal);
  56.             Map<LL1Key, GeneralSymbol> cells = new HashMap<LL1Key, GeneralSymbol>(); // Guarda as células que serão preenchidas
  57.  
  58.             // Itera sobre os símbolos da produção
  59.             List<GeneralSymbol> symbols = production.getProduction();
  60.             for (int c = 0; c < symbols.size(); c++) {
  61.                 GeneralSymbol symbol = symbols.get(c);
  62.  
  63.                 // A produção entra na célula de todos os símbolos presentes em seu FIRST
  64.                 if (symbol instanceof Terminal) {
  65.                     LL1Key cell = row.get(symbol);
  66.  
  67.                     cells.put(cell, symbol);
  68.  
  69.                     break; // Encerra a produção ao encontrar um terminal
  70.                 } else if (symbol instanceof Nonterminal) {
  71.                     // Em caso de não-terminal encontrado, adicionar a produção em todas as células presentes no FIRST do não-terminal
  72.                     for (GeneralSymbol symbolFirst : first.get(symbol)) {
  73.                         if (symbolFirst != SpecialSymbol.EPSILON) {
  74.                             LL1Key cell = row.get(symbolFirst);
  75.  
  76.                             cells.put(cell, symbolFirst);
  77.                         } else if (c + 1 == symbols.size()) { // Caso EPSILON esteja presente, a produção é colocada em todas as células presentes no FOLLOW
  78.                             for (GeneralSymbol symbolFollow : follow.get(nonterminal)) {
  79.                                 LL1Key cell = row.get(symbolFollow);
  80.  
  81.                                 cells.put(cell, symbolFollow);
  82.                             }
  83.                         }
  84.                     }
  85.  
  86.                     if (!first.get(symbol).contains(SpecialSymbol.EPSILON)) {
  87.                         break; // Encerra a produção ao encontrar um não-terminal sem EPSILON em seu FIRST
  88.                     }
  89.                 } else { // EPSILON apenas. Coloca a produção em todas as células presentes no FOLLOW
  90.                     for (GeneralSymbol symbolFollow : follow.get(nonterminal)) {
  91.                         LL1Key cell = row.get(symbolFollow);
  92.  
  93.                         cells.put(cell, symbolFollow);
  94.                     }
  95.                 }
  96.             }
  97.  
  98.             // Define as produções na parsing table
  99.             for (Entry<LL1Key, GeneralSymbol> entry : cells.entrySet()) {
  100.                 LL1Key cell = entry.getKey();
  101.                 GeneralSymbol symbol = entry.getValue();
  102.  
  103.                 if (parsingTable.containsKey(cell)) { // Caso a célula já tenha conteúdo, não será LL1
  104.                     Production production2 = new Production(nonterminal, parsingTable.get(cell));
  105.  
  106.                     throw new NotLL1Exception(String.format("Table cell (%s,%s) has two productions. (%s) (%s)", nonterminal, symbol, production, production2));
  107.                 } else {
  108.                     parsingTable.put(row.get(symbol), symbols);
  109.                 }
  110.             }
  111.         }
  112.  
  113.         return parsingTable;
  114.     }
  115.  
  116.     // Imprime a parsing table formatada (experimental)
  117.     @SuppressWarnings("unused")
  118.     private void printParsingTable(Grammar g, Map<LL1Key, List<GeneralSymbol>> parsingTable, Map<Nonterminal, Map<GeneralSymbol, LL1Key>> mapping) {
  119.         System.out.printf("%-20s", "");
  120.         for (Terminal terminal : g.getTerminals()) {
  121.             System.out.printf("%-20s", terminal);
  122.         }
  123.         System.out.printf("$\n");
  124.  
  125.         for (Nonterminal nonterminal : g.getNonterminals()) {
  126.             System.out.printf("%-20s", nonterminal);
  127.             for (Terminal terminal : g.getTerminals()) {
  128.                 if (mapping.containsKey(nonterminal) && mapping.get(nonterminal).containsKey(terminal)) {
  129.                     if (parsingTable.get(mapping.get(nonterminal).get(terminal)) != null) {
  130.                         System.out.printf("%-20s", parsingTable.get(mapping.get(nonterminal).get(terminal)));
  131.                     } else {
  132.                         System.out.printf("%-20s", "");
  133.                     }
  134.                 } else {
  135.                     System.out.printf("%-20s", "");
  136.                 }
  137.             }
  138.             if (mapping.containsKey(nonterminal) && mapping.get(nonterminal).containsKey(SpecialSymbol.EOF)) {
  139.                 if (parsingTable.get(mapping.get(nonterminal).get(SpecialSymbol.EOF)) != null) {
  140.                     System.out.printf("%-20s", parsingTable.get(mapping.get(nonterminal).get(SpecialSymbol.EOF)));
  141.                 } else {
  142.                     System.out.printf("%-20s", "");
  143.                 }
  144.             } else {
  145.                 System.out.printf("%-20s", "");
  146.             }
  147.             System.out.println();
  148.         }
  149.  
  150.         System.out.println();
  151.         System.out.println();
  152.         System.out.println();
  153.         System.out.println();
  154.     }
  155.  
  156. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top