I know how to tell what the k in LL(k) is, but I don't know how to differentiate LL and LR. I don't know what "x-most derivation" means and haven't found a good explanation that I could understand. |
I am assuming you do not understand terminal and no-terminal.
In a context free grammar, production rules are written as:
Where 'S' is a non-terminal (i.e. can be transformed into something else) and 'x' is a string of terminals and/or non-terminals. (terminals cannot be transformed into something else, and thus can never be on the left hand side of the production).
Okay so now onto LL and LR:
If we have the productions:
Rule 1: S->SX
Rule 2: S->m
Rule 3: X->1 |
then there are multiple ways to form the string "m11"
We always start at the first production rule. So 'S'.
S can be transformed (bu rule 1) into SX.
From there we can either transform S or X next. If we use the left-most non-terminal to transform we are using LL. If we use the right most terminal, we are using LR.
Transformation of the string using LL:
rule 1; rule 1; rule 2; rule 3; rule 3;
Transformation of the string using LR:
rule 1; rule 3; rule 1; rule 3; rule 2;
As you can see you will always use the same number of rules, just in a different order.
Hope this helps.
Please let me know of any error/ thing that are not explained properly.
EDIT: @chrisname I just realised that you have not made an LL or an LR. They refer to parsers, you have made a tokeniser with one look-ahead character.