Каков хороший подход к созданию модульного парсера как для интерпретаторов REPL, так и для компиляторов? - PullRequest
Новая
       38

Каков хороший подход к созданию модульного парсера как для интерпретаторов REPL, так и для компиляторов?

0 голосов
/ 21 мая 2018

Каков хороший подход для создания универсального парсера как для интерпретаторов REPL, так и для компиляторов?Под интерпретаторами я подразумеваю что-то вроде цикла read-eval-print.Для поддержки обоих из них, синтаксический анализатор должен поддерживать синтаксический анализ всей программы и построчный анализ.Алгоритм LALR (1), представленный в книге «Дракон», хорош для анализа всей программы, но его следует немного спроектировать, чтобы использовать для поддержки построчного анализа одновременно.Поскольку два стиля синтаксического анализа используют одну и ту же грамматику для языка программирования, я считаю, что был бы модульный метод для создания одного синтаксического анализатора для двух целей, но я не могу его найти.Можете ли вы помочь мне в этом вопросе?

1 Ответ

0 голосов
/ 21 мая 2018

То, что вам нужно, это GLR парсер (или GLL), и вы должны злоупотреблять им особым образом.

Что делает анализатор GLR полезным здесь, так это его готовность следовать все возможных разборов до тех пор, пока один из них не станет действительным ответом.(Большинство предлагаемых стандартных синтаксических анализаторов (LL, LALR, рекурсивный спуск) преследуют только один возможный синтаксический анализ и часто не могут обрабатывать сложности, возникающие в результате длинных (например, неопределенных) просмотров.

Теперь вы можете настроитьВаша исходная грамматика имеет правило цели G и множество других нетерминалов AZ: 

 G -> A;
 A -> B;
 B -> C;
 ...
 Y -> Z;

: 

 G -> A;
 G -> B;
 G -> C;
 ...
 G -> Z
 A -> B
 B -> C
  ...

, то есть вы добавляете каждый нетерминал какдополнительное правило цели.

Теперь ваш синтаксический анализатор будет использовать любой допустимый нетерминал языка. Вы можете использовать «нетерминальное редуцирование до G» в качестве триггера, чтобы решить, хотите ли вы «скомпилировать» нетерминал, если исходный уровень не является терминальнымВозвращается A или «интерпретирует» этот нетерминал (если он не является исходным нетерминалом верхнего уровня, например, BZ) или просто игнорирует этот ввод и ждет большего, если вы думаете, что интерпретация таких вещей, как then, без части if не интересна.

Вы можете явно изменить грамматику (easist) или вы можете согнуть синтаксический анализатор GLR для запуска всех неопределенныхОн находится в исходном состоянии, что дает тот же эффект.

Моя компания использует GLR для анализа шаблонов исходного кода (как нетерминалов), а не «компилирует» или «интерпретирует», но использует тот же трюк.

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

...