1 正则表达式
1 最基础：
要找一个数字，它可能有一个负号在前面，那么就写上一个负号加上一个问号： -?
在JAVA中，\\的意思是“我要插入一个正则表达式的反斜线，表示其后的字符具有特殊的意义”，所以要描述一个整数，正则表达式应该是： \\d。同理，要插入一个普通的反斜线，则应该是：\\\\。
要表示“一个或多个之前的表达式”，应该使用：+
综上，要表示“可能有一个负号，后面跟着一位或多位数字”，可以这样： -?\\d+.
使用正则表达式的最简单途径——String类的内建功能：
匹配：“-1234”.matches("-?\\d+");
切分：split()方法，将字符串从正则表达式匹配的地方切开。string.split("n\\W+"); 表示字母n后面跟着一个或多个非单词字符。被匹配的字符串是不出现在切分结果中的。
替换：替换正则表达式第一个匹配的子串，或是替换所有匹配的地方。 s.replaceFirst("f\\w+","located"); s.replaceAll(“shrubbery|tree|herring”,"banana");
如果正则表达式不是只使用一次的话，非String对象的正则表达式明显具备更佳的性能。这个在稍后就会看到。
例：下面的每一个正则表达式都能成功匹配字符序列“Rudolph”
for(String pattern: new String[]{
"Rudolph","[rR]udolph","[rR][aeIoU][a-z].*","R.*" })
})
System.out.println("Rudolph".matched(pattern));
2 量词
量词描述了一个模式吸收输入文本的方式
- 贪婪型：为所有可能的模式发现极可能多的匹配
- 勉强型：匹配满足模式所需要的最少字符数
- 占有型：只能用于Java。
测试代码：
import java.util.regex.*;
public class testRegex
{
public static String t = "Java now has regular expressions";
public static String r = "((^[aeIoUs])|(\s+[aeIoU]))"
{
System.out.println("Input: \"" + args[0] + "\"");
for(String arg: args)
{
System.out.println("Regular expression: \"" + arg + "\"");
Pattern p = Pattern.compile(arg);
Matcher m = p.matcher(t);
while(m.find())
{
System.out.println("Match \"" + m.group() + "\" at position" + m.start() + "-" + (m.end()-1));
}
}
}
}
功能更强大的正则表达式工具：
- boolean matches()：匹配整个输入的字符串是否匹配正则表达式
- bollean lookingAt()：判断该字符串（不必是整个字符串）的某一部分是否能够匹配模式。
- bollean find()：在字符串中查找多个匹配，用Matcher.group()返回查找到的匹配的字符串。
- boolean find(int start)
2 正题——语法分析
简单的看了一下Java中正则表达式的基本知识，下面仔细看一看在虎书中语法分析的章节。
2.1 词法分析器实现正则表达式
匹配括号对于有限自动机是不可识别的。
在翻译成有限自动机以前，在所有正则表达式出现digits的地方都简单地用右边的式子代替。
简化的概念并没有增前正则表达式的描述能力，除非简化形式是递归的。这种递归附加功能正式在语法分析中所需要的，一旦使用了递归简化形式，就不再需要进行迭代，除非是表达式的首部。
定义：
expr = ab(c|d)e可以用附加定义重写：
aux = c d expr = a b aux e
为了避免使用交替符号，对于同一符号，可以使用一些辅助扩充：
aux = c aux = d expr = a b aux e
另外一个i例子：
expr = (a b c)*
重写为：
expr = (a b c)expr expr = &
2.2 上下文无关文法CFG
CFG = <T,N,P,S>
T：终结符 N：非终结符 P：产生式集合 S：初始非终结符
正如正则表达式可以静态声明的方式定义词法结构一样，文法也可以用声明的方式定义语法结构，但需要比有限自动机更强大的方式来分析文法描述的语言。
对于语法分析，字符串就是源程序，符号就是词法记号，字母表就是词法分析器返回的记号类型集。
文法的产生式集： symbol -> symbol symbol ... symbol
有0个或多于0个的记号在产生式的右边，这些符号要么是终结符，即描述语言中字符串在字母表中的记号；要么是非终结符，即出现在产生式左边的记号。产生式左边不会出现终结符的记号。最后，还需要使用一个非终结符作为文法的开始符号。
推导：从开始符号出发，对于任一非终结符，用其产生式的右侧部分进行替换并重复进行这一操作。
2.3 分析树
分析树就是将推导式中的每个符号同其派生符号连接而成。
二义性文法：若一个文法可以用两棵不同的分析树派生出同一个句子，那么该文法就是二义性的。
如何避免二义性，即如何将二义性文法转换成非二义性文法：
途径：引入一些非终结符号可以得到非二义性文法：
文法3.5为二义性文法：
引入T和F后所得的非二义性文法：
符号E T 和F分别代表表达式、项和因子。习惯上，因子用于乘法，项用于加法。
综上，消除二义性的通常做法是转换文法，虽然这些文法只是在文法上存在二义性，但是它们在编程时也会出现二义性。
通常，使用$符号代表全文的结束，即分析器读入的终结符。
文法3.8加入终结符后的文法：
2.4 预测分析——递归下降分析
把每个文法产生式转换成一个递归函数的子句。
递归下降分析器对应每个非终结符都有一个函数，对应每个产生式都有一个子句。
递归下降、预测或者分析仅限于如下的文法中：每个子表达式的第一个终结符号为选择产生式提供了足够多的信息。这样们需要引入一个FIRST集的概念才能推导出一个无冲突递归下降分析器。
PS: 虎书太难懂了，今天就先到这吧。。
