Как убрать запятые и скобки из вызовов функций

В компиляторе функционального языка, написанном с использованием парсера happy, который очень похож на yacc/bison, я реализовал списки и некоторые основные функции map, concat и filter со списками, используя следующие правила:

Exp:
...
| concat '(' Exp ',' Exp ')'         { Concat $3 $5 }
| map '(' Exp ',' Exp ')'            { Map $3 $5 }
| filter '(' Exp ',' Exp ')'         { Filter $3 $5 }

Это прекрасно работает, но в большинстве функциональных языков нет круглых скобок или запятых, поэтому вместо map(myfun, [1,2,3]) я предпочитаю писать map myfun [1,2,3]. Очевидная модификация в грамматике следующая:

Exp:
...
| concat Exp Exp         { Concat $2 $3 }
| map Exp Exp            { Map $2 $3 }
| filter Exp Exp         { Filter $2 $3 }

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

Наименьшая конфликтующая грамматика, которую я смог извлечь, была следующей:

Exp :
    -- Math
     Exp '+' Exp                         { Op $1 Add $3 }
    | Exp '-' Exp                        { Op $1 Sub $3 }

    -- Literals
    | num                                { Num $1 }
    | '-' num %prec NEGATIVE             { Num (-$2) }

    -- Lists
    | map Exp Exp                        { Map $2 $3 }

Он генерирует 4 конфликта уменьшения/уменьшения. Удаление любого из правил также приводит к конфликтам. Вот полная грамматика, если вы заинтересованы.


person fotanus    schedule 06.10.2016    source источник
comment
Я преобразовал грамматику на github в bison, и bison не сообщил о конфликтах.   -  person rici    schedule 07.10.2016
comment
@ric, это потому, что полная ссылка на грамматику имеет правила, которые я указал первым, а не те, которые мне действительно нужны (второй пример в копии моего поста)   -  person fotanus    schedule 07.10.2016
comment
: вот почему мы всегда просим предоставить минимальный воспроизводимый пример.   -  person rici    schedule 07.10.2016
comment
@rici Я обновил свой вопрос, указав минимальную грамматику, которая генерирует конфликты сокращения/уменьшения. Я не уверен, как вам удается преобразовать это в бизона? Если для этого вам нужен полный файл, вот он   -  person fotanus    schedule 07.10.2016
comment
Сокращенный пример связан с неоднозначностью map f - 3 ..., в которой неясно, является ли f первым аргументом map (в этом случае -3 является отрицательным числом) или частью инфиксного оператора. Я сомневаюсь, что это можно решить с помощью объявлений приоритета, но я могу ошибаться. Его, безусловно, можно решить (в некотором смысле) грамматически, как это делает сам Haskell; в Haskell, если вы хотите написать отрицательное число, вам придется использовать круглые скобки ( map f (-3) ), и, возможно, это будет приемлемо и для вашего языка. Чуть позже постараюсь написать ответ.   -  person rici    schedule 08.10.2016
comment
@rici Спасибо! использование круглых скобок для -3 определенно приемлемо. Я не могу сейчас представить, как структурировать грамматику с учетом этого, но я попробую сейчас, когда лучше понимаю проблему.   -  person fotanus    schedule 08.10.2016


Ответы (1)


Проблема в том, что, поскольку в приложении-функции нет токена, разрешение конфликта приоритетов на основе токенов работает не очень хорошо — когда он пытается принять решение о сдвиге, который может быть приложением-функцией и сокращением какого-либо другого выражения, упреждающая лексема — это то, с чего начинается выражение аргумента; нет маркера «пустого места», который можно использовать.

Чтобы обойти эту проблему и заставить ее работать, вам нужно установить приоритет КАЖДОЙ лексемы, которая может быть выражением (каждая лексема в FIRST(Exp)) на приоритет приложения функции. Если какой-либо из этих токенов нужен какой-то другой приоритет (например, любой токен, который может быть либо инфиксным, либо префиксным), это становится намного сложнее и может не работать.

Альтернатива, которая может работать лучше, — вообще не использовать правила приоритета — вместо этого устраняйте неоднозначность грамматики с помощью разных правил для каждого уровня приоритета:

Exp: Term | Exp '+' Term
Term: Factor | Term '*' Factor
Factor: Primary | Factor Primary
Primary: num | id | '(' Exp ')'
person Chris Dodd    schedule 09.10.2016