Stack Overflow
Stack Overflow

Questions tagged [lalr]

LALR parsers (lookahead LR) are a family of parsers that are often used in parser generators. They provide a balance between the expressivity of LR(1) parsers and the size of LR(0) parsers.

176 questions
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
42
votes
3 answers

What is the difference between LALR and LR parsing?

I understand both LR and LALR are bottom-up parsing algorithms, but what's the difference between the two? What's the difference between LR(0), LALR(1), and LR(1) parsing? How can I tell if a grammar is LR(0), LALR(1), or LR(1)?
AAB
  • 1,594
  • 2
  • 25
  • 40
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
35
votes
4 answers

Is C#'s lambda expression grammar LALR(1)?

The question I wish to ask is succintly given in the title. Let me give an example of the grammar in question: identifier_list : identifier | identifier_list identifier; lambda_arguments : '(' identifier_list ')' |…
Puppy
  • 144,682
  • 38
  • 256
  • 465
21
votes
3 answers

Are C# and Java Grammars LALR(x)?

I wonder if C# and Java grammars are LALR(x)? If yes, what's the value of x? Edit: After accepting the true answer, I think it is better to change the Q in this way: Is there any LALR(x) parser that could parse current releases of Java (version 7)…
TonySalimi
  • 8,257
  • 4
  • 33
  • 62
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
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
14
votes
1 answer

Why is this LR(1) grammar not LALR(1)?

This is not my homework, I'm trying to understand LALR(1) grammars. So I found this S -> aEa | bEb | aFb | bFa E -> e F -> e I wrote the LR items, but I can't figure out why this is an LR(1) grammar and not LALR(1)? Can anyone help me? Thank you
Jan Vorcak
  • 19,261
  • 14
  • 54
  • 90
14
votes
5 answers

Packrat parsing vs. LALR parsing

A lot of websites states that packrat parsers can parse input in linear time. So at the first look they me be faster than LALR parser contructed by the tools yacc or bison. I wanted to know if the performance of packrat parsers is better/worse than…
raisyn
  • 4,514
  • 9
  • 36
  • 55
13
votes
2 answers

Irony: How to give KeyTerm precedence over variable?

Relevant chunk of Irony grammar: var VARIABLE = new RegexBasedTerminal("variable", @"(?-i)\$?\w+"); variable.Rule = VARIABLE; tag_blk.Rule = html_tag_kw + attr_args_opt + block; term_simple.Rule = NUMBER | STRING | variable | boolean | "null" |…
mpen
  • 272,448
  • 266
  • 850
  • 1,236
13
votes
3 answers

How to solve a shift/reduce conflict?

I'm using CUP to create a parser that I need for my thesis. I have a shift/reduce conflict in my grammar. I have this production rule: command ::= IDENTIFIER | IDENTIFIER LPAREN parlist RPAREN; and I have this warning: Warning : *** Shift/Reduce…
dierre
  • 7,140
  • 12
  • 75
  • 120
12
votes
5 answers

Generate an AST in C++

I'm making an interpreter in C++, so far I've got my lexer to generate tokens. The problem is I'm not sure how to generate an "walk" a parse tree. I was thinking of making my parse tree using an array of arrays, but I'm not sure how to actually…
Francis
  • 919
  • 3
  • 14
  • 23
10
votes
2 answers

Ambiguity resolution when making a C++ parser

I wrote a LALR(1) parser for C++17. I found 156 ambiguities, some of them I can resolve it according to standard but the others I can't. For example: Shift-Reduce conflict occurs while parsing "operator+ < ......" when a less-than is encountered: We…
ChungkingExpress
  • 323
  • 1
  • 12
9
votes
2 answers

Visualize LALR grammar

I'd like to visualize a grammar file (actually the Jison grammar for coffee-script). So the input file is a grammar file of Bison/Yacc style. The expected output could be a Graphviz dot file or something similar. I'm not necessarily looking for a…
Adam Schmideg
  • 10,590
  • 10
  • 53
  • 83
8
votes
2 answers

How does the yacc/bison LALR(1) algorithm treat "empty" rules?

In a LALR(1) parser, the rules in the grammar are converted into a parse table that effectively says "If you have this input so far, and the lookahead token is X, then shift to state Y, or reduce by rule R". I have successfully constructed a LALR(1)…
d11wtq
  • 34,788
  • 19
  • 120
  • 195
1
2 3
…
11 12