Анализ приложений функций в стиле лямбда-исчисления с помощью синтаксического анализатора LL1

Я использую TinyPG, анализатор LL1. генератор для разбора лямбда-исчисления. Я пытаюсь написать правило, которое будет анализировать приложение функции, такое как (a b) или (a b c) и так далее.

Пока у меня есть это правило (немного упрощенное):

APPLICATION -> LPARENTHESES VARIABLE (SPACE+ VARIABLE)+ RPARENTHESES;

Но это не помогло бы проанализировать термин, в котором есть пробелы после левой и перед правой скобками: ( a b ). Я могу разрешить пробелы после открывающей скобки следующим образом:

APPLICATION -> LPARENTHESES SPACE* VARIABLE (SPACE+ VARIABLE)+ RPARENTHESES;

Но у меня возникли проблемы с настройкой пробелов перед закрывающей скобкой. Я придумал это, которое, кажется, работает:

ARG_LIST        -> (RPARENTHESES | (SPACE+ (RPARENTHESES | (VARIABLE ARG_LIST))));
APPLICATION     -> LPARENTHESES SPACE* VARIABLE ARG_LIST;

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


parsing ll tinypg
person Juan    schedule 13.05.2015    source источник
comment
Вы смотрели на обработку пробелов в учебнике? (Найти [Skip])   -  person rici    schedule 13.05.2015
comment
Да, но при этом будут пропущены все пробелы, включая пробелы между каждым аргументом, которые не следует пропускать.   -  person Juan    schedule 13.05.2015
comment
Почему их нельзя пропускать? Пропущено не значит удалено: это значит распознано, а затем проигнорировано. Маркер VARIABLE по-прежнему будет заканчиваться, когда встретится символ пробела. Попробуйте и посмотрите.   -  person rici    schedule 13.05.2015
comment
Я только что попробовал. Это работает только тогда, когда я определяю пространство для пропуска после определения пространства без пропуска (тот, который я бы использовал между аргументами). Я не могу использовать одно и то же пространство как для пропуска, так и между аргументами. В противном случае он просто не сможет его проанализировать. Я сделаю это так, если нет другого пути, просто это немного хакерски.   -  person Juan    schedule 13.05.2015
comment
Просто оставьте непропускаемое пространство. Вам не нужно сообщать синтаксическому анализатору, что между аргументами должны быть пробелы.   -  person rici    schedule 13.05.2015
comment
Ага, понятно! Не стесняйтесь публиковать это как ответ, и я приму его. Хотя мне все еще интересно, есть ли способ сделать это без функции Skip.   -  person Juan    schedule 13.05.2015
comment
Я полагаю, вы могли бы попробовать сократить свою грамматику с помощью WHITESPACE?, но это будет отвлекать и неэффективно, и это ничего не добавит к удобочитаемости грамматики. Кроме того, это почти наверняка оставит вас с грамматикой, которая больше не будет LL(1). Пропуск пробелов — это не хак. Честный.   -  person rici    schedule 13.05.2015

Ответы (1)


arrow_upward
1
arrow_downward

Нет причин путать синтаксический анализатор с пробелами. Достаточно игнорировать его в сканере с помощью атрибута [Skip], как показано в руководстве:

[Skip] WHITESPACE -> @"\s+";

"Пропустить" не означает "удалить". Это означает, что сканер должен распознать токен, а затем проигнорировать его. Если вы пропустите пробелы, пробелы по-прежнему будут прекрасно разделять буквенно-цифровые токены. Вам просто не нужно включать токен пробела в свою грамматику, оставляя вам:

APPLICATION -> LPARENTHESES VARIABLE VARIABLE+ RPARENTHESES;

(На самом деле пустые списки приложений обычно разрешены, поэтому я бы написал это с помощью * вместо +. Но это ваш язык.)

person rici    schedule 13.05.2015