Почему синтаксический анализ aaaaabb не увенчался успехом при заданной грамматике?


Предположим, что грамматика G имеет следующие произведения…

  1. S → aSb | А | Б
  2. А → λ | а | аа | ааа
  3. Б → ББ | б

Используя грамматику G, вывод строки aaaaabb будет …

S ⇒ aSb ⇒ aaSbb ⇒ aaAbb ⇒ aaaaabb


Почему в грамматике Раку, показанной ниже, разбор строки aaaaabb не удался? Вывод, показанный выше, неприменим?


# Goal: language generated by grammar = { a^n b^m : n <= m + 3 }
# Example string is:
#   aaaaabb = a^5 b^2, where 5 <= 2 + 3
# Derivation of string aaaaabb is:
#   S => aSb => aaSbb => aaAbb => aaaaabb

grammar MyContextFreeGrammar
    {
    token TOP { <S> }
    token S   { 'a' <S> 'b' | <A> | <B> }
    token A   { '' | 'a' | 'a' 'a' | 'a' 'a' 'a' }
    token B   { 'b' <B> | 'b' }
    } # end grammar

my $abString = 'aaaaabb';

my $myParseResult = MyContextFreeGrammar.parse( $abString ) ;

if $myParseResult.Bool
  {
  printf( "\nParsing of \'%s\' was *SUCCESSFUL*.\n", $abString ) ;
  }
else
  {
  printf( "\nParsing of \'%s\' was *NOT* successful.\n", $abString ) ;
  }

Вывод программы…

Parsing of 'aaaaabb' was *NOT* successful.

Обновлять

Документация Раку (https://docs.raku.org/language/grammars) указывает, что…

(Деклараторы token и rule) являются храповыми, что означает, что механизм сопоставления не будет выполнять резервное копирование и пытаться снова, если ему не удастся что-то сопоставить.

Пересмотренная грамматика, показанная ниже, в которой используется regex, а не token, допускает возврат и ведет себя так, как нужно для двух тестовых строк aaaaabb (на языке, сгенерированном грамматикой G) и aaaaaabb (на языке, сгенерированном грамматикой G). ) …

grammar MyContextFreeGrammar
    {
    regex TOP { <S> }
    regex S   { 'a' <S> 'b' | <A> | <B> }
    regex A   { '' | 'a' | 'a' 'a' | 'a' 'a' 'a' }
    regex B   { 'b' <B> | 'b' }
    } # end grammar

my $abString = 'aaaaabb';
my $myParseResult = MyContextFreeGrammar.parse( $abString ) ;
printf( "\nParsing of \'%s\' was "
        ~ ($myParseResult ?? "*SUCCESSFUL*.\n" !! "*NOT* successful.\n" ),
        $abString ) ;

$abString = 'aaaaaabb';
$myParseResult = MyContextFreeGrammar.parse( $abString ) ;
printf( "\nParsing of \'%s\' was "
        ~ ($myParseResult ?? "*SUCCESSFUL*.\n" !! "*NOT* successful.\n" ),
        $abString ) ;

Вывод программы…

Parsing of 'aaaaabb' was *SUCCESSFUL*.

Parsing of 'aaaaaabb' was *NOT* successful.

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
7
0
157
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Грамматики Раку — это синтаксические анализаторы, а не порождающие грамматики.

Естественный идиоматический пример решения проблемы:

grammar S { token TOP { (a*) (b*) <?{ $0.chars <= $1.chars + 3 }> } }

Это напрямую кодирует описание вашего примера в синтаксическом анализаторе - token¹ выполняет сопоставление/захват нуля или более as, затем сопоставление/захват нуля или более bs и, наконец, проверку предиката, соответствующую формуле вашего примера.


Код теста и результаты:

say "$_: {so S.parse: $_}" for ^9 .map: { 'a' x $_ ~ 'bb' }

bb: False
abb: True
aabb: True
aaabb: True
aaaabb: True
aaaaabb: True
aaaaaabb: False
aaaaaaabb: False
aaaaaaaabb: False

Генеративные грамматики можно использовать с Раку точно так же, как их можно использовать с любым другим ЯП.

Но видение и миссия Раку включают в себя первоклассные грамматики (и фрагменты грамматики), которые можно составить.

Если вы объедините две или более генеративные CFG, результат может быть неоднозначным, даже если составляющие их грамматики однозначны. Не существует алгоритма, который может определить, является ли результат неоднозначным, поэтому не может быть даже предупреждения или ошибки, если композиция дает этот результат.

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


Чтобы было ясно, составление грамматики — это не просто очень приятно иметь, но что-то, что становится все более важным в мире, который становится все более многоязычным. Люди хотят иметь возможность делать такие вещи, как встраивание SQL в код GPL. Что теперь? Если SQL находится в строке, вы подвергаетесь инъекционным атакам. Ларри Уолл решил, что должен быть лучший, принципиальный способ: составные грамматики.

см. мои комментарии в ветке Reddit Эргономичный встроенный SQL как библиотека Python. Два ключевых отрывка:

(Одна ключевая вещь, которую я забыл упомянуть, и которая может быть неочевидной, заключается в том, что сленги Raku полностью интегрируются во время компиляции. Таким образом, могут быть ошибки синтаксиса, типа и т. д. во время компиляции, а также полная защита от атак внедрения, что является намного сложнее, если DSL (например, SQL) находится в строках.)

Вау, я понятия не имел, что существует такая идея языковой «косы». Спасибо, что поделились этой небольшой частью Раку. Строка «sql вставить в ...; с» особенно крута, поскольку вы буквально пишете несколько языков друг в друге с очень небольшим синтаксическим шумом.

Сноски

¹ Декларатор token подразумевает храповик:

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

В документе не упоминается еще один важный аспект: устранение (риска) катастрофического возврата.

(a+) (b+) можно заменить на (a*) (b*) как S ⇒ A ⇒ λ в исходной грамматике, указанной в начале вопроса.
user3134725 13.10.2022 03:23

Другие вопросы по теме