René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Error when handling partial terminal","articleBody":"I'm trying to use syncode to generate Java programs, but it fails when given a valid token. I simplify the case in the reproduction code.\n\nI use a simple test case to demonstrate the case. In the grammar, there are four types of terminals: `WS`, `NUMBER`, `BLOCK_COMMENT` and operators e.g. `+` or `*`. The grammar only allows simple operations, and both `WS` and `BLOCK_COMMENT` are ignored.\n\nWhen the text starts with `/**/`, which by itself is a legal `BLOCK_COMMENT`, it is divided by the tokenizer into `/**` and `/`. Then, if the `/**` token is selected by the model, because it is not a complete `BLOCK_COMMENT`, it is lexed into `/`, `*` and `*`, and then causes error like this.\n```text\n[YYYY-MM-DD hh:mm:ss,sss -syncode.grammar_mask.grammar_constrainer] - Parsing failed!\nPartial code: /**\nParsed lexical tokens: [Token('SLASH', '/')]\n[YYYY-MM-DD hh:mm:ss,sss -syncode.grammar_mask.grammar_constrainer] - --------------------------------------------------\nTraceback (most recent call last):\n  File \".../lib/python3.11/site-packages/syncode/larkm/parsers/lalr_parser_state.py\", line 77, in feed_token\n    action, arg = states[state][token.type]\n                  ~~~~~~~~~~~~~^^^^^^^^^^^^\nKeyError: 'SLASH'\n```\n\nThis is because, the terminals are lexed purely based on the visible partial code, but doesn't consider the possibility that the partial code could be a prefix of another terminal. When it fails to match one terminal in the partial code (`BLOCK_COMMENT` in this case), it turns to match another code. This can be seen from the following `match` method of the `Scanner` class who does the real lexing job for the partial code. This behavior is totally fine in the `lark` library, because the code is almost always complete, but it is not OK for a constrained decoding method like `syncode`.\nhttps://github.com/structuredllm/syncode/blob/8afb425570440afcaada961b2da483867d9f2ff8/syncode/larkm/lexer.py#L387-L391\n\n\n### Reproduction code\n```Python\nfrom syncode.grammar_mask.grammar_constrainer import GrammarConstrainer\nfrom syncode.parsers.grammars import Grammar\nfrom syncode.mask_store.byte_tokenizer import ByteTokenizer\n\nfrom transformers import AutoTokenizer\nimport torch\n\nclass FakeGrammar(Grammar):\n  def __init__(self, name: str, ebnf: str):\n    self.ebnf = ebnf\n    self.name = name\n\ntokenizer = AutoTokenizer.from_pretrained('Qwen/Qwen2.5-0.5B')\ngrammar = FakeGrammar('custom',\nr'''start: sum\nsum: sum (\"+\" | \"-\") term\nterm: term (\"*\" | \"/\") factor\nfactor: \"(\" sum \")\" | NUMBER\nNUMBER: /[0-9]+/\nBLOCK_COMMENT: /\\/\\*.*?\\*\\//s\n%ignore BLOCK_COMMENT\n%import common.WS\n''')\nbyte_tokenizer = ByteTokenizer(tokenizer)\ngrammar_constrainer = GrammarConstrainer(\n  grammar=grammar,\n  tokenizer=tokenizer, # type: ignore\n  byte_tokenizer=byte_tokenizer,\n  use_cache=True,\n  parse_output_only=True,\n  batch_size=1,\n  dev_mode=True,\n  parser='lalr',\n  mode='grammar_strict',\n  indent=False\n)\n\nvocab_size = len(tokenizer.get_vocab())\n\ndef process_logit(input_ids: list[int], logit: torch.Tensor) -\u003e torch.Tensor:\n  return grammar_constrainer.mask_scores(torch.tensor([input_ids]), logit.unsqueeze(0)).squeeze(0) # type: ignore\n\ndef process_tokens(tokens: list[int]):\n  for i in range(len(tokens)):\n    logit = torch.zeros((vocab_size,), dtype=torch.float)\n    visible_tokens = tokens[:i]\n    masked_logit = process_logit(visible_tokens, logit)\n    assert masked_logit[tokens[i]] != float('-inf'), f'token {i} ({tokens[i]}, {tokenizer.decode(tokens[i])!r}) is masked'\n\ntext = '/**/1+1'\ntokens = tokenizer.encode(text)\nprint(tokens)\nprocess_tokens(tokens)\n```","author":{"url":"https://github.com/Gompyn","@type":"Person","name":"Gompyn"},"datePublished":"2025-08-20T15:16:06.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":1},"url":"https://github.com/227/syncode/issues/227"}