Prefix Parsing is Just Parsing

• URL: http://arxiv.org/abs/2604.21191v1
• Date: Thu, 23 Apr 2026 01:20:40 GMT
• Title: Prefix Parsing is Just Parsing
• Abstract summary: 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.
• Score: 53.010152712125766
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Prefix parsing asks whether an input prefix can be extended to a complete string generated by a given grammar. In the weighted setting, it also provides prefix probabilities, which are central to context-free language modeling, psycholinguistic analysis, and syntactically constrained generation from large language models. We introduce the prefix grammar transformation, an efficient reduction of prefix parsing to ordinary parsing. Given a grammar, our method constructs another grammar that generates exactly the prefixes of its original strings. Prefix parsing is then solved by applying any ordinary parsing algorithm on the transformed grammar without modification. The reduction is both elegant and practical: the transformed grammar is only a small factor larger than the input, and any optimized implementation can be used directly, eliminating the need for bespoke prefix-parsing algorithms. We also present a strategy-based on algorithmic differentiation-for computing the next-token weight vector, i.e., the prefix weights of all one-token extensions, enabling efficient prediction of the next token. Together, these contributions yield a simple, general, and efficient framework for prefix parsing.

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)
• A Fundamental Algorithm for Dependency Parsing (With Corrections) [0.0]
  This paper presents a fundamental algorithm for parsing natural language sentences into dependency trees.<n>Unlike phrase-structure parsing, this algorithm operates one word at a time, attaching each word as soon as it can be attached.
  arXiv  Detail & Related papers  (2025-10-22T19:48:38Z)
• Tokenization as Finite-State Transduction [24.19959327497118]
  We introduce a finite-state framework which can efficiently encode all possible tokenizations of a regular language. We show that Byte-Pair. Match (BPE) and MaxPiece (WordPiece) fit within this framework. An application of this is to guided generation, where the outputs of a language model are constrained to match some pattern.
  arXiv  Detail & Related papers  (2024-10-21T07:10:07Z)
• 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.<n>Recent semantics have been developed with sequence-to-sequence (seq2seq) pre-trained language models (PLMs)<n>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)
• Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
  We phrase semantic parsing as a two-step process: we first tag each input token with a multiset of output tokens. Then we arrange the tokens into an output sequence using a new way of parameterizing and predicting permutations. Our model outperforms pretrained seq2seq models and prior work on realistic semantic parsing tasks.
  arXiv  Detail & Related papers  (2023-05-26T14:09:35Z)
• 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)
• On Parsing as Tagging [66.31276017088477]
  We show how to reduce tetratagging, a state-of-the-art constituency tagger, to shift--reduce parsing. We empirically evaluate our taxonomy of tagging pipelines with different choices of linearizers, learners, and decoders.
  arXiv  Detail & Related papers  (2022-11-14T13:37:07Z)
• Inducer-tuning: Connecting Prefix-tuning and Adapter-tuning [53.72897232951918]
  We show that inducer-tuning can close the performance gap between prefix-tuning and fine-tuning. We suggest a new variant of prefix-tuning -- textitinducer-tuning, which shares the exact mechanism as prefix-tuning while leveraging the residual form found in adapter-tuning.
  arXiv  Detail & Related papers  (2022-10-26T04:39:42Z)
• Improving Tokenisation by Alternative Treatment of Spaces [7.596737214110957]
  We experiment with an alternative tokenisation approach where spaces are always treated as individual tokens. We find that our modified algorithms lead to improved performance on downstream NLP tasks.
  arXiv  Detail & Related papers  (2022-04-08T13:22:30Z)
• Prefix-Tuning: Optimizing Continuous Prompts for Generation [85.6357778621526]
  Fine-tuning is the de facto way to leverage large pretrained language models to perform downstream tasks. We propose prefix-tuning, a lightweight alternative to fine-tuning for natural language generation tasks. We find that by learning only 0.1% of the parameters, prefix-tuning obtains comparable performance in the full data setting.
  arXiv  Detail & Related papers  (2021-01-01T08:00:36Z)
• A Unifying Theory of Transition-based and Sequence Labeling Parsing [14.653008985229617]
  We map transition-based parsing algorithms that read sentences from left to right to sequence labeling encodings of syntactic trees. This establishes a theoretical relation between transition-based parsing and sequence-labeling parsing. We implement sequence labeling versions of four algorithms, showing that they are learnable and obtain comparable performance to existing encodings.
  arXiv  Detail & Related papers  (2020-11-01T18:25:15Z)
• Anchor & Transform: Learning Sparse Embeddings for Large Vocabularies [60.285091454321055]
  We design a simple and efficient embedding algorithm that learns a small set of anchor embeddings and a sparse transformation matrix. On text classification, language modeling, and movie recommendation benchmarks, we show that ANT is particularly suitable for large vocabulary sizes.
  arXiv  Detail & Related papers  (2020-03-18T13:07:51Z)

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.