如何从BNF文法构造NFA？递归文法构造难点求助

先明确你给出的文法含义：

<case> ::= <case> <int> 'b' | 'b'
这个文法定义的字符串是：以单个'b'为基础，后面可以追加任意次数（包括0次）的<int>+'b'组合。比如合法字符串可以是b、b123b、b45b67b这类（假设<int>匹配整数）。

下面一步步构造对应的NFA，解决左递归和'b'的状态转换问题：

前提假设 #

先假设<int>的NFA已经构造完成：它有一个起始状态S_int，接受状态F_int，输入整数字符时能从S_int走到F_int。

构造的NFA步骤 #

• 处理基础产生式 <case> → 'b'
  创建<case>的起始状态S_case和接受状态F_case，从S_case到F_case添加一条输入为'b'的边，对应匹配最基础的单个'b'。

• 处理左递归产生式 <case> → <case> <int> 'b'
  左递归的本质是“重复执行某个动作”，我们用循环结构实现：

  1. 创建中间状态M，从F_case到M添加一条ε-边（无需输入字符即可跳转），表示匹配完当前<case>后可进入递归循环。
  2. 把<int>的NFA接入：从M到<int>的起始状态S_int添加一条ε-边。
  3. 在<int>的接受状态F_int之后，添加一条输入为'b'的边指向F_case，对应匹配完<int>后读入'b'，回到<case>的接受状态完成一次递归循环。

最终NFA结构说明 #

• 起始状态为S_case，接受状态为F_case。
• 基础匹配路径：S_case →（输入'b'）→ F_case，对应单个'b'。
• 递归匹配路径：S_case →（'b'）→ F_case →（ε）→ M →（ε）→ S_int →（匹配整数）→ F_int →（'b'）→ F_case，对应b<int>b；重复循环部分可得到更长的合法字符串，完全符合文法递归定义。

内容的提问来源于stack exchange，提问作者yes12345