0
$\begingroup$

This is the unmodified SLR(1) table

I have constructed an SLR(1) parsing table with the following rules.

  • S -> S + S + S (rule 1)
  • S -> S + S (rule 2)
  • S -> y

Is reducing rule 2, then shifting + and y, then again rule 2, equivalent to reducing rule 1? Can I claim to have reduced by rule 1, even though I did so indirectly?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Note that your grammar is ambiguous. Since SLR is a type of deterministic parsing it won't ever work for this grammar. Hence, isn't the question moot? $\endgroup$ – Raphael♦ Dec 2 '14 at 12:43
  • 1
    $\begingroup$ If you assign priority to rule 2, you'll of course never see rule 1 used so you might as well drop it. What is the purpose then; what do you want with several parse trees for the same word? Do you intend to count and/or do stochastic parsing? In that case, your shortcut won't work (consider S + S + S + S + S + S). $\endgroup$ – Raphael♦ Dec 2 '14 at 13:03
  • 2
    $\begingroup$ I just chanced on this question ... the reference @ babou will work only when I have already commented. ... Well I have seen it now (flattered you call on me, though I do not know why: competence on your previous question does not imply competence on this one), I think @Raphael gave you very sensible comments. There are many things that can be said about this, but one really has to understand what original problem you are really trying to address. Too often, question are about a solutions thought of by the user, rather than the problem he is addressing. Why do you want both rule 1 and rule 2? $\endgroup$ – babou Dec 2 '14 at 22:48
  • 2
    $\begingroup$ @Raphael did answer that. Basically, the language you define is usually intended to express clearly what you have to say. This is parsed into a structure, usually an Abstract Syntax Tree (AST) derived from the parse tree. Then translating into commands for the CPU is a different problem. Usually you do not want your language to be dependent on the machine (that is one purpose of programming languages). So the CPU should not matter, unless you have a specific motivation in your project, but I would have to understand it to give you a more specific answer. $\endgroup$ – babou Dec 2 '14 at 23:07
  • 2
    $\begingroup$ The "y+y+y" rule will not ne used since the "y+y" will be used. Then, the parse tree or the AST can be transformed so that arguments are reorganized by groups of 3 arguments, if that is useful. Actually, program optimizers do things that are a lot more complicated than that. There is also the possibility of building several parse trees when the grammar is ambiguous. Actually, you can even manage to use a parser the will give preference to rule 1 whenever possible. But that requires very different and costlier parsing techniques (dynamic programming, with weighted grammar rules). $\endgroup$ – babou Dec 2 '14 at 23:17

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.