Stack Overflow
Stack Overflow

Questions tagged [ll-grammar]

LL(k) grammars are grammars that can be parsed from left-to-right, creating a leftmost derivation, using k tokens of lookahead.

209 questions
269
votes
4 answers

What is the difference between LL and LR parsing?

Can anyone give me a simple example of LL parsing versus LR parsing?
Creativity2345
  • 2,721
  • 3
  • 15
  • 3
93
votes
1 answer

Difference between an LL and Recursive Descent parser?

I've recently being trying to teach myself how parsers (for languages/context-free grammars) work, and most of it seems to be making sense, except for one thing. I'm focusing my attention in particular on LL(k) grammars, for which the two main…
Noldorin
  • 144,213
  • 56
  • 264
  • 302
80
votes
5 answers

How to identify whether a grammar is LL(1), LR(0) or SLR(1)?

How do you identify whether a grammar is LL(1), LR(0), or SLR(1)? Can anyone please explain it using this example, or any other example? X → Yz | a Y → bZ | ε Z → ε
Prashant Bhardwaj
  • 1,203
  • 2
  • 18
  • 26
61
votes
4 answers

Examples of LL(1), LR(1), LR(0), LALR(1) grammars?

Is there a good resource online with a collection of grammars for some of the major parsing algorithms (LL(1), LR(1), LR(0), LALR(1))? I've found many individual grammars that fall into these families, but I know of no good resource where someone…
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
38
votes
7 answers

What advantages do LL parsers have over LR parsers?

What advantages do LL parsers have over LR parsers to warrant their relative popularity in today's parser generator tools? According to Wikipedia, LR parsing appears to have advantages over LL: LR parsing can handle a larger range of languages than…
Adam Paynter
  • 46,244
  • 33
  • 149
  • 164
34
votes
2 answers

Which contemporary computer languages are LL(1)?

(I am spending the holiday time on some language theory. Excuse me if this is a naive question.) According to here: LL grammars, particularly LL(1) grammars, are of great practical interest, as parsers for these grammars are easy to construct,…
smwikipedia
  • 61,609
  • 92
  • 309
  • 482
28
votes
1 answer

Purpose of FIRST and FOLLOW sets in LL(1) parsers?

Can anyone explain to me how FIRST and FOLLOW should be used in LL(1) grammar? I understand that they are used for syntax table construction, but I don't understand how.
Kobe-Wan Kenobi
  • 3,694
  • 2
  • 40
  • 67
21
votes
1 answer

Why are there LR(0) parsers but not LL(0) parsers?

I've been reading on both in Wikipedia, and noticed that although LR(0) parsers exist, there's no such thing as LL(0) parser. From what I read, I understand that the k in LL(k)/LR(k) means how many characters the parser can see beyond the current…
Shmoopy
  • 5,334
  • 4
  • 36
  • 72
20
votes
1 answer

Example of an LR grammar that cannot be represented by LL?

All LL grammars are LR grammars, but not the other way around, but I still struggle to deal with the distinction. I'm curious about small examples, if any exist, of LR grammars which do not have an equivalent LL representation.
Puppy
  • 144,682
  • 38
  • 256
  • 465
19
votes
4 answers

Why can't a LL grammar be left-recursive?

In the dragon book, LL grammar is defined as follows: A grammar is LL if and only if for any production A -> a|b, the following two conditions apply. FIRST(a) and FIRST(b) are disjoint. This implies that they cannot both derive EMPTY If b can…
wangshuaijie
  • 1,821
  • 3
  • 21
  • 37
19
votes
2 answers

LALR vs LL parser

I've been using lex/yacc and now I'm trying to switch to ANTLR. The major concern is that ANTLR is an LL(*) parser unlike yacc which is LALR. I'm used to thinking bottom-up and I don't exactly know what the advantage of LL grammars is. People say…
K J
  • 4,505
  • 6
  • 27
  • 45
18
votes
1 answer

Which grammars can be parsed using recursive descent without backtracking?

According to "Recursive descent parser" on Wikipedia, recursive descent without backtracking (a.k.a. predictive parsing) is only possible for LL(k) grammars. Elsewhere, I have read that the implementation of Lua uses such a parser. However, the…
user200783
  • 13,722
  • 12
  • 69
  • 135
18
votes
2 answers

Performance of parsers: PEG vs LALR(1) or LL(k)

I've seen some claims that optimized PEG parsers in general cannot be faster than optimized LALR(1) or LL(k) parsers. (Of course, performance of parsing would depend on a particular grammar.) I'd like to know if there are any specific limitations of…
Roman Boiko
  • 3,576
  • 1
  • 25
  • 41
16
votes
7 answers

Limitations of LL vs LR parsers?

I know the basic differences of LL vs LR parsers. I also know that GLR, SLR, and LALR are all extensions of LR parsers. So my question in more details is... Given a LL(*) parser and any variation on a LR parser, is there any language that can be…
Andrew White
  • 52,720
  • 19
  • 113
  • 137
14
votes
1 answer

How to determine if a language is LL(1)?

I have a grammar and I can check whether or not is is LL(1). However, is there any way to check if the language generated by the grammar is LL(1)? And what exactly is the difference between LL(1) grammars and LL(1) languages?
Rakesh
  • 141
  • 1
  • 3
1
2 3
…
13 14