写这篇是做LC 770的时候受到了，参考评论区@mbinary 的答案的启发。
编译原理学了不能白学吧，遇到这类题目可以根据编原有一套方法论，而不是自己在那瞎递归瞎调试，又慢又容易出错
像很多表达式分析等题，括号是嵌套的，这种是没办法只用正则解决的，需要通过语法分析来搞定。

LC 770为例，参考评论区@mbinary 的答案
所有的token包括：

• num：数字，由0-9数字构成，由于题目不会给出非法数字，故为[0-9]+
• var：变量，由小写字母构成，故为[a-z]+
• +：加号
• -：减号
• *：乘号
• `(’：左括号
• )：右括号

结合下文语法分析看，token就是语法分析里说的“终结符号集合”

LC 770为例，参考评论区@mbinary 的答案

• $V_T=\text{num,var,’+’,’-’,’*’,’(’,’)’}$

  expr->term {'+'|'-'} expr | term
  term->item '*' term | item
  item->var | num | '(' expr ')'
  

  • 匹配item的时候，只要看下一个token是num、var或者'('就行了
  • 匹配完一个item之后，只要看下一个token是不是*就行
  • 匹配完一个term之后，只要看下一个token是不是+或-就行

  ###自底向上构建语法分析树
  就是从字符串开始，不断寻找合适的规则，向前推到S
  具体操作表现为移进-规约，就是维护一个符号栈，从左向右扫描token

  1. 如果操作为移进，token入栈
  2. 如果操作为规约，应用的是$A\to aBc$

0: expr->expr {'+'|'-'} term
1: expr->term
2: term->term '*' item
3: term->item
4: item->var
5: item->num
6: item->'(' expr ')'

自动机不画了，比较复杂，直接上状态和表吧：

在I1、I3和I6都存在着移进-规约冲突，没关系，我们只要判断后面那个token是啥就能知道是移进还是规约了：


把这种方法用在解题上的实例详见LC 770的解答