Предположим, что грамматика G имеет следующие произведения…
Используя грамматику 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.
Естественный идиоматический пример решения проблемы:
grammar S { token TOP { (a*) (b*) <?{ $0.chars <= $1.chars + 3 }> } }
Это напрямую кодирует описание вашего примера в синтаксическом анализаторе - token
¹ выполняет сопоставление/захват нуля или более a
s, затем сопоставление/захват нуля или более b
s и, наконец, проверку предиката, соответствующую формуле вашего примера.
Код теста и результаты:
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 ⇒ λ в исходной грамматике, указанной в начале вопроса.