The LL(finite) strategy for optimal LL(k) parsing

• URL: http://arxiv.org/abs/2010.07874v2
• Date: Wed, 20 Jan 2021 10:22:50 GMT
• Title: The LL(finite) strategy for optimal LL(k) parsing
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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, and it is optimal in the number of lookahead terminal scans performed. Modifications to the algorithm are shown that allow for resolution of grammar ambiguities by precedence -- effectively interpreting the input as a parsing expression grammar -- as well as for the use of predicates, and a proof of concept, the open-source parser generator Astir, employs the LL(finite) strategy in the output it generates.

Related papers

• Efficient Grammar-Constrained Decoding via Parser Stack Classification [27.415578917916054]
  Grammar-constrained decoding (GCD) can guarantee the syntactic validity of the generated output, by masking out tokens that violate rules specified by a context-free grammar.<n>We propose PSC, a novel grammar-constrained decoding method.<n> PSC can compute the complete mask by checking the stack exactly once per decoding step, with time independent of the vocabulary size.
  arXiv  Detail & Related papers  (2026-08-04T03:26:54Z)
• 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)
• Joint Semantic Token Selection and Prompt Optimization for Interpretable Prompt Learning [57.91658393667469]
  Interpretable Prompt Learning is a hybrid framework that alternates between discrete semantic token selection and continuous prompt optimization.<n>Our framework is plug-and-play, allowing seamless integration with existing prompt learning methods.
  arXiv  Detail & Related papers  (2026-05-06T02:38:59Z)
• 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)
• MicLog: Towards Accurate and Efficient LLM-based Log Parsing via Progressive Meta In-Context Learning [26.849902115105255]
  Recent large language model (LLM)-baseds leverage in-context learning (ICL) to extract semantics from examples, demonstrating superior accuracy.<n>We present MicLog, the first progressive meta in-consuming learning (ProgMeta-ICL) log parsing framework that combines meta-learning with ICL on small open-source LLMs.<n>MicLog achieves 10.3% higher parsing accuracy than the state-of-the-art, while reducing parsing time by 42.4%.
  arXiv  Detail & Related papers  (2026-01-11T17:46:10Z)
• Step-by-step Instructions and a Simple Tabular Output Format Improve the Dependency Parsing Accuracy of LLMs [1.088291253486435]
  We propose a novel step-by-step instruction strategy, where universal part-of-speech tagging precedes the prediction of syntactic heads and dependency labels.<n>Our method achieves state-of-the-art accuracy on Universal Dependencies datasets across 17 languages without hallucination or contamination.
  arXiv  Detail & Related papers  (2025-06-11T17:56:10Z)
• $\texttt{SEM-CTRL}$: Semantically Controlled Decoding [53.86639808659575]
  $texttSEM-CTRL$ is a unified approach that enforces rich context-sensitive constraints and task- and instance-specific semantics directly on an LLM decoder. texttSEM-CTRL$ allows small pre-trained LLMs to efficiently outperform larger variants and state-of-the-art reasoning models.
  arXiv  Detail & Related papers  (2025-03-03T18:33:46Z)
• Flexible and Efficient Grammar-Constrained Decoding [5.671312847528642]
  Grammar-constrained decoding (GCD) can guarantee that LLM outputs matches such rules. Existing GCD algorithms require tens of minutes to preprocess common grammars. We present a new GCD algorithm together with an implementation that offers 17.71x faster offline preprocessing than existing approaches.
  arXiv  Detail & Related papers  (2025-02-07T17:35:17Z)
• Semantic Parsing with Candidate Expressions for Knowledge Base Question Answering [4.795837146925278]
  Semantics convert natural language to logical forms, which can be evaluated on knowledge bases (KBs) to produce denotations. Recent semantics have been developed with sequence-to-sequence (seq2seq) pre-trained language models (PLMs) We propose a grammar augmented with candidate expressions for semantic parsing on a large KB with a seq2seq PLM.
  arXiv  Detail & Related papers  (2024-10-01T05:46:22Z)
• Graph-Structured Speculative Decoding [52.94367724136063]
  Speculative decoding has emerged as a promising technique to accelerate the inference of Large Language Models. We introduce an innovative approach utilizing a directed acyclic graph (DAG) to manage the drafted hypotheses. We observe a remarkable speedup of 1.73$times$ to 1.96$times$, significantly surpassing standard speculative decoding.
  arXiv  Detail & Related papers  (2024-07-23T06:21:24Z)
