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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.