Recursion, Regular Expressions, BNF(Backus-Naur Form grammar) and use of MAP

新開了一門外教課程，Object-oriented Programming(JAVA), 記錄一些學習經驗，以及部分和c++的差別感悟。

本文主要有三部分：

1. 遞歸的interesting point
2. 正規表達式
3. BNF grammar
4. map and set in JAVA的使用，與cpp的相似

Plus. BNF的規則為：< nonterminal symbol >::= < rule > | < rule > | < rule > | … | < rule >

比如：

< adjp >::=< adj >|< adj > < adjp >

< adj >::=big|small|black|wonderful

nonterminal symbol：一種描述語言文法的進階符号，根據文法規則可以将其轉化為其他非終端或終端符号

terminal：語言的基本符号

代碼即根據使用者指定的nonterminal symbol（必須是規定的幾種符号，其他符号抛異常）生成sentence。（讀取如上述規則以及scanner使用者輸入的client代碼在此文沒有給出）

import java.util.*;

public class GrammarSolver {

    private SortedMap<String, String[]> map;
    private Random rand;

    /**
     * building map of non-terminal to rules
     */
    public GrammarSolver(List<String> grammar){
        if(grammar.isEmpty()) { throw new IllegalArgumentException(); }
        
        map = new TreeMap<>();
        for (int i = 0; i < grammar.size(); i++)
        {
            // regex. map of non-terminal to rules
            String line[] = grammar.get(i).split("::=");
            if (map.containsKey(line[0])) { throw new IllegalArgumentException(); }
            String nonterSymbol = line[0];
            // regex. split rules to relu
            String rules[] = line[1].split("[|]");
            map.put(nonterSymbol,rules);
        }
        // use for chose rule.
        rand = new Random();
    }

    public boolean grammarContains(String symbol){
        return map.containsKey(symbol);
    }

    public String[] generate(String symbol,int times){
        if (!grammarContains(symbol) || times <= 0) { throw new IllegalArgumentException(); }

        String[] result = new String[times];
        for (int i = 0; i < times; i++)
        {
            String temp = recursion(symbol).trim();
            result[i] =  temp;
        }
        return result;
    }

    /**
     * recursion to find terminal. The keyidea like DFS but not use the stack.
     */
    private String recursion(String symbol){
        // stop condition
        if (!map.containsKey(symbol)) { return symbol+" "; }

        // chose random rule of rules.
        int equProbNum = this.rand.nextInt(map.get(symbol).length);
        String rule = map.get(symbol)[equProbNum];
        // regex. split space and tab. 
        //Plus. Maybe one rule include many non-terminals or terminals. So ruleList is used
        String ruleList[] = rule.split("[ \t]+");
        // recursion algorithm.
        StringBuilder res = new StringBuilder();
        for (int i =0; i < ruleList.length; i++)
        {
            res.append(recursion(ruleList[i]));
        }
        return res.toString();
    }

    public String getSymbols(){
        return map.keySet().toString();
    }
}
           

1. 遞歸的interesting point

   在c++中，這樣的題目更習慣去定義一個void的遞歸函數，然後用引用的方式去傳一個res的字元串，拼接結果。需要注意的是，java中用到了一個新的類需要new出來且初始化，c++中很多時候可以直接在棧空間玩。

   （比如vector< int > myarray; myarray.push_back(6);）

2. 正規表達式

   一種字元串比對的方法，比如我們想查找某種模式而不是某種特定字元的字元串。在java中split可以接收regex的參數來分割字元串，比如split("[ \t]+")指分割一個或多個空格orTab。此方法應該我個人了解在模式比對、檢測請求時常用（比如通信時必須按協定的格式發送資料，如果格式不對直接不接收或傳回資料格式錯誤的相應，比如輸入密碼時當我們不按某種規則輸入時會傳回格式錯誤（開頭大寫，必須包含字母和數字，不能用空格等等規則））

3. BNF grammar

   語言的文法規則

4. map and set in JAVA的使用，與C++的相似

   java中的Map接口，有TreeMap和HashMap等的實作方式。使用對标c++STL中map和unordered_map。