• Grammar-Aligned Decoding [30.972850034752884]
  Large Language Models (LLMs) struggle with reliably generating highly structured outputs, such as program code, mathematical formulas, or well-formed markup. Constrained decoding approaches mitigate this problem by greedily restricting what tokens an LLM can output at each step to guarantee that the output matches a given constraint. In this paper, we demonstrate that GCD techniques can distort the LLM's distribution, leading to outputs that are grammatical but appear with likelihoods that are not proportional to the ones given by the LLM.
  arXiv  Detail & Related papers  (2024-05-31T17:39:15Z)
• Constrained Decoding for Fill-in-the-Middle Code Language Models via Efficient Left and Right Quotienting of Context-Sensitive Grammars [11.279507894576213]
  This paper contributes an incremental synthesis that allows early rejection of syntactically incorrect code. We extend the Earley parsing algorithm to allow for left and right quotients of context-free grammars.
  arXiv  Detail & Related papers  (2024-02-28T02:12:47Z)
• PIP: Parse-Instructed Prefix for Syntactically Controlled Paraphrase Generation [61.05254852400895]
  Parse-Instructed Prefix (PIP) is a novel adaptation of prefix-tuning to tune large pre-trained language models. In contrast to traditional fine-tuning methods for this task, PIP is a compute-efficient alternative with 10 times less learnable parameters.
  arXiv  Detail & Related papers  (2023-05-26T07:42:38Z)
• Happy-GLL: modular, reusable and complete top-down parsers for parameterized nonterminals [0.0]
  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.
  arXiv  Detail & Related papers  (2023-03-14T16:23:23Z)
• Finding Dataset Shortcuts with Grammar Induction [85.47127659108637]
  We propose to use probabilistic grammars to characterize and discover shortcuts in NLP datasets. Specifically, we use a context-free grammar to model patterns in sentence classification datasets and use a synchronous context-free grammar to model datasets involving sentence pairs. The resulting grammars reveal interesting shortcut features in a number of datasets, including both simple and high-level features.
  arXiv  Detail & Related papers  (2022-10-20T19:54:11Z)
• Classifiers are Better Experts for Controllable Text Generation [63.17266060165098]
  We show that the proposed method significantly outperforms recent PPLM, GeDi, and DExperts on PPL and sentiment accuracy based on the external classifier of generated texts. The same time, it is also easier to implement and tune, and has significantly fewer restrictions and requirements.
  arXiv  Detail & Related papers  (2022-05-15T12:58:35Z)
• Provable Adversarial Robustness for Fractional Lp Threat Models [136.79415677706612]
  Attacks bounded by fractional L_p "norms" have yet to be thoroughly considered. We propose a defense with several desirable properties. It provides provable (certified) robustness, scales to ImageNet, and yields deterministic (rather than high-probability) certified guarantees.
  arXiv  Detail & Related papers  (2022-03-16T21:11:41Z)
• LAGr: Labeling Aligned Graphs for Improving Systematic Generalization in Semantic Parsing [6.846638912020957]
  We show that better systematic generalization can be achieved by producing the meaning representation directly as a graph and not as a sequence. We propose LAGr, the Labeling Aligned Graphs algorithm that produces semantic parses by predicting node and edge labels for a complete multi-layer input-aligned graph.
  arXiv  Detail & Related papers  (2021-10-14T17:37:04Z)
• The Limitations of Limited Context for Constituency Parsing [27.271792317099045]
  Parsing-Reading-Predict architecture of (Shen et al., 2018a) was first to perform unsupervised syntactic parsing. What kind of syntactic structure can current neural approaches to syntax represent? We ground this question in the sandbox of probabilistic-free-grammars (PCFGs) We identify a key aspect of the representational power of these approaches: the amount and directionality of context that the predictor has access to.
  arXiv  Detail & Related papers  (2021-06-03T03:58:35Z)
• Reducing Confusion in Active Learning for Part-Of-Speech Tagging [100.08742107682264]
  Active learning (AL) uses a data selection algorithm to select useful training samples to minimize annotation cost. We study the problem of selecting instances which maximally reduce the confusion between particular pairs of output tags. Our proposed AL strategy outperforms other AL strategies by a significant margin.
  arXiv  Detail & Related papers  (2020-11-02T06:24:58Z)

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.