New answers tagged

2 votes
Accepted

How is the lookahead for an LR(1) automaton computed?

$\text{FIRST}(\beta)$ is the set of possible first tokens in a derivation from β. (It's usual to also add ε to the first set if β could derive the empty sequence.) So $\text{FIRST}(\mathbf{+}\mathit{T}...
user avatar
  • 11.2k
1 vote

What is the time complexity of SLR and LALR parsers?

They all run linear time with regards to input length ($O(n)$). The different algorithms have different memory trade offs for making it easier to write grammar for. That is not all grammars that work ...
user avatar
  • 157
0 votes
Accepted

find LR(1) items of the first state

$S\to.E$,\$.........$(1)$, now compute the closure of $E$, which is $E\to.E+T,$\$..........$(2)$ and $E\to.T,$\$.........$(3)$ use lookahead \$ because in $(1)$ after $E$ is \$ and $FIRST$ of \$ is \$ ...
user avatar

Top 50 recent answers are included