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。