1) regexp : expr
| '^' expr
| expr '$'

2) expr : expr '|' expr_without_or
| expr_without_or

3) expr_without_or : expr_without_or expr_without_concatenation
| expr_without_concatenation

4) expr_without_concatenation : term '*'
| term '+'
| term '?'
| term '{' dup '}'

5) dup : digit ',' digit
: digit ','
| digit


6) term : '[' string ']'
| '[' '^' string ']'
| '.'
| character
| '(' expr ')'

消除 2) 3) 的左递归

2.1) expr : expr_without_or expr0

2.2) expr0 : '|' expr_without_or expr0
|

3.1) expr_without_or : expr_without_concatenation expr_without_or0

3.2) expr_without_or0 : expr_without_concatenation expr_without_or
|

这里. character 为非空白字符
string 为 character 连接而成
digit 为 0-9

均由 lex scanner 产生