Будущее ИИ — формальные грамматики

Человеческий язык — это механизм, который ограничивает бесконечную вариабельность возможных звуков и их последовательностей в строгую систему коммуникации.

1. Фонемы ограничивают сочетания звуков. В русском языке, например, их всего 42.

2. Слова ограничивают сочетания фонем и переводят наш мир в дискретное множество понятий — так рождается семантика.

3. Предложения, в свою очередь, ограничивают сочетания слов, создавая структуры для описания явлений воспринимаемого нами мира.

Все эти ограничения составляют суть языка, его синтаксис и семантику.

Однако, наш язык всё ещё остаётся излишне свободным и эту свободу большие языковые модель с лёгкостью перенимают. LLM демонстрируют впечатляющую гибкость в генерации текста, но их фундаментальная слабость — неконтролируемая вариативность. Теоретически, пространство возможных генераций модели растёт экспоненциально: если длина генерации — M, а словарь содержит N токенов, то число вариантов равно. На практике распределение вероятностей и методы вроде top-p/top-k sampling отсекают маловероятные варианты, но даже после этого LLM остаются подвержены хаотичным отклонениям — галлюцинациям, противоречиям и нестабильности форматов.

Один из способов обуздать эту вариативность — внедрение формальных грамматик, задающих жёсткие правила генерации. Грамматика резко сужает пространство возможных токенов, но взамен даёт предсказуемость и структурированность. Это не просто ограничение, а переход от хаотичной генерации к управляемому синтезу, где модель действует в рамках строгих синтаксических правил. Таким образом, больше внимания ^[1] уделяется семантике, так необходимой для решения прикладных задач.

Формальные грамматики

Формальная грамматика — это система правил, определяющая, какие последовательности символов принадлежат языку, а какие нет. Она задаётся в терминах:  

• Терминалов (элементарные символы, из которых строятся строки языка)

  • Пример терминалов в грамматике арифметических выражений: “0”, “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, “9”, “+”, “-“, “=”, “*”, “(“, “)”, “/”, …

  • Пример терминалов в грамматике ДНК: “ATG”, “TTT”, “TAA” и другие триплеты нуклеотидов (всего их 64).  

• Нетерминалов (вспомогательные сущности, обозначающие синтаксические категории) 

  • Пример нетерминалов в грамматике арифметических выражений: Expression, Number — абстрактные сущности, составляющие арифметические выражения.

  • Пример нетерминалов в грамматике ДНК: Gene, Codon, Codons, Promoter, START, STOP — абстрактные сущности, составляющие ДНК.

• Правил вывода (описывают, как нетерминалы раскрываются в комбинации терминалов и других нетерминалов).  

  • Пример правил вывода в грамматике арифметических выражений:

Expression ::= Term (("+" | "-") Term)*

Term   	::= Factor (("*" | "/") Factor)*

Factor 	::= NUMBER | "(" Expression ")"

NUMBER 	::= [0-9]+

Способ описания правил, который здесь показан, используется для ограничения генерации LLM и называется GBNF — расширение EBNF с регулярными выражениями, который в свою очередь расширяет BNF (Backus–Naur form). В этом зоопарке нотаций можно запутаться, но в целом всё это сводится к простому описанию правил подстановок вида A → B. Кстати говоря, в данном случае правила весьма простые и их все можно свернуть в одно при помощи тех же подстановок:

Expression ::= [0-9]+ | "(" Expression ")" (("*" | "/") [0-9]+ | "(" Expression ")")* (("+" | "-") [0-9]+ | "(" Expression ")" (("*" | "/") [0-9]+ | "(" Expression ")")*)*

Это, конечно, сильно сложнее прочитать, но зато легко виден практический смысл нетерминалов при задании грамматик.

