a couple of questions to those who know compilers

[juan_gandhi]

1. Is it true that transforming a word in a context-free language into an AST takes linear time and finite space (except for the growing AST), so it could be done by an FSM? If so, all the stack requirements are about evaluating the trees...

2. Say, I have a language for some kind of expressions, and I want to use the fact that operations are associative (or maybe even commutative); is there a way to stipulate it somehow; or, rather, does it give us something that can be used to facilitate compilation? I wonder...

Comments

[thedeemon.livejournal.com]

LR needs some temp storage that doesn't resemble parse tree, so it's hardly possible, however for recursive descent that's an interesting idea, yes. Needs some more thought and experiments to find the answer.