Недавно я приступил к чтению некоторой литературы по компиляции функциональных языков, и мне хотелось бы получить некоторое представление о том, как на самом деле разрешается синтаксический анализ обычно используемой грамматики EBNF для, скажем, выражений.
Например, в простом лямбда-исчислении с константами:
expr ::=
var
| literal
| 'λ' var '.' expr
| expr expr
| '(' expr ')'
Дело, которое меня интересует, - это приложение; expr expr, который является рекурсивным как слева, так и справа. Как разработчики парсера решают эту проблему? Для целей вопроса мне больше всего интересны генераторы синтаксических анализаторов, такие как bison (я знаю, что ANTLR, кажется, проделывает некоторую хитрость для разрешения этого случая).
Возможно ли выделить это? Существует ли структурированный способ устранения такого рода двусмысленности или это чисто heuristi c? Я понимаю, что OCaml использует генератор синтаксического анализа для своей грамматики, но я не смог разобрать его достаточно, чтобы понять, что происходит.
Любое понимание будет высоко ценится.