将正则表达式模式转换为 LL1 解析器

Question

背景：我正在尝试解决这个 leetcode 问题：regular-expression-matching。我的方法是实现一个 LL(1) 解析器生成器，对于这个问题可能有点矫枉过正，但这只是一个大脑练习。

我只有入门级的解析器理论知识，如果我问的这个问题很愚蠢，请原谅。

所以，这个测试用例我失败了。要求是正则表达式模式应该匹配整个字符串

Regex: a*a
Input: aaa

我想不通如何将此模式转换为 LL(1) 解析器。

依我看，a*a模式可以转化为生产规则：

S -> Aa      # a*a
A -> aA | ε  # a*

解析table:

	a	$
S	S -> Aa
A	A -> aA	A -> ε

解析步骤如下：

0: S$    aaa$  # use [S,a]
1: Aa$   aaa$  # use [A,a]
2: aAa$  aaa$  # eat 'a'
3: Aa$   aa$   # use [A,a]
4: aAa$  aa$   # eat 'a'
5: Aa$   a$    # use [A,a]
6: aAa$  a$    # eat 'a'
7: Aa$   $     # use [A,$]
8: a$    $     # Error!

正确的匹配应该是：

a* -> aa
a -> a

但我得到的却是：

a* -> aaa
a -> Error!

我不知道我漏掉了哪一部分。

Answer 1

在解析步骤 5 中，解析器应该使用 [A,$] 而不是 [A,a]。但它只能通过向前看或回溯才能做出这个决定。两者都超出了 LL(1).

问题的原因在于您的生产规则。存在FIRST/FOLLOW冲突：FIRST(A)包含ε，FIRST(A)和FOLLOW( A) 都包含 a。这里用一个例子来解释：

https://inst.eecs.berkeley.edu/~cs164/sp18/discussion/04/04-solutions.pdf

更直观地说，您要求解析器向前看，超越 S -> Aa 中的 a，以便能够决定 a 应该使用多少终端A -> aA | ε.

基本上，LL(1) 解析器无法解析 a*a。必须先将其重写为 aa*。可能有一些算法可以成功地将 a*a 之类的简单内容重写为 aa*，但不可能将所有可能的正则表达式重写为 LL(1) 文法。

将正则表达式模式转换为 LL1 解析器

Convert regex pattern to LL1 parser

regex

parsing