Человеческий язык — это механизм, который ограничивает бесконечную вариабельность возможных звуков и их последовательностей в строгую систему коммуникации.
Фонемы ограничивают сочетания звуков. В русском языке, например, их всего 42.
Слова ограничивают сочетания фонем и переводят наш мир в дискретное множество понятий — так рождается семантика.
Предложения, в свою очередь, ограничивают сочетания слов, создавая структуры для описания явлений воспринимаемого нами мира.
Все эти ограничения составляют суть языка, его синтаксис и семантику.
Однако наш язык всё ещё остаётся излишне свободным и эту свободу большие языковые модель с лёгкостью перенимают. LLM демонстрируют впечатляющую гибкость в генерации текста, но их фундаментальная слабость — неконтролируемая вариативность. Теоретически, пространство возможных генераций модели растёт экспоненциально: если длина генерации — M, а словарь содержит N токенов, то число вариантов равно
. На практике распределение вероятностей и методы вроде top-p/top-k sampling отсекают маловероятные варианты, но даже после этого LLM остаются подвержены хаотичным отклонениям — галлюцинациям, противоречиям и нестабильности форматов.
Один из способов обуздать эту вариативность — внедрение формальных грамматик, задающих жёсткие правила генерации. Грамматика резко сужает пространство возможных токенов, но взамен даёт предсказуемость и структурированность. Это не просто ограничение, а переход от хаотичной генерации к управляемому синтезу, где модель действует в рамках строгих синтаксических правил. Таким образом, больше внимания уделяется семантике, так необходимой для решения прикладных задач.
Формальные грамматики
Формальная грамматика — это система правил, определяющая, какие последовательности символов принадлежат языку, а какие нет. Она задаётся в терминах:
Терминалов (элементарные символы, из которых строятся строки языка)
Пример терминалов в грамматике арифметических выражений: "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 (терминал грамматики), вышел весьма компактный инструмент описания действительности. Однако, в силу контекстной независимости, у нас легко могут получиться такие вот последовательности: "🐕🎶🚀🔍🌕❤️🚀", "🧑🍽️🧑", "🐕🍽️🧑", "🧑❤️🍖🍽️🐕". Последние три особо жуткие, ну а первая просто бессмысленна, хоть и является частью заданного языка. Конечно, можно расписать, какие субъекты какие действия могут использовать над какими объектами/субъектами, но это уже распаковывание контекстных зависимостей, что очень сильно раздувает грамматику — перечислить все варианты экспоненциально сложно.
Контекстно-зависимые грамматики (Тип 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. Его ключевая особенность — разделение всех токенов на контекстно-независимые (их маски предвычисляются) и контекстно-зависимые (проверяются в рантайме), что сокращает 99% проверок. Очень удобно, что XGrammar поддерживается несколькими популярными LLM-движками, типа vLLM и TensorRT-LLM.
Мы в работе используем 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-грамматикой для трёх строк в массиве
Эта грамматика используется на первом этапе нашего RAG Fusion чат-бота для получения трёх вариантов переформулированных запросов пользователя — это нужно для более точного получения релевантных документов и учёта истории чата.
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") "``yaml\n" 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 ::= [ \t\n\r]*
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 при генерации не сможет обратиться к несуществующим столбцам или несуществующим таблицам, потому что у неё просто не будет возможности использовать соответствующие токены в процессе генерации из-за заданных нами динамических ограничений языка.
