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

Question

Я использую Menhir для создания парсера, и меня всегда смущает такое поведение, и я этого не понимаю. Я создал следующий минимальный пример, чтобы продемонстрировать это; здесь показано объявление аргумента получателя в объявлении метода на языке Go ( http://golang.org/ref/spec):

%{

%}

%token <string> T_identifier
%token T_star

%start <unit> demo


%%


(* This rule has a shift/reduce conflict
demo:
| option(T_identifier) option(T_star) T_identifier { () } 
*)

(* This rule is okay. *)
demo:
| T_identifier T_star T_identifier { () }
| T_identifier T_identifier        { () }
| T_star T_identifier              { () }
| T_identifier                     { () }

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

Я смог прогрессировать в моем парсере, заменив option с несколькими правилами всякий раз, когда это происходит, но меня мучает то, что я не понимаю, почему это происходит.

(Если вы не знаете, менгир, это генератор синтаксического анализатора LR(1), поэтому, вероятно, подойдет знание того, как работают другие подобные инструменты.)

Answer 1

Я полагаю, что Менгир уменьшает EBNF до BNF посредством некоторых стандартных преобразований. Это довольно часто. К сожалению, эти преобразования могут подорвать парситность LR(1).

Рассмотрим ваше правило в другом EBNF-подобном синтаксисе:

demo → IDENTIFIER? STAR? IDENTIFIER

Один из способов перевести это на BNF будет таким же, как вы делаете это во втором наборе правил: определите четыре разных правила, по одному для каждой возможности. Это преобразование никогда не изменит анализируемость LR(1), и это всегда возможно для правил с "необязательным" оператором, но имеет два недостатка:

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

2. Это не работает для операторов повторения.

Другой способ, который кажется более общим, состоит в создании нового нетерминала для каждого расширенного оператора BNF. Таким образом, мы могли бы сделать это:

optional_identifier → IDENTIFIER | ε
optional_star       → STAR | ε
demo                → optional_identifier optional_star IDENTIFIER

Подобное преобразование будет работать для x*:

repeated_x → ε | repeated_x x

Это, конечно, производит эквивалентный язык, но теперь грамматика может не быть LR(1).

Особенно, demo больше не LR(1). Это терпит неудачу прямо в начале. Скажем, первый входной токен IDENTIFIER, Это может быть началом

IDENTIFIER IDENTIFIER

или же

IDENTIFIER

(или некоторые другие возможности, но этого достаточно, чтобы показать проблему.)

Во втором случае (просто тип) нам нужно уменьшить optional_identifier и optional_star прежде чем мы сможем сдвинуть IDENTIFIER, В первом случае (переменная и тип) нам нужно сдвинуть IDENTIFIER немедленно. И единственная информация, которая у нас есть, чтобы понять разницу, это жетон предвкушения, IDENTIFIERчто явно недостаточно.

Если мы используем четырехстороннее расширенное производство, то проблем нет:

demo → IDENTIFIER
     | STAR IDENTIFIER
     | IDENTIFIER IDENTIFIER
     | IDENTIFIER STAR IDENTIFIER

Здесь, когда мы видим IDENTIFIERмы не знаем, является ли это частью первого производства, третьего производства или четвертого производства. Но это не имеет значения, потому что во всех случаях мы просто сдвигаем IDENTIFIER и ждать дополнительной информации.

Подобное явление происходит с yacc/bison и другие генераторы синтаксического анализатора, которые разрешают действия среднего правила (MRA). MRA превращается в новый нетерминал, единственным производством которого является ε производство; Целью нового нетерминала является запуск MRA при его уменьшении. Это действительно круто, за исключением того, что иногда новый нетерминал вводится в момент, когда мы не можем знать, уместно ли его уменьшать или нет. Таким образом, MRA может превратить совершенно хорошую грамматику LR(1) в грамматику без LR(1), даже если язык не изменился.

Хотя это и не относится к Менгиру, возможно, интересно, что приведенная выше трансформация EBNF, если она сделана тщательно, не привносит двусмысленности, которой не было в противном случае. Таким образом, даже если полученная грамматика больше не является LR(1), она все еще однозначна и может быть проанализирована с помощью анализатора GLR. Однако, поскольку Menhir, насколько я знаю, не генерирует парсеры GLR, этот факт может быть не очень полезным.

Answer 2

Во втором правиле вы четко указали, в каком порядке должна быть разрешена неоднозначность. Действительно, вы можете переписать второе правило несколькими различными способами, просто переупорядочив предложения. Вот почему Менгир жалуется, он не знает, какой порядок вы предпочитаете.