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*
|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)?