Entry
Compiler: Syntax: Parser: LL versus LR: What is the difference between an LL and an LR parser?
Jan 5th, 2008 10:51
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 25 October 2003 - 10:12 pm --------------------
Compiler: Syntax: Parser: LL versus LR: What is the difference between
an LL and an LR parser?
---
The LL and LR inform about the DIRECTION in which scanning and
derivation takes place.
===
LL = scanning from 'L'eft to right, and derivation from 'L'eft to
right.
(You scan your given input thus from the 'L'eft to the right, and
successively replace the 'L'eft hand rule by the right hand rule
(until the given input remains))
---
LR = scanning from 'L'eft to right, and derivation from 'R'ight to
left.
(You scan your given input thus from the 'L'eft to the right, and
successively replace the 'R'ight hand rule by the left hand rule
(until the given start symbol remains))
===
In LL( k ) grammars,
the k refers to how many tokens of lookahead one
needs to examine at the START of a rule to determine which rule
(or alternative of a rule) to apply.
---
This is also called a topdown grammar.
===
e.g.
LL( 1 ) needs to read 1 token maximally at the START of a rule, to be
able to decide which rule to apply or similarly which
procedure to go to next.
This is the most common case.
===
In LR( k ) grammars,
the k refers to how many tokens of lookahead one
needs to examine at the END of a rule to decide which rule to apply.
---
This is also called a bottom up grammar.
===
e.g.
LR( 1 ) needs to read 1 token maximally from the END of a rule, to be
able to decide which rule to apply or similarly which
procedure to go to next.
This is the most common case.
===
Internet: see also:
---
Recursive Descent LL vs. LALR
http://compilers.iecc.com/comparch/article/03-07-024
---
Compiler: Syntax: Parser: LALR: What is the meaning of LALR?
http://www.faqts.com/knowledge_base/view.phtml/aid/25989/fid/1262
---
Wikipedia: LL parser
http://en.wikipedia.org/wiki/LL_parser
===
Wikipedia: LR parser
http://en.wikipedia.org/wiki/LR_parser
----------------------------------------------------------------------
