Happy-GLL: modular, reusable and complete top-down parsers for parameterized nonterminals

• URL: http://arxiv.org/abs/2303.08044v1
• Date: Tue, 14 Mar 2023 16:23:23 GMT
• Title: Happy-GLL: modular, reusable and complete top-down parsers for parameterized nonterminals
• Abstract summary: This paper presents a strategy for generating modular reusable and complete top-down grammars. The strategy is discussed and demonstrated as a novel back-end for the Happy generator.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Parser generators and parser combinator libraries are the most popular tools for producing parsers. Parser combinators use the host language to provide reusable components in the form of higher-order functions with parsers as parameters. Very few parser generators support this kind of reuse through abstraction and even fewer generate parsers that are as modular and reusable as the parts of the grammar for which they are produced. This paper presents a strategy for generating modular, reusable and complete top-down parsers from syntax descriptions with parameterized nonterminals, based on the FUN-GLL variant of the GLL algorithm. The strategy is discussed and demonstrated as a novel back-end for the Happy parser generator. Happy grammars can contain `parameterized nonterminals' in which parameters abstract over grammar symbols, granting an abstraction mechanism to define reusable grammar operators. However, the existing Happy back-ends do not deliver on the full potential of parameterized nonterminals as parameterized nonterminals cannot be reused across grammars. Moreover, the parser generation process may fail to terminate or may result in exponentially large parsers generated in an exponential amount of time. The GLL back-end presented in this paper implements parameterized nonterminals successfully by generating higher-order functions that resemble parser combinators, inheriting all the advantages of top-down parsing. The back-end is capable of generating parsers for the full class of context-free grammars, generates parsers in linear time and generates parsers that find all derivations of the input string. To our knowledge, the presented GLL back-end makes Happy the first parser generator that combines all these features. This paper describes the translation procedure of the GLL back-end and compares it to the LALR and GLR back-ends of Happy in several experiments.

Related papers

• An Empirical Comparison of General Context-Free Parsers [9.393047946491487]
  Parsing underpins a vast range of software engineering tasks, from compilers and static analyzers to language servers and fuzz testing tools.<n>Most algorithms deployed in practice are deterministic (LL or LR), forcing developers to contort their grammars to fit the languages they design sacrificing for the sake of parseability.<n>We present the first unified, controlled benchmark of six generalized parsing algorithms implemented in Rust with shared data structures and parse-tree extraction.<n>Our results show that the cost of generality is lower than widely assumed. On deterministic grammars, the GLR family incurs only a 3x median slowdown with a narrow and predictable
  arXiv  Detail & Related papers  (2026-06-07T05:58:58Z)
• Prefix Parsing is Just Parsing [53.010152712125766]
  Prefix parsing asks whether an input prefix can be extended to a complete string generated by a given grammar.<n>We introduce the prefix grammar transformation, an efficient reduction of prefix parsing to ordinary parsing.<n>We also present a strategy-based on algorithmic differentiation-for computing the next-token weight vector.
  arXiv  Detail & Related papers  (2026-04-23T01:20:40Z)
• Neuro-Symbolic Query Compiler [57.78201019000895]
  This paper presents QCompiler, a neuro-symbolic framework inspired by linguistic grammar rules and compiler design, to bridge this gap.<n>It theoretically designs a minimal yet sufficient Backus-Naur Form (BNF) grammar $G[q]$ to formalize complex queries.<n>The atomicity of the sub-queries in the leaf ensures more precise document retrieval and response generation, significantly improving the RAG system's ability to address complex queries.
  arXiv  Detail & Related papers  (2025-05-17T09:36:03Z)
• Inferring Input Grammars from Code with Symbolic Parsing [12.567395326774754]
  Common test generation techniques rely on sample inputs, which are abstracted into matching grammars and/or evolved guided by test coverage. In this work, we present the first technique for symbolically automatically generating input grammars from the code of descents. The resulting grammars cover the entire input space, allowing for comprehensive and effective test generation, reverse engineering, and documentation.
  arXiv  Detail & Related papers  (2025-03-11T14:40:56Z)
• Automatic Prediction of the Performance of Every Parser [0.0]
  We present a new performance prediction (PPP) model using machine translation performance prediction system (MTPPS) This new system, MTPPS-PPP, can predict the performance of any language and can be useful for estimating the grammatical difficulty when understanding a text.
  arXiv  Detail & Related papers  (2024-07-06T15:49:24Z)
• ChatGPT is a Potential Zero-Shot Dependency Parser [5.726114645714751]
  It remains an understudied question whether pre-trained language models can spontaneously exhibit the ability of dependency parsing without introducing additional structure in the zero-shot scenario. In this paper, we propose to explore the dependency parsing ability of large language models such as ChatGPT and conduct linguistic analysis.
  arXiv  Detail & Related papers  (2023-10-25T14:08:39Z)
• Compositional Program Generation for Few-Shot Systematic Generalization [59.57656559816271]
  This study on a neuro-symbolic architecture called the Compositional Program Generator (CPG) CPG has three key features: textitmodularity, textitcomposition, and textitabstraction, in the form of grammar rules. It perfect achieves generalization on both the SCAN and COGS benchmarks using just 14 examples for SCAN and 22 examples for COGS.
  arXiv  Detail & Related papers  (2023-09-28T14:33:20Z)
• Adapting Language Models to Compress Contexts [71.98287002918941]
  Transformer-based language models (LMs) are powerful and widely-applicable tools, but their usefulness is constrained by a finite context window. We propose to adapt pre-trained LMs into AutoCompressors, which are capable of compressing long contexts into compact summary vectors. We fine-tune OPT and Llama-2 models on sequences of up to 30,720 tokens and show that AutoCompressors can utilize long contexts to improve perplexity.
  arXiv  Detail & Related papers  (2023-05-24T06:42:44Z)
• SPINDLE: Spinning Raw Text into Lambda Terms with Graph Attention [0.8379286663107844]
  The module transforms raw text input to programs for meaning composition, expressed as lambda terms. Its output consists of hi-res derivations of a multimodal type-logical grammar.
  arXiv  Detail & Related papers  (2023-02-23T14:22:45Z)
• Evaluating the Impact of Source Code Parsers on ML4SE Models [3.699097874146491]
  We evaluate two models, namely, Supernorm2Seq and TreeLSTM, in the name prediction language. We show that trees built by differents vary in their structure and content. We then analyze how this diversity affects the models' quality.
  arXiv  Detail & Related papers  (2022-06-17T12:10:04Z)
• Generalized Funnelling: Ensemble Learning and Heterogeneous Document Embeddings for Cross-Lingual Text Classification [78.83284164605473]
  emphFunnelling (Fun) is a recently proposed method for cross-lingual text classification. We describe emphGeneralized Funnelling (gFun) as a generalization of Fun. We show that gFun substantially improves over Fun and over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2021-09-17T23:33:04Z)
• Head-driven Phrase Structure Parsing in O($n^3$) Time Complexity [48.683350567504604]
  Constituent and dependency parsing, the two classic forms of syntactic parsing, have been found to benefit from joint training and decoding under a uniform formalism. We propose an improved head scorer that helps achieve a novel performance-preserved in $O$($n3$) time complexity.
  arXiv  Detail & Related papers  (2021-05-20T15:33:51Z)
• The LL(finite) strategy for optimal LL(k) parsing [0.0]
  The LL(finite) parsing strategy for parsing of LL(k) grammars where k needs not to be known is presented. The strategy parses input in linear time, uses arbitrary but always minimal lookahead necessary to disambiguate between alternatives of nonterminals.
  arXiv  Detail & Related papers  (2020-10-15T16:52:29Z)
• Glushkov's construction for functional subsequential transducers [91.3755431537592]
  Glushkov's construction has many interesting properties and they become even more evident when applied to transducers. Special flavour of regular expressions is introduced, which can be efficiently converted to $epsilon$-free functional subsequential weighted finite state transducers.
  arXiv  Detail & Related papers  (2020-08-05T17:09:58Z)
• Towards Instance-Level Parser Selection for Cross-Lingual Transfer of Dependency Parsers [59.345145623931636]
  We argue for a novel cross-lingual transfer paradigm: instance-level selection (ILPS) We present a proof-of-concept study focused on instance-level selection in the framework of delexicalized transfer.
  arXiv  Detail & Related papers  (2020-04-16T13:18:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.