Improving LLM Code Generation with Grammar Augmentation
Shubham Ugare Tarun Suresh Hangoo Kang Sasa Misailovic Gagandeep Singh
We present SynCode a novel framework for efficient and general syntactical
decoding of code with large language models (LLMs). SynCode leverages the
grammar of a programming language, utilizing an offline-constructed efficient
lookup table called DFA mask store based on language grammar terminals. We
demonstrate SynCode's soundness and completeness given the context-free grammar
(CFG) of the programming language, presenting its ability to retain
syntactically valid tokens while rejecting invalid ones. The framework
seamlessly integrates with any language defined by CFG, as evidenced by
experiments on CFGs for Python and Go. The results underscore the significant
reduction of 96.07% of syntax errors achieved when SynCode is combined with
state-of-the-art LLMs, showcasing its substantial impact on enhancing
syntactical precision in code generation.
  Our code is available at https://github.com/uiuc-focal-lab/syncode.