所以我有一个上下文无关语法的问题，我没有解决。它不是用于成绩之类的，所以不用担心。
问题是这样的：
有一个上下文无关的语法，看起来像
S-> S1 | S2
S1-> aS1B |乙
S2-> S2aB |乙
B-> bS | b
任务是编写一个函数（使用任何编程语言）
count_words（n）。函数需要返回带有“ n”的单词数
长度，即在这种情况下与语言无关的语言。
*假设我用count_words（3）调用了函数，函数必须返回可能的单词数（在该上下文无关语言中）
长度为3。应为：bab，abb，aab等。
有人可以帮我吗？我一点都不知道...假设这并不难，但是我不能强迫自己以正确的方式思考。
最佳答案
您将需要模拟语法。给定终端a和b，构造一个接受您的语言的自动机。由于您呈现的语法是左递归语法，因此可以选择构造类似于LR解析器的下推自动机。每次符号推送后，如果可以将生成的分析堆栈简化为起始符号，则该字符串可以被语法接受。继续此操作，直到达到所需的字符串长度。
本质上来说，您是在模拟自动机并进行分支，因为您将在减少解析堆栈之后尝试使用所有可能的输入进行模拟。
您可能可以避免完全构建自动机，而只需查看在每种状态下处于哪种可能的规则即可。