В целом грамматики бывают принципиально разные. Некоторые задаются обычным регулярным выражением, например, множество возможных email-адресов. Некоторые требуют использование стека и рекурсивной обработки, например, для проверки правильных скобочных комбинаций. Есть грамматики, в которых правила вывода зависят от контекста и в разных контекстах применяются различные правила. Более того, в некоторых случаях правила вывода могут практически не иметь ограничений. Все описанные случаи фундаментально отличаются и выделяются в отдельные классы грамматик, которые в 1956 году были предложены Ноамом Хомским в рамках разработанной иерархии:

Каждая из них отличается реализацией через конкретный автомат, позволяет задавать правила определённого вида, а также обладает собственной сложностью распознавания языка:

Начнём с самого простого — регулярных языков, ну или языков, задаваемых регулярными выражениями.

Регулярные грамматики (Тип 3)

Регулярные выражения широко применяются для распознавания простых символьных паттернов, например, email-адреса:

^[a-zA-Z0-9._]+@[a-zA-Z0-9]+(?:.[a-zA-Z0-9]+)+$

Зададим ту же самую грамматику в показанном ранее синтаксисе GBNF, используя терминалы, нетерминалы и правила вывода:

email  	::= local_part "@" domain

local_part ::= (letter | digit | "." | "_")+

domain 	::= label "." domain | label

label      ::= (letter | digit)+

letter     ::= [a-zA-Z]

digit      ::= [0-9]

Покажем поэтапно, как происходит вывод для строки “user.123@somemail.com”:

email 

→ local_part "@" domain

→ "u" local_part "@" domain

→ ... → "user.123" "@" domain

→ "user.123@" label "." domain

→ "user.123@somemail." domain

→ "user.123@somemail." label

→ "user.123@somemail.com"

Контекстно-свободные грамматики (Тип 2)

Можно ли задать грамматику SQL в виде контекстно-свободной грамматики? Давайте рассмотрим случай, состоящий из обычного SELECT … FROM … и нескольких условий в WHERE:

query   	::= "SELECT" columns "FROM" entity_name "WHERE" condition

columns 	::= (entity_name ", ")+

condition   ::= entity_name operator value

                | condition ("AND" | "OR") condition 

                | "(" condition ")"

operator	::= "=" | ">" | "<" | "!="

value   	::= string | number

entity_name ::= [a-zA-Z0-9_]+

string  	::= """ [a-zA-Z0-9_ ]* """

number  	::= [0-9]+

Такая грамматика уже не реализуется в виде регулярного выражения, потому что здесь есть вложенные структуры и рекурсии, для которых необходимо иметь стек.

Разберём, как будет выглядеть вывод для следующего выражения: ‘SELECT name, age FROM users WHERE age > 25 AND name = “Андрей”‘:

query

→ 'SELECT' columns 'FROM' entity_name 'WHERE' condition

→ 'SELECT' entity_name ',' entity_name 'FROM' 'users' 'WHERE' condition

→ 'SELECT' 'name' ',' 'age' 'FROM' 'users' 'WHERE' condition 'AND' condition

→ 'SELECT name, age FROM users WHERE' entity_name operator value 'AND' entity_name operator value

→ 'SELECT name, age FROM users WHERE' 'age' '>' number 'AND' 'name' '=' string

→ 'SELECT name, age FROM users WHERE age > 25 AND name = "Андрей"'

Далее в качестве показательного примера разберём простой язык emoji:

story    ::= event+

event    ::= subject (verb (object | subject)+)+

subject  ::= "🧑" | "🐕"

verb     :: "🏃" | "🍽️" | "❤️" | "🔍" | "🫴" | "🎶"

object   :: "🍖" | "🏠" | "🌕" | "🌳" | "🚀"

Вывод для “🧑🏃 🏠 🫴 🍖 🐕 🐕 🍽️ 🍖 ❤️ 🧑” (человек прибежал домой и дал еду собаке, собака съела еду и любит человека):

story

→ event event

→ subject verb object verb object subject event

→ '🧑' verb object verb object subject event

→ '🧑 🏃' object verb object subject event

→ '🧑 🏃 🏠' verb object subject event

...

→ '🧑 🏃 🏠 🫴 🍖 🐕' event

→ '🧑 🏃 🏠 🫴 🍖 🐕' subject verb object verb subject

