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

Грамматика регулярна, если она либо праволинейна, либо леволинейна. В этом руководстве утверждается, что из-за этого он обладает особым свойством:

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

Поэтому я решил проверить эту идею и преобразовать обычный грамматику EcmaScript для IdentifierName в регулярные выражения:

IdentifierName ::
    IdentifierStart
    IdentifierName  IdentifierPart

Предположим, что IdentifierStart и IdentifierPart ограничены следующим:

IdentifierStart ::       IdentifierPart ::
    A                        A                 
    B                        C
    C                        &
    $                    
    _

Но я не уверен, как поступить, поскольку грамматика для IdentifierName имеет как рекурсию, так и чередование. Любая помощь?

Меня больше интересует подход, а не поиск результирующего регулярного выражения, которое, как показал @Bergi, равно [ABC$_][AC&]*.


javascript compiler-construction ecmascript-next
person Max Koretskyi    schedule 23.10.2017    source источник
comment
IdentifierName — это либо IdentifierName, за которым следует IdentifierPart, либо IdentifierStart, если IdentifierStart — это S, а IdentifierPart — это P, то некоторые допустимые имена IdentifierName — это S, SP, SPP и т. д.… IE — это S, за которой следует некоторое количество P . можете ли вы придумать регулярное выражение, чтобы соответствовать этому?   -  person Mor A.    schedule 23.10.2017
comment
Только 1_   -  person Bergi    schedule 23.10.2017
comment
@Bergi, спасибо, но меня больше интересует подход к замене, чем само регулярное выражение. Или пример слишком упрощен, чтобы можно было придумать регулярное выражение, не следуя подходу?   -  person Max Koretskyi    schedule 23.10.2017
comment
@M.Aroosi, спасибо, см. мой комментарий выше   -  person Max Koretskyi    schedule 23.10.2017

Ответы (1)


arrow_upward
2
arrow_downward

В этом руководстве используются некоторые нестандартные (и на удивление неявные) определения.

Прежде всего, они используют операторы повторения в своей грамматике, как они могут быть найдены в регулярных выражениях или EBNF. Затем они неявно определяют обычную грамматику как грамматику, которая использует только эти операторы повторения и не использует рекурсию. Учитывая это, тривиально превратить «обычную грамматику» в регулярное выражение, просто встроив все нетерминалы. Но по этому определению грамматика спецификации JS для идентификаторов не является регулярной, поскольку она содержит рекурсию. Поэтому, прежде чем вы сможете встроить все, вам сначала нужно заменить рекурсию операторами повторения.

Однако это не стандартное определение того, что такое обычная грамматика. Стандартное определение таково, как вы сказали: грамматика является регулярной, если она либо леволинейна, либо праволинейна, то есть если только крайний левый элемент продукции является нетерминалом или если только самый правый. Операторы повторения не существуют в обычном определении формальной грамматики.

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

Однако на практике при выполнении преобразования вручную (а не написании программы для этого) самый простой и наиболее распространенный способ выполнить преобразование — подумать о том, какой язык описывает грамматика (в данном случае «язык всех слов, которые начать с символа IdentifierStart, а затем содержать 0 или более символов IdentifierPart"), а затем придумать регулярное выражение, выражающее этот язык (также известный как алгоритм "посмотри очень внимательно на проблему, пока не увидишь решение").

person sepp2k    schedule 23.10.2017
comment
спасибо, так будет ли работать этот алгоритм: 1) заменить рекурсию операторами повторения, а затем 2) заменить каждый нетерминал (кроме корневого) его правой частью? или первая часть действительно нетривиальна с применением механического подхода? - person Max Koretskyi; 23.10.2017
comment
также я писал Грамматика является регулярной, если она либо праволинейна, либо леволинейна. В этом руководстве утверждается, что из-за этого.... Так вроде не из-за этого будет работать алгоритм замены, а из-за оператора повторения? - person Max Koretskyi; 23.10.2017
comment
@ AngularInDepth.com Да, этот алгоритм будет работать, но замена рекурсии операторами повторения в общем случае является явно нетривиальным шагом. И да, к вашему второму комментарию также: алгоритм замены работает, потому что они определили обычные грамматики не как леволинейные или праволинейные грамматики (что было бы обычным определением), а как грамматики, которые используют только операторы повторения вместо рекурсии. - person sepp2k; 23.10.2017