Convert regex pattern to LL1 parser

Question

Background: I'm trying to solve this leetcode problem: regular-expression-matching. My approach is to implement a LL(1) parser generator, might be overkilling for this problem but it's just a brain exercise.

I only have entry level knowledge of parser theory, so excuse me if this is a silly question that I ask.

So, there's this testcase that I fail. Requirement is regex pattern should match the whole string

Regex: a*a
Input: aaa

I cannot wrap my mind about how to convert this pattern into a LL(1) parser.

The way I see it, a*a pattern can be converted into production rules:

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

Parse table:

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

Here's the steps to parse:

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!

The correct matching should be:

a* -> aa
a -> a

But what I get instead is:

a* -> aaa
a -> Error!

I don't know which part I'm missing 😫. Is this problem even solvable using LL(1)?

Answer 1

No, it's not possible in general. There's no guarantee that a regular expression be LL(1), not even the simplified form of regular expressions required by that exercise, and the example you provide is a perfect illustration.

To be LL(1), it must be possible to work out which production to match based only on the parse up to that point and the first symbol in the input. ("First symbol" because it's LL(1).) But that's not possible for your grammar; in general, it's not possible to decide between $A\to\epsilon$ and $A\to a A$, because the fact that the next symbol is an $a$ doesn't give you enough information to decide between them.

In slightly more technical terms, that happens because $A$ is nullable (matches the empty string) and $FIRST(A) \cap FOLLOW(A) \ne \emptyset$.

In fact, grammars derived from regular expressions (in the way you show) are not guaranteed to be unambiguous, and an ambiguous grammar cannot be deterministically parsed (by definition). Your grammar is unambiguous, but that wouldn't be the case for $.^*a^*$ (strings ending with one or more $a$s).