→ '🧑 🏃 🏠 🫴 🍖 🐕 🐕' verb object verb subject

...

→ '🧑 🏃 🏠 🫴 🍖 🐕 🐕 🍽️ 🍖 ❤️ 🧑'

Синтаксически получился чрезвычайно простой язык, но из-за семантики, которую мы закладываем в каждый emoji (терминал грамматики), вышел весьма компактный инструмент описания действительности. Однако, в силу контекстной независимости, у нас легко могут получиться такие вот последовательности: “🐕🎶🚀🔍🌕❤️🚀”, “🧑🍽️🧑”, “🐕🍽️🧑”, “🧑❤️🍖🍽️🐕”. Последние три3 особо жуткие, ну а первая просто бессмысленна, хоть и является частью заданного языка. Конечно, можно расписать, какие субъекты какие действия могут использовать над какими объектами/субъектами, но это уже распаковывание контекстных зависимостей, что очень сильно раздувает грамматику — перечислить все варианты экспоненциально сложно.

Контекстно-зависимые грамматики (Тип 1)

В языке emoji для учёта контекстных зависимостей нам поможет следующий тип грамматик в иерархии Хомского — контекстно-зависимые грамматики. 

Повторим предыдущую грамматику, но введём некоторые ограничения:

story    ::= event+

event    ::= subject (verb (object | subject)+)+

subject  ::= "🧑" | "🐕"

verb     ::= "🏃" | "🍽️" | "❤️" | "🔍" | "🫴" | "🎶"

object   ::= "🍖" | "🏠" | "🌕" | "🌳" | "🚀"

 

# 1. Ограничения для собак [Собака может только определенные действия]

"🐕" verb ::= "🐕" dog_verb

dog_verb ::= "🏃" | "🍽️" | "❤️" | "🔍"

 

# 2. Запрет на поедание живых существ

verb "🧑" ::= accepted_actions "🧑"

verb "🐕" ::= accepted_actions "🐕"

accepted_actions ::= "🏃" | "❤️" | "🔍" | "🫴" | "🎶"

 

# 3. Ограничения на поедание несъедобных объектов объектов

"🧑" "🍽️" object ::= "🧑" "🍽️" edible

"🐕" "🍽️" object ::= "🐕" "🍽️" edible

edible        	::= "🍖"

В этой грамматике допустимы описания по типу “🧑❤️🐕”, но никак не “🐕🎶🚀” или что хуже “🧑🍽️🧑”.

Вот теперь строки языка являются более осмысленными и морально корректными, хоть нам и пришлось сделать переход в более сложный класс грамматик — на то она и контекстная зависимость, которая, например, полностью пронизывает наш естественный язык.

Неограниченные грамматики (Тип 0)

Остаётся рассмотреть последний тип неограниченных грамматик, в котором правила вывода могут быть практически чем угодно. Что-то осмысленное и прикладное для наших задач здесь привести сложно, поэтому давайте просто выдумывать:

💥⭐️ ::= 🌫️🌫️🌫️ ::= 🌍                     	# Взрыв сверхновой привёл к появлению газопылевых облаков, что привело к появлению планеты Земля (видно, что последовательности терминалов могут и укорачиваться в типе 0)

 

person_subject ::= 👩 | 👨

person_subject💣🏦🫳💰 ::= ⛓️person_subject⛓️  # Если кто-то грабит банк, то наказание для него неотвратимо

person_subject🚬 ::= ☠️                      	# Очевидно, курение ни к чему хорошему не приводит

Ну и так далее, принцип ясен.

Как заставить LLM говорить на нужном языке

Для того, чтобы заставить LLM не выходить за пределы заданной в GBNF грамматики, существует такой инструмент, как XGrammar ^[2]. Его ключевая особенность — разделение всех токенов на контекстно-независимые (их маски предвычисляются) и контекстно-зависимые (проверяются в рантайме), что сокращает 99% проверок. Очень удобно, что XGrammar поддерживается несколькими популярными LLM-движками, типа vLLM ^[3] и TensorRT-LLM ^[4].

