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

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

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

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

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

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

Однако наш язык всё ещё остаётся излишне свободным и эту свободу большие языковые модель с лёгкостью перенимают. 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 "\nproperties:" (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 при генерации не сможет обратиться к несуществующим столбцам или несуществующим таблицам, потому что у неё просто не будет возможности использовать соответствующие токены в процессе генерации из-за заданных нами динамических ограничений языка.