Как преобразовать эту грамматику в LR (1)?

Question

У меня есть грамматика с конфликтом LR (1), который я не могу решить; Тем не менее, грамматика должна быть однозначной. Сначала я продемонстрирую проблему на упрощенной грамматике с пятью токенами: (, ), {}, , и id.

EBNF будет выглядеть следующим образом:

 args = (id ',')* 

expression = id 
      | '(' expression ')' 
      | '(' args ')' '{}' 

грамматика однозначна и требует не более двух жетонов опережающего просмотра. Когда ( сдвинут, есть только пять вариантов:

1. ( → повторялись.
2. ) → Уменьшить как '(' args ')'.
3. id) не {} → Уменьшить как '(' expression ')'.
4. id){} → Снижение в '(' args ')' '{}'
5. id, → Снижение в '(' args ')' '{}' (в конце концов).

Наивный перевод дает следующий результат (и conflicts):

formal_arg: Ident 
       {} 

    formal_args: formal_arg Comma formal_args 
      | formal_arg 
      | /* nothing */ 
       {} 

     primary: Ident 
      | LParen formal_args Curly 
      | LParen primary RParen 
       {} 

Таким образом, грамматика требует не более трех жетонов опережающего просмотра, чтобы решить. Я знаю, что грамматика LR (3) can be transformed для грамматики LR (1).

Однако я не совсем понимаю, как сделать преобразование в данном конкретном случае. Обратите внимание, что упрощенная грамматика выше - извлечение из larger body of code; в частности, можно ли преобразовать primary, не касаясь expr и всего выше?

Answer 1

Я нашел решение проблемы, очень похожей на эту: Is C#'s lambda expression grammar LALR(1)?. Основная идея заключалась в том, чтобы отделить корпус (id) от двух других возможностей ((expr_not_id) и (list_at_least_2_ids)). Тогда решение о том, как уменьшить (id), может быть отложено до тех пор, пока не будет доступен токен (в вашем случае {, считая, что этого достаточно).

К сожалению, в то время как трансформация expr в expr_not_id довольно проста и почти механическая, она определенно затрагивает множество производств. Кроме того, это несколько уродливо. Поэтому он не может решить проблему, представленную вами в последнем предложении. На самом деле я не думаю, что можно преобразовать primary, не касаясь expr, но я был удивлен раньше.

(Другое очевидное решение, так как грамматика фактически недвусмысленным, является использование РВО парсер-генератор, но я не считаю, что анализатор-генератор вы используете имеет эту функцию.)