Мы в работе используем vLLM с интерфейсом ChatOpenAI — это позволяет легко задавать грамматику в поле guided_grammar следующим образом:

from langchain_openai import ChatOpenAI

llm = ChatOpenAI(

    model="Qwen/Qwen3-32B-AWQ",

    max_completion_tokens=10000,

    temperature=0.6,

    base_url="base_url",

    api_key="api_key",

    extra_body={

        "guided_grammar":grammar,

        "top_k": 20,

        "chat_template_kwargs": {"enable_thinking": False}

    }

)

Составление грамматик для прикладных задач

Пример с JSON-грамматикой для трёх3 строк в массиве

Эта грамматика используется на первом этапе нашего RAG Fusion чат-бота ^[5] для получения трёх вариантов переформулированных запросов пользователя — это нужно для более точного получения релевантных документов и учёта истории чата.

root        	::= "[" string_value "," string_value "," string_value "n]"

string_value	::= "n  " """ [^"n]* """

Например, для запроса “Как уничтожить все строки таблицы?” будут сгенерированы следующие варианты:

[

  "Как удалить все строки из таблицы с помощью SQL?",

  "How to delete all rows from a table using SQL?",

  "Как полностью очистить таблицу, удалив все строки?"

]

Пример с грамматикой для языка миграций моделей данных

Один из наших проектов — генератор моделей данных и спецификации приложений на основе диалога с пользователем. Эта система изначально проектировалась, как транзакционная, то есть любые изменения на основе новых данных от пользователя производятся при помощи заданного набора миграций: add_property, remove_property, rename_property, add_enum_value и других. Всего их на текущий момент 18 штук и для каждой операции миграции существует своё собственное описание в формате yaml:

root        	        ::= (think_block "n") "``yamln" operations "n``"

 

# Thinking block

think_block 	::= "<think>nOk," allowed_char "n</think>"

