I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related.
Suppose I have a regular expression: RE=(aa)?(aa)
and I convert it to a grammar: G ::= A B A ::= C | (empty) C ::= D D D ::= aD | empty B ::= D D
Can an LALR(1) parser such as Bison generate matches such that I can perform actions such as recording captures, etc... If so, is the cost linear in the size of the input?
If not, is the lower bound on this operation the cost of simulating an NFA generated by the regular expression? I know that DFAs can't perform sub-match captures.