On different LL and LR parsers used in LLLR parsing. (December 2017)

• Record Type: Journal Article
• Authors: Slivnik, Boštjan
• Is Part Of: Computer languages, systems & structures. Volume 50(2017)
• Page Start: 108
• Page End: 126
• Publication Date: 2017-12
• Subjects: LL parsing -- LR languages -- Left parse; Programming languages (Electronic computers) -- Periodicals; Computer networks -- Periodicals; Computer architecture -- Periodicals; Computer systems -- Periodicals; Langage de programmation; Réseau d'ordinateurs; Architecture d'ordinateur; Périodique électronique (Descripteur de forme); Ressource Internet (Descripteur de forme); 005.13
• DOI: 10.1016/j.cl.2017.06.002
• Languages: English
• ISSNs: 1477-8424

Abstract

Highlights: The LLLR parser can be constructed for any LR grammar. The LLLR parser produces the left parse of the input string without backtracking. The canonical LL or the LALL parser can be used as the backbone parser. Small canonical or LALR parsers are used for LL conflict resolution. Abstract: As described in Slivnik (2016), LLLR parsing is a method that parses as much of its input string as possible using the backbone SLL( k ) parser and uses small embedded canonical left LR( k ) parsers to resolve LL conflicts. Once the LL conflict is resolved, the embedded parser produces the left parse of the substring it has just parsed and passes the control back to the backbone parser together with the information about how the backbone parser should realign its stack as a part of the input has been read by the embedded parser. The LLLR parser produces the left parse of the input string without any backtracking and, if used for a syntax-directed translation, it evaluates semantic actions using the same top-down strategy as the canonical LL( k ) parser. In this paper, a more general approach towards LLLR parsing is presented as it is described how any kind of canonical LL( k ) or LA( k )LL( k ′) parser can be used as the backbone parser and how different kinds of embedded canonical left LR( k ) or left LA( k )LR( k ′) parsers can be used for LL conflict resolution.