allowed_char	::= [na-zA-Zа-яА-ЯёЁ0-9!@#$%^&*()_+{}[]\|;:'",./? -]*

 

# Operations

operations  	  ::= "operations:" ("n" operation_item)+

operation_item  ::= "  - operation: " operation

operation   	  ::= add_property | remove_property | rename_property | add_enum_value

                | remove_enum_value | replace_enum | modify_ref | add_definition

                | remove_definition | rename_definition | remove_user_stories

                | add_user_stories | update_description | add_ui_page | remove_ui_page

                | change_ui_page | add_endpoint | remove_endpoint

 

# Common rules

entity       	::= [a-zA-Z_]+

key          	::= [a-zA-Z_]+

string_value	::= """ [^"n]* """

integer     	::= [0-9]+

boolean          ::= "true" | "false"

 

# Types

types       	::= exact_numeric | floating_point | integer_type

                  | string_type | temporal_type | geometric_type

                  | network_type | json_type | binary_type

                  | boolean_type | uuid_type | monetary_type

                  | bit_type | text_search_type | serial_type

 

# Numeric Types

exact_numeric   ::= "numeric" "(" integer "," integer ")"

floating_point  ::= "real" | "double precision"

monetary_type   ::= "money"

 

# Integer Types

integer_type	::= "smallint" | "integer" | "bigint"

serial_type 	::= "smallserial" | "serial" | "bigserial"

# ...

# Definition Operations

add_definition   	::= "add_definition" entity_spec "n	properties:" (property_def)+

property_def     	::= "n  	" key ":" (prop_schema_type | prop_schema_ref | prop_schema_enum | prop_schema_elements) prop_pk? prop_optional?

prop_schema_type 	::= "n    	type: " types

prop_schema_elements ::= "n    	elements: " (prop_schema_elements_ref | prop_schema_elements_type)

prop_schema_ref  	::= "n    	ref: " entity

prop_schema_enum 	::= "n    	enum:" ("n      	- " string_value)+

prop_optional    	::= "n    	optional: " boolean

prop_pk          	::= "n    	primary_key: " boolean

# ...

Здесь представлена небольшая часть грамматики миграций с базовыми нетерминалами, примером задания типов данных и описанием операции добавления новой сущности в модель данных (add_definition).

Вот как выглядит миграция в этом языке на запрос “Сгенерируй модель данных для приложения по продаже хоррор-книг”:

<think>

...

</think>

```yaml

operations:

  - operation: add_definition

    entity: user

    properties:

      id:

        type: uuid

        primary_key: true

      email:

        type: varchar(255)

      password_hash:

        type: char(60)

      is_admin:

        type: boolean

      created_at:

        type: timestamptz

  - operation: add_definition

    entity: book

    properties:

      id:

        type: uuid

        primary_key: true

      title:

        type: varchar(255)

      description:

        type: text

      price:

        type: numeric(10,2)

      stock_quantity:

        type: integer

      category:

        ref: category

      author:

        ref: author

      created_at:

        type: timestamptz

  - operation: add_definition

    entity: category

    properties:

      id:

        type: uuid

        primary_key: true

      name:

        type: varchar(100)

  - operation: add_definition

    entity: author

    properties:

      id:

        type: uuid

        primary_key: true

      name:

        type: varchar(100)

  - operation: add_definition

    entity: order

    properties:

      id:

        type: uuid

        primary_key: true

      user:

        ref: user

      total_amount:

        type: numeric(10,2)

      status:

        enum:

          - "pending"

          - "completed"

          - "cancelled"

      placed_at:

        type: timestamptz

  - operation: add_definition

    entity: orderItem

    properties:

      id:

        type: uuid

        primary_key: true

      order:

        ref: order

      book:

        ref: book

      quantity:

        type: integer

      price_at_purchase:

        type: numeric(10,2)

  - operation: add_definition

    entity: cart

    properties:

      user:

        ref: user

        primary_key: true

      items:

        elements:

          ref: cartItem

  - operation: add_definition

    entity: cartItem

    properties:

      book:

        ref: book

        primary_key: true

      quantity:

        type: integer

      added_at:

        type: timestamptz

  - operation: add_user_stories

    stories:

      - "As a user, I can browse horror books by category."

      - "As a user, I can view detailed information about a book including author and description."

      - "As a user, I can add books to my shopping cart."

      - "As a user, I can update or remove items from my cart."

      - "As a user, I can place an order and receive a confirmation."

      - "As a user, I can view my order history."

      - "As an admin, I can add, update, or remove books from the catalog."

      - "As an admin, I can manage user accounts and view all orders."

  - operation: update_description

    text: "A horror book selling application where users can browse, purchase, and manage horror-themed books. Admins can manage the catalog and orders."

```

А вот как будет выглядеть доработка со следующим уточнением “У книги может быть несколько авторов”:

<think>

...

</think>

```yaml

operations:

  - operation: remove_property

    entity: book

    key: author

  - operation: add_property

    entity: book

    key: authors

    schema:

      elements:

        ref: author

  - operation: update_description

    text: "A horror book selling application where users can browse, purchase, and manage horror-themed books. Books can have multiple authors. Admins can manage the catalog and orders."

```"

То есть мы не перегенерируем всю схему с нуля, а добавляем любое изменение через заданную грамматику миграций, за рамки которой LLM выйти никак не сможет.

Пример с грамматикой PostgreSQL в GBNF, полученной из Bison+Flex

Для того, чтобы LLM генерировала синтаксически корректный SQL для разных версий СУБД, нами были приняты работы по преобразованию LALR грамматики PostgreSQL (Bison+Flex) в LL (GBNF), что не является такой уж тривиальной задачей.

root ::= parse_toplevel

ws ::= [ tnr]*

parse_toplevel ::= toplevel_stmt ws ( ";" ws toplevel_stmt )*

 

toplevel_stmt ::= stmt

           | TransactionStmtLegacy

stmt ::= ( AlterEventTrigStmt | AlterCollationStmt | AlterDatabaseStmt | AlterDatabaseSetStmt | AlterDefaultPrivilegesStmt | AlterDomainStmt | AlterEnumStmt | AlterExtensionStmt | AlterExtensionContentsStmt | AlterFdwStmt | AlterForeignServerStmt | AlterFunctionStmt | AlterGroupStmt | AlterObjectDependsStmt | AlterObjectSchemaStmt | AlterOwnerStmt | AlterOperatorStmt | AlterTypeStmt | AlterPolicyStmt | AlterSeqStmt | AlterSystemStmt | AlterTableStmt | AlterTblSpcStmt | AlterCompositeTypeStmt | AlterPublicationStmt | AlterRoleSetStmt | AlterRoleStmt | AlterSubscriptionStmt | AlterStatsStmt | AlterTSConfigurationStmt | AlterTSDictionaryStmt | AlterUserMappingStmt | AnalyzeStmt | CallStmt | CheckPointStmt | ClosePortalStmt | ClusterStmt | CommentStmt | ConstraintsSetStmt | CopyStmt | CreateAmStmt | CreateAsStmt | CreateAssertionStmt | CreateCastStmt | CreateConversionStmt | CreateDomainStmt | CreateExtensionStmt | CreateFdwStmt | CreateForeignServerStmt | CreateForeignTableStmt | CreateFunctionStmt | CreateGroupStmt | CreateMatViewStmt | CreateOpClassStmt | CreateOpFamilyStmt | CreatePublicationStmt | AlterOpFamilyStmt | CreatePolicyStmt | CreatePLangStmt | CreateSchemaStmt | CreateSeqStmt | CreateStmt | CreateSubscriptionStmt | CreateStatsStmt | CreateTableSpaceStmt | CreateTransformStmt | CreateTrigStmt | CreateEventTrigStmt | CreateRoleStmt | CreateUserStmt | CreateUserMappingStmt | CreatedbStmt | DeallocateStmt | DeclareCursorStmt | DefineStmt | DeleteStmt | DiscardStmt | DoStmt | DropCastStmt | DropOpClassStmt | DropOpFamilyStmt | DropOwnedStmt | DropStmt | DropSubscriptionStmt | DropTableSpaceStmt | DropTransformStmt | DropRoleStmt | DropUserMappingStmt | DropdbStmt | ExecuteStmt | ExplainStmt | FetchStmt | GrantStmt | GrantRoleStmt | ImportForeignSchemaStmt | IndexStmt | InsertStmt | ListenStmt | RefreshMatViewStmt | LoadStmt | LockStmt | MergeStmt | NotifyStmt | PrepareStmt | ReassignOwnedStmt | ReindexStmt | RemoveAggrStmt | RemoveFuncStmt | RemoveOperStmt | RenameStmt | RevokeStmt | RevokeRoleStmt | RuleStmt | SecLabelStmt | SelectStmt | TransactionStmt | TruncateStmt | UnlistenStmt | UpdateStmt | VacuumStmt | VariableResetStmt | VariableSetStmt | VariableShowStmt | ViewStmt )?

opt_single_name ::= ColId?

opt_qualified_name ::= any_name?

opt_concurrently ::= "CONCURRENTLY"?

opt_drop_behavior ::= ( "CASCADE" | "RESTRICT" )?

CallStmt ::= "CALL" ws func_application

CreateRoleStmt ::= "CREATE" ws "ROLE" ws RoleId ws opt_with ws OptRoleList

opt_with ::= ( "WITH" | "WITH" )?

OptRoleList ::= CreateOptRoleElem*

AlterOptRoleElem ::= "PASSWORD" ws ( Sconst | "NULL" )

           | ( ( "ENCRYPTED" | "UNENCRYPTED" ) ws "PASSWORD" | "VALID" ws "UNTIL" ) ws Sconst

           | "INHERIT"

           | "CONNECTION" ws "LIMIT" ws SignedIconst

           | "USER" ws role_list

           | IDENT

CreateOptRoleElem ::= AlterOptRoleElem

           | "SYSID" ws Iconst

           | ( "ADMIN" | "ROLE" | "IN" ws ( "ROLE" | "GROUP" ) ) ws role_list

CreateUserStmt ::= "CREATE" ws "USER" ws RoleId ws opt_with ws OptRoleList

 

# ...

 

ICONST ::= [0-9] ([0-9]){0,8} |

           "1" ([0-9]){9} |

           "20" ([0-9]){8} |

           "21" [0-3]([0-9]){7} |

           "214" [0-6]([0-9]){6} |

           "2147" [0-3]([0-9]){5} |

           "21474" [0-7]([0-9]){4} |

           "214748" [0-2]([0-9]){3} |

           "2147483" [0-5]([0-9]){2} |

           "21474836" [0-3]([0-9]){1} |

           "214748364" [0-7]

Особенности преобразования Bison → GBNF

GBNF- формат впервые появился как часть экосистемы llama.cpp примерно в 2023 году. Будучи сравнительно новым форматом грамматики, он не имеет инструментов, позволяющих напрямую приводить Bison к GBNF. Ближайшим схожим форматом, который дает возможность переводить грамматики Bison, является EBNF. 

Глобально, GBNF отличается от EBNF (диалекта W3C EBNF) необходимостью ручного описания пробелов, символами комментариев (остаются в стиле парсера, т.е. такие, как и в Bison), символами кавычек (двойные вместо одинарных).

Также существуют отличия и в самой сущности парсеров и форматов грамматик: в Bison фрагменты кода являются частью грамматик, в то время как GBNF/EBNF являются чисто декларативными языками описания, а потому частные случаи в Bison либо невозможно определить через GBNF, либо необходимо задавать вручную.

Кроме того, стоит учитывать, что грамматика изначально описывается не только в самом Bison, но и частично задана в файле лексера (Flex). При преобразовании Bison → GBNF константы лексера нужно обрабатывать вручную, так как инструмента для их автоматического извлечения пока нет.

Отдельную сложность представляет обработка леворекурсивных правил. Так как парсер в Xgrammar относится к классу LL, все леворекурсивные правила вызывают бесконечный цикл. Для разрешения леворекурсивных правил можно применить следующее преобразование:

Пусть имеется (1) A ::= A a1 a2 a3… | b | c, где a1, a2, a3, …, b и c –- свободные от A правила. Тогда:

(2) A ::= (b | c) A'?

     A' ::= a1 a2 a3 ... A'?

Так как A в новом определении обязательно начинается с b или c, то левых рекурсий не возникает, в то время как правые рекурсии (A’ ::= a1… A’) не вызывают зацикливания.

Покажем эквивалентность (1) и (2).

В (2) правила обязаны начинаться с b | c, докажем от противного что (1) также всегда начинается с b | c:
Пусть A ::= A a1 a2 a3… | b | c и первая рекурсия не равна b | c, значит A ::= A a1 a2 a3…, попробуем снова подставить выражение A a1 a2 a3… вместо А, тогда:

A ::= A a1 a2 a3... a1 a2 a3..

Видим, что у нас получается бесконечный цикл до тех пор, пока А не станет равно b | c. Тогда имеем:

A ::= (b | c) (a1 a2 a3...)*

Или A ::= (b | c) A’,  A’ ::= a1 a2 a3 … A’, то есть привели выражение (1) к (2).

Динамические грамматикиами

Идея динамических грамматик проста до нельзя, но в то же время очень эффективна. Допустим, правильность написанного кода зависит от среды, в котором он исполняется, например, тот же SQL в одной БД будет корректен, а в другой — нет. Теперь, вместо того, чтобы использовать одну и ту же грамматику на все случаи жизни, создадим шаблон, в котором будем доопределять нетерминалы, необходимые для корректного исполнения кода. Получается некоторое введение контекстной зависимости при помощи тех же самых контекстно-независимых грамматик. Таким образом, LLM при генерации не сможет обратиться к несуществующим столбцам или несуществующим таблицам, потому что у неё просто не будет возможности использовать соответствующие токены в процессе генерации из-за заданных нами динамических ограничений языка.