0
$\begingroup$

Is it possible to build a parsing algorithm that build a parse tree using a top-down method that simulate a derivation process for regular expressions, like we do for type 2 languages?

My guess

Given a regular expression r, build its FSA, then obtain the grammar that generate r in order to build a parse tree

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It's not clear to me what your question is. A regular expression is not a grammar (and there is no obvious unique homomorphism between regular expressions and regular grammars), so I'm not sure what you expect to be the parse tree. I suppose you could try recursively mapping substrings to subpatterns in the regular expression, but in many cases there are multiple possible mappings. $\endgroup$ – rici Nov 3 '17 at 18:46
1
$\begingroup$

It is absolutely possible and you are on the right track. You will need to make sure your grammar is %100 correct and probably LL(1), from there you can choose one of many algorithm examples that are out there or write your own.

See https://en.wikipedia.org/wiki/Top-down_parsing and https://en.wikipedia.org/wiki/LL_parser

Word of warning: The tricky part won't be the implementation but getting your grammar right.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.