Как обращаться с x *, x + или x? регулярные выражения в LR-парсере?

Question

я реализовал рекурсивный спуск и PEG-как ​​парсер в прошлом, где вы могли бы сделать что-то вроде этого:

Path -> Segment+ 
Segment -> Slash Name 
Segment ->/
Name -> /\w+/ 
Slash ->/

• где Segment+ означает «матч один или более Segment»
• и есть простой старый регулярное выражение для сопоставления одного или более символов слова с \w+

Как вы обычно выполнить эту же рода вещи с LR грамматик/анализаторами? Все примеры парсеров LR, которые я видел, очень просты, например, разбор 1 + 2 * 3 или (())(), где шаблоны очень просты и, похоже, не связаны с «одной или несколькими» функциональными возможностями (или ноль или более с * или необязательно с ?). Как вы это делаете в парсере LR?

Или же для анализа LR сначала требуется лексическая фаза (т. Е. Парсер LR требует терминальных и нетерминальных «токенов»). Надеясь, что есть способ провести партицию LR без двух этапов. определение из LR парсеры говорят о «входных символах» в книгах/сайтах я читал, но потом вы видите случайно/тонко линию, как:

терминальные символы грамматики являются мульти- символьные символы или «токены», найденные во входном потоке с помощью лексического сканера.

И это как что, откуда появился сканер.

Answer 1

Вы можете написать грамматику сканера без языка, но в большинстве случаев это не будет LR(), потому что 1 токен взгляда не так много, когда токен - это один символ.

Как правило, генераторы парсеров LALR (1) используются вместе с генератором сканера (например, flex).

Answer 2

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

Добавление операторов регулярных выражений в «грамматику» удобно. Но они не распространяют силу контекстных свободных грамматик.

У вас есть 3 варианта использования регулярных выражений в грамматиках.

1) Используйте их на уровне персонажа последовательно по грамматике. Если вы это сделаете, ваш парсер будет работать с токенами, являющимися отдельными символами. Вероятно, это плохо работает с большинством генераторов парсеров, потому что решение для большинства из них основано только на токере следующего входного потока, в данном случае на одном символе. Для выполнения этой работы вам нужен либо синтаксический анализатор обратного отслеживания, либо тот, который будет пытаться использовать несколько путей через пространство альтернативных парсов; Анализаторы LR и LL этого не делают. Существуют сканерные анализаторы GLR, для которых это будет работать, если вы не возражаете против дополнительных накладных расходов GLR на основе каждого символа. (Кроме того, если вы работаете на уровне символов, вы, вероятно, явно укажете синтаксис прокси и комментариев).

2) Используйте их в качестве спецификаций отдельных последовательностей символьных символов (как в OP «Name ->/w + /»). В этой форме то, что вы делаете, это писать лексические спецификации маркера, интегрированные с грамматикой. Затем грамматику можно обработать на две части: лексическую спецификацию и более условный BNF. Эта идея совместима со многими генераторами лексеров и парсеров; он все еще не меняет выразительную силу.

3) Используйте операторы регулярных выражений только для элементов грамматики. Эти легко превращаются в обычные правила грамматики BNF:

Path -> Segment + 

эквивалентно:

Path -> Segment 
    Path -> Path Segment 

После таких преобразований результаты совместимы с большинством генераторов анализаторов. Это оставляет открытым то, как лексический синтаксис грамматических токенов указан.

Вы можете реализовать гибридную схему, объединяющую 1) и 2), которая, по-видимому, является тем, что сделал OP.

Answer 3

Регулярные выражения в грамматике называются «правильными правыми частями».
Они облегчают жизнь парню, пишущему грамматику, но делают жизнь сложнее для генератора синтаксического анализатора.

Умный генератор синтаксического анализатора, такой как LRSTAR 8.0, расширит эти правильные правые части в дополнительные правила автоматически для вас.

Yacc и Bison не позволяют использовать обычные правые части (последний раз, когда я проверил).

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

ПЭГ не заставит вас отделить лексические символы из символов грамматики, создавая тем самым серьезные проблемы, такие, как требующие бесконечного предпросмотр в некоторых случаях (AFAIK).