В компиляторе функционального языка, написанном с использованием парсера 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 конфликта уменьшения/уменьшения. Удаление любого из правил также приводит к конфликтам. Вот полная грамматика, если вы заинтересованы.
map f - 3 ...
, в которой неясно, является лиf
первым аргументомmap
(в этом случае-3
является отрицательным числом) или частью инфиксного оператора. Я сомневаюсь, что это можно решить с помощью объявлений приоритета, но я могу ошибаться. Его, безусловно, можно решить (в некотором смысле) грамматически, как это делает сам Haskell; в Haskell, если вы хотите написать отрицательное число, вам придется использовать круглые скобки (map f (-3)
), и, возможно, это будет приемлемо и для вашего языка. Чуть позже постараюсь написать ответ. - person rici   schedule 08.10.2016