Recursion, Regular Expressions, BNF(Backus

Regular Expressions, BNF(Backus"/>

Recursion, Regular Expressions, BNF(Backus

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 rulesString line[] = grammar.get(i).split("::=");if (map.containsKey(line[0])) { throw new IllegalArgumentException(); }String nonterSymbol = line[0];// regex. split rules to reluString 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 conditionif (!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 usedString 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。