Generalized LR parsing algorithm for grammars with one-sided contexts

DOI10.1007/S00224-016-9683-3MaRDI QIDQ2411044zbMATH OpenOpenAlexFDO

Authors Mikhail Barash, Alexander Okhotin

Publication date 20 October 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-016-9683-3

zbMATH Keywords

conjunctive grammarscontextsformal grammarsGLR parsingLR parsing

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Generalized LR parsing for grammars with contexts
• scientific article; zbMATH DE number 4197438
• LR parsing for conjunctive grammars
• A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS

Cites work

• LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
• An extension of context-free grammars with one-sided context specifications
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Even faster generalized LR parsing
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
• scientific article; zbMATH DE number 3664336 (Why is no real title available?)
• scientific article; zbMATH DE number 3470007 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• Improved normal form for grammars with one-sided contexts
• Input-driven languages are linear conjunctive
• Learning conjunctive grammars and contextual binary feature grammars
• Linear grammars with one-sided contexts and their automaton representation
• LR parsing for conjunctive grammars
• On the translation of languages from left to right
• Parsing by matrix multiplication generalized to Boolean grammars
• Recognizing two-sided contexts in cubic time
• Reducing non-determinism in right nulled GLR parsers
• Two-sided context specifications in formal grammars
• Using contextual representations to efficiently learn context-free languages

Cited in

(15)

• Generation of efficient LALR parsers for regular right part grammars
• A yo-yo parsing algorithm for a large class of van Wijngaarden grammars
• Linear-space recognition for grammars with contexts
• LR parsing for LCFRS
• LR parsing for conjunctive grammars
• An extension of context-free grammars with one-sided context specifications
• Two-sided context specifications in formal grammars
• Improved normal form for grammars with one-sided contexts
• Generalized LR parsing for grammars with contexts
• scientific article; zbMATH DE number 40796 (Why is no real title available?)
• Grammars with two-sided contexts
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
• The hardest language for grammars with context operators
• One-sided random context grammars
• A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead

This page was built for publication: Generalized LR parsing algorithm for grammars with one-sided contexts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2411044)