Difference between revisions of "LALR Parsers"

From eplmediawiki
Jump to: navigation, search
(LALR parser generators [INSERIR LINKS])
Line 2: Line 2:
 
<br><br>
 
<br><br>
  
LALR parsers are a specialized form of [http://eplmediawiki.di.uminho.pt/index.php/LL(k)_----_LL(1)_Parsers| LR parsers] that can deal with more context-free grammars than Simple LR parsers [INSERIR LINKS] but less than [http://eplmediawiki.di.uminho.pt/index.php/LL(k)_----_LL(1)_Parsers| LR(1)] parsers can.  
+
LALR parsers are a specialized form of [http://eplmediawiki.di.uminho.pt/index.php/LL(k)_----_LL(1)_Parsers LR parsers] that can deal with more context-free grammars than Simple LR parsers [INSERIR LINKS] but less than [http://eplmediawiki.di.uminho.pt/index.php/LL(k)_----_LL(1)_Parsers LR(1)] parsers can.  
 
<br><br>
 
<br><br>
  
Line 12: Line 12:
  
 
== LALR parser generators [INSERIR LINKS]==
 
== LALR parser generators [INSERIR LINKS]==
# [http://www.parsifalsoft.com/| AnaGram]
+
# [http://www.parsifalsoft.com/ AnaGram]
# [http://beaver.sourceforge.net/| BEAVER]
+
# [http://beaver.sourceforge.net/ BEAVER]
# [http://www.cs.princeton.edu/~appel/modern/java/CUP| CUP]
+
# [http://www.cs.princeton.edu/~appel/modern/java/CUP CUP]
 
# ELI [INSERIR LINK]
 
# ELI [INSERIR LINK]
# [http://www.devincook.com/goldparser/| Gold]
+
# [http://www.devincook.com/goldparser/ Gold]
# [http://www.hwaci.com/sw/lemon/| Lemon]
+
# [http://www.hwaci.com/sw/lemon/ Lemon]
# [http://eplmediawiki.di.uminho.pt/index.php/Lisa| LISA]
+
# [http://eplmediawiki.di.uminho.pt/index.php/Lisa LISA]
# [http://www.mathematik.uni-ulm.de/modula| Ulm's Modula-2 System]
+
# [http://www.mathematik.uni-ulm.de/modula Ulm's Modula-2 System]
# [http://eplmediawiki.di.uminho.pt/index.php/Yacc| YACC]
+
# [http://eplmediawiki.di.uminho.pt/index.php/Yacc YACC]
# [http://www.gradsoft.com.ua/products/yayacc_eng.html| YaYacc]
+
# [http://www.gradsoft.com.ua/products/yayacc_eng.html YaYacc]
  
 
[[Category:Basic Concepts]]
 
[[Category:Basic Concepts]]

Revision as of 22:47, 10 December 2012

LALR - Look Ahead Left-to-right parse, Rightmost-derivation.

LALR parsers are a specialized form of LR parsers that can deal with more context-free grammars than Simple LR parsers [INSERIR LINKS] but less than LR(1) parsers can.

LALR parsers were introduced as practical parsers for deterministic languages. Rather than building an exponential number of LR(k) states, LALR(k) parsers add lookahead sets to the actions of the small LR(0) parser. While SLR uses follow sets to construct reduce actions, LALR uses lookahead sets, which are more specific because they take more of the parsing context into account.

In LR(1) parsing, an item A ::= a (s1) is different from A ::= a (s2) if s1 is different from s2. This results to a large number of states since the combinations of expected lookahead symbols can be very large. To reduce the number of states, when we have two items like those two, instead of creating two states (one for each item), we combine the two states into one by creating an item A := a (s3) where s3 is the union of s1 and s2. Since we make the expected lookahead sets larger, there is a danger that some conflicts will have worse chances to be resolved. But the number of states we get is the same as that for LR(0). This grammar is called LALR(1).

LALR parser generators [INSERIR LINKS]

  1. AnaGram
  2. BEAVER
  3. CUP
  4. ELI [INSERIR LINK]
  5. Gold
  6. Lemon
  7. LISA
  8. Ulm's Modula-2 System
  9. YACC
  10. YaYacc
Personal tools
Namespaces

Variants
Actions
Navigation
extras
Toolbox