Я пытаюсь определить, вносят ли предложенные изменения в грамматику EcmaScript двусмысленности.
Грамматика несколько странная
- Не существует регулярной или контекстно-свободной лексической грамматики, означающей, что нет способа разбить входные данные на серию токенов, которые могут быть переданы в конструктор дерева, хотя в данном состоянии синтаксического анализатора существует контекстно-свободная грамматика, используется для получения следующего токена.
- Некоторые токены неявны. В частности, точки с запятой вставляются в некоторых местах, когда они отсутствуют в исходном тексте. Для этого требуется только один невоспламеняемый токен предвидения, но поскольку игнорируемые токены могут иметь произвольную длину, это предотвращает бесконечное упреждение.
- Нет более простого перевода, чем полный анализ, позволяющий удалить или свернуть игнорируемые токены.
- Токены терминаторов строки (и многострочные комментарии, эквивалентные терминаторам строки) в большинстве контекстов игнорируются, но в некоторых имеют значение.
Я знаю, что доказать отсутствие двусмысленности вообще невозможно, но я бы хотел достичь более простой цели:
Тест, который является истинным тогда и только тогда, когда нет строки, такой, что два разных пути через возможную грамматику могут создать два разных дерева, где каждый путь включает разбиение строки на менее чем k токенов.
Я был бы очень рад, если бы я мог доказать такую вещь для кандидата грамматики до k 50.
Есть ли литература по обнаружению двусмысленности в таких пределах?